Hispanopedia WikiLa semántica segura es un modelo de consistencia del hardware de las computadoras . Describe un tipo de garantía que proporciona un registro de datos cuando es compartido por varios procesadores en una computadora paralela o en una red de computadoras que trabajan juntas.
Historia
La semántica segura fue definida por primera vez por Leslie Lamport en 1985. [1] Fue definida formalmente en "On Interprocess Communication" de Lamport en 1986. [2]
El registro seguro se ha implementado en muchos sistemas distribuidos.
Descripción
Se define una semántica segura para una variable con un solo escritor pero múltiples lectores (SWMR). Un registro SWMR es seguro si cada operación de lectura satisface estas propiedades:
- Una operación de lectura no simultánea con ninguna operación de escritura devuelve el valor escrito por la última operación de escritura.
- Una operación de lectura que sea concurrente con una operación de escritura puede devolver cualquier valor dentro del rango de valores permitido del registro (por ejemplo, 0,1,2,...).
superposición de registros segura
En particular, si se dan simultáneamente operaciones de lectura y escritura, la operación de lectura puede devolver un valor que no haya sido escrito por una operación de escritura. El valor de retorno solo debe pertenecer al dominio de registro.
Un registro binario seguro puede verse como un modelo de parpadeo de bits. Cualquiera que sea el valor anterior del registro, su valor podría parpadear hasta que finalice la escritura. Por lo tanto, la lectura que se superpone con una escritura podría devolver 0 o 1.
El término churn hace referencia a la entrada y salida de servidores a/desde un sistema distribuido. Baldoni et al. muestran que ningún registro puede tener la propiedad más fuerte de la semántica regular en un sistema sincrónico bajo un churn continuo. [3] Sin embargo, se puede implementar un registro seguro bajo un churn continuo en un sistema no sincrónico. [4] Modelar e implementar un tipo de memoria de almacenamiento (registro seguro) bajo un churn no inactivo requiere algunos modelos de sistema, como sistemas cliente y servidor. [4] Los sistemas cliente contienen una cantidad finita y arbitraria de procesos que son responsables de leer y escribir en el sistema servidor. Sin embargo, el sistema servidor debe garantizar que las operaciones de lectura y escritura se realicen correctamente.
Implementación
La implementación de un registro seguro implica:
El registro seguro es mantenido por el conjunto de servidores activos.
Los clientes no mantienen información de registro.
Sistema eventualmente sincrónico
Quora (conjunto de sistemas servidores o clientes)
Tamaño de la operación de lectura y escritura ejecutada en quora = n – f – J (n es el número de servidores, J es el número de servidores que entran y salen, y f es el número de fallas bizantinas ).
Algoritmos como unir, leer y escribir. [4]
Unirse
Un servidor ( si ) que desea ingresar a un sistema de servidores transmite un mensaje de consulta a otros servidores para informarles de su entrada; si solicita un valor actual del registro. Una vez que otro servidor recibe esta consulta, envía mensajes de respuesta a si. Después de que si recibe suficientes respuestas de otros servidores, recopila las respuestas y las guarda en un conjunto de respuestas. Si espera hasta que recibe suficientes respuestas (nfj) de otros servidores y luego elige el valor recibido con mayor frecuencia. Si también:
- Actualiza su copia local del registro
- Se vuelve activo
- Respuestas a los procesos en el conjunto de respuestas
- Si se activa envía mensajes de respuesta a los demás servidores. De lo contrario, almacena las consultas y responde cuando se activa.
- Cuando recibe respuestas de otros servidores, agrega la nueva respuesta al conjunto de respuestas y descarta el valor anterior.
- Si el valor del servidor que responde es mayor que el valor de si, si conserva el nuevo valor.
Leer
El algoritmo de lectura es una versión básica de join. La diferencia es el mecanismo de transmisión utilizado por la operación de lectura. Un cliente ( cw ) transmite un mensaje al sistema y, una vez que un servidor recibe la consulta, envía un mensaje de respuesta al cliente. Una vez que el cliente recibe suficientes respuestas (nfj), deja de enviar una consulta.
Escribir
El cliente ( cw ) envía una consulta al sistema en diferentes rondas y espera hasta recibir dos confirmaciones. ( sn = número de secuencia)
El motivo de recibir dos acuses de recibo es evitar peligros en un sistema. Cuando un proceso envía un acuse de recibo ( ack ), puede morir después de un milisegundo. Por lo tanto, el cliente no recibe ninguna confirmación.
La validez del registro seguro (si una lectura no es concurrente con ninguna escritura, devuelve el último valor escrito) se demostró con base en el sistema de quórum. [4] Dados dos sistemas de quórum (Qw, Qr), Qw indica los servidores que conocen el último valor y Qr indica los valores de las respuestas de lectura. El tamaño de cada quórum es igual a nfj. [4] Para probar la validez del registro seguro es necesario probar
donde B es el número de fracasos bizantinos.
Demostración: La región roja indica (Qw∩Qr)\B y la región azul indica Qr∩B. A partir de la suposición, el tamaño de cada quórum es nfj, por lo que la región roja tiene n-3f-2j servidores activos. Por lo tanto,
es estrictamente mayor que f.
Notas
- ^ Lamport, Leslie (junio de 1986). "Sobre la comunicación entre procesos: Parte I: Formalismo básico" (PDF) . Computación distribuida . 1 (2): 77–85. doi :10.1007/BF01786227. ISSN 0178-2770. S2CID 22834932.
- ^ Lamport, Leslie (junio de 1986). "Sobre la comunicación entre procesos: Parte I: Formalismo básico". Computación distribuida . 1 (2): 77–85. doi :10.1007/BF01786227. ISSN 0178-2770. S2CID 22834932.
- ^ Baldoni, Roberto; Bonomi, Silvia; Raynal, Michel (enero de 2012). "Implementación de un registro regular en un sistema distribuido eventualmente sincrónico propenso a una rotación continua". IEEE Transactions on Parallel and Distributed Systems . 23 (1): 102–109. doi :10.1109/TPDS.2011.97. ISSN 1045-9219. S2CID 12717004.
- ^ abcde Baldoni, Roberto; Bonomi, Silvia; Nezhad, Amir Soltani (noviembre de 2013). "Un protocolo para implementar almacenamiento bizantino en sistemas distribuidos propensos a la rotación". Ciencias de la Computación Teórica . 512 : 28–40. doi : 10.1016/j.tcs.2013.04.005 .