A reduction theorem for randomized distributed algorithms under weak adversaries

DOI10.1007/978-3-030-67067-2_11MaRDI QIDQ2234073zbMATH OpenOpenAlexFDO

Authors 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

distributed algorithmsreductionrandomized consensusparameterized verificationweak adversariescommunication closure

Mathematics Subject Classification ID

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

Recommendations

• A Reduction Theorem for the Verification of Round-Based Distributed Algorithms
• Lower bounds for randomized consensus under a weak adversary
• Lower bounds for randomized consensus under a weak adversary
• A lower bound for probabilistic distributed algorithms
• Randomized distributed online algorithms against adaptive offline adversaries
• Distributed algorithms made secure: a graph theoretic approach
• Verification of randomized consensus algorithms under round-rigid adversaries
• The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms
• A tight unconditional lower bound on distributed randomwalk computation

Cites work

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

Cited in

(2)

• Randomization helps to perform independent tasks reliably
• Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker

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

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