Calling names on nameless networks

Baruch Schieber, Marc Snir

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


We consider the problem of constructing a rooted spanning tree in an anonymous connected) network. In case no upper bound on the network size is known, we give the following algorithms, all of which have error probability ε: (1) A message terminating algorithm that runs in O(n) time and O(m log(n2/m)) messages, each of size O(log(n/ε)), where n and m are the number of nodes and links in the network. (2) A message terminating algorithm with expected running time O(n log log(n/ε)) and expected message complexity O(n log n + m log log(n/ε)), each of size O(log(n/ε)). For any fixed ε, this algorithm can be modified to run in O(nf(n)) expected time and O(n log n + mf(n)) expected message complexity, where f(n) is any slowly-growing function. However, this requires the use of longer messages. In case an upper bound on the network size is known, we give a processor terminating algorithm with error probability ε that runs in O(n) time, and O(n log n + m) messages. Finally, in case the network size is known within a factor of 2, we give an algorithm that processor terminates and always succeeds, in expected O(n) time and O(n log n + m) messages.

Original languageEnglish (US)
Pages (from-to)80-101
Number of pages22
JournalInformation and Computation
Issue number1
StatePublished - Aug 15 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Calling names on nameless networks'. Together they form a unique fingerprint.

Cite this