A Reduction Theorem for Randomized Distributed Algorithms under Weak Adversaries
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.
Sun 17 Jan Times are displayed in time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
18:30 - 19:30: Concurrent and Distributed SystemsVMCAI at VMCAI Chair(s): Dana Drachsler CohenTechnion | |||
18:30 - 18:45 Talk | Concurrent Correctness in Vector Space VMCAI Christina PetersonUniversity of Central Florida, Victor CookUniversity of Central Florida, Damian DechevUniversity of Central Florida Media Attached | ||
18:45 - 19:00 Talk | Verification of Concurrent Programs Using Petri Net Unfoldings VMCAI Daniel DietschUniversity of Freiburg, Matthias HeizmannUniversity of Freiburg, Germany, Dominik KlumppUniversity of Freiburg, Mehdi NaouarUniversity of Freiburg, Andreas PodelskiUniversity of Freiburg, Germany, Claus SchätzleUniversity of Freiburg Media Attached | ||
19:00 - 19:15 Talk | Eliminating Message Counters in Synchronous Threshold Automata VMCAI Ilina StoilkovskaVienna University of Technology , Igor KonnovInformal Systems Inc, Josef WidderInformal Systems, Florian ZulegerVienna University of Technology Media Attached | ||
19:15 - 19:30 Talk | A Reduction Theorem for Randomized Distributed Algorithms under Weak Adversaries VMCAI Nathalie BertrandINRIA Rennes, Marijana LazicTechnical University of Munich, Josef WidderInformal Systems Media Attached |