Supervision : Pierre SENS

Co-supervision : ARANTES Luciana

Causal broadcast algorithms for dynamic distributed systems

Causal broadcast is a fundamental building block of many distributed or parallel applications such as distributed databases, pub-sub, or social networks, which all need to share information among all participants (e.g., processes, machines, etc.),
Respecting the causality among exchanged messages. Existing causal broadcast algorithms are either not scalable or they do not always tolerate the dynamics due to processes that join and leave the system, fail during execution, or change their set of communication channels. Some works append to messages all the information required to causally order them at the destination.
However, it has been proved that a structure with one entry per process of the system is the minimal structure required to track causality. Hence, algorithms that use such a structure to track causality do not scale. Some other works scale by making assumptions about the system, such as the network topology or the FIFO property of the communication channels. On the other hand, they do not cover all possible dynamics of distributed systems. In this thesis, we propose causal broadcast algorithms that do scale and tolerate the dynamics of distributed systems.
We first propose a causal broadcast algorithm for Mobile Networks, composed of mobile hosts connected by a wireless network and support stations connected by wired channels. Such networks have specific features: limited capacities of mobile nodes (computation, storage, energy), unreliable communication channels, and the dynamics of connections due to node mobility, failure, and join/leave operations. We implemented the first algorithm on OMNeT++/INET. In the second part, we propose an error detector for causal broadcast algorithms implemented with M-entry clocks, as well as a new logical clock implemented with Probabilistic clocks. We implemented the algorithms on OMNeT++.

2020-2023 Publications