Implementing fault-tolerant services using the state machine approach: a tutorial

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementing fault-tolerant services using the state machine approach: a tutorial

Full text

Pdf (2.10 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 22 , Issue 4 (December 1990) table of contents

Pages: 299 - 319

Year of Publication: 1990

ISSN:0360-0300

Author

Fred B. Schneider

Cornell Univ., Ithaca, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 77, Downloads (12 Months): 647, Citation Count: 165

Additional Information:

abstract references cited by index terms review 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/98163.98167 What is a DOI?

ABSTRACT

The state machine approach is a general method for implementing fault-tolerant services in distributed systems. This paper reviews the approach and describes protocols for two different failure models—Byzantine and fail stop. Systems reconfiguration techniques for removing faulty components and integrating repaired components are also discussed.

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	Jacob Itzhack Aizikowitz, Designing distributed services using refinement mappings, Cornell University, Ithaca, NY, 1990
	2	BERNSTEIN, A. J. 1985. A loosely coupled system for reliably storing data. IEEE Trans. Softw. Eng. SE-11, 5 (May), 446-454.
	3	Kenneth P. Birman, Replication and fault-tolerance in the ISIS system, Proceedings of the tenth ACM symposium on Operating systems principles, p.79-86, December 1985, Orcas Island, Washington, United States
	4	Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
	5	CRISTIAN, F., AGHILI, H., STRONG, H. R., AND DOLEV, D. 1985. Atomic broadcast: From simple message diffusion to Byzantine agreement. In Proceedings of the 15th International Conference on Fault-tolerant Computing (Ann Arbor, Mich., June 1985), IEEE Computer Society.
	6	Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
	7	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	8	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 [doi>10.1145/5236.5243]
	9	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 [doi>10.1145/93385.93430]
	10	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	11	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]
	12	N. Hutchinson , L. Peterson, Design of the x-kernel, Symposium proceedings on Communications architectures and protocols, p.65-75, August 16-18, 1988, Stanford, California, United States
	13	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]
	14	LAMPORT, L. 1979b. The implementation of reliable distributed multiprocess systems. Comput. Networks 2, 95-114.
	15	Leslie Lamport, Using Time Instead of Timeout for Fault-Tolerant Distributed Systems., ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.254-280, April 1984 [doi>10.1145/2993.2994]
	16	LAMPORT, L. 1989. The part-time parliament. Tech. Rep. 49. Digital Equipment Corporation Systems Research Center, Palo Alto, Calif.
	17	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]
	18	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]
	19	Barbara Liskov , Rivka Ladin, Highly available distributed services and fault-tolerant distributed garbage collection, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.29-39, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10593]
	20	Luigi V. Mancini , Giuseppe Pappalardo, Towards a theory of replicated processing, Proceedings of a Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, p.175-192, September 1988, Warwick, United Kingdom
	21	MARZULLO, K. 1989. Implementing fault-tolerant sensors. Tech. Rep. TR 89-997. Computer Science Dept., Cornell Univ., Ithaca, New York.
	22	MARZULLO, K., AND SCHMUCK, F. 1988. Supplying high availability with a standard network file system. In Proceedings of the 8th International Conference on Distributed Computing Systems (San Jose, CA, June), IEEE Computer Society, pp. 447-455.
	23	Larry L. Peterson , Nick C. Buchholz , Richard D. Schlichting, Preserving and using context information in interprocess communication, ACM Transactions on Computer Systems (TOCS), v.7 n.3, p.217-246, Aug. 1989 [doi>10.1145/65000.65001]
	24	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 [doi>10.1145/58564.59294]
	25	Richard D. Schlichting , Fred B. Schneider, Fail-stop processors: an approach to designing fault-tolerant computing systems, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.222-238, August 1983 [doi>10.1145/357369.357371]
	26	SCHNEIDER, F. B. 1980. Ensuring consistency on a distributed database system by use of distributed semaphores. In Proceedings of International Symposium on Distributed Data Bases (Paris, France, Mar.), INRIA, pp. 183-189.
	27	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]
	28	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]
	29	M. W. Alford , J. P. Ansart , G. Hommel , L. Lamport , B. Liskov , G. P. Mullery , F. B. Schneider, Distributed systems: methods and tools for specification. An advanced course, Springer-Verlag New York, Inc., New York, NY, 1985
	30	SCHNEIDER, F. B. 1986. A paradigm for reliable clock synchronization. In Proceedings of the Advanced Seminar on Real-Time Local Area Networks (Bandol, France, Apr.), INRIA, pp. 85-104.
	31	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]
	32	SIEWIOREK, D. P., AND SWARZ, R. S. 1982. The Theory and Practice of Reliable System Design. Digital Press, Bedford, Mass.
	33	SKEEN, D. 1982. Crash recovery in a distributed database system. Ph.D. dissertation, Univ. of California at Berkeley, May.
	34	STRONG, H. R., AND DOLEV, D. 1983. Byzantine agreement. Intellectual Leverage for the Information Society, Digest of Papers. (Compcon 83, IEEE Computer Society, Mar.), IEEE Computer Society, pp. 77-82.
	35	WENSLEY, J., WENSKY, J. H., LAMPORT, L., GOLDBERG, J., GREEN, M. W., LEVITT, K. N., MELLIAR-SMITH, P. M., SHOSTAK, R. E., and WEINSTOCK, C. B. 1978. SIFT: Design and analysis of a fault-tolerant computer for aircraft control. Proc. IEEE 66, 10 (Oct.), 1240-1255.

