Publication:

Protocolo de difusión de mensajes fiable y uniforme con garantía parcial de Orden Total

En este trabajo presentamos el diseño y la implementación de un algoritmo de difusión de mensajes tolerante a fallos con las propiedades de fiabilidad, uniformidad, acuerdo de terminación y orden total (débil). El sistema distribuido considerado para la corrección del algoritmo es un sistema asíncrono con canales fiables en los que se fija el número mínimo de procesos correctos. Al ser un sistema asíncrono no se garantiza la propiedad fuerte de orden total, que por el resultado de imposibilidad FLP no es posible obtener en este tipo de sistemas. El algoritmo, por tanto, realiza el mayor esfuerzo para obtener una garantía parcial del orden total en la entrega de los mensajes. No obstante, la implementación realizada en NodeJS sobre un grupo de contenedores Docker en un sistema tipo ‘cluster’ de máquinas asegura que un gran porcentaje de mensajes son entregados en orden total por todos los procesos, lo que hace que sea un algoritmo de utilidad en estos entornos. Además, por la uniformidad y fiabilidad, todos los mensajes enviados por procesos correctos son entregados a la capa de la aplicación. Como desventaja, el precio a pagar por obtener orden total en la mayoría de los procesos es una mayor latencia en la entrega de los mensajes.

In this project, we present the design and implementation of a fault tolerant broadcast algorithm that guarantees reliability, uniformity, termination agreement and (weak) total order. Algorithm correctness is provided for an asynchronous system based on reliable channels in where the minimum of correct processes is fixed a priori. As the system is asynchronous it does not guarantee the strong total order property, as it is shown by the FLP impossibility result. Strong total order property cannot be obtained in this kind of systems. Therefore, the proposed algorithm does a best effort to obtain a partial guarantee of the total order property. The algorithm is implemented using NodeJS and it is deployed on a cluster using a group of Docker containers. In this environment, the algorithm delivers an high percentage of messages in total order by all the correct processes. This makes the algorithm very useful in these types of environments. By the uniformity and reliability properties, it also guarantees that every message sent by any correct process is delivered to the application layer. As a disadvantage, total order in the majority of processes has a price to pay: an higher latency on delivering messages.