Inexact agreement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Inexact agreement: accuracy, precision, and graceful degradation

Full text

Pdf (1.10 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fourth annual ACM symposium on Principles of distributed computing table of contents

Minaki, Ontario, Canada

Pages: 237 - 249

Year of Publication: 1985

ISBN:0-89791-168-7

Authors

Stephen R. Mahaney	AT&T Bell Laboratories, Murray Hill, N.J
Fred B. Schneider	Department of Computer Science, Cornell University, Ithaca, N.Y.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 15, Citation Count: 32

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/323596.323618 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.

	D82	Dolev, D. The byzantine generals strike again. J. of Algorithms 3, 14-30 (1982).
	DLPSW83	Dolev, D., N.A. Lynch, S.S Pinter, E.W. Stark, and W.E. Weihl. Reaching approximate agreement in the presence of faults. Proc. Third Symposium on Reliability in Distributed Software and Database Systems, Oct. 1983, IEEE Computer Society, 145- 154.
	HSSD84	Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806739]
	LL84	Jennifer Lundelius , Nancy Lynch, A new fault-tolerant algorithm for clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.75-88, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806738]
	LM84	Leslie Lamport , P. M. Melliar-Smith, Byzantine clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.68-74, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806737]
	LM85	Leslie Lamport , P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, Journal of the ACM (JACM), v.32 n.1, p.52-78, Jan. 1985 [doi>10.1145/2455.2457]
	LSP82	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]
	MO83	Keith Marzullo , Susan Owicki, Maintaining the time in a distributed system, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.295-305, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806730]
	MS85	Mahaney, S.R. and F.B. Schneider. Failing with Grace. In preparation.
	S84	Fred B. Schneider, Byzantine generals in action: implementing fail-stop processors, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.145-154, May 1984 [doi>10.1145/190.357399]

CITED BY 32

	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 , 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
	Shlomi Dolev , Jennifer L. Welch, Wait-free clock synchronization, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.97-108, August 15-18, 1993, Ithaca, New York, United States
	Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993
	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
	D. Agrawal , A. El Abbadi, Efficient solution to the distributed mutual exclusion problem, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.193-200, June 1989, Edmonton, Alberta, Canada
	D. Agrawal , A. El Abbadi, The generalized tree quorum protocol: an efficient approach for managing replicated data, ACM Transactions on Database Systems (TODS), v.17 n.4, p.689-717, Dec. 1992
	Piotr Berman , J'anos Simon, Investigations of fault-tolerant networks of computers, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.66-77, May 02-04, 1988, Chicago, Illinois, United States
	Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991
	Louise E. Moser , P. M. Melliar-Smith , Vivek Agrawala, Necessary and sufficient conditions for broadcast consensus protocols, Distributed Computing, v.7 n.2, p.75-85, December 1993
	Özalp Babaoğlu, On the reliability of consensus-based fault-tolerant distributed computing systems, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.394-416, Nov. 1987
	Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994
	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
	T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987
	Keith Marzullo, Tolerating failures of continuous-valued sensors, ACM Transactions on Computer Systems (TOCS), v.8 n.4, p.284-304, Nov. 1990
	Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.59-70, August 1985, Minaki, Ontario, Canada
	Ulrich Schmid, Editorial, Real-Time Systems, v.12 n.2, p.119-122, March 1997
	Marcelo Moraes de Azevedo , Douglas M. Blough, Multistep Interactive Convergence: An Efficient Approach to the Fault-Tolerant Clock Synchronization of Large Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.9 n.12, p.1195-1212, December 1998
	John Havlicek, Computable obstructions to wait-free computability, Distributed Computing, v.13 n.2, p.59-83, April 2000
	Richard R. Brooks , S. Sitharama Iyengar, Robust Distributed Computing and Sensing Algorithm, Computer, v.29 n.6, p.53-60, June 1996
	Shlomi Dolev , Jennifer L. Welch, Self-stabilizing clock synchronization in the presence of Byzantine faults, Journal of the ACM (JACM), v.51 n.5, p.780-799, September 2004
	Thomas Clouqueur , Kewal K. Saluja , Parameswaran Ramanathan, Fault Tolerance in Collaborative Sensor Networks for Target Detection, IEEE Transactions on Computers, v.53 n.3, p.320-333, March 2004
	Rogério Drummond , Özalp Babaoğlu, Low-cost clock synchronization, Distributed Computing, v.6 n.4, p.193-203, July 1993
	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
	Yi Zhao , Farokh B. Bastani, A self-adjusting algorithm for byzantine agreement, Distributed Computing, v.5 n.4, p.219-226, April 1992
	Hermann Kopetz , Astrit Ademaj , Alexander Hanzlik, Combination of clock-state and clock-rate correction in fault-tolerant distributed systems, Real-Time Systems, v.33 n.1-3, p.139-173, July 2006
	Douglas Herbert , Vinaitheerthan Sundaram , Yung-Hsiang Lu , Saurabh Bagchi , Zhiyuan Li, Adaptive correctness monitoring for wireless sensor networks using hierarchical distributed run-time invariant checking, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.2 n.3, p.8-es, September 2007
	Ulrich Schmid, Editorial, Real-Time Systems, v.12 n.1, p.5-8, Jan. 1997
	Anatol Slissenko, A Logic Framework for Verification of Timed Algorithms, Fundamenta Informaticae, v.62 n.1, p.29-67, January 2004
	Divyakant Agrawal , Amr El Abbadi, The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data, Proceedings of the 16th International Conference on Very Large Data Bases, p.243-254, August 13-16, 1990
	Rex E. Gantenbein, An annotated bibliography of dependable distributed computing, ACM SIGOPS Operating Systems Review, v.26 n.2, p.60-81, April 1992
	Saurabh Ganeriwal , Christina Pöpper , Srdjan Čapkun , Mani B. Srivastava, Secure Time Synchronization in Sensor Networks, ACM Transactions on Information and System Security (TISSEC), v.11 n.4, p.1-35, July 2008