A lightweight asynchronous algorithm for causal delivery using extra message insertion

César Sánchez and Angel Alvarez

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.

Short paper in DISC 2000, 14th International Symposium on DIStributed Computing, Toledo (Spain), October 2000.
Download: BIB PDF