Synchronous t-resilient consensus in arbitrary graphs

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 ( G, t ), that extends the standard graph theoretical notion of radius, for considering all the ways in which t nodes may crash, and we present an algorithm that solves consensus in radius ( G, t ) rounds. Then we derive a lower bound showing that, among oblivious algorithms, our algorithm is optimal for a large family of graphs including all vertex-transitive graphs.

Authors

• Armando Castañeda
• Pierre Fraigniaud
• Ami Paz
• Sergio Rajsbaum
• Matthieu Roy
• Corentin Travers

Keywords

• Crash failures
• Consensus
• Combinatorial topology
• Distributed graph algorithms