Multicasting in the presence of aggregated deliveries

An increasing number of distributed systems relies on forms of message correlation, which result in atomic delivery of multiple messages aggregated by following process-specific criteria. Generally, more than one process is aggregating messages, implying that messages are multicast. While delivery guarantees for multicast scenarios with single message delivery are well understood, existing systems and models for aggregated deliveries either consider only unicast, centralized setups, or focus on efficiency thus providing only best-effort guarantees. This paper investigates the foundations of Multi-Delivery Multicast (MDMcast) in asynchronous distributed systems with crash-stop failures. We first describe a succinct aggregation model with a concise and generic predicate grammar for expressing conjunctions on messages and properties for a corresponding multicast primitive, which we term Conjunction-MDMcast (C-MDMcast). We show that for processes interested in identical conjunctions to achieve agreement on delivered messages, a total order on individual messages (or equivalent oracle) is not only useful but necessary, which is clearly opposed to single-message deliveries. We show this indirectly by exhibiting an algorithm implementing C-MDMcast on top of Total Order Broadcast (TOBcast) and vice-versa for a majority of correct processes. Then, we extend our predicate grammar with disjunctions, leading to the specification of Disjunction-MDMcast (D-MDMcast). We exhibit an algorithm implementing D-MDMcast, derived from our algorithm implementing C-MDMcast. We formalize several additional properties for both of our specifications, including ordering properties on aggregated messages and a notion of agreement capturing non-identical yet “related” conjunctions, and show how our respective algorithms implement these.

► Agreement on deliveries of aggregated messages requires total order (or equivalent oracle) for individual messages.
► Agreement properties which are sensitive to coverage among subscriptions are constrained e.g. by priorities among message types.
► A total order on individual messages can be leveraged to establish a total order on aggregated deliveries.
► For FIFO and causal order properties we want to restrict ourselves to individual message types.