Show simple item record

dc.creatorKirchhofer, Grant W
dc.date.accessioned2018-05-23T15:37:26Z
dc.date.available2018-05-23T15:37:26Z
dc.date.created2018-05
dc.date.submittedMay 2018
dc.identifier.urihttp://hdl.handle.net/1969.1/166537
dc.description.abstractThis 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.
dc.format.mimetypeapplication/pdf
dc.subjectRMTP
dc.subjectreliable
dc.subjectmessage
dc.subjecttransmission
dc.subjectunknown
dc.subjectreordering
dc.subjectbound
dc.subjectcounter
dc.subjecttag
dc.subjectimpossibility
dc.subjectproof
dc.subjectdistributed
dc.subjectalgorithm
dc.titleSolving the RMTP with an Unknown Bound on Reordering using Bounded Counters
dc.typeThesis
thesis.degree.departmentComputer Science & Engineering
thesis.degree.disciplineComputer Science
thesis.degree.grantorUndergraduate Research Scholars Program
thesis.degree.nameBS
thesis.degree.levelUndergraduate
dc.contributor.committeeMemberWelch, Jennifer
dc.type.materialtext
dc.date.updated2018-05-23T15:37:27Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record