Computer Science
Document Type
Conference Paper
Abstract
This paper studies the feasibility of reaching consensus in an anonymous dynamic network. In our model, n anonymous nodes proceed in synchronous rounds. We adopt a hybrid fault model in which up to f nodes may suffer crash or Byzantine faults, and the dynamic message adversary chooses a communication graph for each round. We introduce a stability property of the dynamic network - (T, D)-dynaDegree for T ≥ 1 and n - 1 ≥ D ≥1 - which requires that for every T consecutive rounds, any fault-free node must have incoming directed links from at least D distinct neighbors. These links might occur in different rounds during a T- round interval. (1, n-1) -dynaDegree means that the graph is a complete graph in every round. (1, 1) -dynaDegree means that each node has at least one incoming neighbor in every round, but the set of incoming neighbor(s) at each node may change arbitrarily between rounds. We show that exact consensus is impossible even with (1, n - 2) -dynaDegree. For an arbitrary T, we show that for crash-tolerant approximate consensus, (T, ⌊ n/2 ⌋)-dynaDegree and n > 2 f are together necessary and sufficient, whereas for Byzantine approximate consensus, (T, ⌊(n + 3f)/2⌋)-dynaDegree and n > 5f are together necessary and sufficient.
Publication Title
Proceedings - International Conference on Distributed Computing Systems
Publication Date
2024
Volume
44th IEEE International Conference on Distributed Computing Systems
First Page
128
Last Page
138
ISSN
1063-6927
ISBN
9798350386059
DOI
10.1109/ICDCS60910.2024.00021
Keywords
approximate consensus, Byzan-tine, consensus, dynamic network, impossibility, message adversary
Repository Citation
Zhang, Qinzi and Tseng, Lewis, "Fault-tolerant Consensus in Anonymous Dynamic Network" (2024). Computer Science. 236.
https://commons.clarku.edu/faculty_computer_sciences/236
APA Citation
Zhang, Q., & Tseng, L. (2024). Fault-tolerant Consensus in Anonymous Dynamic Network. arXiv preprint arXiv:2405.03017.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
