Texas A&M University LibrariesTexas A&M University LibrariesTexas A&M University Libraries
    • Help
    • Login
    OAKTrust
    View Item 
    •   OAKTrust Home
    • Programs, Centers, and Institutes
    • Undergraduate Research and Capstones
    • Undergraduate Research Scholars Capstone (2006–present)
    • View Item
    •   OAKTrust Home
    • Programs, Centers, and Institutes
    • Undergraduate Research and Capstones
    • Undergraduate Research Scholars Capstone (2006–present)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Average Case Analysis of a Shared Register Emulation Algorithm

    Thumbnail
    View/Open
    HU-FINALTHESIS-2019.pdf (194.9Kb)
    Author
    Hu, Gerald Lee
    Metadata
    Show full item record
    Abstract
    Distributed 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.
    URI
    http://hdl.handle.net/1969.1/175420
    Subject
    distributed computing
    shared register emulation
    asynchronous
    dynamic
    simulation
    average case analysis
    Collections
    • Undergraduate Research Scholars Capstone (2006–present)
    Citation
    Hu, Gerald Lee (2019). Average Case Analysis of a Shared Register Emulation Algorithm. Undergraduate Research Scholars Program. Available electronically from http : / /hdl .handle .net /1969 .1 /175420.

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Advanced Search

    Browse

    All of OAKTrustCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDepartmentThis CollectionBy Issue DateAuthorsTitlesSubjectsDepartment

    My Account

    LoginRegister

    Statistics

    View Usage Statistics
    Help and Documentation

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV