Solving the RMTP with an Unknown Bound on Reordering using Bounded Counters
MetadataShow full item record
This research analyzes the reliable message transmission problem, or RMTP, with a different set of constraints than has been previously studied. The RMTP describes the task of simulating a reliable computer communication channel on top of an unreliable one. The unreliable channel can exhibit undesirable behavior, including message loss, duplication, and reordering. The reliable channel exhibits none of these. Prior research has proposed an algorithm that solves the RMTP using bounded message counters when the channel exhibits duplication and bounded reordering, where the bound on reordering is known. This paper studies a variation of that configuration with an unknown bound on reordering. Using well documented C++ code, data collected from experimental executions of that code, and formal logical and mathematical proofs, we show that for several classes of algorithms, there is no possible algorithm that solves the RMTP where the bound on reordering is unknown. We also develop an algorithm that can, with enough input, solve the RMTP when the reordering bound is unknown but is within a known range.
Kirchhofer, Grant W (2018). Solving the RMTP with an Unknown Bound on Reordering using Bounded Counters. Undergraduate Research Scholars Program. Available electronically from