Carleton University
Technical Report TR-96-18
July 1996
Symmetry and Computability in Anonymous Networks: A Brief Survey
Abstract
Processors in anonymous networks are as identical to each other as possible and possess “little” knowledge about the network. Anonymous networks are very useful in theoretical studies for testing “true distributivity”. In this paper we give a brief survey of results illuminating how symmetry influences computability in anonymous networks. Problems and issues considered include leader election, spanning tree construction, orientations, randomization, processor views, and computability problems on arbitrary as well as symmetric functions. Results mentioned are applicable to several topologies ranging from the rings, tori, hypercubes, and Cayley networks to arbitrary networks. We also propose several related open problems.
Dedicated to the memory of my beloved father Konstantionos who passed away unexpectedly on June 17, 1996.