research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleNot All Fair Probabilistic Schedulers are Equivalent
Bibtex cite IDRACTI-RU1-2009-27
Booktitle 13th International Conference On Principles Of DIstributed Systems (OPODIS 2009)
Series Lecture Notes in Computer Science
Year published 2009
Month December
Volume 5923
Pages 33-47
Publisher Springer-Verlag Berlin Heidelberg
Location Nimes, France
Keywords population protocol,probabilistic scheduler,fair scheduler,fairness,communicating automata
We propose a novel, generic definition of probabilistic schedulers for population protocols. We then identify the consistent probabilistic schedulers, and prove that any consistent scheduler that assigns a non-zero probability to any transition i->j, where i and j are configurations satisfying that i is not equal to j, is fair with probability 1. This is a new theoretical framework that aims to simplify proving specific probabilistic schedulers fair. In this paper we propose two new schedulers, the State Scheduler and the Transition Function Scheduler. Both possess the significant capability of being protocol-aware, i.e. they can assign transition probabilities based on information concerning the underlying protocol. By using our framework we prove that the proposed schedulers, and also the Random Scheduler that was defined by Angluin et al., are all fair with probability 1. We also define and study equivalence between schedulers w.r.t. performance (time equivalent schedulers) and correctness (computationally equivalent schedulers). Surprisingly, we prove the following. 1. The protocol-oblivious (or agnostic) Random Scheduler is not time equivalent to the State and Transition Function Schedulers, although all three are fair probabilistic schedulers (with probability 1). To prove the statement we study the performance of the One-Way Epidemic Protocol (OR Protocol) under these schedulers. To illustrate the unexpected performance variations of protocols under different fair probabilistic schedulers, we additionally modify the State Scheduler to obtain a fair probabilistic scheduler, called the Modified Scheduler, that may be adjusted to lead the One-Way Epidemic Protocol to arbitrarily bad performance. 2. The Random Scheduler is not computationally equivalent to the Transition Function Scheduler. To prove the statement we study the Majority Protocol w.r.t. correctness under the Transition Function Scheduler. It turns out that the minority may win with constant probability under the same initial margin for which the majority w.h.p. wins under the Random Scheduler (as proven by Angluin et al.).
Chatzigiannakis, Ioannis
Dolev, Shlomi
Fekete, Sandor
Michail, Othon
Spirakis, Paul
Opodis09 - proceedings.pdf (main file)
Publication ID670