• Find People
  • Campus Map
  • PiratePort
  • A-Z
    • About
    • Submit
    • Browse
    • Login
    View Item 
    •   ScholarShip Home
    • ECU Main Campus
    • College of Engineering and Technology
    • Computer Science
    • View Item
    •   ScholarShip Home
    • ECU Main Campus
    • College of Engineering and Technology
    • Computer Science
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of The ScholarShipCommunities & CollectionsDateAuthorsTitlesSubjectsTypeDate SubmittedThis CollectionDateAuthorsTitlesSubjectsTypeDate Submitted

    My Account

    Login

    Statistics

    View Google Analytics Statistics

    Group Mutual Exclusion in Linear Time and Space

    Thumbnail
    View/ Open
    He_ecu_0600O_11265.pdf (261.2Kb)

    Show full item record
    Author
    He, Yuan
    Abstract
    The Group Mutual Exclusion (GME) problem, introduced by Joung, is a natural extension of the classical Mutual Exclusion problem. In the classical Mutual Exclusion problem, two or more processes are not simultaneously allowed to be in their CRITICAL SECTION, a piece of code where a common resource is accessed. In the GME problem, it is necessary to impose mutual exclusion on different groups in processes in accessing a resource, while allowing processes of the same group to share the resource. The Group Mutual Exclusion problem arises in several applications and is the focus of this thesis. We present an algorithm for the GME problem that satisfies the properties of Mutual Exclusion, Starvation Freedom, Bounded Exit, Concurrent Entry and First-Come-First Served. Our algorithm has [theta] (N) shared space complexity and [omicron] (N)RMR (Remote Memory Reference) complexity. Our algorithm is developed by generalizing the well-known Lamport's Bakery Algorithm for the classical mutual exclusion problem, while preserving its simplicity and elegance. Just like Lamport's Bakery Algorithm, our algorithm has the disadvantage that the token numbers can grow in an unbunded manner. When all shared variables are required to be of bounded size, Hadzilacos presented an algorithm, whose shared space complexity is [theta] (N²) and whose RMR complexity is claimed to be [omicron] (N). Hadzilacos posed as an open problem, the development of a linear time and space algorithm that uses only bounded shared variables and only simple read and write instructions. As a solution to the open problem, Jayanti et al. presented a space efficient adaptation of the above algorithm that uses only [theta] (N) shared space and inherited the claim that the RMR complexity is [omicron] (N) We show that both of these algorithms are of RMR complexity [omega] (N²) and thus demonstrate that both claims are erroneous. So, the open problem posed by Hadzilacos is still open.
    URI
    http://hdl.handle.net/10342/4516
    Subject
     Computer science; Distributed algorithm; Distributed system; Group mutual exclusion; Mutual exclusion 
    Date
    2014
    Citation:
    APA:
    He, Yuan. (January 2014). Group Mutual Exclusion in Linear Time and Space (Master's Thesis, East Carolina University). Retrieved from the Scholarship. (http://hdl.handle.net/10342/4516.)

    Display/Hide MLA, Chicago and APA citation formats.

    MLA:
    He, Yuan. Group Mutual Exclusion in Linear Time and Space. Master's Thesis. East Carolina University, January 2014. The Scholarship. http://hdl.handle.net/10342/4516. September 27, 2023.
    Chicago:
    He, Yuan, “Group Mutual Exclusion in Linear Time and Space” (Master's Thesis., East Carolina University, January 2014).
    AMA:
    He, Yuan. Group Mutual Exclusion in Linear Time and Space [Master's Thesis]. Greenville, NC: East Carolina University; January 2014.
    Collections
    • 2017-2018 Open Access Publishing Fund
    • Computer Science
    • Master's Theses
    Publisher
    East Carolina University

    xmlui.ArtifactBrowser.ItemViewer.elsevier_entitlement

    East Carolina University has created ScholarShip, a digital archive for the scholarly output of the ECU community.

    • About
    • Contact Us
    • Send Feedback