Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks

DOI10.1016/j.tcs.2018.02.019zbMath1390.68086arXiv1501.02716OpenAlexW2789563213MaRDI QIDQ1743719

Manfred Schwarz, Martin Biely, Ulrich Schmid, Kyrill Winkler, Peter Robinson

Publication date: 16 April 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.02716

zbMATH Keywords

lower boundsconsensusimpossibility results\(k\)-set agreementfailure detectorsdirected dynamic networksmessage adversaries

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network protocols (68M12)

Related Items (9)

Derivation of Heard-of Predicates from Elementary Behavioral Patterns ⋮ Valency-based consensus under message adversaries without limit-closure ⋮ Self-stabilizing systems in spite of high dynamics ⋮ On linear-time data dissemination in dynamic rooted trees ⋮ Consensus in rooted dynamic networks with short-lived stability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A topological perspective on distributed network algorithms ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems
• Synchronous consensus under hybrid process and link failures
• Distributed computing and networking. 14th international conference, ICDCN 2013, Mumbai, India, January 3--6, 2013. Proceedings
• Decomposition of distributed programs into communication-closed layers
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks
• Dynamic graph models
• Consensus in rooted dynamic networks with short-lived stability
• A characterization of oblivious message adversaries for which consensus is solvable
• The Heard-Of model: computing in distributed systems with benign faults
• Towards worst-case churn resistant peer-to-peer systems
• Round-by-round fault detectors (extended abstract)
• A Characterization of Dynamic Networks Where Consensus Is Solvable
• Distributed computation in dynamic networks
• Coordinated consensus in dynamic networks
• Expander graphs and their applications
• Beyond Lamport’s Happened-Before: On the Role of Time Bounds in Synchronous Systems
• Impossibility Results and Lower Bounds for Consensus under Link Failures
• Distributed agreement in the presence of processor and communication faults
• Complexity of network synchronization
• Impossibility of distributed consensus with one faulty process
• Fault Tolerance in Networks of Bounded Degree
• Unreliable failure detectors for reliable distributed systems
• The weakest failure detector for solving consensus
• Distributed Computing: A Locality-Sensitive Approach
• Time is not a healer
• Fast byzantine agreement in dynamic networks
• Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors
• The birth of the giant component
• The weakest failure detectors to solve certain fundamental problems in distributed computing

This page was built for publication: Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks