Efficient atomic broadcast using deterministic merge.pdfVIP

Efficient Atomic Broadcast Using Deterministic Merge Marcos Kawazoe Aguilera LIX Laboratoire d’Informatique E?cole Polytechnique 91128 Palaiseau Cedex, France aguilera@lix.polytechnique.fr Robert E. Strom IBM T.J. Watson Research Center Yorktown Heights, NY 10598 USA strom@ ABSTRACTWe present an approach for merging message streams fromproducers distributed over a network, using a determinis-tic algorithm that is independent of any nondeterminismof the system, such as the amount of time the messagesare delayed by the network, or their arrival order. Thus, ifthis algorithm is replicated at multiple \mergers, then eachmerger will merge the message streams in exactly the sameway. The technique is therefore a solution to atomic broad-cast and global atomic multicast [12]. We assume that eachproducer has access to (approximately) synchronized clocksand can estimate the expected message rates of all produc-ers. We propose an algorithm, called the Bias Algorithm.To measure the performance of the Bias Algorithm, we as-sume that messages are generated by memoryless processesoperating at known message rates, and we measure the ex-pected total merge delay at a given time L. For the case oftwo producer processes, we give optimal algorithms in thismetric, and show that the optimal algorithm converges toour Bias algorithm when L ! 1. We recon rm our opti-mality result using Dynamic Programming theory, and weuse simulations to validate the robustness of this optimalityresult under more realistic conditions.Our motivating application is middleware for a widely-dis-tributed publish-subscribe system, where subscribers requireuniform reliable ordered delivery. To allow recovery, mes-sages are logged to stable storage at \logger nodes, whichserve as the sources for the message streams to be merged.We discuss the practical bene ts of our approach in suchenvironments. 1. INTRODUCTION 1.1 Background and motivationConsider the system shown in Figure 1, derived from Gryphon,an experimental