Department of Computer Science and Technology

Technical reports

Latency-optimal Uniform Atomic Broadcast algorithm

Piotr Zieliński

February 2004, 28 pages


We present a new asynchronous Uniform Atomic Broadcast algorithm with a delivery latency of two communication steps in optimistic settings, which is faster than any other known algorithm and has been shown to be the lower bound. It also has the weakest possible liveness requirements (the Ω failure detector and a majority of correct processes) and achieves three new lower bounds presented in this paper. Finally, we introduce a new notation and several new abstractions, which are used to construct and present the algorithm in a clear and modular way.

Full text

PDF (0.3 MB)

BibTeX record

  author =	 {Zieli{\'n}ski, Piotr},
  title = 	 {{Latency-optimal Uniform Atomic Broadcast algorithm}},
  year = 	 2004,
  month = 	 feb,
  url = 	 {},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-582}