On the Runtime of Local Mutual Exclusion for Anonymous Dynamic Networks
Abstract
Algorithms for mutual exclusion aim to isolate potentially concurrent accesses to the same shared resources. Motivated by distributed computing research on programmable matter and population protocols where interactions among entities are often assumed to be isolated, Daymude, Richa, and Scheideler (SAND‘22) introduced a variant of the local mutual exclusion problem that applies to arbitrary dynamic networks: each node, on issuing a lock request, must acquire exclusive locks on itself and all its persistent neighbors, i.e., the neighbors that remain connected to it over the duration of the lock request. Assuming adversarial edge dynamics, semi-synchronous or asynchronous concurrency, and anonymous nodes communicating via message passing, their randomized algorithm achieves mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1). However, they did not analyze their algorithm’s runtime. In this paper, we prove that any node will successfully lock itself and its persistent neighbors within open rounds of its lock request in expectation, where is the number of nodes in the dynamic network, is the maximum degree of the dynamic network, rounds are normalized to the execution time of the “slowest” node, and “closed” rounds when some persistent neighbors are already locked by another node are ignored (i.e., only “open” rounds are considered).
Keywords and phrases:
Mutual exclusion, dynamic networks, message passing, concurrencyFunding:
Anya Chaturvedi: NSF (CCF-2312537) and U.S. ARO (MURI W911NF-19-1-0233).Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Distributed algorithms ; Theory of computation Concurrency ; Software and its engineering Mutual exclusionEditors:
Kitty Meeks and Christian ScheidelerSeries and Publisher:

