Classifying Anonymous Networks: When Can Two Networks Compute the Same Vector-Valued Functions ?
Nancy Norris · McGill-Queen's University Press eBooks · 1995
An “anonymous network” is a computer network in which all processors run the same algorithm during a computation. This paper addresses the problem of classifying anonymous networks by the functions they can compute: Let us say that two networks are “ f -equivalent” if the set of vector-valued functions each can compute is the same. We will find an algorithm polynomial in the number of processors in a network for determining whether two networks are in the same f equivalence-class. Thus, classifying networks by what they can compute is not hard. Before we derive this algorithm we will characterize the set of vector-valued functions that a given anonymous network can compute, in terms of the network’s toplogy. This extends results Characterizing the scalar-valued functions computable on an anonymous ring ([2]) and on an arbitrary anonymous network ([3]). We will also develop algebraic and topological techniques for handling edge-labeled directed graphs.