Agreement in synchronous networks with ubiquitous faults

DOI10.1016/j.tcs.2007.04.036zbMath1125.68012MaRDI QIDQ2382676

Nicola Santoro, Peter Widmayer

Publication date: 2 October 2007

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.036

zbMATH Keywords

agreement; majority; synchronous systems; dynamic faults; mobile faults; bivalency argument; arbitrary network topology; limits to computability; Theory of distributed computation; transmission failure model

Mathematics Subject Classification ID

68M14: Distributed systems

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

Unnamed Item, Back to the Coordinated Attack Problem, What Can be Computed in a Distributed System?, Synchronous \(t\)-resilient consensus in arbitrary graphs, Asynchronous Byzantine reliable broadcast with a message adversary, A simple characterization of asynchronous computations, Randomization can be a healer: consensus with dynamic omission failures, Synchronous consensus under hybrid process and link failures, On fractional dynamic faults with thresholds, A characterization of oblivious message adversaries for which consensus is solvable, The Heard-Of model: computing in distributed systems with benign faults, A Characterization of Dynamic Networks Where Consensus Is Solvable, Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults

Cites Work

• Unnamed Item
• Computing input multiplicity in anonymous synchronous networks with dynamic faults
• Easy impossibility proofs for distributed consensus problems
• A lower bound for the time to assure interactive consistency
• Broadcasting in a hypercube when some calls fail
• Efficient broadcasting with linearly bounded faults
• Agreement in the presence of faults, on networks of bounded degree
• Broadcasting with linearly bounded transmission faults
• Optimal broadcasting in hypercubes with dynamic faults
• A simple bivalency proof that \(t\)-resilient consensus requires \(t+1\) rounds
• Atomic broadcast: From simple message diffusion to Byzantine agreement
• Broadcasting in hypercubes and star graphs with dynamic faults.
• A Layered Analysis of Consensus
• A tight lower bound for randomized synchronous consensus
• Distributed agreement in the presence of processor and communication faults
• Impossibility of distributed consensus with one faulty process
• Fault Tolerance in Networks of Bounded Degree
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem
• The Byzantine generals strike again
• Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds
• Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds
• An efficient algorithm for byzantine agreement without authentication
• Time is not a healer
• Broadcasting in synchronous networks with dynamic faults