Agreement in synchronous networks with ubiquitous faults

DOI10.1016/j.tcs.2007.04.036zbMath1125.68012OpenAlexW2137845880MaRDI 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

agreementmajoritysynchronous systemsdynamic faultsmobile faultsbivalency argumentarbitrary network topologylimits to computabilityTheory of distributed computationtransmission failure model

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (13)

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

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

This page was built for publication: Agreement in synchronous networks with ubiquitous faults