Computer Laboratory

Technical reports

Indirect channels: a bandwidth-saving technique for fault-tolerant protocols

Piotr Zieliński

April 2007, 24 pages

Abstract

Sending large messages known to the recipient is a waste of bandwidth. Nevertheless, many fault-tolerant agreement protocols send the same large message between each pair of participating processes. This practical problem has recently been addressed in the context of Atomic Broadcast by presenting a specialized algorithm.

This paper proposes a more general solution by providing virtual indirect channels that physically transmit message ids instead of full messages if possible. Indirect channels are transparent to the application; they can be used with any distributed algorithm, even with unreliable channels or malicious participants. At the same time, they provide rigorous theoretical properties.

Indirect channels are conservative: they do not allow manipulating message ids if full messages are not known. This paper also investigates the consequences of relaxing this assumption on the latency and correctness of Consensus and Atomic Broadcast implementations: new algorithms and lower bounds are shown.

Full text

PDF (0.3 MB)

BibTeX record

@TechReport{UCAM-CL-TR-681,
  author =	 {Zieli{\'n}ski, Piotr},
  title = 	 {{Indirect channels: a bandwidth-saving technique for
         	   fault-tolerant protocols}},
  year = 	 2007,
  month = 	 apr,
  url = 	 {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-681.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-681}
}