Stopping times of distributed consensus protocols: a probabilistic analysis

DOI10.1016/0020-0190(87)90127-XMaRDI QIDQ1089784zbMATH OpenOpenAlexWikidataFDO

Authors Ozalp Babaoglu

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90127-x

zbMATH Keywords

Byzantine agreementdistributed computing systemprobabilistic failureprocessorsreliable computingresiliencysystem executions

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Review text

Given a model where each processor remains correct for an exponentially distributed random time and then fails independently of the others, we characterize system executions that permit the processors to reach consensus. We show that, with nonzero probability, a protocol can achieve consensus even during executions where the number of actual processors to fail exceeds its resiliency.

Recommendations

• Simple constant-time consensus protocols in realistic failure models
• Randomized protocols for asynchronous consensus
• Fast and simple distributed consensus
• Impossibility of distributed consensus with one faulty process
• On the minimal synchronism needed for distributed consensus

Cites work

• Authenticated Algorithms for Byzantine Agreement
• scientific article; zbMATH DE number 3819094 (Why is no real title available?)
• scientific article; zbMATH DE number 3338194 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem

Cited in

(6)

• On the scalability and mean-time to failure of \(k\) resilient protocols
• A crash-tolerant consensus algorithm in presence of probabilistic message omission
• Simple constant-time consensus protocols in realistic failure models
• Computing reliability intervals for k-resilient protocols
• Distributed Stopping for Average Consensus in Digraphs
• Closed schedulers: a novel technique for analyzing asynchronous protocols

This page was built for publication: Stopping times of distributed consensus protocols: a probabilistic analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089784)