Objetos de instantánea compartida

En computación distribuida , un objeto de instantánea compartida es un tipo de estructura de datos que se comparte entre varios hilos o procesos. Para muchas tareas, es importante tener una estructura de datos que pueda proporcionar una vista consistente del estado de la memoria. En la práctica, resulta que no es posible obtener un estado tan consistente de la memoria simplemente accediendo a un registro compartido tras otro, ya que los valores almacenados en los registros individuales pueden cambiar en cualquier momento durante este proceso. Para resolver este problema, los objetos de instantánea almacenan un vector de n componentes y proporcionan las siguientes dos operaciones atómicas : update(i,v) cambia el valor en el i -ésimo componente a v , y scan() devuelve los valores almacenados en los n componentes. ^{[ 1 ]}^{[ 2 ]} Los objetos de instantánea se pueden construir utilizando registros compartidos atómicos de un solo escritor y múltiples lectores .

En general, se distingue entre objetos de instantánea de escritura única y lectura múltiple (swmr) y objetos de instantánea de escritura múltiple y lectura múltiple (mwmr). En un objeto de instantánea swmr, el número de componentes coincide con el número de procesos, y solo un proceso P _i puede escribir en la posición de memoria i, mientras que todos los demás procesos pueden leerla. Por el contrario, en un objeto de instantánea mwmr, todos los procesos pueden escribir en todas las posiciones de memoria y también pueden leerla.

General

Una memoria compartida se particiona en múltiples partes. Cada una de estas partes contiene un único valor de datos. En el caso de un solo escritor y múltiples lectores, a cada proceso P _i se le asigna una posición de memoria i , y solo este proceso puede escribir en dicha posición. Sin embargo, cualquier proceso puede leer cualquier posición de la memoria. En el caso de múltiples escritores y múltiples lectores, la restricción cambia y cualquier proceso puede modificar cualquier posición de la memoria. Cualquier proceso P _i $\in$ {1,..., n } en un sistema de n procesos puede realizar dos operaciones en el objeto de instantánea: scan() y update(i,v) . La operación scan no tiene argumentos y devuelve una vista consistente de la memoria. La operación update(i,v) actualiza la memoria en la posición i con el valor v .

Se considera que ambos tipos de operaciones ocurren de forma atómica entre la llamada del proceso y el retorno de la memoria. En términos más generales, en el vector de datos ${\overline {d}}$ Cada entrada d _k corresponde al argumento de la última operación de actualización linealizada , que actualiza la parte k de la memoria. ^[¹^]

Para obtener el máximo beneficio de los objetos de instantánea compartidos, en términos de simplificaciones para validaciones y construcciones, se agregan dos restricciones adicionales a la construcción de objetos de instantánea. ^{[ 1 ]} La primera restricción es de carácter arquitectónico, lo que significa que cualquier objeto de instantánea se construye únicamente con registros de un solo escritor y múltiples lectores como elemento básico. Esto es posible para instantáneas de un solo escritor y múltiples lectores. Para objetos de instantánea de múltiples escritores y múltiples lectores, es posible utilizar registros de múltiples lectores y múltiples escritores , que a su vez pueden construirse a partir de registros de un solo escritor y múltiples lectores. ^{[ 1 ]}^{[ 3 ]}^{[ 4 ]}

En la computación distribuida, la construcción de un sistema se rige por el objetivo de que todo el sistema progrese durante su ejecución. Por lo tanto, el comportamiento de un proceso no debe detener todo el sistema ( ausencia de bloqueos ). Una versión más estricta de esto es la propiedad de ausencia de esperas , lo que significa que ningún proceso puede impedir que otro proceso finalice su operación. En términos más generales, esto significa que cada operación debe finalizar después de un número finito de pasos, independientemente del comportamiento de otros procesos. Un algoritmo de instantánea muy básico garantiza el progreso de todo el sistema, pero solo es libre de bloqueos. Es fácil extender este algoritmo para que sea libre de esperas. El algoritmo de Afek et al., ^{[ 1 ]} que se presenta en la sección Implementación posee esta propiedad.

Implementación

