Technical report detail

Fast, Flexible, and Highly Resilient Genuine Fifo and Causal Multicast Algorithms

by Nicolas Schiper and Fernando Pedone

We study the fifo and causal multicast problem, two group-communication abstractions that deliver messages in an order consistent with their context. With fifo multicast, the context of a message $m$ at a process p is all messages that were previously multicast by m's sender and addressed to p. Causal multicast extends the notion of context to all messages that are causally linked to m by a chain of multicast and delivery events. We propose multicast algorithms for systems composed of a set of disjoint groups of processes: server racks or data centers. These algorithms offer several desirable properties: (i) the protocols are latency-optimal, (ii) to deliver a message m only m's sender and addressees communicate, (iii) messages can be addressed to any subset of groups, and (iv) these algorithms are highly resilient: an arbitrary number of process failures is tolerated and we only require the network to be quasi-reliable, i.e., a message m is guaranteed to be received only if the sender and receiver of m are always up. To the best of our knowledge, these are the first multicast protocols to offer all of these properties at the same time.

Technical report 2009/03, October 2009

BibTex entry

@techreport{09fast, author = {Nicolas Schiper and Fernando Pedone}, title = {Fast, Flexible, and Highly Resilient Genuine Fifo and Causal Multicast Algorithms}, institution = {University of Lugano}, number = {2009/03}, year = 2009, month = oct }