CITED BY 165

	Felix C. Gärtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Computing Surveys (CSUR), v.31 n.1, p.1-26, March 1999
	Thomas Wolf, Fault tolerance in distributed Ada 95, ACM SIGAda Ada Letters, v.XVII n.5, p.106-110, Sept./Oct. 1997
	Luís Miguel Pinho , Francisco Vasques, Multi-μ: an Ada 95 based architecture for fault tolerance support of real-time systems, ACM SIGAda Ada Letters, v.XVIII n.6, p.52-60, Nov./Dec. 1998
	André Schiper , Michel Raynal, From group communication to transactions in distributed systems, Communications of the ACM, v.39 n.4, p.84-87, April 1996
	Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001
	Marcos Kawazoe Aguilera , Robert E. Strom, Efficient atomic broadcast using deterministic merge, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.209-218, July 16-19, 2000, Portland, Oregon, United States
	Dahlia Malkhi , Michael Reiter , Rebecca Wright, Probabilistic quorum systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.267-273, August 21-24, 1997, Santa Barbara, California, 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
	Maria Hybinette , Richard Fujimoto, Dynamic virtual logical processes, ACM SIGSIM Simulation Digest, v.28 n.1, p.100-107, July 1998
	Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998
	Michael Reiter, Distributing trust with the Rampart toolkit, Communications of the ACM, v.39 n.4, p.71-74, April 1996
	James H. Anderson, Lamport on mutual exclusion: 27 years of planting seeds, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.3-12, August 2001, Newport, Rhode Island, United States
	M. N. Nelson , M. Linton , S. Owicki, A highly available scalable ITV system, ACM SIGOPS Operating Systems Review, v.29 n.5, p.54-67, Dec. 3, 1995
	Alan Fekete , Nancy Lynch , Alex Shvartsman, Specifying and using a partitionable group communication service, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.53-62, August 21-24, 1997, Santa Barbara, California, United States
	Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998
	Gregory Chockler , Dahlia Malkhi, Active disk paxos with infinitely many processes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Idit Keidar , Danny Dolev, Efficient message ordering in dynamic networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.68-76, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Thomas C. Bressoud , Fred B. Schneider, Hypervisor-based fault tolerance, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.80-107, Feb. 1996
	Ajei S. Gopal , Kenneth J. Perry, Unifying self-stabilization and fault-tolerance, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.195-206, August 15-18, 1993, Ithaca, New York, United States
	Anish Arora , Paul C. Attie , E. Allen Emerson, Synthesis of fault-tolerant concurrent programs, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.173-182, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996
	Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993
	Jeremy B. Sussman , Keith Marzullo, Comparing primary-backup and state machines for crash failures, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.90, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	John A. Hine , Walt Yao , Jean Bacon , Ken Moody, An architecture for distributed OASIS services, IFIP/ACM International Conference on Distributed systems platforms, p.104-120, April 03-07, 2000, New York, New York, United States
	Michael K. Reiter, Secure agreement protocols: reliable and atomic group multicast in rampart, Proceedings of the 2nd ACM Conference on Computer and communications security, p.68-80, November 1994, Fairfax, Virginia, United States
	Shivakant Mishra , Lei Wu, An evaluation of flow control in group communication, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.571-587, Oct. 1998
	Udo Fritzke, Jr. , Philippe Ingels , Achour Mostefaoui , Michel Raynal, Consensus-based fault-tolerant total order multicast, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.146-156, February 2001
	Maria Hybinette , Richard Fujimoto, Cloning: a novel method for interactive parallel simulation, Proceedings of the 29th conference on Winter simulation, p.444-451, December 07-10, 1997, Atlanta, Georgia, United States
	Michael K. Reiter , Stuart G. Stubblebine, Path independence for authentication in large-scale systems, Proceedings of the 4th ACM conference on Computer and communications security, p.57-66, April 01-04, 1997, Zurich, Switzerland
	Michael K. Reiter , Kenneth P. Birman , Robbert van Renesse, A security architecture for fault-tolerant systems, ACM Transactions on Computer Systems (TOCS), v.12 n.4, p.340-371, Nov. 1994
	Nina T. Bhatti , Matti A. Hiltunen , Richard D. Schlichting , Wanda Chiu, Coyote: a system for constructing fine-grain configurable communication services, ACM Transactions on Computer Systems (TOCS), v.16 n.4, p.321-366, Nov. 1998
	Haifeng Yu , Amin Vahdat, Design and evaluation of a conit-based continuous consistency model for replicated services, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.239-282, August 2002
	Michael K. Reiter , Kenneth P. Birman, How to securely replicate services, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.986-1009, May 1994
	Michael K. Reiter , Matthew K. Franklin , John B. Lacy , Rebecca N. Wright, The Ω key management service, Proceedings of the 3rd ACM conference on Computer and communications security, p.38-47, March 14-15, 1996, New Delhi, India
	David Powell, Distributed Fault Tolerance: Lessons from Delta-4, IEEE Micro, v.14 n.1, p.36-47, February 1994
	Marta Patiño-Martínez , Ricardo Jiménez-Peris , Sergio Arévalo, Exception handling and resolution for transactional object groups, Advances in exception handling techniques, Springer-Verlag New York, Inc., New York, NY, 2001
	Idit Keidar , Sergio Rajsbaum, On the cost of fault-tolerant consensus when there are no faults: preliminary version, ACM SIGACT News, v.32 n.2, June 2001
	W. L. Yeung , S. A. Schneider, Design and Verification of Distributed Recovery Blocks with CSP, Formal Methods in System Design, v.22 n.3, p.225-248, May 2003
	Roy Friedman , Achour Mostefaoui , Michel Raynal, A weakest failure detector-based asynchronous consensus protocol for f < n, Information Processing Letters, v.90 n.1, p.39-46, 15 April 2004
	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
	Fathi Tenzakhti , Khaled Day , M. Ould-Khaoua, Replication algorithms for the World-Wide Web, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.10, p.591-605, October 2004
	F. Pedone , A. Schiper, Handling message semantics with Generic Broadcast protocols, Distributed Computing, v.15 n.2, p.97-107, April 2002
	S. K. Shrivastava , D. L. McCue, Structuring Fault-Tolerant Object Systems for Modularity in a Distributed Environment, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.421-432, April 1994
	T. C. Bressoud , F. B. Schneider, Hypervisor-based fault tolerance, ACM SIGOPS Operating Systems Review, v.29 n.5, p.1-11, Dec. 3, 1995
	Carlos Almeida , Brad Glade , Keith Marzullo , Robbert van Renesse, High availability in a real-time system, Proceedings of the 5th workshop on ACM SIGOPS European workshop: Models and paradigms for distributed systems structuring, September 21-23, 1992, Mont Saint-Michel, France
	Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
	Rodrigo Rodrigues , Miguel Castro , Barbara Liskov, BASE: using abstraction to improve fault tolerance, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
	A. P. Atlee , H. Gannon, Specifying and Verifying Requirements of Real-Time Systems, IEEE Transactions on Software Engineering, v.19 n.1, p.41-55, January 1993
	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
	Jian Yin , Jean-Philippe Martin , Arun Venkataramani , Lorenzo Alvisi , Mike Dahlin, Separating agreement from execution for byzantine fault tolerant services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
	Jeremy Sussman , Keith Marzullo, The Bancomat problem: an example of resource allocation in a partitionable asynchronous system, Theoretical Computer Science, v.291 n.1, p.103-131, 4 January 2003
	Ashish Mehra , Jennifer Rexford , Farnam Jahanian, Design and Evaluation of a Window-Consistent Replication Service, IEEE Transactions on Computers, v.46 n.9, p.986-996, September 1997
	Francisco V. Brasileiro , Paul Devadoss Ezhilchelvan , Santosh K. Shrivastava , Neil A. Speirs , S. Tao, Implementing Fail-Silent Nodes for Distributed Systems, IEEE Transactions on Computers, v.45 n.11, p.1226-1238, November 1996
	Alberto Bartoli, Implementing a replicated service with group communication, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.8, p.493-519, August 2004
	Paul C. Attie , Anish Arora , E. Allen Emerson, Synthesis of fault-tolerant concurrent programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.1, p.125-185, January 2004
	Mehul A. Shah , Joseph M. Hellerstein , Eric Brewer, Highly available, fault-tolerant, parallel dataflows, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	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
	Wanlei Zhou , Li Wang , Weijia Jia, An analysis of update ordering in distributed replication systems, Future Generation Computer Systems, v.20 n.4, p.565-590, May 2004
	Woei-Jiunn Tsaur , Shi-Jinn Horng, Auditing Causal Relationships of Group Multicast Communications in Group-Oriented Distributed Systems, The Journal of Supercomputing, v.18 n.1, p.25-45, Jan. 2001
	Robert Miller , Anand Tripathi, The Guardian Model and Primitives for Exception Handling in Distributed Systems, IEEE Transactions on Software Engineering, v.30 n.12, p.1008-1022, December 2004
	Swaminathan Sivasubramanian , Michal Szymaniak , Guillaume Pierre , Maarten van Steen, Replication for web hosting systems, ACM Computing Surveys (CSUR), v.36 n.3, p.291-334, September 2004
	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
	Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000
	Hengming Zou , Farnam Jahanian, A Real-Time Primary-Backup Replication Service, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.533-548, June 1999
	Christos T. Karamanolis , Jeffrey N. Magee, Client-Access Protocols for Replicated Services, IEEE Transactions on Software Engineering, v.25 n.1, p.3-21, January 1999
	Anish Arora , Sandeep S. Kulkarni, Designing Masking Fault-Tolerance via Nonmasking Fault-Tolerance, IEEE Transactions on Software Engineering, v.24 n.6, p.435-450, June 1998
	Stefan Poledna , Alan Burns , Andy Wellings , Peter Barrett, Replica Determinism and Flexible Scheduling in Hard Real-Time Dependable Systems, IEEE Transactions on Computers, v.49 n.2, p.100-111, February 2000
	Michael K. Reiter, A Secure Group Membership Protocol, IEEE Transactions on Software Engineering, v.22 n.1, p.31-42, January 1996
	Matthias Wiesmann , Andre Schiper, Comparison of Database Replication Techniques Based on Total Order Broadcast, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.551-566, April 2005
	Sriram Rao , Lorenzo Alvisi , Harrick M. Vin, The Cost of Recovery in Message Logging Protocols, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.160-173, March 2000
	Geographically Distributed System for Catastrophic Recovery, Proceedings of the 16th USENIX conference on System administration, November 03-08, 2002, Philadelphia, PA
	Partha Pal , Franklin Webber , Richard Schantz, Survival by defense-enabling, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico
	Shivakant Mishra , Lan Fei , Xiao Lin , Guming Xing, On Group Communication Support in CORBA, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.193-208, February 2001
	Fernando Pedone , Rachid Guerraoui , André Schiper, The Database State Machine Approach, Distributed and Parallel Databases, v.14 n.1, p.71-98, July 2003
	Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Vassos Hadzilacos , Petr Kouznetsov , Sam Toueg, The weakest failure detectors to solve certain fundamental problems in distributed computing, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Haifeng Yu , Amin Vahdat, Consistent and automatic replica regeneration, ACM Transactions on Storage (TOS), v.1 n.1, p.3-37, February 2005
	Eli Gafni , Leslie Lamport, Disk Paxos, Distributed Computing, v.16 n.1, p.1-20, February 2003
	Deepti Srivastava , Priya Narasimhan, Architectural support for mode-driven fault tolerance in distributed applications, ACM SIGSOFT Software Engineering Notes, v.30 n.4, July 2005
	Fred B. Schneider , Lidong Zhou, Implementing Trustworthy Services Using Replicated State Machines, IEEE Security and Privacy, v.3 n.5, p.34-43, September 2005
	Roy Friedman , Achour Mostefaoui , Michel Raynal, Simple and Efficient Oracle-Based Consensus Protocols for Asynchronous Byzantine Systems, IEEE Transactions on Dependable and Secure Computing, v.2 n.1, p.46-56, January 2005
	Abdelkrim Beloued , Jean-Marie Gilliot , Maria-Teresa Segarra , Françoise André, Dynamic data replication and consistency in mobile environments, Proceedings of the 2nd international doctoral symposium on Middleware, p.1-5, November 28-December 02, 2005, Grenoble, France
	Remzi H. Arpaci-Dusseau, Run-time adaptation in river, ACM Transactions on Computer Systems (TOCS), v.21 n.1, p.36-86, February 2003
	Michael Abd-El-Malek , Gregory R. Ganger , Garth R. Goodson , Michael K. Reiter , Jay J. Wylie, Fault-scalable Byzantine fault-tolerant services, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
	Mahesh Kallahalla , Erik Riedel , Ram Swaminathan , Qian Wang , Kevin Fu, Plutus: Scalable Secure File Sharing on Untrusted Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
	Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
	Vijayan Prabhakaran , Lakshmi N. Bairavasundaram , Nitin Agrawal , Haryadi S. Gunawi , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, IRON file systems, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
	Luís Miguel Pinho , Francisco Vasques , Andy Wellings, Replication Management in Reliable Real-Time Systems, Real-Time Systems, v.26 n.3, p.261-296, April 2004
	Miguel Castro , Rodrigo Rodrigues , Barbara Liskov, BASE: Using abstraction to improve fault tolerance, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.236-269, August 2003
	David Edward Bakken , Richard D. Schlichting, Supporting Fault-Tolerant Parallel Programming in Linda, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.287-302, March 1995
	Michael K. Reiter , Stuart G. Stubblebine, Resilient Authentication Using Path Independence, IEEE Transactions on Computers, v.47 n.12, p.1351-1362, December 1998
	Gregory Chockler , Dahlia Malkhi, Active disk Paxos with infinitely many processes, Distributed Computing, v.18 n.1, p.73-84, July 2005
	Maria Hybinette , Richard M. Fujimoto, Cloning parallel simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.4, p.378-407, October 2001
	Santosh K. Shrivastava , Paul D. Ezhilchelvan , Neil A. Speirs , Sha Tao , Alan Tully, Principal Features of the VOLTAN Family of Reliable Node Architectures for Distributed Systems, IEEE Transactions on Computers, v.41 n.5, p.542-549, May 1992
	Richard D. Schlichting , Vicraj T. Thomas, Programming Language Support for Writing Fault-Tolerant Distributed Software, IEEE Transactions on Computers, v.44 n.2, p.203-212, February 1995
	Tudor Dumitraş , Priya Narasimhan, Got predictability?: experiences with fault-tolerant middleware, Proceedings of the 8th ACM/IFIP/USENIX international conference on Middleware, November 26-30, 2007, Newport Beach, California
	Vincenzo De Florio , Chris Blondia, A survey of linguistic structures for application-level fault tolerance, ACM Computing Surveys (CSUR), v.40 n.2, p.1-37, April 2008
	Robbert van Renesse, Causal controversy at Le Mont St.-Michel, ACM SIGOPS Operating Systems Review, v.27 n.2, p.44-53, April 1993
	Carlos Almeida , Brad Glade , Keith Marzullo, High availability in a real-time system, ACM SIGOPS Operating Systems Review, v.27 n.2, p.82-87, April 1993
	Soila Pertet , Rajeev Gandhi , Priya Narasimhan, Fingerpointing correlated failures in replicated systems, Proceedings of the 2nd USENIX workshop on Tackling computer systems problems with machine learning techniques, p.1-6, April 10, 2007, Cambridge, MA
	Maciej Koutny , Giuseppe Pappalardo, Behaviour Abstraction for Communicating Sequential Processes, Fundamenta Informaticae, v.48 n.1, p.21-54, January 2001
	Alysson Neves Bessani , Joni da Silva Fraga , Lau Cheuk Lung, BTS: a Byzantine fault-tolerant tuple space, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Specifying and using a partitionable group communication service, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.171-216, May 2001
	Chanathip Namprempre , Jeremy Sussman , Keith Marzullo, Implementing causal logging using OrbixWeb interception, Proceedings of the 5th conference on USENIX Conference on Object-Oriented Technologies & Systems, p.5-5, May 03-07, 1999, San Diego, California
	Arash Baratloo , P. Emerald Chung , Yennun Huang , Sampath Rangarajan , Shalini Yajnik, Filterfresh: hot replication of java RMI server objects, Proceedings of the 4th conference on USENIX Conference on Object-Oriented Technologies and Systems (COOTS), p.5-5, April 27-30, 1998, Santa Fe, New Mexico
	Jorge Salas , Francisco Perez-Sorrosal , Marta Patiño-Martínez , Ricardo Jiménez-Peris, WS-replication: a framework for highly available web services, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
	Aydan R. Yumerefendi , Jeffrey S. Chase, Trust but verify: accountability for network services, Proceedings of the 11th workshop on ACM SIGOPS European workshop: beyond the PC, p.37-es, September 19-22, 2004, Leuven, Belgium
	Bogdan C. Popescu , Bruno Crispo , Andrew S. Tanenbaum , Arno Bakker, Design and implementation of a secure wide-area object middleware, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.10, p.2484-2513, July, 2007
	Sameh Elnikety , Steven Dropsho , Fernando Pedone, Tashkent: uniting durability with transaction ordering for high-performance scalable database replication, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
	Jacob R. Lorch , Atul Adya , William J. Bolosky , Ronnie Chaiken , John R. Douceur , Jon Howell, The SMART way to migrate replicated stateful services, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
	Flavio Junqueira , Ranjita Bhagwan , Keith Marzullo , Stefan Savage , Geoffrey M. Voelker, The phoenix recovery system: rebuilding from the ashes of an internet catastrophe, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.13-13, May 18-21, 2003, Lihue, Hawaii
	Joseph G. Slember , Priya Narasimhan, Static analysis meets distributed fault-tolerance: enabling state-machine replication with nondeterminism, Proceedings of the 2nd conference on Hot Topics in System Dependability, p.2-2, November 08, 2006, Seattle, WA
	Robbert van Renesse , Fred B. Schneider, Chain replication for supporting high throughput and availability, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.7-7, December 06-08, 2004, San Francisco, CA
	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
	Bogdan C. Popescu , Bruno Crispo , Andrew S. Tanenbaum, Secure data replication over untrusted hosts, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.21-21, May 18-21, 2003, Lihue, Hawaii
	Miguel Castro , Barbara Liskov, Proactive recovery in a Byzantine-fault-tolerant system, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.19-19, October 22-25, 2000, San Diego, California
	Haifeng Yu , Amin Vahdat, Consistent and automatic replica regeneration, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.24-24, March 29-31, 2004, San Francisco, California
	Aydan R. Yumerefendi , Jeffrey S. Chase, Strong accountability for network storage, ACM Transactions on Storage (TOS), v.3 n.3, p.11-es, October 2007
	Peter T. Liu , Brian Smith , Lawrence Rowe, Tcl-DP name server, Proceedings of the 3rd conference on USENIX Third Annual Tcl/Tk Workshop, p.1-1, July 06-08, 1995, Toronto, Canada
	Naftaly H. Minsky , Victoria Ungureanu, Unified support for heterogeneous security policies in distributed systems, Proceedings of the 7th conference on USENIX Security Symposium, 1998, p.10-10, January 26-29, 1998, San Antonio, Texas
	HariGovind Ramasamy , Mouna Seri , William H. Sanders, The coBFIT toolkit, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Joe Meehean , Miron Livny, Environmentally responsible middleware:: an altruistic behavior model for distributed middleware components, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA
	Sameh Elnikety , Steven Dropsho , Willy Zwaenepoel, Tashkent+: memory-aware load balancing and update filtering in replicated databases, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
	Meng Yu , Peng Liu , Wanyu Zang, Specifying and using intrusion masking models to process distributed operations, Journal of Computer Security, v.13 n.4, p.623-658, July 2005
	Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin , Allen Clement , Edmund Wong, Zyzzyva: speculative byzantine fault tolerance, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Aldri L. Dos Santos , Elias P. Duarte, Jr. , Glenn M. Keeni, Reliable Distributed Network Management by Replication, Journal of Network and Systems Management, v.12 n.2, p.191-213, June 2004
	Hagit Attiya , Keren Censor, Tight bounds for asynchronous randomized consensus, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Arno Bakker , Maarten van Steen , Andrew S. Tanenbaum, Replicated invocations in wide-area systems, Proceedings of the 8th ACM SIGOPS European workshop on Support for composing distributed applications, p.130-137, September 1998, Sintra, Portugal
	Mark Hayden, Distributed communication in ML, Journal of Functional Programming, v.10 n.1, p.91-120, January 2000
	Tushar D. Chandra , Robert Griesemer , Joshua Redstone, Paxos made live: an engineering perspective, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, p.398-407, August 12-15, 2007, Portland, Oregon, USA
	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
	Udo Fritzke , Philippe Ingels , Achour Mostefaoui , Michel Raynal, Consensus-Based Fault-Tolerant Total Order Multicast, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.147-156, February 2001
	Jean-Philippe Martin , Lorenzo Alvisi, Fast Byzantine Consensus, IEEE Transactions on Dependable and Secure Computing, v.3 n.3, p.202-215, July 2006
	Andreas Haeberlen , Petr Kouznetsov , Peter Druschel, PeerReview: practical accountability for distributed systems, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Fernando Pedone , Svend Frølund, Pronto: High availability for standard off-the-shelf databases, Journal of Parallel and Distributed Computing, v.68 n.2, p.150-164, February, 2008
	Kiron Vijayasankar , Gopalan Sivathanu , Swaminathan Sundararaman , Erez Zadok, Exploiting type-awareness in a self-recovering disk, Proceedings of the 2007 ACM workshop on Storage security and survivability, October 29-29, 2007, Alexandria, Virginia, USA
	Byung-Gon Chun , Petros Maniatis , Scott Shenker , John Kubiatowicz, Attested append-only memory: making adversaries stick to their word, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Hiroshi Horii , Hayato Yamana, Optimistic transactional active replication, Proceedings of the 2nd international conference on Ubiquitous information management and communication, January 31-February 01, 2008, Suwon, Korea
	Alysson Neves Bessani , Eduardo Pelison Alchieri , Miguel Correia , Joni Silva Fraga, DepSpace: a byzantine fault-tolerant coordination service, ACM SIGOPS Operating Systems Review, v.42 n.4, May 2008
	James Cowling , Daniel Myers , Barbara Liskov , Rodrigo Rodrigues , Liuba Shrira, HQ replication: a hybrid quorum protocol for byzantine fault tolerance, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
	Vaidė Zuikevičiūtė , Fernando Pedone, Conflict-aware load-balancing techniques for database replication, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Soontaree Tanaraksiritavorn , Shivakant Mishra, Flexible intrusion tolerant voting architecture, Proceedings of the 2007 ACM workshop on Scalable trusted computing, November 02-02, 2007, Alexandria, Virginia, USA
	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
	Huaigu Wu , Bettina Kemme, Showing correctness of a replication algorithm in a component based system, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	Thomas Repantis , Vana Kalogeraki, Replica placement for high availability in distributed stream processing systems, Proceedings of the second international conference on Distributed event-based systems, July 01-04, 2008, Rome, Italy
	Roy Friedman , Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Asynchronous Agreement and Its Relation with Error-Correcting Codes, IEEE Transactions on Computers, v.56 n.7, p.865-875, July 2007
	HariGovind V. Ramasamy , Adnan Agbaria , William H. Sanders, A Parsimonious Approach for Obtaining Resource-Efficient and Trustworthy Execution, IEEE Transactions on Dependable and Secure Computing, v.4 n.1, p.1-17, January 2007
	Laurent George , Pascale Minet, Preserving the consistency of distributed objects with real-time transactions, Proceedings of the 8th international conference on New technologies in distributed systems, June 23-27, 2008, Lyon, France
	Hagit Attiya , Keren Censor, Tight bounds for asynchronous randomized consensus, Journal of the ACM (JACM), v.55 n.5, p.1-26, October 2008
	YongChul Kwon , Magdalena Balazinska , Albert Greenberg, Fault-tolerant stream processing using a distributed, replicated file system, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	James Aspnes , Hagit Attiya , Keren Censor, Randomized consensus in expected O(n log n) individual work, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Miguel Correia , Alysson Neves Bessani , Paulo Veríssimo, Research note: On Byzantine generals with alternative plans, Journal of Parallel and Distributed Computing, v.68 n.9, p.1291-1296, September, 2008
	Gregory Chockler , Seth Gilbert , Nancy Lynch, Virtual infrastructure for collision-prone wireless networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Rachel Akimana , Olivier Markowitch, Data and code integrity in Grid environments, Proceedings of the 6th WSEAS International Conference on Simulation, Modelling and Optimization, p.677-682, September 22-24, 2006, Lisbon, Portugal
	Gabriel L. Zenarosa , Soumya Simanta, Experiences in engineering active replication into a traditional three-tiered client-server system, Proceedings of the 2008 RISE/EFTS Joint International Workshop on Software Engineering for Resilient Systems, November 17-19, 2008, Newcastle upon Tyne, United Kingdom
	Alain Girault , írik Saule , Denis Trystram, Reliability versus performance for critical applications, Journal of Parallel and Distributed Computing, v.69 n.3, p.326-336, March, 2009
	Joseph Slember , Priya Narasimhan, Living with nondeterminism in replicated middleware applications, Proceedings of the ACM/IFIP/USENIX 2006 International Conference on Middleware, November 01-01, 2006, Melbourne, Australia
	Benjamin Reed , Flavio P. Junqueira, A simple totally ordered broadcast protocol, Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, September 15-17, 2008, Yorktown Heights, New York
	Jonathan Kirsch , Yair Amir, Paxos for System Builders: an overview, Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, September 15-17, 2008, Yorktown Heights, New York
	Wenbing Zhao, Design and implementation of a Byzantine fault tolerance framework for Web services, Journal of Systems and Software, v.82 n.6, p.1004-1015, June, 2009
	Christopher Stewart , Kai Shen , Arun Iyengar , Jian Yin, Configuration-space performance anomaly depiction, Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, September 15-17, 2008, Yorktown Heights, New York
	Marco Serafini , Neeraj Suri, Reducing the costs of large-scale BFT replication, Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, September 15-17, 2008, Yorktown Heights, New York
	Maysam Yabandeh , Nikola Knezevic , Dejan Kostic , Viktor Kuncak, CrystalBall: predicting and preventing inconsistencies in deployed distributed systems, Proceedings of the 6th USENIX symposium on Networked systems design and implementation, p.229-244, April 22-24, 2009, Boston, Massachusetts
	Benjamin Wester , James Cowling , Edmund B. Nightingale , Peter M. Chen , Jason Flinn , Barbara Liskov, Tolerating latency in replicated state machines through client speculation, Proceedings of the 6th USENIX symposium on Networked systems design and implementation, p.245-260, April 22-24, 2009, Boston, Massachusetts
	Marcos Kawazoe Aguilera , Idit Keidar , Dahlia Malkhi , Alexander Shraer, Dynamic atomic storage without consensus, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada

INDEX TERMS

Primary Classification:
C. Computer Systems Organization
C.4 PERFORMANCE OF SYSTEMS
Subjects: Reliability, availability, and serviceability

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

D. Software
D.4 OPERATING SYSTEMS
D.4.5 Reliability
Subjects: Fault-tolerance
D.4.7 Organization and Design
Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Design, Performance, Reliability

REVIEW

"Valentin Cristea : Reviewer"

Distributed software structured in terms of clients and servers is considered. Replicas of a single server are executed on separate processors of a distributed system, and protocols coordinate client interactions with these replicas. The paper more...

Collaborative Colleagues:

Fred B. Schneider: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player