Existen varios métodos para implementar objetos de instantánea compartida. El primer algoritmo presentado proporciona una implementación principal de objetos de instantánea. Sin embargo, esta implementación solo ofrece la propiedad de ausencia de bloqueo . La segunda implementación presentada, propuesta por Afek et al. ^{[ 1 ]} , posee una propiedad más robusta denominada ausencia de espera . Fich ^[²^] ofrece una visión general de otras implementaciones.

Algoritmo básico de instantáneas SWMR

La idea básica de este algoritmo es que cada proceso que ejecuta las scan()operaciones lee todos los valores de la memoria dos veces. Si el algoritmo lee exactamente el mismo contenido de la memoria dos veces, ningún otro proceso modificó un valor entre lecturas y lecturas, y puede devolver el resultado. Un proceso que ejecuta una update(i,v)operación simplemente actualiza su valor en la memoria.

función scan() mientras sea verdadero a[1..n] := recolectar; b[1..n] := recolectar; si (∀i∈{1, .., n} la ubicación i no cambió entre las lecturas de la misma durante las dos recopilaciones)) entonces return b; // doble recolección exitosa fin del bucle

función actualizar(i, v) M[i] := v; fin

Este algoritmo proporciona una implementación muy básica de objetos de instantánea. Garantiza que el sistema continúe, aunque los hilos individuales pueden sufrir inanición debido al comportamiento de los procesos individuales. Un proceso P _i puede impedir que otro proceso P _j finalice una scan()operación cambiando siempre su valor entre las dos recolecciones de memoria. Por lo tanto, el algoritmo no requiere bloqueo , pero sí espera . Para reforzar esta propiedad, ningún proceso puede sufrir inanición debido al comportamiento de otros procesos. La Figura 1 ilustra el problema. Mientras P ₁ intenta ejecutar la scan()operación, un segundo proceso P ₂ interrumpe constantemente la "doble recolección". Por lo tanto, el proceso de escaneo siempre tiene que reiniciar la operación y nunca puede finalizar ni sufrir inanición.

Implementación de lector múltiple con un solo escritor por Afek et al.

La idea básica del algoritmo de instantáneas SWMR de Afek et al. es que un proceso puede detectar si otro proceso modificó su ubicación de memoria y que los procesos se ayudan mutuamente. Para detectar si otro proceso modificó su valor, se adjunta un contador a cada registro, y un proceso incrementa dicho contador con cada actualización. La segunda idea es que cada proceso que actualiza su posición de memoria también realiza una scan()operación y proporciona su "vista de la memoria" en su registro a otros procesos. Un proceso de escaneo puede tomar prestado este scanresultado y devolverlo.

Basado en memoria ilimitada

Utilizando esta idea, se puede construir un algoritmo sin esperas que utilice registros de tamaño ilimitado. Un proceso que realiza una operación de actualización puede ayudar a otro proceso a completar el escaneo. La idea básica es que si un proceso ve que otro proceso actualiza una ubicación de memoria dos veces, ese proceso debe haber ejecutado una operación de actualización completa y linealizada entretanto. Para implementar esto, cada operación de actualización primero realiza un escaneo de la memoria y luego escribe el valor de la instantánea de forma atómica junto con el nuevo valor v y un número de secuencia. Si un proceso está realizando un escaneo de la memoria y detecta que otro proceso actualizó la parte de la memoria dos veces, puede "tomar prestado" el escaneo "incrustado" de la actualización para completar la operación de escaneo . ^{[ 1 ]}

función scan() // devuelve una vista consistente de la memoria para j = 1 a n hacer moved[j] := 0 fin mientras sea verdadero hacer a[1..n] := collect; // recopila tripletas (datos, secuencia, vista) b[1..n] := collect; // recopila tripletas (datos, secuencia, vista) if (∀j∈{1, ..., n}) (a[j].seq = b[j].seq) then return (b[1].data, ..., b[n].data) // ningún proceso cambió la memoria else for j = 1 to n do if a[j].seq ≠ b[j].seq then // el proceso se movió if moved[j] = 1 then // el proceso ya se movió antes return b[j].view; else moved[j] := moved[j] + 1; end end end function

procedimiento update( i , v ) // actualiza los registros con los valores de datos, actualiza el número de secuencia, escaneo integrado s[1..n] := escaneo; // escaneo incrustado r _i := (v, r _i .seq = r _i .seq + 1, s[1..n]); fin del procedimiento

