Calling names on nameless networks

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. © 1994 Academic Press, Inc.