Semántica segura

Semántica segura es un modelo de coherencia de hardware informático. 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. Se definió formalmente en 'Sobre la comunicación entre procesos' de Lamport. en 1986.

El registro seguro se ha implementado en muchos sistemas distribuidos.

Descripción

La semántica segura se define 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:

Registro seguro sin superposición

1. Una operación de lectura no coincide con cualquier operación de escritura devuelve el valor escrito por la última operación de escritura.
2. Una operación de lectura que coincida con una operación de escritura puede devolver cualquier valor dentro del rango permitido del registro de valores (por ejemplo, 0,1,2,...).
   

   registro seguro superposición

En particular, dada la simultaneidad de una operación de lectura y escritura, la lectura puede devolver un valor que no ha sido escrito por una escritura. El valor de retorno solo necesita pertenecer al dominio de registro.

Un registro binario seguro puede verse como un modelo que parpadea un poco. 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.

Churn se refiere a la entrada y salida de servidores hacia/desde un sistema distribuido. Baldoni et al. mostrar que ningún registro puede tener la propiedad más fuerte de la semántica regular en un sistema síncrono bajo una rotación continua. Sin embargo, se puede implementar un registro seguro bajo una rotación continua en un sistema no síncrono. Modelar e implementar un tipo de memoria de almacenamiento (registro seguro) bajo una rotación no inactiva requiere algunos modelos de sistema, como sistemas de cliente y servidor. Los sistemas cliente contienen un número finito y arbitrario de procesos que son responsables de leer y escribir en el sistema del servidor. Sin embargo, el sistema del 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.

Eventualmente sistema síncrono

Quora (conjunto de servidores o sistemas cliente)

Tamaño de la operación de lectura y escritura ejecutada en quora = n – f – J (n es la cantidad de servidores, J es la cantidad de servidores que entran y salen, y f es la cantidad de fallas bizantinas.

Algoritmos como unir, leer y escribir.

Únete

Un servidor (si) que desea ingresar a un sistema de servidores transmite un mensaje de consulta a otros servidores para informarles de su ingreso, 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 (n-f-j) de otros servidores, luego elige el valor recibido con más frecuencia. Si también:

• Actualiza su copia local del registro
• Se vuelve activo
• Respuestas a los procesos en la respuesta establecida
• Si se vuelve activo envía mensajes de respuesta a los otros servidores. De lo contrario, almacena las preguntas, respondiendo cuando se activa.
• Cuando recibe respuestas de otros servidores añade la nueva respuesta al conjunto de respuestas y descarta el valor antiguo.
• Si el valor del servidor que responde es más grande 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 difusió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 (n-f-j), deja de enviar una consulta.

Escribir

El cliente (cw) envía una consulta al sistema en diferentes rondas y espera hasta que recibe dos reconocimientos. (sn = número de secuencia)

La razón para recibir dos reconocimientos es evitar peligros en un sistema. Cuando un proceso envía un reconocimiento (ack), puede morir después de un milisegundo. Por lo tanto, no se recibe ninguna confirmación por parte del cliente.

La validez del registro seguro (si una lectura no coincide con ninguna escritura, devuelve el último valor escrito) se probó con base en el sistema de quórum. Dados dos sistemas de quórum (Qw, Qr), Qw indica los servidores que conocen el valor más reciente y Qr indica los valores de las respuestas de lectura. El tamaño de cada quórum es igual a n-f-j. Probar la validez del registro seguro requiere probar

(Qrcup B)}" xmlns="http://www.w3.org/1998/Math/MathML">()Qw∪ ∪ Qr)∖ ∖ B■()Qr∪ ∪ B){displaystyle (Qwcup Qr)backslash B confía(Qrcup B)}(Qrcup B)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a83c7e6fb572a06d58af26cb72f90909789a5963" style="vertical-align: -0.838ex; width:25.849ex; height:2.843ex;"/>

were B es el número de fracasos bizantinos.

Prueba: la región roja indica (Qw∩Qr)B y la región azul indica Qr∩B. Partiendo de la suposición, el tamaño de cada quórum es n-f-j, por lo que la región roja tiene n-3f-2j servidores activos. Por lo tanto,

f-->n>4f+2J-->n}" xmlns="http://www.w3.org/1998/Math/MathML">n− − 3f− − 2J■f− − − − ■n■4f+2J− − − − ■n{displaystyle n-3f-2J confíaf...f-->n>4f+2J-->n}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85979257048f7e9697d66e869fcde0b519969eff" style="vertical-align: -0.671ex; width:45.825ex; height:2.509ex;"/>es estrictamente mayor que f.