CALLING NAMES ON NAMELESS NETWORKS

We consider the problem of constructing a rooted spanning tree in an a nonymous connected) network. In case no upper bound on the network siz e is known, we give the following algorithms, all of which have error probability epsilon: (1) A message terminating algorithm that runs in O(n) time and O(m log(n2/m)) messages, each of size O(log(n/epsilon)), 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/epsilon)) and expected message complexity O(n log n + m log log(n/ep silon)), each of size 9(log(n/epsilon)). For any fixed epsilon, this a lgorithm 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-grow ing function. However, this requires the use of longer messages. In ca se an upper bound on the network size is known, we give a processor te rminating algorithm with error probability epsilon that runs in O(n) t ime, and 0(n log n + m) messages. Finally, in case the network size is known within a factor of 2, we give an algorithm that processor termi nates and always succeeds, in expected O(n) time and O(n log n + m) me ssages. (C) 1994 Academic Press, Inc.