A response to Cheriton and Skeen's criticism of causal and totally ordered communication

ABSTRACT

In a paper to be presented at the 1993 ACM Symposium on Operating Systems Principles, Cheriton and Skeen offer their understanding of causal and total ordering as a communication property. In this brief rebuttal. I present some responses to their criticism, and also explain why I find their discussion of causal and total communication ordering to be narrow and incomplete.

REFERENCES

• 1: [ADKM91] Yair Amir, Danny Dolev, Shlomo Kramer, and Dalia Malki. Transis: A communication sub-system for high availability. Technical Report TR 91-13, Computer Science Department, The Hebrew University of Jerusalem, November 1991.
• 2: [AMMS⁺93] Yair Amir, Louise E. Moser, P. M. Melliar-Smith, Deb A. Agarwal, and Paul Ciarfella. Fast message ordering and membership using a logical token-passing ring. In Proceedings of the 13th International IEEE Conference on Distributed Computing Systems, pages 551-560, Pittsburgh, PA, May 1993.
• 3: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 4: [Bir94] Kenneth P. Birman. Maintaining consistency in distributed systems. Journal of Parallel and Distributed Computing, 1994. Accepted for publication.
• 5: K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.123-138, November 08-11, 1987, Austin, Texas, United States
• 6: 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]
• 7: Kenneth P. Birman , Robbert Van Renesse, Reliable Distributed Computing with the ISIS Toolkit, IEEE Computer Society Press, Los Alamitos, CA, 1993
• 8: 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 [doi>10.1145/128738.128742]
• 9: 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]
• 10: 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]
• 11: M. Frans Kaashoek , A. S. Tanenbaum , S. F. Hummel, An efficient reliable broadcast protocol, ACM SIGOPS Operating Systems Review, v.23 n.4, p.5-19, Oct. 1989 [doi>10.1145/70730.70732]
• 12: 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 [doi>10.1145/93385.93399]
• 13: 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 [doi>10.1109/71.80121]
• 14: 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]
• 15: D. Powell , I. Bey , J. Leuridan, Delta Four: A Generic Architecture for Dependable Distributed Computing, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 16: [Sch86] Fred B. Schneider. The state machine approach: a tutorial. Technical Report TR 86-800, Department of Computer Science, Cornell University, December 1986. Revised June 1987.
• 17: [Ste91] Pat Stephenson. Fast Causal Multicast. PhD thesis, Cornell University, February 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Design, Human Factors, Management, Theory