Show simple item record

dc.creatorHu, Gerald Lee
dc.date.accessioned2019-06-10T16:15:23Z
dc.date.available2019-06-10T16:15:23Z
dc.date.created2019-05
dc.date.submittedMay 2019
dc.identifier.urihttps://hdl.handle.net/1969.1/175420
dc.description.abstractDistributed algorithms are important for managing systems with multiple networked components, where each component operates independently but coordinates to achieve a common goal. Previous theoretical research has produced numerous distributed algorithms but primarily uses mathematical proofs to yield theoretical results, such as worst-case runtime complexity. However, less research has been done on how these algorithms behave in practice, such as average-case runtime complexity. This paper will describe the empirical behavior of the distributed algorithm CCReg in a realistic environment, using the language DistAlgo to implement said algorithm. CCReg emulates a shared read/write register using a message-passing system. In particular, CCReg allows the underlying message-passing system to experience continuous changes to the set of components present, and tolerates crash failures of components. When the rate of component change and the fraction of crash failures are bounded, CCReg is proven to work correctly. The original paper specifies bounds for both that are guaranteed to work, and gives proof for those bounds. However, these bounds are restrictive and do not allow for much component change or many crash failures. Thus the goal of our implementation is to determine if CCReg's theoretical bounds can be relaxed in practice. We focus on CCReg's safety and liveness conditions: the algorithm eventually terminates, and a consistency condition called linearizability is maintained. We use a general method developed by Gibbons and Korach for determining if any ordering of operations satisfying linearizability exists. We find that, for executions where operations are randomly invoked, the algorithm does not exhibit any adverse behaviors. Each execution we tested terminates in finite time and has an order of operations satisfying linearizability. We discuss these findings, as well as future approaches and methodology for testing the theoretical boundaries in practice.en
dc.format.mimetypeapplication/pdf
dc.subjectdistributed computingen
dc.subjectshared register emulationen
dc.subjectasynchronousen
dc.subjectdynamicen
dc.subjectsimulationen
dc.subjectaverage case analysisen
dc.titleAverage Case Analysis of a Shared Register Emulation Algorithmen
dc.typeThesisen
thesis.degree.departmentComputer Science & Engineeringen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorUndergraduate Research Scholars Programen
thesis.degree.nameBSen
thesis.degree.levelUndergraduateen
dc.contributor.committeeMemberWelch, Jennifer
dc.type.materialtexten
dc.date.updated2019-06-10T16:15:23Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record