Causal separators and topological timestamping: an approach to support causal multicast in large-scale systems

Luís Rodrigues and Paulo Veríssimo

Selected sections of this report will be published in the Proceedings of the 15th International Conference on Distributed Computing Systems, Vancouver, British Columbia, Canada, May 1995.

Abstract

In recent years there has been a growing interest in developing communication systems that are able to deliver messages respecting potential causality. Unfortunately, causal delivery cannot be provided without costs: extra delays may be induced on message delivery or processes may be required to maintain and exchange records of causal relations. In this paper we present an extension to previous work on compression of causal information using knowledge about the topology of the communication structure.

In order to make practical use of this result, we present a methodology to model the communication system. The technique exploits the physical structure of existing networks, in particular its hierarchical nature, to create a communication graph where causal separators match the underlying physical and administrative organization. We show that this approach can be applied to existing large-scale systems, providing the means for using topological timestamping with negligible overhead.

Also available extended report (gzip postscript),(pdf) .

Luís Rodrigues