A Non-Blocking Lightweight Implementation of Causal Order Message Delivery 

In: K.P. Birman, F. Mattern, A. Schiper (Eds.): Theory and Practice in 
Distributed Systems, Springer-Verlag, LNCS 938, pp. 197 - 213, 1995 

This paper presents an algorithm to implement point-to-point causal order 
message delivery in distributed systems which does not force the sender to 
wait and which does not piggyback control information (such as timestamps) on 
messages. The algorithm is based on a message transmission protocol using 
low-level acknowledgements between FIFO buffers. We show that on the one 
hand causal order can easily and efficiently be realized in that way, but that 
on the other hand the loss of knowledge--induced by not using dependency 
matrices as in previously known protocols--leads to a slight restriction with 
respect to the applicability of the new protocol. The advantages of our 
scheme, however, are obvious because it is non-blocking and the piggybacking 
of huge control information on messages is avoided. Furthermore, the new 
algorithm is easily implementable since many distributed systems and 
low-level transmission protocols already provide message buffers and explicit 
or implicit message acknowledgements.