A reduction theorem for randomized distributed algorithms under weak adversaries

DOI10.1007/978-3-030-67067-2_11zbMATH Open1472.68083OpenAlexW3120281858MaRDI QIDQ2234073FDOQ2234073

Authors: Nathalie Bertrand, Marijana Lazić, Josef Widder 

Publication date: 18 October 2021

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

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

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)

Cites Work

• Title not available (Why is that?)
• Decomposition of distributed programs into communication-closed layers
• A Reduction Theorem for the Verification of Round-Based Distributed Algorithms
• Reduction
• Bosco: One-Step Byzantine Asynchronous Consensus
• Randomized protocols for asynchronous consensus
• A short counterexample property for safety and liveness verification of fault-tolerant distributed algorithms
• Asynchronous byzantine agreement protocols
• The correctness proof of Ben-Or's randomized consensus algorithm
• Synchronizing the asynchronous
• 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
• On the completeness of verifying message passing programs under bounded asynchrony
• Title not available (Why is that?)
• Communication-closed asynchronous protocols

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)