We consider the task of learning a ring in a distributed way: each node of an unknown ring has to construct a labeled map of it. Nodes are equipped with unique labels. Communication proceeds in synchronous rounds. In every round every node can send arbitrary messages to its neighbors and perform arbitrary local computations. We study tradeoffs between the time (number of rounds) and the cost (number of messages) of completing this task in a deterministic way: for a given time T we seek bounds on the smallest number of messages needed for learning the ring in time T. Our bounds depend on the diameter D of the ring and on the delay θ = T - D above the least possible time D in which this task can be performed. We prove a lower bound Ω(D2/θ) on the number of messages used by any algorithm with delay θ, and we design a class of algorithms that give an almost matching upper bound: for any positive constant 0 &lt; ε &lt; 1 there is an algorithm working with delay θ ≤ D and using O(D2 (log* D)/θ1 - ε) messages. © 2013 Springer-Verlag.

Learning a ring cheaply and fast / Fusco, EMANUELE GUIDO; Andrzej, Pelc; Petreschi, Rossella. - STAMPA. - 7966:(2013), pp. 557-568. (Intervento presentato al convegno 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 tenutosi a Riga, Latvia nel July 8-12 2013) [10.1007/978-3-642-39212-2_49].

### Learning a ring cheaply and fast

#### Abstract

We consider the task of learning a ring in a distributed way: each node of an unknown ring has to construct a labeled map of it. Nodes are equipped with unique labels. Communication proceeds in synchronous rounds. In every round every node can send arbitrary messages to its neighbors and perform arbitrary local computations. We study tradeoffs between the time (number of rounds) and the cost (number of messages) of completing this task in a deterministic way: for a given time T we seek bounds on the smallest number of messages needed for learning the ring in time T. Our bounds depend on the diameter D of the ring and on the delay θ = T - D above the least possible time D in which this task can be performed. We prove a lower bound Ω(D2/θ) on the number of messages used by any algorithm with delay θ, and we design a class of algorithms that give an almost matching upper bound: for any positive constant 0 < ε < 1 there is an algorithm working with delay θ ≤ D and using O(D2 (log* D)/θ1 - ε) messages. © 2013 Springer-Verlag.
##### Scheda breve Scheda completa
2013
40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
time; tradeoff; labeled ring; message complexity
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Learning a ring cheaply and fast / Fusco, EMANUELE GUIDO; Andrzej, Pelc; Petreschi, Rossella. - STAMPA. - 7966:(2013), pp. 557-568. (Intervento presentato al convegno 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 tenutosi a Riga, Latvia nel July 8-12 2013) [10.1007/978-3-642-39212-2_49].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/516506`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 0
• 0