License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24286
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2428/

Chatzigiannakis, Ioannis ; Dolev, Shlomi ; Fekete, Sándor ; Michail, Othon ; Spirakis, Paul

On the Fairness of Probabilistic Schedulers for Population Protocols

pdf-format:
Dokument 1.pdf (506 KB)


Abstract

We propose a novel, generic definition of emph{probabilistic schedulers} for population protocols. We design two new schedulers, the emph{State Scheduler} and the emph{Transition Function Scheduler}. Both possess the significant capability of being emph{protocol-aware}, i.e. they can assign transition probabilities based on information concerning the underlying protocol. We prove that the proposed schedulers, and also the emph{Random Scheduler} that was defined by Angluin et al. cite{AADFP04}, are all fair with probability $1$. We also define and study emph{equivalence} between schedulers w.r.t. emph{performance} and emph{correctness} and prove that there exist fair probabilistic schedulers that are not equivalent w.r.t. to performance and others that are not equivalent w.r.t. correctness. We implement our schedulers using a new tool for simulating population protocols and evaluate their performance from the viewpoint of experimental analysis and verification. We study three representative protocols to verify stability, and compare the experimental time to convergence with the known complexity bounds. We run our experiments from very small to extremely large populations (of up to $10^{8}$ agents). We get very promising results both of theoretical and practical interest.

BibTeX - Entry

@InProceedings{chatzigiannakis_et_al:DSP:2010:2428,
  author =	{Ioannis Chatzigiannakis and Shlomi Dolev and S{\'a}ndor Fekete and Othon Michail and Paul Spirakis},
  title =	{On the Fairness of Probabilistic Schedulers for Population Protocols},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  year =	{2010},
  editor =	{S{\'a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  number =	{09371},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2428},
  annote =	{Keywords: Population Protocols, Fairness, Probabilistic Schedulers, Communicating Automata, Sensor Networks, Experimental Evaluation}
}

Keywords: Population Protocols, Fairness, Probabilistic Schedulers, Communicating Automata, Sensor Networks, Experimental Evaluation
Seminar: 09371 - Algorithmic Methods for Distributed Cooperative Systems
Issue date: 2010
Date of publication: 22.04.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI