Reliable communication in the presence of failures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reliable communication in the presence of failures

Full text

Pdf (2.62 MB)

Source

ACM Transactions on Computer Systems (TOCS) archive
Volume 5 , Issue 1 (February 1987) table of contents

Pages: 47 - 76

Year of Publication: 1987

ISSN:0734-2071

Authors

Kenneth P. Birman	Cornell Univ., Ithaca, NY
Thomas A. Joseph	Cornell Univ., Ithaca, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 210, Citation Count: 155

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/7351.7478 What is a DOI?

ABSTRACT

The design and correctness of a communication facility for a distributed computer system are reported on. The facility provides support for fault-tolerant process groups in the form of a family of reliable multicast protocols that can be used in both local- and wide-area networks. These protocols attain high levels of concurrency, while respecting application-specific delivery ordering constraints, and have varying cost and performance that depend on the degree of ordering desired. In particular, a protocol that enforces causal delivery orderings is introduced and shown to be a valuable alternative to conventional asynchronous communication protocols. The facility also ensures that the processes belonging to a fault-tolerant process group will observe consistent orderings of events affecting the group as a whole, including process failures, recoveries, migration, and dynamic changes to group properties like member rankings. A review of several uses for the protocols in the ISIS system, which supports fault-tolerant resilient objects and bulletin boards, illustrates the significant simplification of higher level algorithms made possible by our approach.

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	Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
	2	Kenneth P. Birman, Replication and fault-tolerance in the ISIS system, ACM SIGOPS Operating Systems Review, v.19 n.5, p.79-86, Dec. 1-4, 1985
	3	Kenneth P. Birman , Thomas A. Joseph , Frank B. Schmuck , Patrick Stephenson, Programming with Shared Bulletin Boards in Asynchronus Distributed Systems, Cornell University, Ithaca, NY, 1986
	4	Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
	5	David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
	6	Eric C. Cooper, Replicated distributed programs, ACM SIGOPS Operating Systems Review, v.19 n.5, p.63-78, Dec. 1-4, 1985
	7	CRISTIAN, F., AGHILI, H., STRONG, R., AND DOLEV, D. Atomic broadcast: From simple message diffusion to Byzantine agreement. IBM Tech. Rep. RJ 4540 (48668), Oct. 1984.
	8	Amr El Abbadi , Sam Toueg, Availability in partitioned replicated databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.240-251, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15418]
	9	Amr El Abbadi , Dale Skeen , Flaviu Cristian, An efficient, fault-tolerant protocol for replicated data management, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.215-229, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325443]
	10	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	11	Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588061]
	12	Thomas A. Joseph , Kenneth P. Birman, Low cost management of replicated data in fault-tolerant distributed systems, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.54-70, Feb. 1986 [doi>10.1145/6306.6309]
	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	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]
	15	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]
	16	SKEEN, D. Crash recovery in distributed database systems. Ph.D. dissertation, Dept. of Electrical Engineering and Computer Science, Univ. of California, Berkeley, 1980.
	17	Dale Skeen, Determining the last process to fail, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.15-30, Feb. 1985 [doi>10.1145/214451.214453]

