Algorithmes de diffusion ordonnée dans les systèmes répartis dynamiques
Wilhelm, Daniel · HAL (Le Centre pour la Communication Scientifique Directe) · 2023
Causal broadcast is a fundamental building block of many distributed and parallel applications, where processes collaborate to perform common tasks, such as high performance computing, distributed databases, conferencing, social networks or other services providing a service to many users. In such systems, processes often require a broadcast primitive to share information that must be ordered to be meaningful, and causal order has been proven to be the strongest order that can be implemented in systems where partitioning can occur. Existing causal broadcast algorithms are either not scalable or they do not tolerate all the dynamics introduced by processes that join and leave the system or fail during execution. Some works append on messages all the information required to causally order them at destination. However, it has been proved that a structure with one entry per process in the system is the minimal structure required to ensure the causal delivery of broadcast messages. Hence, algorithms that append all the causal information on messages do not scale. Some other works make assumptions on the system, such as the network topology or the FIFO property of the communication channels. Such works do not handle well the dynamics caused by processes that join and leave the system or fail. Hence, these works do not handle all the possible dynamics of distributed systems. In this thesis, we provide causal broadcast algorithms that do scale and tolerate the dynamics of distributed systems. We first provide causal broadcast algorithms for Mobile Networks. Such networks have specific features: limited capacities of nodes (computation, storage, energy), unreliable communication channels, and the dynamics of connections due to node mobility, node failure, and join/leave operations of nodes. In the second part, we address causal broadcast provided with constant size clocks. Constant size clocks tolerate process churn and have a size that does not depend on the number of processes. However, they do not characterize causality and algorithms using them only ensure causal order probabilistically. We first propose an error detector, based on hashes, which analyzes the constant size clocks of messages before delivering them in order to detect messages which have causal dependencies that the process did not deliver yet. Second, we propose an algorithm to retrieve the causal dependencies of messages, which we use to ensure the causal delivery of messages tagged by the error detector. Third, we propose a new clock build with constant size clocks and which adapts its size to the number of concurrent messages inside the system. We implemented the contributions on the OMNeT++ simulator. Both causal broadcast algorithms were implemented on the framework INET, which is a realistic network simulator implementing interferences on the wireless network, network layers and node mobility among others. Results confirm that the presented causal broadcast algorithms outperform existing algorithms done for Mobile Networks while making realistic network assumptions. The contributions to constant size clocks were implemented on the OMNeT++ simulator. Results show that the hash-based error detector detected all messages whose causal dependencies have not been delivered yet. Combining the hash-based error detector with the algorithm to retrieve the causal dependencies of messages allowed to deliver all messages in causal order. We analyzed the limits of the hash-based error detector and the retrieval of causal dependencies. Finally, results show that the proposed clock adapts itself well to the number of concurrent messages inside the system.