Terminating Reliable Broadcast ( TRB ) es un problema en la computación distribuida que encapsula la tarea de transmitir un mensaje a un conjunto de procesos de recepción en presencia de fallas . [1] En particular, el remitente y cualquier otro proceso pueden fallar ("bloquearse") en cualquier momento.
Descripción del problema
Un protocolo TRB generalmente organiza el sistema en un proceso de envío y un conjunto de procesos de recepción, que pueden incluir al propio remitente. Un proceso se denomina "correcto" si no falla en ningún momento durante su ejecución. El objetivo del protocolo es transferir datos (el "mensaje") del remitente al conjunto de procesos de recepción. Un proceso puede realizar muchas operaciones de E / S durante la ejecución del protocolo, pero finalmente "entrega" un mensaje pasándolo a la aplicación en ese proceso que invocó el protocolo TRB.
El protocolo debe brindar garantías importantes a los procesos de recepción. Todos los procesos de recepción correctos, por ejemplo, deben entregar el mensaje del remitente si el remitente también es correcto. Un proceso de recepción puede entregar un mensaje especial,("remitente defectuoso"), si el remitente falló, pero todos los procesos correctos entregaráno ninguno lo hará. Por lo tanto, se garantiza un proceso correcto que los datos entregados también se entregaron a todos los demás procesos correctos.
Más precisamente, un protocolo TRB debe satisfacer las cuatro propiedades formales siguientes.
- Terminación : todo proceso correcto aporta algún valor.
- Validez : si el remitente es correcto y emite un mensaje, entonces cada proceso correcto entrega .
- Integridad : un proceso entrega un mensaje como máximo una vez, y si entrega algún mensaje, luego fue transmitido por el remitente.
- Acuerdo : si un proceso correcto entrega un mensaje, entonces todos los procesos correctos cumplen .
La presencia de fallas en el sistema hace que estas propiedades sean más difíciles de satisfacer. Un protocolo TRB simple pero no válido puede hacer que el remitente transmita el mensaje a todos los procesos y que los procesos de recepción entreguen el mensaje tan pronto como se reciba. Sin embargo, este protocolo no satisface el acuerdo si pueden ocurrir fallas: si el remitente falla después de enviar el mensaje a algunos procesos, pero antes de enviarlo a otros, entonces el primer conjunto de procesos puede entregar el mensaje mientras que el segundo conjunto lo entrega..
TRB está estrechamente relacionado, pero no es idéntico, al problema fundamental de la computación distribuida del consenso .
Referencias
- ^ Alvisi, Lorenzo (2006). "Consenso y difusión confiable" (PDF) . Consultado el 21 de mayo de 2006 .