Node Labels in Local Decision

Abstract : The role of unique node identifiers in network computing is well understood as far as symmetry breaking is concerned. However, the unique identifiers also leak information about the computing environment— in particular, they provide some nodes with information related to the size of the network. It was recently proved that in the context of local decision, there are some decision problems such that (1) they cannot be solved without unique identifiers, and (2) unique node identifiers leak a sufficient amount of information such that the problem becomes solvable (PODC 2013). In this work we give study what is the minimal amount of information that we need to leak from the environment to the nodes in order to solve local decision problems. Our key results are related to scalar oracles f that, for any given n, provide a multiset f (n) of n labels; then the adversary assigns the labels to the n nodes in the network. This is a direct generalisation of the usual assumption of unique node identifiers. We give a complete characterisation of the weakest oracle that leaks at least as much information as the unique identifiers. Our main result is the following dichotomy: we classify scalar oracles as large and small, depending on their asymptotic behaviour, and show that (1) any large oracle is at least as powerful as the unique identifiers in the context of local decision problems, while (2) for any small oracle there are local decision problems that still benefit from unique identifiers.
Type de document :
Communication dans un congrès
22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO), Jul 2015, Montserrat, Spain. Springer, LNCS 9439, pp.589-598, 2015, 〈10.1007/978-3-319-25258-2_3〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01247355
Contributeur : Pierre Fraigniaud <>
Soumis le : lundi 21 décembre 2015 - 17:41:45
Dernière modification le : jeudi 11 janvier 2018 - 06:21:34
Document(s) archivé(s) le : samedi 29 avril 2017 - 23:47:41

Fichier

sub-SIROCCO2015.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Fraigniaud, Juho Hirvonen, Jukka Suomela. Node Labels in Local Decision. 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO), Jul 2015, Montserrat, Spain. Springer, LNCS 9439, pp.589-598, 2015, 〈10.1007/978-3-319-25258-2_3〉. 〈hal-01247355〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

38