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.
Similar content being viewed by others
References
J. Akiyama, A. M. Kano, and A. Saito, Factors and factorizations of graphs-a survey,Journal of Graph Theory 9 (1985), 1–42.
D. Angluin, Local and global properties in networks of processors,Proc. 12thACM Symposium on Theory of Computing, 1980, pp. 82–93.
H. Attiya and M. Snir, Better computing on the anonymous ring,Journal of Algorithms 12 (1991), 204–238.
H. Attiya, M. Snir, and M. K. Warmuth, Computing on the anonymous ring,Journal of the Association for Computing Machinery 35(4) (1988), 845–875.
P. W. Beame and H. L. Bodlaender, Distributed computing on transitive networks: the torus,Proc. 6thSymposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 349, Springer-Verlag, Berlin, 1989, pp. 294–303.
P. Duris and Z. Galil, Two lower bounds in asynchronous distributed computation,Journal of Computer and System Sciences 42 (1991), 245–266.
A. F. Harary,Graph Theory, Addison-Wesley, Reading, MA, 1969.
R. E. Johnson and F. B. Schneider, Symmetry and similarity in distributed systems,Proc. 4thACM Symposium on Principles of Distributed Computing, 1985, pp. 13–22.
E. Kranakis and D. Krizanc, Computing boolean functions on anonymous hypercube networks (extended abstract), Technical Report CS-R9040, Center for Mathematics and Computer Science, 1990.
E. Kranakis, D. Krizanc, and J. van den Berg, Computing boolean functions on anonymous networks,Proc. 17thInternational Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 443, Springer-Verlag, Berlin, 1990, pp. 254–267.
S. Moran and M. K. Warmuth, Gap theorems for distributed computation,SIAM Journal on Computing 22(2) (1993), 379–394.
N. Norris, Universal covers of edge-labeled digraphs: isomorphism to depthn-1 implies isomorphism to all depths,Applied Discrete Mathematics, to appear.
J. Petersen, Die Theorie der regulären Graphs,Acta Mathematica 15 (1891), 193–220.
M. Yamashita and T. Kameda, Computing functions on an anonymous network, LCCR Technical Report 87-16, Simon Fraser University, Canada, Burnaby, BC, 1987.
M. Yamashita and T. Kameda, Computing on anonymous networks,Proc. 7thACM Symposium on Principles of Distributed Computing, 1988, pp. 117–130.
M. Yamashita and T. Kameda, Computing on anonymous networks, Part I: Characterizing the solvable cases,IEEE Transactions on Parallel and Distributed Systems 7(1) (1996), 69–89.
M. Yamashita and T. Kameda, Computing on anonymous networks, Part II: Decision and membership problems,IEEE Transactions on Parallel and Distributed Systems 7(1) (1996), 90–96.
Author information
Authors and Affiliations
Additional information
This work was supported in part by the Natural Sciences and Engineering Research Council of Canada and in part by Scientific Research Grant-in-Aid No. 63750360 from the Ministry of Education, Science, and Culture of Japan.
Rights and permissions
About this article
Cite this article
Yamashita, M., Kameda, T. Computing functions on asynchronous anonymous networks. Math. Systems Theory 29, 331–356 (1996). https://doi.org/10.1007/BF01192691
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01192691