ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract In an “anonymous” network the processors have no identity numbers. We investigate the problem of computing a given functionf on an asynchronous anonymous network in the sense that each processor computesf(I) for any inputI = (I(v 1),...,I(v n )), whereI(v i) is the input to processorv i ,i = 1, 2,...,n. We address the following three questions: (1) What functions are computable on a given network? (2) Is there a “universal” algorithm which, given any networkG and any functionf computable onG as inputs, computesf onG? (3) How can one find lower bounds on the message complexity of computing various functions on anonymous networks? We give a necessary and sufficient condition for a function to be computable on an asynchronous anonymous network, and present a universal algorithm for computingf(I) on any networkG, which acceptsG andf computable onG, as well as {I(v i )}, as inputs. The universal algorithm requiresO(mn) messages in the worst case, wheren andm are the numbers of processors and links in the network, respectively. We also propose a method for deriving a lower bound on the number of messages necessary to solve the above problem on asynchronous anonymous networks.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01192691
Permalink