[Zurück]

M. Schwarz, U. Schmid:
"Round-Oblivious Stabilizing Consensus in Dynamic Networks";
Vortrag: 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021), virtuell (eingeladen); 17.11.2021 - 20.11.2021; in: "Proceedings 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2023)", Springer, LNCS 13046 (2021), ISBN: 978-3-030-91080-8; S. 154 - 172.

In this paper, we study deterministic consensus in practical directed dynamic networks. We show that it is straightforward to remove the dependence on round numbers even for quite complex algorithms like the optimal terminating consensus algorithm for the short-lived vertex-stable root components message adversary (Winkler et al., Distributed Computing, 2019). The resulting algorithm is inherently resilient against synchronization-related errors, and can be proved correct by a simple simulation equivalence. Moreover, our approach naturally leads to a novel optimal solution for stabilizing consensus for this message adversary. Finally, we negatively answer the question of whether such algorithms could benefit from a stronger communication model, where senders get immediate notification of successful transmission. The typical strive for implementing low-level bidirectional connectivity, or implicit acknowledgments as in the JAG protocol (Boano et al., RTSS´12), in practical implementations hence appears to be an overkill for solving consensus.

Directed dynamic networks, message adversaries, stabilizing consensus , synchronization errors, immediate acknowledgments

http://dx.doi.org/10.1007/978-3-030-91081-5_11