Causal controversy at Le Mont St.-Michel

ABSTRACT

As usual, the SIGOPS workshop provided a great platform for interesting discussion. Among other things, a controversy arose around the usefulness of causal ordering in a distributed system. In this paper, I explain causality in non-technical terms, and enumerate some of the most prevalent misconceptions that surrounded causality. Next I present some important examples where causal delivery is a necessary and sufficient ordering of events.

REFERENCES

• 1: 1. Proceedings of the 5th ACM SIGOPS Workshop, IRISA INRIA, Rennes, France, September 21-23, 1992.
• 2: 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]
• 3: André Schiper , Jorge Eggli , Alain Sandoz, A New Algorithm to Implement Causal Ordering, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.219-232, September 26-28, 1989
• 4: 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]
• 5: 5. L. Rodrigues and P. Verissimo, "xAMp: a Multi-primitive Group Communications Service," Proc. of the 11th Symposium on Reliable Distributed Systems, IEEE, Houston, TX, October 1992.
• 6: José M. Piquer, Indirect reference counting: a distributed garbage collection algorithm, Proceedings on Parallel architectures and languages Europe : volume I: parallel architectures and algorithms: volume I: parallel architectures and algorithms, p.150-165, June 1991, Eindhoven, The Netherlands
• 7: 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 [doi>10.1145/98163.98167]
• 8: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 9: 9. R. Ladin, B. Liskov, and L. Shrira, "Lazy Replication: Exploiting the Semantics of Distributed Services," IEEE TCOS Newsletter, special issue on the Management of Replicated Data, vol. 4, no. 3, pp. 4-7, Fall 1990.
• 10: 10. M. Ahamad, P. Hutto, and R. John, "Implementing and Programming Causal Distributed Shared Memory," Proc. of the 11th International Conference on Distributed Computing Systems, Arlington, TX, May 20-24, 1991.
• 11: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 12: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• 13: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 14: 14. H.E. Bal, M.F. Kaashoek, and A.S. Tanenbaum, "Experience with Distributed Programming in Orca," Proc. of the International Conference on Computer Languages '90, IEEE, 1990.
• 15: 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]
• 16: Michael Reiter , Kenneth Birman , Li Gong, Integrating Security in a Group Oriented Distributed System, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.18, May 04-06, 1992
• 17: 17. R. Schwarz and F. Mattern, "Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail," Tech. Report 215/91, Dept. of Comp. Sc., Univ. of Kaiserslautern, Kaiserslautern, Germany, November 1991.
• 18: 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]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Management