Cada registro consta de un campo para el valor de los datos, el número de secuencia y un campo para el resultado del último escaneo incrustado, recopilado antes de la última actualización. En cada operación de escaneo, el proceso P _i puede determinar si un proceso modificó su memoria utilizando el número de secuencia. Si no hay cambios en la memoria durante la doble recopilación, P _i puede devolver el resultado del segundo escaneo. Una vez que el proceso observa que otro proceso actualizó la memoria entretanto, guarda esta información en el campo movido. Si un proceso P _j modificó su memoria dos veces durante la ejecución de scan(), el proceso de escaneo P _i puede devolver el escaneo incrustado del proceso que actualizó, el cual guardó en su propio registro durante su operación de actualización.

Estas operaciones se pueden linealizar linealizando cada operación update() en el momento de escribir en el registro. La operación scan es más compleja de linealizar. Si la doble recolección de la operación scan es exitosa, la operación scan se puede linealizar al final del segundo escaneo. En el otro caso, cuando un proceso actualiza su registro dos veces, la operación se puede linealizar en el momento en que el proceso de actualización recolecta su escaneo incrustado antes de escribir su valor en el registro. ^{[ 1 ]}

Basado en memoria limitada

Una de las limitaciones del algoritmo presentado es que se basa en una memoria ilimitada, ya que el número de secuencia aumentará constantemente. Para superar esta limitación, es necesario introducir una forma diferente de detectar si un proceso ha cambiado su posición de memoria dos veces entretanto. Cada par de procesos $\langle P_{i},P_{j}\rangle$ Se comunica mediante dos registros de escritura única y lectura única (swsr), que contienen dos bits atómicos. Antes de que un proceso comience a realizar una "doble recolección", copia el valor de su proceso asociado a su propio registro. Si el proceso escáner P _i observa, después de ejecutar la "doble recolección", que el valor del proceso asociado P _j ha cambiado, esto indica que el proceso ha realizado una operación de actualización en la memoria. ^{[ 1 ]}

función scan() // devuelve una vista consistente de la memoria para j=1 a n hacer moved[j] := 0 fin mientras verdadero hacer para j=1 a n hacer q _i,j := r _j .p _j,ifin a[1..n] := collect; // recopila triples (datos, vector de bits, alternancia, vista) b[1..n] := collect; // recopila tripletas (datos, vector de bits, alternancia, vista) si (∀j∈{1, ...,n}) (a[j].p _j,i = b[j].p _j,i = q _i,j ) y a[j].toggle = b[j].toggle entonces devuelve (b[1].data, ..., b[n].data) // ningún proceso cambió la memoria sino para j=1 a n hacer si (a[j].p _j,i ≠ q _i,j ) o (b[j].p _j,i ≠ q _i,j ) o (a[j].toggle ≠ b[j].toggle) entonces // el proceso j realizó una actualización si moved[j] = 2 entonces // el proceso ya se movió antes devolver b[j].view; sino moved[j] := moved[j] + 1; fin fin fin función

procedimiento update( i , v ) // actualiza los registros con el valor de datos, el "estado de escritura" de todos los registros, invierte el bit de conmutación y el escaneo incrustado para j = 1 a n hacer f[j] := ¬q _j,ifin s[1..n] := escaneo; // escaneo incrustado r _i := (v, f[1..n], ¬r _i .toggle, s[1..n]); fin procedimiento

El número de secuencia ilimitado se reemplaza por dos bits de protocolo de enlace para cada par de procesos. Estos bits de protocolo de enlace se basan en registros SWSR y se pueden expresar mediante una matriz M , donde el proceso P _i puede escribir en la fila i y leer los bits de protocolo de enlace en la columna i . Antes de que el proceso de escaneo realice la doble recopilación, recopila todos los bits de protocolo de enlace de todos los registros, leyendo su columna. Posteriormente, puede determinar si un proceso cambió su valor durante la doble lectura o no. Por lo tanto, el proceso solo tiene que comparar la columna nuevamente con los bits de protocolo de enlace leídos inicialmente. Si solo un proceso P _j ha escrito dos veces, durante la recopilación de P _i es posible que los bits de protocolo de enlace no cambien durante el escaneo. Por lo tanto, es necesario introducir otro bit llamado "bit de conmutación", que cambia en cada escritura. Esto permite distinguir dos escrituras consecutivas, incluso si ningún otro proceso actualizó su registro. Este enfoque permite sustituir los números de secuencia ilimitados por los bits de protocolo de enlace, sin cambiar nada más en el procedimiento de escaneo.

