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
Asymptotically optimal algorithms for approximate agreement
Full text PdfPdf (874 KB)
Source Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fifth annual ACM symposium on Principles of distributed computing table of contents
Calgary, Alberta, Canada
Pages: 73 - 87  
Year of Publication: 1986
ISBN:0-89791-198-9
Author
A D Fekete  Department of Mathematics, Harvard University, Cambridge, MA
Sponsor
SIGOPS: ACM Special Interest Group on Operating Systems
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 8,   Citation Count: 11
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   
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/10590.10597
What is a DOI?

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.

C
Brian A Coan, A communication-efficient canonical form for fault-tolerant distributed protocols, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.63-72, August 11-13, 1986, Calgary, Alberta, Canada  [doi>10.1145/10590.10596]
 
CD
B. Coan, C. Dwork, "Simultaneity is Harder than Agreement", Proceedings of the 5th Symposium on Reliability in Distributed Software and Database Systems, 141-150, January 1986.
 
D
D. Dolev, "The Byzantine Generals Strike Again", Journal of Algorithms 3, 14-30 (1982).
DLPSW
Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986  [doi>10.1145/5925.5931]
 
DM
C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
 
F
M. Fischer, "The Consensus Problem in Unreliable Distributed Systems (A Brief Survey)" Yale University Technical Report YALEU/DCS/RR-273 (1983).
 
FL
M. Fischer, N. Lynch, "A Lower Bound for the Time to Assure Interactive Consistency", Information Processing Letters 1-4, 183-186 (1982).
 
LL
J. Lundelius, N. Lynch, "A New Fault-Tolerant Algorithm for Clock Synchronization", Information and Control, 62, 2, 190-204 (1984)
LSP
Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982  [doi>10.1145/357172.357176]
PSL
M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980  [doi>10.1145/322186.322188]

CITED BY  11
A. D. Fekete, Asynchronous approximate agreement, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.64-76, August 10-12, 1987, Vancouver, British Columbia, Canada
 
B. A. Coan, A Compiler that Increases the Fault Tolerance of Asynchronous Protocols, IEEE Transactions on Computers, v.37 n.12, p.1541-1553, December 1988
Maurice Herlihy , Nir Shavit, A simple constructive computability theorem for wait-free computation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.243-252, May 23-25, 1994, Montreal, Quebec, Canada
Brian A Coan, A communication-efficient canonical form for fault-tolerant distributed protocols, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.63-72, August 11-13, 1986, Calgary, Alberta, Canada
Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States
Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States
 
Yi Zhao , Farokh B. Bastani, A self-adjusting algorithm for byzantine agreement, Distributed Computing, v.5 n.4, p.219-226, April 1992
 
Maurice Herlihy , Sergio Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, v.291 n.1, p.55-77, 4 January 2003
Gunnar Hoest , Nir Shavit, Towards a topological characterization of asynchronous complexity, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.199-208, August 21-24, 1997, Santa Barbara, California, United States
Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
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

INDEX TERMS

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases


General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:
A D Fekete: colleagues

Peer to Peer - Readers of this Article have also read:

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