Bounded Reordering Allows Efficient Reliable Message Transmission Conference Paper

abstract

• 2017 IEEE. 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-but not lose them-and arbitrarily reorder the messages, the problem is unsolvable. We consider a strengthening of the asynchronous model in which reordering of messages is bounded. In this model, we develop an efficient protocol to solve the RMTP when messages may be duplicated but not lost. This result is in contrast to the impossibility of such an algorithm when reordering is unbounded. Our protocol has the pleasing property that no messages need to be sent from the receiver to the sender and it works when message loss is allowed with some minimal modifications.

name of conference

• 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)

authors

• Welch, Jennifer

published proceedings

• 2017 31ST IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS)

author list (cited authors)

• Ortiz-Lopez, K. D., & Welch, J. L.

citation count

• 0

complete list of authors

• Ortiz-Lopez, Keishla D||Welch, Jennifer L

publication date

• May 2017

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Proceedings of the International Parallel and Distributed Processing Symposium, IPDPS  Journal

keywords

• Communication Networks
• Distributed Computing
• Message Transmission Protocols

Digital Object Identifier (DOI)

• 10.1109/IPDPS.2017.14

International Standard Book Number (ISBN) 13

• 9781538639146

start page

• 327

end page

• 336

URL

• http://dx.doi.org/10.1109/ipdps.2017.14