Fast, flexible, and highly resilient genuine fifo and causal multicast algorithms

Schiper, Nicolas; Pedone, Fernando

Back

Preprint

Fast, flexible, and highly resilient genuine fifo and causal multicast algorithms

Schiper, Nicolas Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
Pedone, Fernando Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera

2009

20 p.

English 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.

Language