Skip to Main content Skip to Navigation
Conference papers

A Reduction Theorem for Randomized Distributed Algorithms Under Weak Adversaries

Abstract : Weak adversaries are a way to model the uncertainty due to asynchrony in randomized distributed algorithms. They are a standard notion in correctness proofs for distributed algorithms, and express the property that the adversary (scheduler), which has to decide which messages to deliver to which process, has no means of inferring the outcome of random choices, and the content of the messages. In this paper, we introduce a model for randomized distributed algorithms that allows us to formalize the notion of weak adversaries. It applies to randomized distributed algorithms that proceed in rounds and are tolerant to process failures. For this wide class of algorithms, we prove that for verification purposes, the class of weak adversaries can be restricted to simple ones, so-called round-rigid adversaries, that keep the processes tightly synchronized. As recently a verification method for round-rigid adversaries has been introduced, our new reduction theorem paves the way to the parameterized verification of randomized distributed algorithms under the more realistic weak adversaries.
Document type :
Conference papers
Complete list of metadata
Contributor : Nathalie Bertrand <>
Submitted on : Tuesday, February 23, 2021 - 5:27:21 PM
Last modification on : Thursday, March 18, 2021 - 1:50:23 PM


Files produced by the author(s)



Nathalie Bertrand, Marijana Lazić, Josef Widder. A Reduction Theorem for Randomized Distributed Algorithms Under Weak Adversaries. VMCAI 2021 - 22nd International Conference on Verification, Model Checking, and Abstract Interpretation, Jan 2021, Copenhagen, Denmark. pp.219-239, ⟨10.1007/978-3-030-67067-2_11⟩. ⟨hal-03150397⟩



Record views


Files downloads