Bounded Protocols for Efficient Reliable Message Transmission

Abstract

In the reliable message transmission problem (RMTP) processors communicate by exchanging messages, but the channel that connects two processors is subject to message loss, duplication, and reordering. Previous work focused on proposing protocols in asynchronous systems, where message size is finite and sequence numbers are bounded. However, if the channel can duplicate messages, lose messages, and arbitrarily reorder the messages, the problem is unsolvable. In this thesis, we consider a strengthening of the asynchronous model in which reordering of messages is bounded. In this model, we develop two efficient protocols to solve the RMTP: (1) when messages may be duplicated but not lost and (2) when messages may be duplicated and lost. This result is in contrast to the impossibility of such an algorithm when reordering is unbounded. Our protocols have the pleasing property that no messages need to be sent from the receiver to the sender.