A reduction theorem for randomized distributed algorithms under weak adversaries

DOI10.1007/978-3-030-67067-2_11zbMath1472.68083OpenAlexW3120281858MaRDI QIDQ2234073

Nathalie Bertrand, Marijana Lazić, Josef Widder

Publication date: 18 October 2021

Full work available at URL: https://hal.inria.fr/hal-03150397/document

zbMATH Keywords

reductiondistributed algorithmsrandomized consensusparameterized verificationweak adversariescommunication closure

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (1)

Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposition of distributed programs into communication-closed layers
• Asynchronous byzantine agreement protocols
• Randomized \(k\)-set agreement in crash-prone and Byzantine asynchronous systems
• \(\text{Para}^2\): parameterized path reduction, acceleration, and SMT for reachability in threshold-guarded distributed algorithms
• The correctness proof of Ben-Or's randomized consensus algorithm
• Bosco: One-Step Byzantine Asynchronous Consensus
• A Reduction Theorem for the Verification of Round-Based Distributed Algorithms
• Reduction
• Randomized protocols for asynchronous consensus
• A short counterexample property for safety and liveness verification of fault-tolerant distributed algorithms
• On the completeness of verifying message passing programs under bounded asynchrony
• Communication-closed asynchronous protocols

This page was built for publication: A reduction theorem for randomized distributed algorithms under weak adversaries