How to avoid the cost of causal communication in large-scale systems.

Luís Rodrigues and Paulo Veríssimo

From the Proceedings of the 6th SIGOPS European Workshop, Sept., 1994, Dagstuhl, Germany.


In a distributed system, consisting of a collection of processes that communicate by exchanging messages, the order in which messages are delivered to processes is of major relevance to the application design. With the aim of simplifying the design of distributed applications, several algorithms and protocols have been proposed to provide causal order delivery.

Despite its advantages, the use of causal communication has been somewhat limited by the overhead incurred by existing implementations. In the Navigators group at INESC, we are currently studying mechanisms to improve the efficiency of multicast communication over (geographically) large-scale networks. We claim that, to allow applications to take advantage of multicast communication, new services (based on weaker assumptions about the system) must be provided. To support this claim, this paper proposes and describes a new quality of service, referred to as transparent causal messages.

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

Luís Rodrigues