The Entropy of a Distributed Computing Schedule - the Example of Population Protocols

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. 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 events are independent and sampled 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.
Type de document :
Communication dans un congrès
International Conference on Principles of DIstributed Systems (OPODIS 2015), Dec 2015, Rennes, France
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01247020
Contributeur : Janna Burman <>
Soumis le : lundi 21 décembre 2015 - 02:21:34
Dernière modification le : mardi 24 avril 2018 - 13:38:35
Document(s) archivé(s) le : samedi 29 avril 2017 - 23:03:49

Fichier

ait_fairness_pp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01247020, version 1

Citation

Joffroy Beauquier, Peva Blanchard, Janna Burman, Rachid Guerraoui. The Entropy of a Distributed Computing Schedule - the Example of Population Protocols. International Conference on Principles of DIstributed Systems (OPODIS 2015), Dec 2015, Rennes, France. 〈hal-01247020〉

Partager

Métriques

Consultations de la notice

171

Téléchargements de fichiers

146