Adding a referee to an interconnection network: What can(not) be computed in one round.

Abstract : In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes -which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3?" cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs.
Type de document :
Communication dans un congrès
25th IEEE International Symposium on Parallel & Distributed Processing (IPDPS), 2011, Anchorage, United States. pp.508-514, 2011
Liste complète des métadonnées


https://hal.inria.fr/inria-00622976
Contributeur : Nicolas Nisse <>
Soumis le : mardi 13 septembre 2011 - 11:10:03
Dernière modification le : mercredi 14 décembre 2016 - 01:06:32
Document(s) archivé(s) le : mardi 13 novembre 2012 - 10:36:27

Fichier

BoundedLocalInformation1_10_10...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00622976, version 1

Collections

Citation

Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, et al.. Adding a referee to an interconnection network: What can(not) be computed in one round.. 25th IEEE International Symposium on Parallel & Distributed Processing (IPDPS), 2011, Anchorage, United States. pp.508-514, 2011. <inria-00622976>

Partager

Métriques

Consultations de
la notice

317

Téléchargements du document

139