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.
multicast aggregation properties order