Symmetric network computation

ABSTRACT

We introduce a simple new model of distributed computation -- finite-state symmetric graph automata (FSSGA) -- which captures the qualitative properties common to fault-tolerant distributed algorithms. Roughly speaking, the computation evolves homogeneously in the entire network, with each node acting symmetrically and with limited resources. As a building block, we demonstrate the equivalence of two automaton models for computing symmetric multi-input functions. We give FSSGA algorithms for several well-known problems.

REFERENCES

• 1: Dana Angluin , James Aspnes , Zoë Diamadi , Michael J. Fischer , René Peralta, Computation in networks of passively mobile finite-state sensors, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011810]
• 2: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 3: Baruch Awerbuch , Rafail Ostrovsky, Memory-efficient and self-stabilizing network RESET (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.254-263, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198104]
• 4: S. R. Buss, C. H. Papadimitriou, and J. N. Tsitsiklis. On the predictability of coupled automata: An allegory about chaos. In Proc. 31st Symp. Foundations of Computer Science, pages 788--293, 1990.
• 5: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 6: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 7: M. Gardner. The fantastic combinations of John Conway's new solitaire game "life". Scientific American, 223:120--123, 1970.
• 8: D. S. Hirschberg , J. B. Sinclair, Decentralized extrema-finding in circular configurations of processors, Communications of the ACM, v.23 n.11, p.627-628, Nov. 1980 [doi>10.1145/359024.359029]
• 9: G. Itkis and L. Levin. Fast and lean self-stabilizing asynchronous protocols. In Proc. 35th Symp. Foundations of Computer Science, pages 226--239, 1994.
• 10: David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007438]
• 11: N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72982]
• 12: Bruno Martin, A geometrical hierarchy on graphs via cellular automata, Fundamenta Informaticae, v.52 n.1-3, p.157-181, September 2002
• 13: Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129777]
• 14: D. L. Milgram. Web automata. Information and Control, 29(2):162--184, 1975.
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 17: Eric Rémila, Recognition of graphs by automata, Theoretical Computer Science, v.136 n.2, p.291-332, Dec. 26, 1994 [doi>10.1016/0304-3975(94)00045-K]
• 18: A. Rosenfeld. Networks of automata: some applications. IEEE Trans. Systems, Man, and Cybernetics, 5:380--383, 1975.
• 19: A. Rosenfeld and D. L. Milgram. Web automata and web grammars. Machine Intelligence, 7:307--324, 1972.
• 20: D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput., 6(5):563--581, 1977.
• 21: P. Rosenstiehl, J. Fiksel, and A. Holliger. Intelligent graphs: Networks of finite automata capable of solving graph problems. In R. C. Read, editor, Graph Theory and Computing, pages 219--265. Academic Press, 1972.
• 22: H. Szwerinkski. Time-optimal solution of the firing-squad synchronization-problem for n-dimensional rectangles with the general at an arbitrary position. Theoret. Comput. Sci., 19:305--320, 1982.
• 23: Gerard Tel, Introduction to distributed algorithms, Cambridge University Press, New York, NY, 1994

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

General Terms:
Algorithms, Reliability, Theory

Keywords:
agents, election, fault-tolerance, symmetry