Consiglio Nazionale delle Ricerche

Tipo di prodottoContributo in atti di convegno
TitoloTime vs. information tradeoffs for Leader election in anonymous trees
Anno di pubblicazione2016
  • Elettronico
  • Cartaceo
Autore/iGlacet C.; Miller A.; Pelc A.
Affiliazioni autoriCNR, IEIIT, Torino, Italy; Universite du Quebec en Outaouais, Gatineau, Canada
Autori CNR e affiliazioni
  • inglese
AbstractLeader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in anonymous trees. Our aim is to establish tradeoffs between the allocated time t and the amount of information that has to be given a priori to the nodes to enable leader election in time r in all trees for which leader election in this time is at all possible. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the size of advice. For a given time ? allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time ?. For most values of ?, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let T be an n-node tree of diameter diam > D. While leader election in time diam can be performed without any advice, for time diam - 1 we give tight upper and lower bounds of ?(log D). For time diam - 2 we give tight upper and lower bounds of ?(log D) for even values of diam, and tight upper and lower bounds of 0(logn) for odd values of diam. Moving to shorter time, in the interval [? · diam, diam - 3] for constant ? > 1/2, we prove an upper bound of O(n log n/D) and a lower bound of ?(n/D), the latter being valid whenever diam is odd or when the time is at most diam - 4. Hence, with the exception of the special case when diam is even and time is exactly diam-3, our bounds leave only a logarithmic gap in this time interval. Finally, for time ? · diam for any constant a < 1/2 (except for the case of very small diameters), we again give tight upper and lower bounds, this time ?(n).
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da600
Pagine a609
Pagine totali-
Numero volume della rivista1
Titolo del volume-
Numero volume della serie/collana1
Curatore/i del volume-
Verificato da referee-
Stato della pubblicazionePublished version
Indicizzazione (in banche dati controllate)
  • Scopus (Codice:2-s2.0-84963532522)
Parole chiaveAdvice, Deterministic distributed algorithm, Leader election, Time, Tree
Link (URL, URI)
Titolo convegno/congressoACM-SIAM Symposium on Discrete Algorithms
Luogo convegno/congresso-
Data/e convegno/congresso01/2016
Titolo parallelo-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR
    Progetti Europei-