ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Compass permits leader election
Full text PdfPdf (220 KB)
Source Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents
Baltimore, Maryland, United States
Pages: 947 - 948  
Year of Publication: 1999
ISBN:0-89871-434-6
Authors
Jacques Mazoyer  LIP, ENS-Lyon, CNRS ura 1398 46 allée d'Italie, 69364 Lyon cedex 07, France
Codrin Nichitiu  LIP, ENS-Lyon, CNRS ura 1398 46 allée d'Italie, 69364 Lyon cedex 07, France
Eric Rémila  Grima, IUT Roanne, Universitié J. Monnet 20 avenue de Paris, 42334 Roanne cedex, France
Sponsors
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics
Publisher
Society for Industrial and Applied Mathematics  Philadelphia, PA, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 13,   Citation Count: 1
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Review this Article  
Save this Article to a Binder    Display Formats: BibTex  EndNote ACM Ref   

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States  [doi>10.1145/800141.804655]
 
2
M. Blum, D. Kozen, on the power of the compass, proceedings of the 19th IEEE symposium on Foundations of Computer Science (1978)
 
3
E. W. Dijkstra, Hierarchical ordering of sequential processes, Acta Informatica 1 (1971) 115-138.
4
Patrick C. Fischer, Generation of Primes by a One-Dimensional Real-Time Iterative Array, Journal of the ACM (JACM), v.12 n.3, p.388-394, July 1965  [doi>10.1145/321281.321290]
 
5
Jacques Mazoyer, A six-state minimal time solution to the firing squad synchronization problem, Theoretical Computer Science, v.50 n.2, p.183-238, 1987  [doi>10.1016/0304-3975(87)90124-1 ]
 
6
Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
 
7
A. Itai, M. Rodeh, Symmetry breaking in distributive networks, proceedings of the 22'#d IEEE symposium on Foundations of Computer Science (1981) 150-159.
 
8
V. Terrier, D#cidabilit# en arithm#thique faible, temps r4el sur les automates cellulaires, Ph. D. Thesis, Universit# Lyon I (1991 ).

CITED BY
 
Michael Stratmann , Thomas Worsch, Leader election in d-dimensional CA in time diam log(diam), Future Generation Computer Systems, v.18 n.7, p.939-950, August, 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

  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)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures


General Terms:
Algorithms, Design, Performance, Standardization, Theory

Collaborative Colleagues:
Jacques Mazoyer: colleagues
Codrin Nichitiu: colleagues
Eric Rémila: colleagues

Peer to Peer - Readers of this Article have also read:
  • LR Parsing ACM Computing Surveys (CSUR)   6, 2
    A. V. Aho ,  S. C. Johnson


The ACM Portal is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player