Skip to Main content Skip to Navigation
Conference papers

Synchronous t-Resilient Consensus in Arbitrary Graphs

Abstract : We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.
Complete list of metadatas
Contributor : Pierre Fraigniaud <>
Submitted on : Thursday, January 9, 2020 - 11:04:55 AM
Last modification on : Tuesday, December 8, 2020 - 10:49:51 AM



Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy, et al.. Synchronous t-Resilient Consensus in Arbitrary Graphs. 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2019), Oct 2019, Pisa, Italy. ⟨10.1007/978-3-030-34992-9_5⟩. ⟨hal-02433524⟩



Record views