Mientras que el proceso de escaneo P _i utiliza un bit de protocolo de enlace para detectar si puede usar su doble recolección o no, otros procesos también pueden realizar operaciones de actualización. Como primer paso, leen nuevamente los bits de protocolo de enlace proporcionados por los otros procesos y generan su complemento. Posteriormente, estos procesos generan nuevamente el escaneo incrustado y guardan el valor de datos actualizado, los bits de protocolo de enlace recolectados y complementados, el bit de conmutación complementado y el escaneo incrustado en el registro.

Dado que los bits de protocolo de enlace reemplazan de forma equivalente a los números de secuencia, la linealización es la misma que en el caso de memoria ilimitada.

Implementación de lector-escritor múltiple por Afek et al.

La construcción de un objeto de instantánea multi-escritor-multi-lector presupone que n procesos pueden escribir en cualquier ubicación de la memoria, la cual consta de m registros. Por lo tanto, ya no existe correlación entre el identificador del proceso y la ubicación de memoria. En consecuencia, ya no es posible vincular los bits de protocolo de enlace ni el escaneo integrado con los campos de datos. Por lo tanto, los bits de protocolo de enlace, la memoria de datos y el escaneo integrado no pueden almacenarse en el mismo registro, y la escritura en la memoria ya no es una operación atómica.

Por lo tanto, el update()proceso debe actualizar tres registros diferentes de forma independiente. Primero, guarda los bits de protocolo de enlace que lee, luego realiza el escaneo integrado y, finalmente, guarda su valor en la posición de memoria designada. Cada escritura, por sí sola, parece realizarse de forma atómica, pero en conjunto no lo son. El nuevo update()procedimiento conlleva algunos cambios en la scan()función. Ya no basta con leer los bits de protocolo de enlace y recopilar el contenido de la memoria dos veces. Para detectar un updateproceso en ejecución, este debe recopilar los bits de protocolo de enlace por segunda vez, después de recopilar el contenido de la memoria.

Si falla una doble recolección, es necesario que un proceso vea a otro proceso moverse tres veces antes de tomar prestado el escaneo incrustado. La Figura 3 ilustra el problema. La primera doble recolección falla porque un updateproceso iniciado antes de la operación de escaneo finaliza su escritura en memoria durante la primera doble recolección. Sin embargo, el escaneo incrustado de esta escritura se realiza y guarda antes de que _P1 comience a escanear la memoria y, por lo tanto _, no hay un punto de linealización válido. La segunda doble recolección falla porque el proceso P2 inicia una segunda escritura y actualiza sus bits de protocolo de enlace. En el escenario swmr, tomaríamos prestado el escaneo incrustado y lo devolveríamos. En el escenario mwmr, esto no es posible porque el escaneo incrustado del segundo writeaún no se ha linealizado dentro del intervalo de escaneo (inicio y fin de la operación). Por lo tanto, el proceso debe ver un tercer cambio del otro proceso para estar completamente seguro de que al menos un escaneo incrustado se ha linealizado durante el intervalo de escaneo. Después del tercer cambio de un proceso, el proceso de escaneo puede tomar prestado el valor de memoria antiguo sin violar el criterio de linealización.

Complejidad

La implementación básica presentada de objetos de instantánea compartida por Afek et al. necesita $O(n^{2})$ operaciones de memoria. ^{[ 1 ]} Otra implementación de Anderson , que se desarrolló de forma independiente, necesita un número exponencial de operaciones. $O(2^{n})$ . ^{[ 5 ]} También existen implementaciones aleatorias de objetos de instantánea basados en registros swmr que utilizan $O(n\log ^{2}n)$ operaciones. ^{[ 6 ]} Otra implementación de Israeli y Shirazi, que utiliza memoria ilimitada, requiere $O(n^{3/2}\log ^{2}n)$ operaciones en la memoria. ^{[ 7 ]}^{[ 8 ]} Israeli et al. muestran en un trabajo diferente el límite inferior de las operaciones de bajo nivel para cualquier operación de actualización. El límite inferior es $\Omega (\min\{w,r\})$ donde w es el número de actualizadores y r es el número de escáneres. Attiya y Rachman presentan un algoritmo de instantánea determinista basado en registros swmr, que utiliza $O(n\log n)$ operaciones por actualización y escaneo. ^{[ 8 ]} Aplicando un método general de Israeli, Shaham y Shirazi ^{[ 9 ]} esto se puede mejorar a un algoritmo de instantáneas ilimitadas, que solo necesita $O(n\log n)$ operaciones por escaneo y $O(n)$ ^{operaciones por actualización. Inoue et al. [ 10 ]} introdujeron mejoras adicionales utilizando solo un número lineal de operaciones de lectura y escritura. A diferencia de los otros métodos presentados, este enfoque utiliza registros mwmr y no registros swmr.

