Synchronous t-Resilient Consensus in Arbitrary Graphs - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

Synchronous t-Resilient Consensus in Arbitrary Graphs

(1) , (2, 3) , (3) , (4) , (5) , (6)
1
2
3
4
5
6

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.
Not file

Dates and versions

hal-02433524 , version 1 (09-01-2020)

Identifiers

Cite

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⟩
52 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More