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

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.
  • English
Computer science and technology
License undefined
  • RERO DOC 22108
  • ARK ark:/12658/srd1318293
Persistent URL

Document views: 27 File downloads:
  • ITR0903.pdf: 66