1 Search Results for "Blanchard, Peva"

Document
DOI: 10.4230/LIPIcs.OPODIS.2015.21
The Benefits of Entropy in Population Protocols

Authors: Joffroy Beauquier, Peva Blanchard, Janna Burman, and Rachid Guerraoui

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
A distributed computing system can be viewed as the result of the interplay between a distributed algorithm specifying the effects of a local event (e.g. reception of a message), and an adversary choosing the interleaving (schedule) of these events in the execution. In the context of large networks of mobile pairwise interacting agents (population protocols), the adversary models the mobility of the agents by choosing the successive pairs of interacting agents. For some problems, assuming that the adversary selects the schedule according to some probability distribution greatly helps to devise (almost) correct solutions. But how much randomness is really necessary? To what extent does a problem admit implementations that are robust against a "not so random" schedule? This paper takes a first step in addressing this question by borrowing the concept of T-randomness, 0 <= T <= 1, from algorithmic information theory. Roughly speaking, the value T fixes the entropy rate of the considered schedules. For instance, the case T = 1 corresponds, in a specific sense, to schedules in which the pairs of interacting agents are chosen independently and uniformly (perfect randomness). The holy grail question can then be precisely stated as determining the optimal entropy rate to solve a given problem. We first show that perfect randomness is never required. Precisely, if a finite-state algorithm solves a problem with 1-randomness, then this algorithm still solves the same problem with T-randomness for some T < 1. Second, we illustrate how to compute bounds on the optimal entropy rate of a specific problem, namely the leader election problem.
Cite as

Joffroy Beauquier, Peva Blanchard, Janna Burman, and Rachid Guerraoui. The Benefits of Entropy in Population Protocols. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{beauquier_et_al:LIPIcs.OPODIS.2015.21,
  author =	{Beauquier, Joffroy and Blanchard, Peva and Burman, Janna and Guerraoui, Rachid},
  title =	{{The Benefits of Entropy in Population Protocols}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.21},
  URN =		{urn:nbn:de:0030-drops-66128},
  doi =		{10.4230/LIPIcs.OPODIS.2015.21},
  annote =	{Keywords: algorithmic randomness, entropy, leader election, distributed computing, scheduler, population protocols}
}
  • Refine by Author
  • 1 Beauquier, Joffroy
  • 1 Blanchard, Peva
  • 1 Burman, Janna
  • 1 Guerraoui, Rachid

  • Refine by Classification

  • Refine by Keyword
  • 1 algorithmic randomness
  • 1 distributed computing
  • 1 entropy
  • 1 leader election
  • 1 population protocols
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact