The Analysis of the Probability of Causal Order Violation in a Causal Broadcast Algorithm in Distributed Systems

With the rapid development of distributed systems and the critical importance of interactions among their nodes, selecting message exchange algorithms that align with system characteristics has become a necessity. Causal broadcast algorithms, as one of the key tools in this domain, preserve the causal relationships between messages. In this study, an algorithm named LCUC is introduced, inspired by two concepts: "reducing communication complexity" and "managing unreliable communications." This algorithm addresses two primary challenges in asynchronous distributed systems: minimizing communication complexity and adapting to unreliable communications. The paper reviews existing causal broadcast algorithms, identifies their limitations, and proposes a new algorithm tailored for distributed systems with unreliable communications, which performs optimally under the assumption of fault-free processes. By employing piggybacked messages, the proposed algorithm resolves existing issues and demonstrates that its communication complexity is of order O(n), ensuring correct message delivery even in the presence of communication failures. Another part of this research considers the presence of faulty processes, analyzing the probability of message loss and its impact on causal order violations using the Poisson distribution model. The findings reveal that as the number of faulty processes increases, the probability of causal order violations also rises.