2021/11/17 by Joshua J. Daymude, Daymude, Joshua J., Andréa W. Richa +3 · 2 citations
Computer Science · #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2111.09449
openalex publication_date 2021/11/17 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
Mutual exclusion is a classical problem in distributed computing that\nprovides isolation among concurrent action executions that may require access\nto the same shared resources. Inspired by algorithmic research on distributed\nsystems of weakly capable entities whose connections change over time, we\naddress the local mutual exclusion problem that tasks each node with acquiring\nexclusive locks for itself and the maximal subset of its "persistent" neighbors\nthat remain connected to it over the time interval of the lock request. Using\nthe established time-varying graphs model to capture adversarial topological\nchanges, we propose and rigorously analyze a local mutual exclusion algorithm\nfor nodes that are anonymous and communicate via asynchronous message passing.\nThe algorithm satisfies mutual exclusion (non-intersecting lock sets) and\nlockout freedom (eventual success with probability 1) under both\nsemi-synchronous and asynchronous concurrency. It requires\n\O(\Δ) memory per node and messages of size \Θ(1), where\n\Δ is the maximum number of connections per node. We conclude by\ndescribing how our algorithm can implement the pairwise interactions assumed by\npopulation protocols and the concurrency control operations assumed by the\ncanonical amoebot model, demonstrating its utility in both passively and\nactively dynamic distributed systems.\n