A Reduction Theorem for Randomized Distributed Algorithms Under Weak Adversaries

Nathalie Bertrand (1) , Marijana Lazic (2) , Josef Widder (3)

1 SUMO - SUpervision of large MOdular and distributed systems
2 TUM - Technische Universität Munchen - Technical University Munich - Université Technique de Munich
3 Informal systems [Vienna]

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.

Domaines: Informatique [cs]

Nathalie Bertrand, Marijana Lazic, 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⟩