Aplicaciones

Hay varios algoritmos en computación distribuida que pueden simplificarse en diseño y/o verificación usando objetos de instantánea compartidos. ^{[ 1 ]} Ejemplos de esto son problemas de exclusión, ^{[ 11 ]}^{[ 12 ]}^{[ 13 ]} sistemas de marcas de tiempo concurrentes, ^{[ 14 ]} acuerdo aproximado, ^{[ 15 ]} consenso aleatorio ^{[ 16 ]}^{[ 17 ]} e implementaciones sin espera de otras estructuras de datos. ^{[ 18 ]} Con objetos de instantánea mwmr también es posible crear registros atómicos de múltiples escritores y múltiples lectores .

Véase también

Referencias

1 2 3 4 5 6 7 8 9 10 11 Afek, Yehuda ; Attiya, Hagit ; Dolev, Danny ; Gafni, Eli; Merritt, Michael; Shavit, Nir (septiembre de 1993). "Instantáneas atómicas de la memoria compartida" . Journal of the ACM . 40 (4): 873–890 . doi : 10.1145/153724.153741 . hdl : 1721.1/149162 . S2CID 52150066 .
1 2 Fich, Faith Ellen (2005). "¿Qué tan difícil es tomar una instantánea?". SOFSEM 2005: Teoría y práctica de la informática . Notas de clase en informática. Vol. 3381. Springer Berlin Heidelberg. pp. 28–37 . doi : 10.1007/978-3-540-30577-4_3 . ISBN 978-3-540-24302-1.
↑ Li, Ming; Tromp, John; Vitanyi, Paul MB (julio de 1996). "Cómo compartir variables concurrentes sin espera". Journal of the ACM . 43 (4): 723– 746. CiteSeerX 10.1.1.56.3236 . doi : 10.1145/234533.234556 . S2CID 15035117 .
↑ Peterson, Gary L.; Burns, James E. (1987). «Lectura simultánea durante la escritura II: El caso de múltiples escritores». 28.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1987) . págs. 383–392 . doi : 10.1109/SFCS.1987.15 . ISBN 0-8186-0807-2.
↑ Anderson, James H (1993). "Registros compuestos". Computación distribuida . 6 (3): 141– 154. doi : 10.1007/BF02242703 . S2CID 1688458 .
^ Attiya, Hagit; Helihy, Mauricio; Rachman, Ofir (1995). "Instantáneas atómicas mediante acuerdo de celosía". Computación distribuida . 8 (3): 121– 132. doi : 10.1007/BF02242714 . S2CID 26538026 .
↑ Israeli, Amos; Shirazi, Asaf (1992). "Protocolo de instantánea eficiente mediante acuerdo de 2 retículos". Manuscrito .
1 2 Attiya, Hagit; Rachman, Ophir (abril de 1998). "Instantáneas atómicas en operaciones O(n log n) ". Actas del duodécimo simposio anual de la ACM sobre Principios de computación distribuida - PODC '93 . págs. 29–40 . doi : 10.1145/164051.164055 . ISBN 0-89791-613-1. S2CID 15199715 .
↑ Israeli, Amos; Shaham, Amnon; Shirazi, Asaf (1993). "Protocolos de instantáneas en tiempo lineal para sistemas desequilibrados" . Algoritmos distribuidos . Springer. págs. 26–38 . doi : 10.1007/3-540-57271-6_25 . ISBN 978-3-540-57271-8.
↑ Inoue, Michiko; Masuzawa, Toshimitsu; Chen, Wei; Tokura, Nobuki (1994). "Instantánea en tiempo lineal mediante registros de múltiples escritores y múltiples lectores". Algoritmos distribuidos . Notas de clase en ciencias de la computación. Vol. 857. Springer. págs. 130–140 . doi : 10.1007/BFb0020429 . ISBN 978-3-540-58449-0.
↑ Dolev, Danny; Gafni, Eli; Shavit, Nir (1988). «Hacia una era no atómica: la l-exclusión como caso de prueba». Actas del vigésimo simposio anual de la ACM sobre Teoría de la Computación - STOC '88 . págs. 78–92 . doi : 10.1145/62212.62220 . ISBN 0-89791-264-0.
↑ Katseff, Howard P. (1978). "Una nueva solución al problema de la sección crítica". Actas del décimo simposio anual de la ACM sobre Teoría de la Computación - STOC '78 . págs. 86–88 . doi : 10.1145/800133.804335 .
↑ Lamport, Leslie (1988). "El problema de la exclusión mutua: parte II: planteamiento y soluciones". Journal of the ACM . 33 (2): 327– 348. CiteSeerX 10.1.1.32.9808 . doi : 10.1145/5383.5385 . S2CID 7387839 .
↑ Dolev, D.; Shavit, N. (1989). "Los sistemas de marcas de tiempo concurrentes acotados son construibles". Actas del vigésimo primer simposio anual de la ACM sobre Teoría de la Computación - STOC '89 . págs. 454–466 . doi : 10.1145/73007.73051 . ISBN 0-89791-307-8.
↑ Attiya, H.; Lynch, N.; Shavit, N. (1990). "¿Son rápidos los algoritmos sin espera?". Actas [ 1990 ] 31.er Simposio Anual sobre Fundamentos de la Informática . págs. 55–64 . doi : 10.1109/FSCS.1990.89524 . ISBN 0-8186-2082-X.
↑ Abrahamson, Karl (1988). «Sobre cómo lograr consenso utilizando una memoria compartida». Actas del séptimo simposio anual de la ACM sobre principios de computación distribuida - PODC '88 . págs. 291–302 . doi : 10.1145/62546.62594 . ISBN 0-89791-277-2.
↑ Attiya, Hagit; Dolev, Danny; Shavit, Nir (1989). «Consenso aleatorio polinomial acotado». Actas del octavo simposio anual de la ACM sobre principios de computación distribuida - PODC '89 . págs. 281–293 . doi : 10.1145/72981.73001 . ISBN 0-89791-326-4.
↑ Aspnes, J.; Herlihy, M. (1990). «Estructuras de datos sin espera en el modelo PRAM asíncrono». Actas del segundo simposio anual de la ACM sobre algoritmos y arquitecturas paralelas - SPAA '90 . págs. 340–349 . doi : 10.1145/97444.97701 . ISBN 0-89791-370-1.

