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

https://hal.inria.fr/hal-02433524
Contributor : Pierre Fraigniaud <>
Submitted on : Thursday, January 9, 2020 - 11:04:55 AM
Last modification on : Friday, April 10, 2020 - 5:28:06 PM

Identifiers

Citation

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

Share

Metrics

Record views

253