Causal multicasts in overlapping groups : towards a low cost approach

Concepts of group (to structure processes) and causality (to structure sendings and deliveries of messages) are of major importance in the design of distributed systems. Mixing both concepts, the ISIS system defined causal multicast in overlapping groups. This paper presents a simple and efficient protocol that implements such causal multicasts. It compares favourably with the ISIS protocol as it uses only one vector of integers (size of this vector being the total number of groups) to timestamp messages. This low cost in the size of timestamps is obtained by using (sometimes) additional resynchronization messages. It is shown that there is a trade-off between the "as early as possible delivery time" criterium and the "as small as possible timestamps size" criterium for timestamp-based protocols implementing causal order