[afek-1] 1 2 3 4 5 6 7 8 9 10 11 Afek, Yehuda ; Attiya, Hagit ; Dolev, Danny ; Gafni, Eli; Merritt, Michael; Shavit, Nir (septiembre de 1993). "Instantáneas atómicas de la memoria compartida" . Journal of the ACM . 40 (4): 873–890 . doi : 10.1145/153724.153741 . hdl : 1721.1/149162 . S2CID 52150066 .

[fich-hard-2] 1 2 Fich, Faith Ellen (2005). "¿Qué tan difícil es tomar una instantánea?". SOFSEM 2005: Teoría y práctica de la informática . Notas de clase en informática. Vol. 3381. Springer Berlin Heidelberg. pp. 28–37 . doi : 10.1007/978-3-540-30577-4_3 . ISBN 978-3-540-24302-1.

[3] Li, Ming; Tromp, John; Vitanyi, Paul MB (julio de 1996). "Cómo compartir variables concurrentes sin espera". Journal of the ACM . 43 (4): 723– 746. CiteSeerX 10.1.1.56.3236 . doi : 10.1145/234533.234556 . S2CID 15035117 .

[4] Peterson, Gary L.; Burns, James E. (1987). «Lectura simultánea durante la escritura II: El caso de múltiples escritores». 28.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1987) . págs. 383–392 . doi : 10.1109/SFCS.1987.15 . ISBN 0-8186-0807-2.

