Back to Search
Start Over
Synchronous t-Resilient Consensus in Arbitrary Graphs
- Source :
- 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2019), 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⟩, SSS 2019-21st International Symposium on Stabilization, Safety, and Security of Distributed Systems, 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⟩, Lecture Notes in Computer Science ISBN: 9783030349912, SSS
- Publication Year :
- 2019
- Publisher :
- HAL CCSD, 2019.
-
Abstract
- Best Paper Award; International audience; 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.
- Subjects :
- Discrete mathematics
Consensus
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Complete graph
Crash
Combinatorial topology
0102 computer and information sciences
02 engineering and technology
Radius
01 natural sciences
Upper and lower bounds
Computer Science Applications
Theoretical Computer Science
Synchronous network
Computational Theory and Mathematics
010201 computation theory & mathematics
Distributed graph algorithms
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Crash failures
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Information Systems
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-030-34991-2
- ISBNs :
- 9783030349912
- Database :
- OpenAIRE
- Journal :
- 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2019), 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⟩, SSS 2019-21st International Symposium on Stabilization, Safety, and Security of Distributed Systems, 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⟩, Lecture Notes in Computer Science ISBN: 9783030349912, SSS
- Accession number :
- edsair.doi.dedup.....6a7b8b1f29d86117088a66c6e896072b