In topology recognition, each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as advice. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes. We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size n and diameter image, for any constant image. In most cases, our bounds are asymptotically tight.

Topology recognition with advice / Petreschi, Rossella; Pelc, Andrzej; Fusco, Emanuele. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - STAMPA. - 247:(2016), pp. 254-265. [10.1016/j.ic.2016.01.005]

Topology recognition with advice

Petreschi, Rossella;Pelc, Andrzej;Fusco, Emanuele
2016

Abstract

In topology recognition, each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as advice. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes. We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size n and diameter image, for any constant image. In most cases, our bounds are asymptotically tight.
2016
Topology recognition; network advice; time tradeoff
01 Pubblicazione su rivista::01a Articolo in rivista
Topology recognition with advice / Petreschi, Rossella; Pelc, Andrzej; Fusco, Emanuele. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - STAMPA. - 247:(2016), pp. 254-265. [10.1016/j.ic.2016.01.005]
File allegati a questo prodotto
File Dimensione Formato  
Petreschi_Topology_2016.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 460.47 kB
Formato Adobe PDF
460.47 kB Adobe PDF
Petreschi_Topology-recognition.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 418.77 kB
Formato Adobe PDF
418.77 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/961782
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 11
social impact