Local and global properties in networks of processors (Extended Abstract)

ABSTRACT

This paper attempts to get at some of the fundamental properties of distributed computing by means of the following question: “How much does each processor in a network of processors need to know about its own identity, the identities of other processors, and the underlying connection network in order for the network to be able to carry out useful functions?” The approach we take is to require that the processors be designed without any knowledge (or only very broad knowledge) of the networks they are to be used in, and furthermore, that all processors with the same number of communication ports be identical. Given a particular network function, e.g., setting up a spanning tree, we ask whether processors may be designed so that when they are embedded in any connected network and started in some initial configuration, they are guaranteed to accomplish the desired function.

REFERENCES

• 1: D. Angluin and A. Gardiner, Finite common coverings of pairs of regular graphs, Journal of Combinatorial Theory Series B, to appear.
• 2: N. Biggs, “Algebraic Graph Theory,” Cambridge University Press, London, 1974; §19.
• 3: M. Blum and D. Kozen, On the power of the compass, 19th IEEE FOCS Symposium, 1978, 132–142.
• 4: M. Blum and W. Sakoda, On the capability of automata in 2 and 3 dimensional space, 18th IEEE FOCS Symposium, 1977, 147–161.
• 5: M. Farzan and D. A. Waller, Kronecker products and local joins of graphs, Canadian Journal of Mathematics 29 (1977), 255–269.
• 6: J. A. Feldman, Synchronizing distant cooperating processes, TR-26, Dept. of Computer Science, University of Rochester, October 1977.
• 7: A. Gardiner, Antipodal covering graphs, Journal of Combinatorial Theory Series B 16 (1974), 255–273.
• 8: J. L. Gross, Every connected regular graph of even degree is a Schreier coset graph, Journal of Combinatorial Theory Series B 22 (1977), 227–232.
• 9: J. L. Gross and F. Harary, Some problems in topological graph theory, preprint, Dept. of Computer Science, Columbia University, 1979.
• 10: J. L. Gross and T. W. Tucker, Generating all graph coverings by permutation voltage assignments, Discrete Mathematics 18 (1977), 273–283.
• 11: D. Kozen, Automata and planar graphs, IBM Research report, RC 7604 (#32912), April 1979.
• 12: N. A. Lynch and M. J. Fischer, On describing the behavior and implementation of distributed systems, School of Information and Computer Science, Georgia Institute of Technology, report #GIT-ICS-79/03, May 1979.
• 13: W. S. Massey, “Algebraic Topology,” Springer-Verlag, New York, 1967; Chapters 5,6.
• 14: D. L. Milgram, Web automata, Information and Control 29 (1975), 162–184.
• 15: George Milne , Robin Milner, Concurrent Processes and Their Syntax, Journal of the ACM (JACM), v.26 n.2, p.302-321, April 1979 [doi>10.1145/322123.322134]
• 16: J. Mylopolous, On the relation of graph grammars and graph automata, 13th IEEE Symposium on SWAT (1972), 108–120.
• 17: A. Rosenfeld, Networks of automata: some applications, IEEE Transactions on Systems, Man, and Cybernetics (1975), 380–383.
• 18: P. Rosenstiehl, J. R. Fiksel, and A. Holliger, Intelligent graphs, in “Graph Theory and Computing,” Ronald C. Read, ed., Academic Press, New York (1972), 219–265.
• 19: H. S. Shank, Graph property recognition machines, Mathematical Systems Theory 5 (1971), 45–49.
• 20: D. A. Waller, Double covers of graphs, Bulletin of the Australian Mathematical Society 14 (1976), 233–248.
• 21: A. Wu and A. Rosenfeld, Cellular graph automata, I and II, Information and Control 42 (1979), 305–329 and 330–353.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Theory