Impossibility Results and Lower Bounds for Consensus under Link Failures

DOI10.1137/S009753970443999XzbMath1192.68377OpenAlexW2086286040MaRDI QIDQ3642868

Idit Keidar, Bettina Weiss, Ulrich Schmid

Publication date: 6 November 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753970443999x

zbMATH Keywords

lower boundsconsensusimpossibility resultsfault-tolerant distributed algorithmstransient link failuresassumption coverage analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Distributed algorithms (68W15)

Related Items (15)

Some lower bounds in dynamic networks with oblivious adversaries ⋮ Distributed computations in fully-defective networks ⋮ Tight bound on mobile Byzantine agreement ⋮ Booting clock synchronization in partially synchronous systems with hybrid process and link failures ⋮ On the impact of link faults on Byzantine agreement ⋮ A simple characterization of asynchronous computations ⋮ Randomization can be a healer: consensus with dynamic omission failures ⋮ Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks ⋮ Consensus in rooted dynamic networks with short-lived stability ⋮ Synchronous consensus under hybrid process and link failures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults ⋮ A characterization of oblivious message adversaries for which consensus is solvable ⋮ A Characterization of Dynamic Networks Where Consensus Is Solvable

This page was built for publication: Impossibility Results and Lower Bounds for Consensus under Link Failures