Large causality: ordering broadcasts and messages

ABSTRACT

The causal order in distributed asynchronous systems is a valuable and useful concept to implement distributed algorithms. In particular, causal broadcasts have been used to solve many well-known distributed problems (as replication using a token-passing mechanism). However, the implementation of a general causal message system (where every message and broadcast respects the causal order) is complicated and involves a hard protocol to ensure delivery order. On the other hand only a few applications really need the causal semantics of the message sending primitives and they typically only concern the broadcast primitives.This paper proposes a new ordering of broadcasts and messages, where the broadcasts are causally ordered, but they only impose an order on messages (which are not causally ordered). This order (called large causality) is easy and cheap to implement on most distributed architectures and is powerful enough to build token-passing (and though replica coherency) and global state applications.This paper does not treat group multicast nor fault-tolerance, however we expect to be able to benefit from the research done on this field by systems such as ISIS, providing all these features together.

REFERENCES

• 1: 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
• 2: 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]
• 3: K. P. Birman , T. A. Joseph, Exploiting replication in distributed systems, Distributed systems, ACM Press, New York, NY, 1990 [doi>10.1145/90417.90751]
• 4: Kenneth P. Birman , Andre Schiper , Patrick Stephenson, Fast Causal Multicast, Cornell University, Ithaca, NY, 1990
• 5: {Garc 89} H. Garcia-Molina, A. Spauster, Message Ordering in a Multicast Environment Proc. 9th International Conference on Distributed Computing Systems, IEEE, June 1989.
• 6: {Fidg 88} C. Fidge, Timestamps in Messaqe-Passing Systems that Preserve the Partial Ordering, Proc.1lth Australian Computer Science Conference, 1988.
• 7: 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]
• 8: Bernard Lang , Christian Queinnec , José Piquer, Garbage collecting the world, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.39-50, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143176]
• 9: {Matt 87} F. Mattern, Algorithms for Distributed Termination Detection, Distributed Computing, N. 2, pp. 161-175, Springer-Verlag, 1987.
• 10: {Matt 89} F. Mattern, Time and Global States in Distributed Systems, Proc. of the International Workshop on Parallel and Distributed Algorithms, North-Holland, 1989.
• 11: 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]
• 12: {Piqu 91a} J. M. Piquer, Parallélisme et Distribution en Lisp, Thèse de Doctorat d'Informatique, École Polytechnique, Paris, France, 1991.
• 13: 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
• 14: {Piqu 91c} J. M. Piquer, Preserving Distributed Data Coherence Using Asynchronous Broadcasts, Proc. of the XI International Conference of the Chilean Computer Science Society, Plenum Press, Santiago, Chile, Oct. 1991.
• 15: {Rayn 89} M. Raynal, A. Schiper, S. Toueg, The Causal Ordering Abstraction and a Simple Way to Implement It, INRIA Research Report 1132, Dec. 1989.
• 16: 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

INDEX TERMS

Keywords:
Causality, Distributed Systems, Global States, Termination Detection, Token Passing