03/01/1994 09:00 AM
Computer Science
An \"anonymous network\" is a computer network in which all processors run the same algorithm during a computation. We will consider two classifications of anonymous networks: Networks will be called \"f-equivalent\" if the set of vector-valued functions each can anonymously compute is the same, and \"p-equivalent\" if the set of functions each can compute is the same, \"up to a permutation\" We first give a characteriz- ation of the vector-valued functions a given network can anonymously compute. This extends a result due to Yamashita and Kameda characterizing the scalar-valued functions a network can compute. Next, we develop algebraic and graph-theoretic techniques for handling edge-labeled digraphs. We will use these techniques, along with results from algebraic automata theory and permutation group theory, to derive a polynomial-time algorithm for determining whether two networks are f- equivalent. This will yield a polynomial-time algorithm for determining whether two edge-labeled digraphs have the same lattice of quotient-graph isomorphisms, and will let us conclude that classifying networks by what they can compute is easy. Classifying networks by \"p-equivalence\" on the other hand, is likely to be a much harder problem. We will present a polynomial-time transformation of the group-isomorphism problem to the problem of \"p-equivalence\" As of this writing, the best known algorithm solves group-isomorphism in order n to the log n steps, for a group of order n.
