New latency bounds for atomic broadcast

Abstract

Tighter bounds are provided on the time required to reach agreement in a distributed system as a function of the failure model. After describing the model of a distributed system that is a context for this work the authors define several failure classes. They define a partial order on classes of failures that involves whether there is a latency penalty in converting from tolerance of one failure class to another. In this setting they distinguish clock and timing failures, showing that there can be a penalty in converting from timing failure tolerance to clock failure tolerance. The authors leave open the exact expression for the optimal latency for timing failure tolerant atomic broadcast, though it is conjectured that there is some penalty in converting from omission failure tolerance to timing failure tolerance.