Technical reports

Low-latency Atomic Broadcast in the presence of contention

Piotr Zieliński

July 2006, 23 pages

DOI: 10.48456/tr-671

Abstract

The Atomic Broadcast algorithm described in this paper can deliver messages in two communication steps, even if multiple processes broadcast at the same time. It tags all broadcast messages with the local real time, and delivers all messages in order of these timestamps. The Ω-elected leader simulates processes it suspects to have crashed (◇S). For fault-tolerance, it uses a new cheap Generic Broadcast algorithm that requires only a majority of correct processes (n > 2f) and, in failure-free runs, delivers all non-conflicting messages in two steps. The main algorithm satisfies several new lower bounds, which are proved in this paper.

Full text

PDF (0.3 MB)

BibTeX record

@TechReport{UCAM-CL-TR-671,
  author =	 {Zieli{\'n}ski, Piotr},
  title = 	 {{Low-latency Atomic Broadcast in the presence of contention}},
  year = 	 2006,
  month = 	 jul,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-671.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-671},
  number = 	 {UCAM-CL-TR-671}
}