A non-blocking lightweight implementation of causal order message delivery

Abstract. 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 bu ers. We show that on the one hand causal order can easily and e ciently 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 bu ers and explicit or implicit message acknowledgements