CITED BY 155

	Jeffery Westbrook , Lenore Zuck, Adaptive algorithms for PASO systems, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.264-273, August 14-17, 1994, Los Angeles, California, United States
	K. Ravindran , K. K. Ramakrishnan, A naming system for feature-based service specification in distributed operating systems, Proceedings of the 1991 ACM SIGSMALL/PC symposium on Small systems, p.83-92, June 12-14, 1991, Toronto, Ontario, Canada
	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
	Bala Rajagopalan, Reliability and scaling issues in multicast communication, ACM SIGCOMM Computer Communication Review, v.22 n.4, p.188-198, Oct. 1992
	Praskash Panangaden , Kim Taylor, Concurrent common knowledge: a new definition of agreement for asynchronous systems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.197-209, August 15-17, 1988, Toronto, Ontario, Canada
	P. Veríssimo , L. Rodrigues , M. Baptista, AMp: a highly parallel atomic multicast protocol, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.83-93, Sep. 1989
	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
	Aomar Maddi , Fodil Dahamni, An efficient algorithm for causal messages ordering, Proceedings of the 2001 ACM symposium on Applied computing, p.499-503, March 2001, Las Vegas, Nevada, United States
	Li Gong , Nachum Shacham, Multicast security and its extension to a mobile environment, Wireless Networks, v.1 n.3, p.281-295, 1995
	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
	Dilip D. Kandlur , Kang G. Shin, Reliable broadcast algorithms for HARTS, ACM Transactions on Computer Systems (TOCS), v.9 n.4, p.374-398, Nov. 1991
	K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, ACM SIGOPS Operating Systems Review, v.21 n.5, p.123-138, Nov. 1987
	Deborah A. Agarwal , Louise E. Moser, A graphical interface for analysis of communication protocols, Proceedings of the 1992 ACM annual conference on Communications, p.149-156, March 03-05, 1992, Kansas City, Missouri, United States
	Gil Neiger , Sam Toueg, Simulating synchronized clocks and common knowledge in distributed systems, Journal of the ACM (JACM), v.40 n.2, p.334-367, April 1993
	Adam Beguelin , Jack Dongarra , Al Geist , Vaidy Sunderam, Visualization and Debugging in a Heterogeneous Environment, Computer, v.26 n.6, p.88-95, June 1993
	Ajay D. Kshemkalyani , Mukesh Singhal, An optimal algorithm for generalized causal message ordering, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.87, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	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
	Lawrence C. N. Tseung , Keh-Chiang Yu, The implementation of guaranteed, reliable, secure broadcast networks, Proceedings of the 1990 ACM annual conference on Cooperation, p.259-265, February 20-22, 1990, Washington, D.C., United States
	Rivka Ladin , Barbara Liskov , Liuba Shrira , Sanjay Ghemawat, Providing high availability using lazy replication, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.360-391, Nov. 1992
	Henri E. Bal , Jennifer G. Steiner , Andrew S. Tanenbaum, Programming languages for distributed computing systems, ACM Computing Surveys (CSUR), v.21 n.3, p.261-322, Sep. 1989
	Aleta M. Ricciardi , Kenneth P. Birman, Using process groups to implement failure detection in asynchronous environments, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.341-353, August 19-21, 1991, Montreal, Quebec, Canada
	Rivka Ladin , Barbara Liskov , Liuba Shrira, Lazy replication: exploiting the semantics of distributed services, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.43-57, August 22-24, 1990, Quebec City, Quebec, Canada
	Mesaac Makpangou , Kenneth P. Birman, Designing application software in wide area network settings, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-5, September 03-05, 1990, Bologna, Italy
	Roy Friedman, Implementing hybrid consistency with high-level synchronization operations, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.229-240, August 15-18, 1993, Ithaca, New York, United States
	Louise E. Moser , P. M. Melliar-Smith , Vivek Agrawala, Total ordering algorithms, Proceedings of the 19th annual conference on Computer Science, p.375-380, April 1991, San Antonio, Texas, United States
	M. Frans Kaashoek , Andrew S. Tanenbaum, Fault tolerance using group communication, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-4, September 03-05, 1990, Bologna, Italy
	Anthony D. Joseph , M. Frans Kaashoek, Building reliable mobile-aware applications using the Rover toolkit, Wireless Networks, v.3 n.5, p.405-419, Oct. 1997
	Roberto Baldoni, A Positive Acknowledgment Protocol for Causal Broadcasting, IEEE Transactions on Computers, v.47 n.12, p.1341-1350, December 1998
	Anthony D. Joseph , M. Frans Kaashoek, Building reliable mobile-aware applications using the Rover toolkit, Proceedings of the 2nd annual international conference on Mobile computing and networking, p.117-129, November 1996, Rye, New York, United States
	Gil Neiger , Sam Toueg, Substituting for real time and common knowledge in asynchronous distributed systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.281-293, August 10-12, 1987, Vancouver, British Columbia, Canada
	Werner Vogels, World wide failures, Proceedings of the 7th workshop on ACM SIGOPS European workshop: Systems support for worldwide applications, September 09-11, 1996, Connemara, Ireland
	Rosario Aiello , Elena Pagani , Gian Paolo Rossi, Causal ordering in reliable group communications, ACM SIGCOMM Computer Communication Review, v.23 n.4, p.106-115, Oct. 1993
	Sean W. O'Malley , Larry L. Peterson, A dynamic network architecture, ACM Transactions on Computer Systems (TOCS), v.10 n.2, p.110-143, May 1992
	David R. Cheriton , Dale Skeen, Understanding the limitations of causally and totally ordered communication, ACM SIGOPS Operating Systems Review, v.27 n.5, p.44-57, Dec. 1993
	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for asynchronous systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.325-340, August 19-21, 1991, Montreal, Quebec, Canada
	Ashwani Gahlot , Mohan Ahuja , Timothy Carlson, Global flush communication primitive for inter-process communication, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.111-120, August 14-17, 1994, Los Angeles, California, United States
	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
	Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability, ACM Transactions on Computer Systems (TOCS), v.12 n.2, p.91-122, May 1994
	Laurence Duchien , Gérard Florin , Lionel Seinturier, Partial order relations in distributed object environments, ACM SIGOPS Operating Systems Review, v.34 n.4, p.56-75, October 2000
	Brian M. Oki , Barbara H. Liskov, Viewstamped replication: a general primary copy, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.8-17, August 15-17, 1988, Toronto, Ontario, Canada
	Paul F. Reynolds, Jr. , Craig Williams , Raymond R. Wagner, Jr., Isotach Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.337-348, April 1997
	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
	V. V. Murty , V. K. Garg, Characterization of message ordering specifications and protocols, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.88, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Brendan Tangney , Vinny Cahill , Chris Horn , Dominic Herity , Alan Judge , Gradimir Starovic , Mark Sheppard, Some ideas on support for fault tolerance in COMANDOS, an object oriented distributed system, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-6, September 03-05, 1990, Bologna, Italy
	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
	Alan Fekete , M. Frans Kaashoek , Nancy Lynch, Implementing sequentially consistent shared objects using broadcast and point-to-point communication, Journal of the ACM (JACM), v.45 n.1, p.35-69, Jan. 1998
	Li-Hsing Yen , Ting-Lu Huang , Shu-Yuen Hwang, A protocol for causally ordered message delivery in mobile computing systems, Mobile Networks and Applications, v.2 n.4, p.365-372, Jan. 1998
	R. N. Chang , C. V. Ravishankar, A Service Acquisition Mechanism for Server-Based Heterogeneous Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.154-169, February 1994
	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
	Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.304-315, July 21-24, 1991, Hilton Head, South Carolina, United States
	Arup Acharya , B. R. Badrinath, A framework for delivering multicast message in networks with mobile hosts, Mobile Networks and Applications, v.1 n.2, p.199-219, Oct. 1996
	André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991
	Henri E. Bal , M. Frans Kaashoek , Andrew S. Tanenbaum, Orca: A Language for Parallel Programming of Distributed Systems, IEEE Transactions on Software Engineering, v.18 n.3, p.190-205, March 1992
	Patrick Th. Eugster , Rachid Guerraoui , Christian Heide Damm, On objects and events, ACM SIGPLAN Notices, v.36 n.11, p.254-269, 11/01/2001
	Hector Garcia-Molina , AnneMarie Spauster, Ordered and reliable multicast communication, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.242-271, Aug. 1991
	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
	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
	Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990
	Chung Fan Liu , Chyi Nan Chen, A sliding-agent-group communication model for constructing a robust roaming environment over internet, Mobile Networks and Applications, v.8 n.1, p.61-74, February 2003
	Li Gong, New protocols for third-party-based authentication and secure broadcast, Proceedings of the 2nd ACM Conference on Computer and communications security, p.176-183, November 1994, Fairfax, Virginia, United States
	Luping Liang , Gerald W. Neufeld , Samuel T. Chanson, A name model for nested group communication, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.414-423, Aug. 1993
	Ricardo Galli , Yuhua Luo, Mu3D: a causal consistency protocol for a collaborative VRML editor, Proceedings of the fifth symposium on Virtual reality modeling language (Web3D-VRML), p.53-62, February 20-24, 2000, Monterey, California, United States
	Gregory R. Andrews, Paradigms for process interaction in distributed programs, ACM Computing Surveys (CSUR), v.23 n.1, p.49-90, March 1991
	Rajendra Yavatkar , James Griffoen , Madhu Sudan, A reliable dissemination protocol for interactive collaborative applications, Proceedings of the third ACM international conference on Multimedia, p.333-344, November 05-09, 1995, San Francisco, California, United States
	J. Crowcroft , K. Paliwoda, A multicast transport protocol, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.247-256, August 1988
	Erwin Mayer, An evaluation framework for Multicast Ordering Protocols, ACM SIGCOMM Computer Communication Review, v.22 n.4, p.177-187, Oct. 1992
	Michael J. Knister , Atul Prakash, DistEdit: a distributed toolkit for supporting multiple group editors, Proceedings of the 1990 ACM conference on Computer-supported cooperative work, p.343-355, October 07-10, 1990, Los Angeles, California, United States
	L. Liang , G. W. Neufeld , S. T. Chanson, Avoiding name resolution loops and duplications in group communications, ACM SIGCOMM Computer Communication Review, v.20 n.4, p.220-230, Sep. 1990
	Bo Xu , Ouri Wolfson , Sam Chamberlain , Naphtali Rishe, Cost based data dissemination in satellite networks, Mobile Networks and Applications, v.7 n.1, January 2002
	P. M. Melliar-Smith , L. E. Moser , V. Agrawala, Broadcast Protocols for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.17-25, January 1990
	Shivakant Mishra , Christof Fetzer , Flaviu Cristian, The Timewheel Group Communication System, IEEE Transactions on Computers, v.51 n.8, p.883-899, August 2002
	L. E. Moser , P. M. Melliar-Smith , V. Agrawala, Processor Membership in Asynchronous Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.459-473, May 1994
	M. Ahuja, An Implementation of F-Channels, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.658-667, June 1993
	Weijia Jia , Jörg Kaiser , Edgar Nett, RMP: Fault-Tolerant Group Communication, IEEE Micro, v.16 n.2, p.59-67, April 1996
	Rong N. Chang , Chinya V. Ravishankar , Jacob Slonim, A service acquisition mechanism for the client/service model in cygnus, Proceedings of the 1991 conference of the Centre for Advanced Studies on Collaborative research, October 28-30, 1991, Toronto, Ontario, Canada
	Christos Papadopoulos , Guru Parulkar , George Varghese, Light-weight multicast services (LMS): a router-assisted scheme for reliable multicast, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.456-468, June 2004
	Yoram Moses , Zvi Polunsky , Ayellet Tal , Leonid Ulitsky, Algorithm Visualization For Distributed Environments, Proceedings of the 1998 IEEE Symposium on Information Visualization, p.71-78, October 19-20, 1998, North Carolina
	Luping Liang , Samuel T. Chanson , Gerald W. Neufeld, Process Groups and Group Communications: Classifications and Requirements, Computer, v.23 n.2, p.56-66, February 1990
	Massimo Franceschetti , Jehoshua Bruck, A Group Membership Algorithm with a Practical Specification, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1190-1200, November 2001
	Flavin Cristian, Understanding fault-tolerant distributed systems, Communications of the ACM, v.34 n.2, p.56-78, Feb. 1991
	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
	G. Cugola , E. Di Nitto , A. Fuggetta, Exploiting an event-based infrastructure to develop complex distributed systems, Proceedings of the 20th international conference on Software engineering, p.261-270, April 19-25, 1998, Kyoto, Japan
	Thomas L. Rodeheffer , Chandramohan A. Thekkath , Darrell C. Anderson, SmartBridge: a scalable bridge architecture, ACM SIGCOMM Computer Communication Review, v.30 n.4, p.205-216, October 2000
	Robert Simon , Robert Sclabassi , Taieb Znati, Communication control in computer supported cooperative work systems, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.311-321, October 22-26, 1994, Chapel Hill, North Carolina, United States
	Carol Critchlow , Kim Taylor, The inhibition spectrum and the achievement of causal consistency, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.31-42, August 22-24, 1990, Quebec City, Quebec, Canada
	Alan Feteke, Formal Models of Communication Services: A Case Study, Computer, v.26 n.8, p.37-47, August 1993
	Andrew S. Tanenbaum , M. Frans Kaashoek , Henri E. Bal, Parallel Programming Using Shared Objects and Broadcasting, Computer, v.25 n.8, p.10-19, August 1992
	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
	Hans-Ruedi Aschmann , Niklaus Giger , Elisabeth Hoepli , Peter Janak , Hubert Kirrmann, Alphorn: A Remote Procedure Call Environment for Fault-Tolerant, Heterogeneous, Distributed Systems, IEEE Micro, v.11 n.5, p.16-19, 60-67, September 1991
	T. Soneoka , T. Ibaraki, Logically Instantaneous Message Passing in Asynchronous Distributed Systems, IEEE Transactions on Computers, v.43 n.5, p.513-527, May 1994
	K. Ravindran , K. K. Ramakrishnan, A naming system for feature-based service specification in distributed operating systems, ACM SIGSMALL/PC Notes, v.17 n.3-4, p.12-21, Fall/Winter 1991
	Carol Critchlow , Kim Taylor, The inhibition spectrum and the achievement of causal consistency, Distributed Computing, v.10 n.1, p.11-27, July 1996
	Alvaro E. Campos , Juan E. Navarro, A page-coherent, causally consistent protocol for distributed shared memory, Journal of Systems and Software, v.72 n.3, p.305-319, August 2004
	P. B. Danzig, Flow Control for Limited Buffer Multicast, IEEE Transactions on Software Engineering, v.20 n.1, p.1-12, January 1994
	Punit Chandra , Pranav Gambhire , Ajay D. Kshemkalyani, Performance of the Optimal Causal Multicast Algorithm: A Statistical Analysis, IEEE Transactions on Parallel and Distributed Systems, v.15 n.1, p.40-52, January 2004
	Ali Sabbir , Kaliappa Ravindran, User-assisted tools for concurrency control in distributed multimedia collaborations, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
	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
	Alexander E. Kostin , Isik Aybay , Gurcu Oz, A Randomized Contention-Based Load-Balancing Protocol for a Distributed Multiserver Queuing System, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1252-1273, December 2000
	Rachid Guerraoui , André Schiper, The Generic Consensus Service, IEEE Transactions on Software Engineering, v.27 n.1, p.29-41, January 2001
	Sridhar Alagar , S. Venkatesan, Causal Ordering in Distributed Mobile Systems, IEEE Transactions on Computers, v.46 n.3, p.353-361, March 1997
	Peter Triantafillou, Independent Recovery in Large-Scale Distributed Systems, IEEE Transactions on Software Engineering, v.22 n.11, p.812-826, November 1996
	S. W. Luan , V. D. Gligor, A Fault-Tolerant Protocol for Atomic Broadcast, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.271-285, July 1990
	Vijay K. Garg , Brian Waldecker, Detection of Strong Unstable Predicates in Distributed Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1323-1333, December 1996
	Michael K. Reiter, A Secure Group Membership Protocol, IEEE Transactions on Software Engineering, v.22 n.1, p.31-42, January 1996
	Lorenzo Alvisi , Keith Marzullo, Message Logging: Pessimistic, Optimistic, Causal, and Optimal, IEEE Transactions on Software Engineering, v.24 n.2, p.149-159, February 1998
	José M. Piquer, Large causality: ordering broadcasts and messages, 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
	Yasushi Saito , Marc Shapiro, Optimistic replication, ACM Computing Surveys (CSUR), v.37 n.1, p.42-81, March 2005
	Prakash Panangaden , Kim Taylor, Concurrent common knowledge: defining agreement for asynchronous systems, Distributed Computing, v.6 n.2, p.73-93, September 1992
	Bernadette Charron-Bost , Friedemann Mattern , Gerard Tel, Synchronous, asynchronous, and causally ordered communication, Distributed Computing, v.9 n.4, p.173-191, February 1996
	Haifeng Yu , Amin Vahdat, Consistent and automatic replica regeneration, ACM Transactions on Storage (TOS), v.1 n.1, p.3-37, February 2005
	Roy Friedman, Implementing hybrid consistency with high-level synchronization operations, Distributed Computing, v.9 n.3, p.119-129, December 1995
	Chafika Benzaid , Nadjib Badache, Mobi_Causal: a protocol for causal message ordering in mobile computing systems, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.2, April 2005
	Joshua Auerbach , Madan Gopal , Marc Kaplan , Shay Kutten, Multicast group membership management, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.166-175, February 2003
	Romain Boichat , Rachid Guerraoui, Reliable and total order broadcast in the crash-recovery model, Journal of Parallel and Distributed Computing, v.65 n.4, p.397-413, April 2005
	Keith Shafer , Mohan Ahuja, Implementation of hierarchical F-channels for high-performance distributed computing, Distributed Computing, v.8 n.4, p.211-218, June 1995
	Ajay D. Kshemkalyani , Mukesh Singhal, Necessary and sufficient conditions on information for causal message ordering and their optimal implementation, Distributed Computing, v.11 n.2, p.91-111, April 1998
	Stephen Cranefield, Reliable group communication and institutional action in a multi-agent trading scenario, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
	Ge-Ming Chiu , Chih-Ming Hsiao , Wen-Ray Chang, Total ordering group communication protocol based on coordinating sequencers for multiple overlapping groups, Journal of Parallel and Distributed Computing, v.65 n.4, p.437-447, April 2005
	Michel Hurfin , Michel Raynal, A simple and fast asynchronous consensus protocol based on a weak failure detector, Distributed Computing, v.12 n.4, p.209-223, September 1999
	Enrique Mafla , Bharat Bhargava, Communication Facilities for Distributed Transaction-Processing Systems, Computer, v.24 n.8, p.61-66, August 1991
	Anish Arora , Sandeep S. Kulkarni , Murat Demirbas, Resettable vector clocks, Journal of Parallel and Distributed Computing, v.66 n.2, p.221-237, February 2006
	Gianpaolo Cugola , Elisabetta Di Nitto , Alfonso Fuggetta, The JEDI Event-Based Infrastructure and Its Application to the Development of the OPSS WFMS, IEEE Transactions on Software Engineering, v.27 n.9, p.827-850, September 2001
	Kwan L. Yeung , Ho-Lun T. Wong, Caching policy design and cache allocation in active reliable multicast, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.2, p.177-193, 7 October 2003
	Xiaohua Jia, A Total Ordering Multicast Protocol Using Propagation Trees, IEEE Transactions on Parallel and Distributed Systems, v.6 n.6, p.617-627, June 1995
	Xingwei Wang , Hong Zhao , Jiakeng Zhu, GRPC: a communication cooperation mechanism in distributed systems, ACM SIGOPS Operating Systems Review, v.27 n.3, p.75-86, July 1993
	Dan Oestreicher, A simple reliable globally-ordered broadcast service, ACM SIGOPS Operating Systems Review, v.25 n.4, p.66-76, Oct. 1991
	Nicolas Schiper , Fernando Pedone, Optimal atomic broadcast and multicast algorithms for wide area networks, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Laurent Nadeau , Wu-Hon F. Leung, Message-ordered multicast by common building blocks, Proceedings of the 1st international conference on Scalable information systems, p.46-es, May 30-June 01, 2006, Hong Kong
	Miguel Correia , Nuno Ferreira Neves , Lau Cheuk Lung , Paulo Veríssimo, Worm-IT - A wormhole-based intrusion-tolerant group communication system, Journal of Systems and Software, v.80 n.2, p.178-197, February, 2007
	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
	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
	Partha Dasgupta, Parallel processing with windows NT networks, Proceedings of the USENIX Windows NT Workshop on The USENIX Windows NT Workshop 1997, p.15-15, August 11-13, 1997, Seattle, Washington
	E. Garcia , H. Guyennet , J.-C. Lapayre, Groups Partitioning Over CORBA for Cooperative Work, Cluster Computing, v.9 n.1, p.67-78, January 2006
	D. Janaki Ram , M. Uma Mahesh , N. S. K. Chandra Sekhar , Chitra Babu, Causal consistency in mobile environment, ACM SIGOPS Operating Systems Review, v.35 n.1, p.34-40, January 1, 2001
	Bo Xu , Ouri Wolfson , Sam Chamberlain, Spatially distributed databases on sensors, Proceedings of the 8th ACM international symposium on Advances in geographic information systems, p.153-160, November 06-11, 2000, Washington, D.C., United States
	Rex E. Gantenbein, An annotated bibliography of dependable distributed computing, ACM SIGOPS Operating Systems Review, v.26 n.2, p.60-81, April 1992
	Ken Birman, A response to Cheriton and Skeen's criticism of causal and totally ordered communication, ACM SIGOPS Operating Systems Review, v.28 n.1, p.11-21, Jan. 1994
	Robbert van Renesse, Why bother with CATOCS?, ACM SIGOPS Operating Systems Review, v.28 n.1, p.22-27, Jan. 1994
	Brendan Tangney , Vinny Cahill , Chris Horn , Dominic Herity , Alan Judge , Gradimir Starovic , Mark Sheppard, Some ideas on support for fault tolerance in COMANDOS, an object oriented distributed system, ACM SIGOPS Operating Systems Review, v.25 n.2, p.130-135, April 1991
	Zhao Hong , Huatian Li, A mechanism of process group for application reliability in distributed systems, ACM SIGOPS Operating Systems Review, v.26 n.1, p.66-77, Jan. 1992
	M. Frans Kaashoek , Andrew S. Tanenbaum, Fault tolerance using group communication, ACM SIGOPS Operating Systems Review, v.25 n.2, p.71-74, April 1991
	Mahmoud Dasser, TOMP a total ordering multicast protocol, ACM SIGOPS Operating Systems Review, v.26 n.1, p.32-40, Jan. 1992
	Injong Rhee , Shun Yan Cheung , Phillip W. Hutto , Alan T. Krantz , Vaidy S. Sunderam, Group communication support for distributed collaboration systems, Cluster Computing, v.2 n.1, p.3-16, 1999
	Zhao Hong , Wayne McCoy, An associated object model for distributed systems, ACM SIGOPS Operating Systems Review, v.24 n.4, p.34-51, Oct. 1990
	Carlo Marchetti , Roberto Baldoni , Sara Tucci-Piergiovanni , Antonino Virgillito, Fully Distributed Three-Tier Active Software Replication, IEEE Transactions on Parallel and Distributed Systems, v.17 n.7, p.633-645, July 2006
	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
	Carlo Bertolli , Massimo Coppola , Corrado Zoccolo, The co-replication methodology and its application to structured parallel programs, Proceedings of the 2007 symposium on Component and framework technology in high-performance and scientific computing, October 21-22, 2007, Montreal, Quebec, Canada
	Jean Botev , Alexander Hohfeld , Hermann Schloss , Ingo Scholtes , Peter Sturm , Markus Esch, The HyperVerse: concepts for a federated and Torrent-based '3D Web', International Journal of Advanced Media and Communication, v.2 n.4, p.331-350, December 2008
	Chafika Benzaid , Nadjib Badache, BMobi_Causal: a causal broadcast protocol in mobile dynamic groups, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Lorenzo Bettini, Timed buffers: A technique for update propagation in nomadic environments, Computer Communications, v.31 n.14, p.3209-3222, September, 2008
	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
	Sergio Mena , André Schiper , Pawel Wojciechowski, A step towards a new generation of group communication systems, Proceedings of the ACM/IFIP/USENIX 2003 International Conference on Middleware, June 16-20, 2003, Rio de Janeiro, Brazil
	Anurag Agarwal , Vijay K. Garg, Efficient dependency tracking for relevant events in concurrent systems, Distributed Computing, v.19 n.3, p.163-183, January 2007
	Cristian Lumezanu , Neil Spring , Bobby Bhattacharjee, Decentralized message ordering for publish/subscribe systems, 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

INDEX TERMS

Classification:
C. Computer Systems Organization
C.2 COMPUTER-COMMUNICATION NETWORKS
C.2.1 Network Architecture and Design
Subjects: Network communications
C.2.4 Distributed Systems
Subjects: Distributed applications; Distributed databases

D. Software
D.4 OPERATING SYSTEMS
D.4.1 Process Management
Subjects: Concurrency; Synchronization
D.4.4 Communications Management
Subjects: Network communication
D.4.5 Reliability
Subjects: Fault-tolerance

H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.2 Physical Design
Subjects: Recovery and restart
H.2.4 Systems
Subjects: Concurrency; Distributed databases

General Terms:
Performance, Reliability

REVIEW

"Andrew Robert Huber : Reviewer"

The premise of this paper is that message orderings should be included in the communications layer of a distributed system. This approach is intended to maximize concurrency at the communications level, yet allow processes to determine (when des more...

Collaborative Colleagues:

Kenneth P. Birman: colleagues

Thomas A. Joseph: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player