Efficient atomic broadcast using deterministic merge

Abstract

We present an approach for merging message streams from producers distributed over a network, using a deterministic algorithm that is independent of any nondeterminism of the system, such as the amount of time the messages are delayed by the network, or their arrival order. Thus, if this algorithm is replicated at multiple “mergers”, then each merger will merge the message streams in exactly the same way. The technique is therefore a solution to atomic broadcast and global atomic multicast [12]. We assume that each producer has access to (approximately) synchronized clocks and can estimate the expected message rates of all producers. We propose an algorithm, called the Bias Algorithm. To measure the performance of the Bias Algorithm, we assume that messages are generated by memoryless processes operating at known message rates, and we measure the expected total merge delay at a given time L. For the case of two producer processes, we give optimal algorithms in this metric, and show that the optimal algorithm converges to our Bias algorithm when L ⇒ ∞. We reconfirm our optimality result using Dynamic Programming theory, and we use simulations to validate the robustness of this optimality result under more realistic conditions.