Efficient Atomic Broadcast Using Deterministic Merge

Marcos Kawazoe Aguilera and Robert E. Strom

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


Abstract

We consider an approach for merging message streams from producers distributed over a network into a single stream. In this approach, the messages are merged using an algorithm that is deterministic. Therefore, if message streams are sent to multiple "mergers" each executing the deterministic merge, then messages will be delivered in consistent total order. The technique is therefore an efficient solution to atomic broadcast and global atomic multicast. We present a specific deterministic merge algorithm, the Bias Algorithm, that exploits knowledge of the expected message rates of the producers. We show that the Bias Algorithm has the least total expected delay when messages are produced according to a binomial process with known rate parameters. Our motivating application is middleware for a widely-distributed publish-subscribe system, in which a subscriber can be intermittently connected, and where subscribers require reliable ordered delivery. Messages are logged to stable storage at "logger" nodes that serve as the sources for the message streams to be merged. As a result, (1) it is not necessary for a second stable log to record the merge order; and (2) the merge function can be replicated at independent sites, and each site is guaranteed to merge messages in the same order. We validate our work using both Dynamic Programming theory and simulations.