Round-Oblivious Stabilizing Consensus in Dynamic Networks
| Autor: | Ulrich Schmid, Manfred Schwarz |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030910808 SSS |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|