Using Time Instead of Timeout for Fault-Tolerant Distributed Systems.

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Using Time Instead of Timeout for Fault-Tolerant Distributed Systems.

Full text

Pdf (1.81 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 6 , Issue 2 (April 1984) table of contents

Pages: 254 - 280

Year of Publication: 1984

ISSN:0164-0925

Author

Leslie Lamport

SRI International

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 112, Citation Count: 42

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/2993.2994 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.

	1	DOLEV, D. The Byzantine Generals strike again. J. Algorithms 3, 1 (1982), 14-30.
	2	D. DOLEV AND H.R. STRONG. Authenticated algorithms for Byzantine agreement. Rep. RJ3416(40682), IBM Research Laboratory, San Jose, Calif., Mar. 1982. SIAM J. Comput. To be published.
	3	K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
	4	FISCHER, M., AND LYNCH, N. A lower bound for the time to assure interactive consistency. In{. Proc. Lett. 14, 4 (1982), 183-186.
	5	M. J. Fischer , N. A. Lynch , M. S. Paterson, IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS, Massachusetts Institute of Technology, Cambridge, MA, 1982
	6	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	7	LAMPORT, L. The implementation of reliable distributed multiprocess systems. Comput. Networks 2 ( 1978 ), 95-114.
	8	LAMPORT, L. AND MELLIAR-SMITH, P.M. Synchronizing clocks in the presence of faults (submitted for publication).
	9	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]
	10	LYNCH, N.A., FISCHER, M.J. ANO FOWLER, R. A simple and efficient Byzantine Generals algorithm. In Proceedings o/2nd Symposium on Reliability in Distributed So{tware and Database Systems (Pittsburgh, Pa., July 1982).
	11	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]
	12	Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982 [doi>10.1145/357162.357163]
	13	Fred B. Schneider , David Gries , Richard D. Schlichting, Fault-tolerant broadcasts, Science of Computer Programming, v.4 n.1, p.1-15, April 1984 [doi>10.1016/0167-6423(84)90009-1]
	14	WENSLEY, J.H., LAMPORT, L., GOLDBERG, J., GREEN, M.W., LEVITT, K.N., MILLIAR-SMITH, P.M., SHOSTAK, R.E., WEINSTOCK, C.B., ANO BERSON, D. SIFT: Design and analysis of a fault-tolerant computer for aircraft control. Proc. IEEE 66, 10 (Oct. 1978), 1240-1254.

CITED BY 42

	Ajei Gopal , Ray Strong , Sam Toueg , Flaviu Cristian, Early-delivery atomic broadcast, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.297-309, August 22-24, 1990, Quebec City, Quebec, Canada
	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
	Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990
	C. S. Hsieh , R. A. Mata, Decentralized mutual exclusion in the presence of link failures, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.195-203, February 21-23, 1989, Louisville, Kentucky
	B Walter, A turnable protocol for symmetric surveillance in distributed systems, ACM SIGCOMM Computer Communication Review, v.16 n.3, p.368-376, Aug. 5, 1986
	Danny Dolev , Ruediger Reischuk , H. Raymond Strong, Early stopping in Byzantine agreement, Journal of the ACM (JACM), v.37 n.4, p.720-741, Oct. 1990
	Andrew S. Tanenbaum , Robbert Van Renesse, Distributed operating systems, ACM Computing Surveys (CSUR), v.17 n.4, p.419-470, Dec. 1985
	Cynthia Dwork , Dale Skeen, The inherent cost of nonblocking commitment, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.1-11, August 17-19, 1983, Montreal, Quebec, Canada
	K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, ACM SIGOPS Operating Systems Review, v.21 n.5, p.123-138, Nov. 1987
	Mark Baugher, Media transports and distributed multimedia flows, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.1132-1143, March 1992, Kansas City, Missouri, United States
	Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998
	Frank M. Pittelli , Hector Garcia-Molina, Reliable scheduling in a TMR database system, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.25-60, Feb. 1989
	Ö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
	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
	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
	Danny Dolev , Joseph Y. Halpern , Barbara Simons , Ray Strong, Dynamic fault-tolerant clock synchronization, Journal of the ACM (JACM), v.42 n.1, p.143-185, Jan. 1995
	Keith Marzullo, Tolerating failures of continuous-valued sensors, ACM Transactions on Computer Systems (TOCS), v.8 n.4, p.284-304, Nov. 1990
	Miguel Castro , Barbara Liskov, Practical byzantine fault tolerance and proactive recovery, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.398-461, November 2002
	Flavin Cristian, Understanding fault-tolerant distributed systems, Communications of the ACM, v.34 n.2, p.56-78, Feb. 1991
	Brett D. Fleisch, Fault-tolerance support in distributed systems, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-6, September 03-05, 1990, Bologna, Italy
	Hector Garcia Molina , Frank Pittelli , Susan Davidson, Applications of Byzantine agreement in database systems, ACM Transactions on Database Systems (TODS), v.11 n.1, p.27-47, March 1986
	Hermann Kopetz , Günter Grünsteidl, TTP-A Protocol for Fault-Tolerant Real-Time Systems, Computer, v.27 n.1, p.14-23, January 1994
	Ajei Gopal , Sam Toueg, Inconsistency and contamination (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.257-272, August 19-21, 1991, Montreal, Quebec, Canada
	Seyed H. Hosseini , Nizar Jamal, Efficient Distributed Algorithms for Self Testing of Multiple Processor Systems, IEEE Transactions on Computers, v.41 n.11, p.1397-1409, November 1992
	Gianluigi Alari , Augusto Ciuffoletti, Implementing a Probabilistic Clock Synchronization Algorithm, Real-Time Systems, v.13 n.1, p.25-46, July 1997
	Parameswaran Ramanathan , Kang G. Shin, Use of Common Time Base for Checkpointing and Rollback Recovery in a Distributed System, IEEE Transactions on Software Engineering, v.19 n.6, p.571-583, June 1993
	Leslie Lamport , P M Melliar Smith, Byzantine clock synchronization, ACM SIGOPS Operating Systems Review, v.20 n.3, p.10-16, July, 1986
	Paul D. Ezhilchelvan , Francisco V. Brasileiro , Neil A. Speirs, A Timeout-Based Message Ordering Protocol for a Lightweight Software Implementation of TMR Systems, IEEE Transactions on Parallel and Distributed Systems, v.15 n.1, p.53-65, January 2004
	Scott D. Stoller, Detecting global predicates in distributed systems with clocks, Distributed Computing, v.13 n.2, p.85-98, April 2000
	Giacomo Bucci , Enrico Vicario, Compositional Validation of Time-Critical Systems Using Communicating Time Petri Nets, IEEE Transactions on Software Engineering, v.21 n.12, p.969-992, December 1995
	Xavier Défago , André Schiper , Péter Urbán, Total order broadcast and multicast algorithms: Taxonomy and survey, ACM Computing Surveys (CSUR), v.36 n.4, p.372-421, December 2004
	P. Ramanathan , Dilip D. Kandlur , Kang G. Shin, Hardware-Assisted Software Clock Synchronization for Homogeneous Distributed Systems, IEEE Transactions on Computers, v.39 n.4, p.514-524, April 1990
	R. Corin , S. Etalle , P. H. Hartel , A. Mader, Timed model checking of security protocols, Proceedings of the 2004 ACM workshop on Formal methods in security engineering, October 29-29, 2004, Washington DC, USA
	Barbara Liskov, Practical uses of synchronized clocks in distributed systems, Distributed Computing, v.6 n.4, p.211-219, July 1993
	Kang G. Shin, HARTS: A Distributed Real-Time Architecture, Computer, v.24 n.5, p.25-35, May 1991
	K. Lakshman , Giri Kuthethoor , Raj Yavatkar, Design and implementation of a multimedia protocol suite in a BSD Unix Kernel, Proceedings of the USENIX Summer 1993 Technical Conference on Summer technical conference, p.1-24, June 21-25, 1993, Cincinnati, Ohio
	Andreas Haeberlen , Petr Kouznetsov , Peter Druschel, The case for Byzantine fault detection, Proceedings of the 2nd conference on Hot Topics in System Dependability, p.5-5, November 08, 2006, Seattle, WA
	John Dunagan , Nicholas J. A. Harvey , Michael B. Jones , Dejan Kostić , Marvin Theimer , Alec Wolman, FUSE: lightweight guaranteed distributed failure notification, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.11-11, December 06-08, 2004, San Francisco, CA
	Chi Ho , Robbert van Renesse , Mark Bickford , Danny Dolev, Nysiad: practical protocol transformation to tolerate Byzantine failures, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.175-188, April 16-18, 2008, San Francisco, California
	Andreas Haeberlen , Petr Kouznetsov , Peter Druschel, PeerReview: practical accountability for distributed systems, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	R. Corin , S. Etalle , P. H. Hartel , A. Mader, Timed analysis of security protocols, Journal of Computer Security, v.15 n.6, p.619-645, December 2007
	Ramakrishna Kotla , Allen Clement , Edmund Wong , Lorenzo Alvisi , Mike Dahlin, Zyzzyva: speculative Byzantine fault tolerance, Communications of the ACM, v.51 n.11, November 2008