Real Time Dynamic Atomic Broadcast

Abstract

This talk introduces a problem of atomic broadcast with real-time latency guarantees in a dynamic setting where processes may join, leave voluntarily, or fail (by stopping) during the course of computation. We provide a formal definition of the Real-Time Dynamic Atomic Broadcast problem and present and analyze a new algorithm for its solution. The algorithm exhibits constant message delivery latency in the absence of failures, even during periods when participants join or leave. When failures occur, the latency bound is linear in the number of actual failures. These bounds improve upon previously suggested algorithms solving similar problems in the context of view-oriented group communication. Our algorithm uses a solution to a variation on the standard distributed consensus problem, in which participants do not know a priori who the other participants are. We define the new problem, which we call Consensus with Unknown Participants, and give an early-stopping algorithm to solve it. Based on joint work with Ziv Bar-Joseph and Idit Keidar.