TY - GEN

T1 - Calling names on nameless networks

AU - Schieber, Baruch

AU - Snir, Marc

PY - 1989/12/1

Y1 - 1989/12/1

N2 - We consider the problem of constructing a rooted spanning tree in an anonymous (connected) network. For the case where no bound is known on the network size, we give the following algorithms, that have error probability ε. (1) A message terminating algorithm that runs in O(n) time and O(n log n + m(1 + 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 error probability ε, the expected time and message complexity can be reduced to O(nf(n)) and O(n log n + mf(n)), respectively, where f(n) is some slowly-growing function, such as log n. 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 both an upper bound and a lower bound are known, which are within a factor of two, we give an algorithm that processor terminates and always succeeds, in expected O(n) time and O(n log n + m) messages.

AB - We consider the problem of constructing a rooted spanning tree in an anonymous (connected) network. For the case where no bound is known on the network size, we give the following algorithms, that have error probability ε. (1) A message terminating algorithm that runs in O(n) time and O(n log n + m(1 + 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 error probability ε, the expected time and message complexity can be reduced to O(nf(n)) and O(n log n + mf(n)), respectively, where f(n) is some slowly-growing function, such as log n. 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 both an upper bound and a lower bound are known, which are within a factor of two, we give an algorithm that processor terminates and always succeeds, in expected O(n) time and O(n log n + m) messages.

UR - http://www.scopus.com/inward/record.url?scp=0024925811&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024925811&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0024925811

SN - 0897913264

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 319

EP - 328

BT - Proc Eighth ACM Symp Princ Distrib Comput

PB - Publ by ACM

T2 - Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing

Y2 - 14 August 1989 through 16 August 1989

ER -