[anderson-5] Anderson, James H (1993). "Registros compuestos". Computación distribuida . 6 (3): 141– 154. doi : 10.1007/BF02242703 . S2CID 1688458 .

[6] Attiya, Hagit; Helihy, Mauricio; Rachman, Ofir (1995). "Instantáneas atómicas mediante acuerdo de celosía". Computación distribuida . 8 (3): 121– 132. doi : 10.1007/BF02242714 . S2CID 26538026 .

[7] Israeli, Amos; Shirazi, Asaf (1992). "Protocolo de instantánea eficiente mediante acuerdo de 2 retículos". Manuscrito .

[attiya-nlogn-8] 1 2 Attiya, Hagit; Rachman, Ophir (abril de 1998). "Instantáneas atómicas en operaciones O(n log n) ". Actas del duodécimo simposio anual de la ACM sobre Principios de computación distribuida - PODC '93 . págs. 29–40 . doi : 10.1145/164051.164055 . ISBN 0-89791-613-1. S2CID 15199715 .

[9] Israeli, Amos; Shaham, Amnon; Shirazi, Asaf (1993). "Protocolos de instantáneas en tiempo lineal para sistemas desequilibrados" . Algoritmos distribuidos . Springer. págs. 26–38 . doi : 10.1007/3-540-57271-6_25 . ISBN 978-3-540-57271-8.

[inoue-10] Inoue, Michiko; Masuzawa, Toshimitsu; Chen, Wei; Tokura, Nobuki (1994). "Instantánea en tiempo lineal mediante registros de múltiples escritores y múltiples lectores". Algoritmos distribuidos . Notas de clase en ciencias de la computación. Vol. 857. Springer. págs. 130–140 . doi : 10.1007/BFb0020429 . ISBN 978-3-540-58449-0.

[11] Dolev, Danny; Gafni, Eli; Shavit, Nir (1988). «Hacia una era no atómica: la l-exclusión como caso de prueba». Actas del vigésimo simposio anual de la ACM sobre Teoría de la Computación - STOC '88 . págs. 78–92 . doi : 10.1145/62212.62220 . ISBN 0-89791-264-0.

[12] Katseff, Howard P. (1978). "Una nueva solución al problema de la sección crítica". Actas del décimo simposio anual de la ACM sobre Teoría de la Computación - STOC '78 . págs. 86–88 . doi : 10.1145/800133.804335 .

[13] Lamport, Leslie (1988). "El problema de la exclusión mutua: parte II: planteamiento y soluciones". Journal of the ACM . 33 (2): 327– 348. CiteSeerX 10.1.1.32.9808 . doi : 10.1145/5383.5385 . S2CID 7387839 .

[14] Dolev, D.; Shavit, N. (1989). "Los sistemas de marcas de tiempo concurrentes acotados son construibles". Actas del vigésimo primer simposio anual de la ACM sobre Teoría de la Computación - STOC '89 . págs. 454–466 . doi : 10.1145/73007.73051 . ISBN 0-89791-307-8.

[15] Attiya, H.; Lynch, N.; Shavit, N. (1990). "¿Son rápidos los algoritmos sin espera?". Actas [ 1990 ] 31.er Simposio Anual sobre Fundamentos de la Informática . págs. 55–64 . doi : 10.1109/FSCS.1990.89524 . ISBN 0-8186-2082-X.

[16] Abrahamson, Karl (1988). «Sobre cómo lograr consenso utilizando una memoria compartida». Actas del séptimo simposio anual de la ACM sobre principios de computación distribuida - PODC '88 . págs. 291–302 . doi : 10.1145/62546.62594 . ISBN 0-89791-277-2.

[17] Attiya, Hagit; Dolev, Danny; Shavit, Nir (1989). «Consenso aleatorio polinomial acotado». Actas del octavo simposio anual de la ACM sobre principios de computación distribuida - PODC '89 . págs. 281–293 . doi : 10.1145/72981.73001 . ISBN 0-89791-326-4.

[18] Aspnes, J.; Herlihy, M. (1990). «Estructuras de datos sin espera en el modelo PRAM asíncrono». Actas del segundo simposio anual de la ACM sobre algoritmos y arquitecturas paralelas - SPAA '90 . págs. 340–349 . doi : 10.1145/97444.97701 . ISBN 0-89791-370-1.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

operaciones por actualización. Inoue et al. [ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]