1 Introduction
The algorithmic theory of dynamic networks formally characterizes distributed systems of processes (or nodes) whose connections change – periodically, randomly, or even adversarially – over time. Using models like time-varying graphs (TVGs) [10, 13], theoreticians have successfully obtained algorithms for many core distributed computing problems including broadcast [11, 12, 34, 32], consensus and agreement [16, 7, 30], leader election [27, 2], counting [31, 14, 19, 29, 20], and more (see [10, 3] for surveys). However – with relatively few exceptions [11, 22, 25, 27] – an overwhelming majority of these algorithms assume synchronous concurrency in which algorithm executions alternate between stages of node computation and instants of network dynamics.
Towards a deeper understanding of concurrency control in dynamic networks, Daymude, Richa, and Scheideler proposed a variant of the local mutual exclusion problem in dynamic anonymous networks [17] in which anonymous nodes of a dynamic network must lock themselves and their persistent neighbors (i.e., those that remain connected throughout the duration of the lock request) before entering their “critical sections” (i.e., before doing an actual action execution). Their randomized algorithm for Lock and Unlock primitives achieves mutual exclusion (non-intersecting lock sets) and lockout freedom (every lock request eventually succeeds with probability 1) even when nodes are anonymous, operate under asynchronous concurrency, and experience edge dynamics concurrently with their computation. Thus, distributed algorithms for dynamic networks can first be designed and analyzed for the sequential setting in which at most one node is active per time, and then – using this locking mechanism to isolate concurrently executed actions and dynamics – can be directly simulated in the asynchronous setting.
However, that algorithm is missing runtime analysis, obscuring the overhead that other algorithms would incur by using this lock-based concurrency control. In this paper, we address this gap, proving an expectation bound on the time any node waits from issuing its lock request to obtaining locks on itself and its persistent neighbors. This analysis requires minor but nontrivial refinements to both the model (specifically, the model is now described in terms of adversarial fairness over node activations, rather than over individual enabled actions) and the algorithm (to close loopholes that allow an adversary to achieve arbitrarily large but finite runtimes), so we also reprove the algorithm’s mutual exclusion and lockout freedom guarantees w.r.t. these changes.
Our Contributions.
We summarize our main results as follows:
-
To support our runtime analysis, we slightly refine the assumptions on adversarial fairness and parts of the local mutual exclusion algorithm of [17]. We then prove that the refined algorithm still satisfies mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1).
-
We prove that, using this (refined) local mutual exclusion algorithm, any node issuing a lock request will obtain locks on itself and its persistent neighbors within open rounds in expectation, where is the number of nodes in the dynamic network, is the maximum degree of the dynamic network, rounds can be viewed as normalized to the execution time of the “slowest” node, and open rounds are those in which none of the node’s persistent neighbors are already locked by some other node, prohibiting progress.
1.1 Related Work
Since its introduction [21], the mutual exclusion problem has been one of the most widely-studied problems in parallel and distributed computing. Here, we briefly situate the variant of the local mutual exclusion problem introduced in [17] and refer the interested reader to their related work section for a detailed literature review. Many past works solve mutual exclusion or a related problem for message passing systems on static network topologies. For example, the arrow protocol [18, 33] and its recent improvements [26, 28] use a token-passing scheme that requires only constant memory per node, and more recent results address mutual exclusion directly for fully anonymous systems [35]. However, these do not immediately apply to dynamic networks. Mutual exclusion and contention resolution algorithms for mobile ad hoc networks (MANETs) handle node and edge dynamics but typically assume time-ordered, instantaneous transmissions that are more powerful than our communication model of asynchronous message passing [1, 4, 5, 15, 36, 37, 6, 8, 9]. Related works on self-stabilizing overlay networks also consider edge dynamics but assume nodes have identifiers [24].
In contrast, the local mutual exclusion problem variant and probabilistic algorithm of [17] explicitly consider the challenge of neighborhood mutual exclusion on a time-varying graph [10, 13] with adversarial edge dynamics where nodes are anonymous and operate under semi-synchronous or asynchronous concurrency. Since our primary goal is to analyze the locking time of this algorithm, we use the same computational model (Section 1.2), problem statement (Section 1.3), and algorithm (Section 2) – with some key minor modifications that we will highlight as we go. These changes support the clarity and tractability of our runtime analysis but do not fundamentally affect the strength or correctness of the results in [17].
1.2 Computational Model
Following the model in [17], we consider a distributed system comprising a fixed set of nodes . Each node is assumed to be anonymous, lacking a unique identifier, and has a local memory storing its state. Nodes communicate with each other via message passing over a communication graph whose topology changes over time. We model this topology using a time-varying graph where is the set of nodes, is a (static) set of undirected pairwise edges between nodes, is the lifetime of , and is the presence function indicating whether or not a given edge exists at a given time [13]. A snapshot of at time is the undirected graph and the neighborhood of a node at time is the set . For , the -th stage lasts from time to the instant just before time ; thus, the communication graph in stage is .
We assume that an adversary controls the presence function and that is the complete set of edges on nodes ; i.e., we do not limit which edges the adversary can introduce. The only constraint we place on the adversary’s topological changes is , where is the fixed number of ports per node. When the adversary establishes a new connection between nodes and , it must assign the endpoints of edge to open ports on and (and cannot do so if either node has no open ports). Node locally identifies using its corresponding port label and does likewise. For convenience of notation, we use to refer to the label of the port on node that is assigned to the edge ; this mapping of port labels to nodes is not available to the nodes. Edge endpoints remain in their assigned ports (and thus labels remain fixed) until disconnection, but nodes and may label differently and their labels are not known to each other a priori. Each node has a disconnection detector that adds the label of any port whose connection is severed to a set . A node’s disconnection detector provides it a snapshot of whenever it starts an action execution (see below) and then resets to .111Without this assumption, the adversary could disconnect an edge assigned to port of node and then immediately connect a different edge to , causing an indistinguishability issue for node .
Nodes communicate via message passing. A node sends a message to a neighbor by calling . Message remains in transit until either receives and processes at a later stage chosen by the adversary, or and are disconnected and is lost. Multiple messages in transit from to may be received by in a different order than they were sent. A node always knows from which port it received a given message.
All nodes execute the same distributed algorithm , which is a set of actions each of the form . An action’s label specifies its name. Its guard is a Boolean predicate determining whether a node can execute it based on the state of and any message in transit that may receive. An action is enabled for a node if its guard is true for ; a node is enabled if it has at least one enabled action. An action’s operations specify what a node does when executing the action, structured as (i) receiving at most one message chosen by the adversary, (ii) a finite amount of internal computation and state updates, and (iii) at most one call to per port label .
Each node executes its own instance of independently, sequentially (executing at most one action at a time), and reliably (meaning we do not consider crash or Byzantine faults). We assume an adversarial scheduler controls the timing of node activations. We primarily focus on semi-synchronous concurrency: in each stage, the adversary activates any (possibly empty) subset of enabled nodes concurrently and all resulting action executions complete within that stage. Asynchronous concurrency allows action executions to span arbitrary finite time intervals.
In [17], the adversary (scheduler) had a notion of fairness that ensured every continuously enabled action is eventually executed and every message in transit on a continuously existent edge is eventually processed. Here, we reinterpret this fairness assumption to support our runtime analysis in terms of node activations. From the perspective of this adversary, each enabled node has a nonempty set of enabled action executions it could enact, where is an action enabled for and – if is enabled by one or more messages in transit to – is any one of these messages. An enabled action execution is disabled for a node when is disabled for or is lost due to disconnection. This adversary must activate enabled nodes such that any continuously enabled node is eventually executed, but once the adversary activates an enabled node, one of that node’s enabled action executions is enacted uniformly at random.222Following the taxonomy in [23], the scheduler adversary would be (weakly) fair and have no restrictions on distribution, boundedeness nor enabledness. We discuss possible alternative approaches for the selection of the enabled action executions by a node, including that of (deterministic) FIFO queues at each node, in Section 4.
Finally, to bound the locking time of the local mutual exclusion algorithm, we define rounds, which can be informally viewed as normalized to the “slowest” node’s action execution. Let be the time that round starts, with . Define as the set of nodes that are enabled or currently executing an action at time . Then is the earliest time by which every node in has either been disabled or completed an action execution. Hence, round is the time interval ; note that one round may span multiple stages.
1.3 Local Mutual Exclusion
Like the classical mutual exclusion problem [21], the local mutual exclusion variant considered in [17] is defined w.r.t. a pair of primitives Lock and Unlock. A node issues a lock request by calling Lock; once acquired, it is assumed that a node eventually releases these locks by calling Unlock. Formally, each node stores a variable that is equal to if is unlocked, if has locked itself, and if is locked by . The lock set of a node in stage is which additionally includes itself if . Suppose that in stage , a node calls Lock to issue a lock request of its current closed neighborhood . This lock request succeeds at some later stage if stage is the first in which ; i.e., is the earliest stage in which obtains locks for itself and every persistent neighbor that remained connected to in stages through . In our context, a (randomized) algorithm solves local mutual exclusion if it implements Lock and Unlock while satisfying the following properties:
-
Mutual Exclusion. For all stages and all pairs of nodes , .
-
Lockout Freedom. Every issued lock request eventually succeeds with probability 1.
Since each node’s lock variable points to at most one node per time, it is impossible for two nodes’ lock sets to intersect, trivially satisfying the mutual exclusion property. But lockout freedom is more elusive, especially in the dynamic setting.
2 Algorithm for Local Mutual Exclusion
The randomized algorithm for local mutual exclusion given by Daymude, Richa and Scheideler [17] specifies actions for the Lock and Unlock primitives satisfying mutual exclusion and lockout freedom. In order for our runtime analysis of that algorithm (Section 3) to be coherent and self-contained, we reproduce their algorithm’s narrative description and pseudocode and highlight our minor modifications where relevant.
An execution of the Lock primitive by a node is organized into two phases: a preparation phase (Algorithm 1) in which determines and notifies the nodes it intends to lock, and a competition phase (Algorithm 2) in which attempts to lock all nodes in , contending with any other node for which . An execution of the Unlock primitive (Algorithm 3) by node is straightforward, simply notifying all nodes in that their locks are released. All local variables used in this algorithm are listed in Table 1 as they appear in the pseudocode. In a slight abuse of notation, and the subsets thereof represent both the nodes in the closed neighborhood of and the port labels of they are connected to. For clarity of presentation, the algorithm pseudocode allows a node to send messages to itself (via “port 0”) just as it sends messages to its neighbors, though in reality these self-messages would be implemented with in-memory variable updates.
Var. | Domain | Init. | Description |
---|---|---|---|
lock | if is unlocked, if has locked itself, and if is locked by | ||
state | , | The lock state of node | |
phase | The algorithm phase node is in | ||
Ports (nodes) intends to lock | |||
Ports via which has received ready(), ack-lock(), or ack-unlock() responses | |||
Port-outcome pairs of win() messages has received | |||
Ports (nodes) on hold for the competition to lock | |||
Ports (nodes) of applicants that can join the competition to lock | |||
Ports (nodes) of candidates competing to lock | |||
Port-priority pairs of the candidates | |||
Ports that were disconnected since last execution |
Nodes that issue lock requests are called initiators and nodes that are being locked or unlocked are participants; it is possible for a node to be an initiator and participant simultaneously. Initiators progress through a series of lock states associated with the state variable; participants advance through the algorithm’s phases as indicated by the phase variable. We first describe the algorithm from an initiator’s perspective and then describe the complementary participants’ actions. In the pseudocode, all actions executed by initiators (resp., participants) are marked with an (resp., ) superscript.
A special CleanUp helper function runs at the beginning of every action execution to ensure that nodes adapt to any disconnections affecting their variables that may have occurred since they last acted (already reflected in the current guard evaluations, which all disregard ports in ), so we omit the handling of these disconnections in the description in the next paragraphs. Note that this is a small modification of the original algorithm in [17], where CleanUp appeared as both a helper function and its own action; we eliminated the standalone action in this version of the algorithm because, in the context of runtime analysis, the adversary could abuse this standalone action to drive up the number of rounds without making any real progress.333In addition to the changes with respect to the CleanUp function, a typo in the guard of the pseudocode for CheckPrioritiesP was corrected in this version of the algorithm.
When an initiator calls Lock, it advances to the prepare state, sets to all nodes in its closed neighborhood , and then sends prepare() messages to all nodes of . Once it has received ready() responses from all nodes of , it advances to the compete state and joins the competitions for each node in by sending request-lock() messages to all nodes of , where is a priority chosen uniformly at random from , where . It then waits for the outcomes of these competitions. If it receives at least one win(false) message, it lost this competition and must compete again. Otherwise, if all responses are win(true), it advances to the win state and sends set-lock() messages to all nodes of . Once it has received ack-lock() responses from all nodes of , it advances to the locked state indicating now represents the lock set . Note that taking incurs messages of size , an increase from the -message size in [17], for . This is necessary, however, to guarantee a polynomial bound on the number of open competition trials it takes in expectation for a node to win, as already pointed out in [17].
A participant is responsible for coordinating the competition among all initiators that want to lock . To delineate successive competitions, distinguishes among initiators that are candidates in the current competition, applicants that may join the current competition, and those that are on hold for the next competition. When receives a prepare() message from an initiator , it either puts on hold (i.e., ) if a competition is already underway or adds as an applicant (i.e., ), advances to the prepare phase and replies ready() otherwise. Participant promotes its applicants to candidates (i.e., ) when receives their request-lock() messages and advances to the compete phase. Once all such messages are received from the competition’s candidates, notifies the one with the unique highest priority of its success and all others of their failure (or, in the case of a tie, all candidates fail). A winning competitor is removed from the candidate set while all others remain to try again; once the candidate set is empty, promotes all initiators that were on hold to applicants. Finally, when receives a set-lock() message, it sets its lock variable accordingly and responds with an ack-lock() message.
3 Locking Time Analysis
In this section, we bound the locking time of the (refined) local mutual exclusion algorithm of Daymude, Richa, and Scheideler [17], i.e., the number of rounds elapsed from the time a node issues its lock request to the time it successfully obtains locks on itself and its persistent neighbors. We first characterize the set and maximum number of enabled action executions a node can have at any point in time (Lemmas 3–3), allowing us to bound the expected number of rounds for a continuously enabled action execution to either be executed or become disabled (Lemma 3).
We then turn to the analysis of competition trials, i.e., the intervals in which an initiator sends a random priority to its participants, waits for those participants to receive priorities from all their competing initiators, and then is informed of whether it won (with the unique highest priority) over all its participants. As is standard in mutual exclusion analyses, our locking time for an initiator ignores any round during which some participant of an initiator is already locked by another node , prohibiting from making progress until unlocks ; we call such a round a closed round for node . We call any round that is not closed an open round for node (Definition 3). Lemma 3 bounds the expected number of open rounds spent within a single competition trial and Theorem 7 analyzes the number of competition trials a node needs to participate in before it will win one, together yielding the locking time bound of open rounds in expectation.
Throughout this analysis, we categorize actions as either Receive actions (e.g., ReceivePrepareP, ReceiveReadyI) or Check actions (e.g., CheckStartI, CheckPrioritiesP); we also categorize them as either initiator actions or participant actions depending on the role of nodes that execute them.
Lemma 1.
At most one initiator Check action is enabled per node per time; moreover, no enabled initiator Check action is ever disabled.
Proof.
Initiator Check actions’ guards have two conditions: one requiring the node’s state to have a particular value (e.g., in CheckStart) and another requiring equality between the set of neighbors the node expects to receive messages from and the set of neighbors it has actually received messages from so far, ignoring disconnections (e.g., in CheckStart). Each initiator Check action requires a different state value, so at most one can be enabled for any given node at a time. Moreover, a node’s state variable can only be modified by that node’s execution of an initiator Check action. So an enabled initiator Check action can’t be disabled due to a state change. Otherwise, for a node with an enabled initiator Check action, the received and expected message sets are equal (less disconnections). Once they are equal, there cannot be any additional messages to receive; moreover, any disconnections are ignored by both sets symmetrically. So once these two sets are equal less disconnections, they remain equal less disconnections and cannot cause the initiator Check action to be disabled.
Recall from Section 1.2 that an enabled node has one or more enabled action executions – where is an action enabled for and is any one of the messages in transit to enabling , if applicable – and when an enabled node is activated, the adversary selects one of its enabled action executions to execute uniformly at random.
Lemma 2.
Any node has at most enabled action executions at any given time.
Proof.
Consider any node . In our algorithm, there are two kinds of enabled action executions : those where is a Check action (with no associated message ) and those where is a Receive action and is a message in transit to that is enabling . By Lemma 3, can have at most one initiator Check action enabled per time. Additionally, there is only one participant Check action, CheckPrioritiesP. So can have at most two enabled action executions where is a Check action at any given time.
Observe that the number of messages in transit to upper bounds its current number of enabled action executions where is a Receive action. Node has at most neighbors, and Lemma 11 of [17] guarantees that there are at most two messages in transit between and any one of these neighbors at any time. Thus, including the messages sends to itself, can have at most enabled action executions where is a Receive action per time. Combined, this yields a total of at most enabled action executions.
We now show that our fairness assumption (Section 1.2) ensures every continuously enabled action execution will be executed in rounds in expectation.
Lemma 3.
Every enabled action execution is either executed or disabled within rounds of becoming enabled, in expectation.
Proof.
Consider any enabled action execution of any enabled node . If is disabled within expected rounds, we are done; otherwise, is continuously enabled for as long as remains enabled. By Lemma 3, is one of at most action executions enabled for node at any time, so has at least probability of being executed each time is activated.
Suppose became enabled for in round . In any round by which has neither been executed nor disabled, we know that . By definition, round will not end until has been activated at least once, and our fairness assumption ensures must eventually be activated. In the worst case, is only activated once per round, so has at least a probability of being chosen and executed per round. For Bernoulli trials with success probability , the expected number of trials to obtain a success is ; therefore, we conclude that is executed (or is disabled) by round in expectation.
Using Lemma 3, we will bound the expected number of rounds elapsed from when an initiator node begins a lock request in InitLockI to when it successfully obtains locks over its persistent neighbors in CheckDoneI. The preparation phase is straightforward: within rounds, in expectation, all persistent neighbors that sent prepare() messages to in InitLockI will execute ReceivePrepareP and either put on hold (if a competition over is ongoing) or add to their applicant sets and reply with a ready() message. Node will receive such ready() responses by executing ReceiveReadyI within another rounds in expectation and – if was not put on hold by any of its persistent neighbors – begin a competition by executing CheckStartI within another expected rounds.
It remains to analyze the competition phase where initiators generate random priorities, send them to their participants in request-lock() messages, wait to learn competition outcomes in the form of win() responses, and retry with a new random priority if they lose. We refer to each of these attempts as a competition trial:
Definition 4 (Competition Trial).
A competition trial of an initiator is an interval that starts from sending out request-lock() messages as a result of CheckStartI or CheckWinI action executions and ends when executes CheckWinI.
We first bound the runtime of one competition trial and later return to the question of how many competition trials an initiator has to participate in before it wins one, in expectation. More specifically, we are only interested in those competition trials in which there is a non-zero probability that an initiator can win. If some participant is already locked, no competition trial involving can progress until is unlocked, so we do not count these rounds towards the locking time.
Definition 5 (Open Competition Trial and Open Round).
A competition trial of an initiator is open if and only if , remains unlocked throughout the competition trial. All rounds elapsed during an open competition trial of an initiator are considered open for .
To the runtime of an (open) competition trial, we make use of the directed acyclic graph (DAG) defined in [17] that captures the dependencies among all nodes involved in concurrent locks at stage . An initiator node is competing if and only if , i.e., if has executed CheckStartI but has not yet received all win() messages needed to execute CheckWinI. Dependencies between competing initiators and participants at the start of stage are represented as a directed bipartite graph where is the set of competing initiators and is the set of participants. Some nodes belong to both partitions and their initiator and participant roles are considered distinct. For nodes and , the directed edge if and only if has not yet sent a win() message to in response to the latest request-lock() message from ; analogously, if and only if has not yet sent a request-lock() message to in response to the latest win() message from .
Lemma 6.
Every competing initiator resolves its competition trial within at most open rounds in expectation, where is the number of initiators along the longest path starting at node in DAG at stage .
Proof.
We define the dependency component of at the start of stage as the subgraph of reachable from . The height of this dependency component, is the number of nodes in the longest path from to a leaf node (i.e., a node with out-degree zero). Any dependency component is finite and acyclic because itself is finite and acyclic as shown in Lemma 4 of [17]. Additionally, due to the bipartite nature of , any path starting from in will alternate between initiator nodes and participant nodes.
Argue by induction on that any initiator (resp., participant) with dependency component of height takes at most open rounds in expectation to complete its next CheckWinI (resp., CheckPrioritiesP) action. In the base case of , contains only the node which is either an initiator or a participant. If is an initiator, then since it is in the DAG , it has previously sent out request-lock() messages to its participants; moreover, since is a leaf in , all those participants must have already sent win() responses back to . Thus, all corresponding action executions of ReceiveWinI are enabled for and by Lemma 3 must be executed or disabled within additional rounds, in expectation. This in turn enables CheckWinI for which likewise by Lemma 3 is executed within an expected additional rounds. Thus, if is an initiator, it executes its next CheckWinI action within open rounds, in expectation.
Otherwise, if is a participant, its presence in the DAG indicates only that some initiator is still competing for it. As a leaf in , is not waiting for any request-lock() messages from existing competing initiators, but it is possible that it is waiting for request-lock() messages from new initiators in its applicant set who have not yet become competing and joined the DAG. By Lemma 3, all participants of these new initiators must have received their prepare() messages within open rounds from stage ; these new initiators then receive the resulting ready() messages during ReceiveReadyI and respond with request-lock() messages via CheckStartI within another open rounds; and finally – by the same logic as for initiators – must receive all request-lock() messages via ReceiveRequestP and execute CheckPrioritiesP within another rounds, totaling open rounds in expectation. This concludes the base case.
Now consider any node with dependency component whose height is , and suppose by induction that all nodes whose dependency components have heights will complete their next Check action within open rounds, in expectation. By the induction hypothesis (using height 1), all leaves of will execute their next Check actions within open rounds, in expectation. Let be the first stage after which all leaves of have completed at least one Check action. We claim that is a subgraph of with a strictly smaller height. Supposing this claim holds, then the induction hypothesis guarantees that will complete its next Check action within at most open rounds of stage in expectation, which is open rounds from stage , concluding the induction argument. Any dependency component rooted at an initiator has height – since paths in the DAG alternate between initiators and participants – proving the lemma.
It remains to prove the claim. Certainly any node in whose dependency path from has not changed since stage cannot have new out-edges in stage , since this requires executing a Check action which would have reversed the edge between and its parent(s). On the other hand, any node in that did execute a Check action between stages and cannot be in , since that Check action reversed the edge between and its parent(s), disrupting any path from to , which cannot be reestablished without also executing a Check action. But since stage occurs immediately after some leaf of completes its first Check action and there was a path of dependencies from to , has not executed its next Check action by the start of stage . Thus, since no new out-edges are added to before stage and every leaf of has executed a Check action by stage , is a subgraph of with strictly smaller height, as desired.
The preceding lemma bounds the runtime of any one (open) competition trial; in our main theorem, we combine this with the expected number of trials any initiator has to participate in before winning (i.e., drawing the unique highest priority over all participants) to obtain an upper bound on the locking time. We assume the set of priorities is size , requiring memory per node and messages of size .
Theorem 7.
For , it takes open rounds in expectation for an initiator to successfully complete its Lock operation, with memory size per node and messages of size .
Proof.
We wish to calculate the number of open rounds it takes in expectation for an initiator to complete its Lock operation, i.e., the time it takes to go from InitLockI to CheckDoneI. Lemma 3 implies that it takes at most expected number of rounds for a competing initiator to resolve its competition trial (since is an upper bound on the number of initiators).
Apart from the four actions involved in a competition trial that we already account for in Lemma 3, there are seven additional actions (namely, InitLockI, ReceivePrepareP, ReceiveReadyI, CheckStartI, ReceiveSetLockP, ReceiveAckLockI and CheckDoneI) on the path from InitLockI to CheckDoneI that will each take at most rounds in expectation to execute, to a total of at most rounds in expectation. It remains to bound the number of trials a competing initiator requires to win the competition, which we denote by . To calculate the expected value of , we utilize the lower bound on the probability of a node winning a trial as calculated in Lemma 7 of [17], namely . It follows that the expected number of competition trials is bounded by
(1) |
Putting it altogether, the expected number of rounds to complete a Lock operation for an initiator is upper bounded by
(2) | ||||
(3) | ||||
(4) | ||||
(5) |
Equation 4 follows from the Taylor series expansion of , by which we get , for , while Equation 5 follows from picking , where is positive constant.
The nodes only need memory proportional to the maximum number of ports and to , and messages exchanged in the algorithm are of size at most .
By definition, lockout freedom requires that every lock request must eventually succeed with probability 1. Let be the random variable that indicates the number of rounds for an initiator node to complete its lock operation. Theorem 7 states that , thus trivially implying that also has to be finite (with probability 1), matching the lockout freedom guarantee of [17].
Corollary 8.
The local mutual exclusion algorithm satisfies lockout freedom.
If is a constant, which is the case in several applications of interest including those addressed in [17], we have the following result.
Corollary 9.
If , the algorithm takes open rounds in expectation for an initiator to successfully complete its Lock operation.
The proof of Lemma 12 in [17] gives us a construction to move from an asynchronous schedule to a semi-synchronous schedule . This construction preserves the causal relationship between action executions while adding in filler time steps (stages) to make sure that each node executes only one action per stage. Combining this construction with our Theorem 7 extends our locking time bound to the asynchronous setting.
Corollary 10.
Under asynchronous concurrency, the algorithm satisfies mutual exclusion, lockout freedom, and has a locking time of open rounds in expectation.
4 Conclusion
In this paper, we analyzed the locking time of a prior algorithm for a variant of local mutual exclusion [17] that enables anonymous, message-passing nodes to isolate concurrent actions involving their persistent neighborhoods despite dynamic network topology. Specifically, we proved that a minor refinement of this algorithm guarantees that any node issuing a lock request will obtain its locks within open rounds, in expectation, where is the number of nodes in the dynamic network, is the maximum degree of the dynamic network, rounds that can be viewed as normalized to the execution time of the “slowest” node, and open rounds are those in which a node’s neighbors are not already locked by some other node, prohibiting progress. We note that the minor modifications introduced to the algorithm in Section 2 and to the scheduler in Section 1.2 are necessary formalizations for runtime analysis, since without them, one can only show eventual termination of the algorithm in [17].
The adversarial scheduler considered in this paper selects an arbitrary subset of enabled nodes at any stage, and each activated node randomly selects one of its enabled actions executions. An alternative that would yield similar expected times as the ones proven here would be to have each node keep a FIFO queue of its enabled action executions, where action executions are inserted into the queue, and executed, in the order they become enabled, and are removed from the queue if they get disabled. Note that, while the choice of action execution now becomes deterministic, the runtime bound of the algorithm would still be probabilistic, given the use of randomization in the algorithm. Another alternative approach would be to change the guards of the actions to induce a set of “priorities” over the enabled action executions (guaranteeing that certain action executions would only be enabled after “higher priority” action executions are all disabled). However, this does not work within the structure of actions of the algorithm in [17], since any fixed priority approach applied to the current algorithmic structure leads to the “starvation” of some action executions and prevents progress.
In future work, it would be interesting to establish a lower bound revealing whether this locking time bound is tight; if so, it remains an open question whether any algorithm exists for local mutual exclusion whose locking time is free of dependence on the size of the dynamic network.
References
- [1] Hagit Attiya, Alex Kogan, and Jennifer L. Welch. Efficient and Robust Local Mutual Exclusion in Mobile Ad Hoc Networks. IEEE Transactions on Mobile Computing, 9(3):361–375, 2010. doi:10.1109/TMC.2009.137.
- [2] John Augustine, Gopal Pandurangan, and Peter Robinson. Fast Byzantine Leader Election in Dynamic Networks. In Distributed Computing, volume 9363 of Lecture Notes in Computer Science, pages 276–291, Berlin, Heidelberg, 2015. Springer. doi:10.1007/978-3-662-48653-5_19.
- [3] John Augustine, Gopal Pandurangan, and Peter Robinson. Distributed Algorithmic Foundations of Dynamic Networks. ACM SIGACT News, 47(1):30, 2016.
- [4] Roberto Baldoni, Antonino Virgillito, and Roberto Petrassi. A distributed mutual exclusion algorithm for mobile ad-hoc networks. In Proceedings ISCC 2002 Seventh International Symposium on Computers and Communications, pages 539–544, 2002. doi:10.1109/ISCC.2002.1021727.
- [5] Mahfoud Benchaïba, Abdelmadjid Bouabdallah, Nadjib Badache, and Mohamed Ahmed-Nacer. Distributed Mutual Exclusion Algorithms in Mobile Ad Hoc Networks: An Overview. ACM SIGOPS Operating Systems Review, 38(1):74–89, 2004. doi:10.1145/974104.974111.
- [6] Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. Adversarial Contention Resolution for Simple Channels. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 325–332, 2005. doi:10.1145/1073970.1074023.
- [7] Martin Biely, Peter Robinson, and Ulrich Schmid. Agreement in Directed Dynamic Networks. In Structural Information and Communication Complexity, volume 7355 of Lecture Notes in Computer Science, pages 73–84, Berlin, Heidelberg, 2012. Springer. doi:10.1007/978-3-642-31104-8_7.
- [8] Federico Cali, Marco Conti, and Enrico Gregori. IEEE 802.11 Protocol: Design and Performance Evaluation of an Adaptive Backoff Mechanism. IEEE Journal on Selected Areas in Communications, 18(9):1774–1786, 2000. doi:10.1109/49.872963.
- [9] John I. Capetanakis. Tree Algorithms for Packet Broadcast Channels. IEEE Transactions on Information Theory, 25(5):505–515, 1979. doi:10.1109/TIT.1979.1056093.
- [10] Arnaud Casteigts. A Journey through Dynamic Networks (with Excursions), 2018. HDR, available online at https://hal.archives-ouvertes.fr/tel-01883384/.
- [11] Arnaud Casteigts, Paola Flocchini, Bernard Mans, and Nicola Santoro. Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility. In Theoretical Computer Science, volume 323 of IFIP Advances in Information and Communication Technology, pages 111–124, Berlin, Heidelberg, 2010. Springer. doi:10.1007/978-3-642-15240-5_9.
- [12] Arnaud Casteigts, Paola Flocchini, Bernard Mans, and Nicola Santoro. Shortest, Fastest, and Foremost Broadcast in Dynamic Networks. International Journal of Foundations of Computer Science, 26(04):499–522, 2015. doi:10.1142/S0129054115500288.
- [13] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-Varying Graphs and Dynamic Networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012. doi:10.1080/17445760.2012.668546.
- [14] Maitri Chakraborty, Alessia Milani, and Miguel A. Mosteiro. A Faster Exact-Counting Protocol for Anonymous Dynamic Networks. Algorithmica, 80(11):3023–3049, 2018. doi:10.1007/s00453-017-0367-4.
- [15] Yu Chen and Jennifer L. Welch. Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks. Journal of Parallel and Distributed Computing, 65(9):1072–1089, 2005. doi:10.1016/j.jpdc.2005.03.009.
- [16] Étienne Coulouma and Emmanuel Godard. A Characterization of Dynamic Networks Where Consensus Is Solvable. In Structural Information and Communication Complexity, volume 8179 of Lecture Notes in Computer Science, pages 24–35, Cham, 2013. Springer. doi:10.1007/978-3-319-03578-9_3.
- [17] Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), volume 221 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:19, Virtual Event, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SAND.2022.12.
- [18] Michael J. Demmer and Maurice P. Herlihy. The arrow distributed directory protocol. In Shay Kutten, editor, Distributed Computing, volume 1499 of Lecture Notes in Computer Science, pages 119–133, 1998. doi:10.1007/BFb0056478.
- [19] Giuseppe Di Luna and Roberto Baldoni. Non Trivial Computations in Anonymous Dynamic Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015), volume 46 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:16, Rennes, France, 2016. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPICS.OPODIS.2015.33.
- [20] Giuseppe A. Di Luna and Giovanni Viglietta. Optimal Computation in Leaderless and Multi-Leader Disconnected Anonymous Dynamic Networks. In 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:20, L’Aquila, Italy, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2023.18.
- [21] E. W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the ACM, 8(9):569, 1965. doi:10.1145/365559.365617.
- [22] Swan Dubois, Mohamed-Hamza Kaaouachi, and Franck Petit. Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems. In Stabilization, Safety, and Security of Distributed Systems, volume 9212 of Lecture Notes in Computer Science, pages 51–66, Cham, 2015. Springer. doi:10.1007/978-3-319-21741-3_4.
- [23] Swan Dubois and Sébastien Tixeuil. A taxonomy of daemons in self-stabilization, 2011. arXiv:1110.0334.
- [24] Michael Feldmann, Christian Scheideler, and Stefan Schmid. Survey on Algorithms for Self-stabilizing Overlay Networks. ACM Computing Surveys, 53(4):74:1–74:24, 2020. doi:10.1145/3397190.
- [25] Paola Flocchini, Matthew Kellett, Peter C. Mason, and Nicola Santoro. Searching for Black Holes in Subways. Theory of Computing Systems, 50(1):158–184, 2012. doi:10.1007/s00224-011-9341-8.
- [26] Abdolhamid Ghodselahi and Fabian Kuhn. Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks. In 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:16, 2017. doi:10.4230/LIPICS.DISC.2017.22.
- [27] Rebecca Ingram, Patrick Shields, Jennifer E. Walter, and Jennifer L. Welch. An asynchronous leader election algorithm for dynamic networks. In 2009 IEEE International Symposium on Parallel & Distributed Processing, pages 1–12, Rome, Italy, 2009. IEEE. doi:10.1109/IPDPS.2009.5161028.
- [28] Pankaj Khanchandani and Roger Wattenhofer. The Arvy Distributed Directory Protocol. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 225–235, 2019. doi:10.1145/3323165.3323181.
- [29] Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations. Journal of the ACM, 67(2):1–17, 2020. doi:10.1145/3385075.
- [30] Fabian Kuhn, Yoram Moses, and Rotem Oshman. Coordinated consensus in dynamic networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 1–10, San Jose, CA, USA, 2011. ACM. doi:10.1145/1993806.1993808.
- [31] Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Naming and Counting in Anonymous Unknown Dynamic Networks. In Stabilization, Safety, and Security of Distributed Systems, volume 8255 of Lecture Notes in Computer Science, pages 281–295, Cham, 2013. Springer. doi:10.1007/978-3-319-03089-0_20.
- [32] Garrett Parzych and Joshua J. Daymude. Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast. In 38th International Symposium on Distributed Computing (DISC 2024), volume 319 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:18, Madrid, Spain, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2024.35.
- [33] Kerry Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1):61–77, 1989. doi:10.1145/58564.59295.
- [34] Michel Raynal, Julien Stainer, Jiannong Cao, and Weigang Wu. A Simple Broadcast Algorithm for Recurrent Dynamic Systems. In 2014 IEEE 28th International Conference on Advanced Information Networking and Applications, pages 933–939, Victoria, BC, Canada, 2014. IEEE. doi:10.1109/AINA.2014.115.
- [35] Michel Raynal and Gadi Taubenfeld. Mutual exclusion in fully anonymous shared memory systems. Information Processing Letters, 158:105938, 2020. doi:10.1016/j.ipl.2020.105938.
- [36] Bharti Sharma, Ravinder Singh Bhatia, and Awadhesh Kumar Singh. A Token Based Protocol for Mutual Exclusion in Mobile Ad Hoc Networks. Journal of Information Processing Systems, 10(1):36–54, 2014. doi:10.3745/JIPS.2014.10.1.036.
- [37] Jennifer E. Walter, Jennifer L. Welch, and Nitin H. Vaidya. A Mutual Exclusion Algorithm for Ad Hoc Mobile Networks. Wireless Networks, 7:585–600, 2001. doi:10.1023/A:1012363200403.