Distributed computing with advice: information sensitivity of graph coloring

Pierre Fraigniaud (1) , Cyril Gavoille (2, 3) , David Ilcinkas (2, 3) , Andrzej Pelc (4)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique
3 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
4 DII - Département d'Informatique et d'Ingénierie

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.

Mots clés: network algorithm; graph coloring; distributed computing

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]

Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, Andrzej Pelc. Distributed computing with advice: information sensitivity of graph coloring. Distributed Computing, 2009, 21 (6), pp.395-403. ⟨10.1007/s00446-008-0076-y⟩. ⟨hal-00395775⟩