# A lightweight asynchronous algorithm for causal delivery using extra message insertion

This paper presents an algorithm to solve the problem of
causal delivery with messages of size bounded to $O(k)$ where the
parameter $n < k < = n^2$ is a constant fixed by the programmer. The
algorithm makes use of the concept of matrix clocks. It works by
inserting some extra messages in the network in a clever manner to create
stronger conditions than causal delivery. These extra messages
simplify the clock matrices, which can then be coded even in linear
space if so desired.

The drawback of the algorithm is that message delivery may sometimes get delayed waiting for these extra messages to arrive, even if all the conditions strictly imposed by the causality of the application are satisfied. The paper proves the correctness of the algorithm presented and compares it with other solutions proposed for the causal ordering problem.

*DISC 2000, 14th International Symposium on DIStributed Computing, Toledo (Spain)*, October 2000.