Timing-Based Mutual Exclusion^{∗}

Nancy Lynch^{†}  Nir Shavit^{‡}

Abstract

Known asynchronous n-process deadlock-free mutual exclusion algorithms require O(n) read/write registers and O(n) operations to access the critical region, rendering them impractical for large scale applications.

Burns and Lynch have shown that n registers are necessary for solving this problem, in the asynchronous setting.

This paper examines the benefits that can be obtained by using timing information in mutual exclusion algorithms. First, a simple and efficient timing-based mutual exclusion algorithm is given. This algorithm always guarantees mutual exclusion (i.e., even when run asynchronously), and also avoids deadlock in case certain (realistic) inexact timing constraints are met. The algorithm uses only two shared read/write registers (a total of log n+1 bits), thus “overcoming” the n register lower bound for asynchronous algorithms. It is proved that the problem cannot be solved with only one shared register, so that this algorithm is optimal in terms of the number of registers.

Second, a lower bound is proved for the time complexity of any deadlock-free mutual exclusion protocol, as a function of the number of shared registers it employs. This bound shows that the algorithm described above is near optimal, in terms of time complexity. Finally, it is shown that two natural ways of weakening the timing assumptions lead (unfortunately) to an n register lower bound.

1 Introduction

Although current-day multiprocessors provide sophisticated synchronization primitives for mutual exclusion, situations that require a register-based exclusion algorithm continue to arise [1, 2]. Known mutual exclusion algorithms [3, 15, 16, 18] require that both the number of read/write registers and the number of operations a process performs to access the critical region be at least equal to the total number of processes in the system. The lower bound of Burns and Lynch [3] implies that this linear complexity is optimal for deterministic algorithms, even if multi-writer registers are used. This implies that such algorithms cannot be expected to perform well in systems that support thousands of concurrent processes [1, 2].

Recently, several researchers [4, 5] have proposed ways of overcoming the linear lower bound on the number of operations a process needs to perform. For example, employing operating system support in a sophisticated way at process creation time, Merritt and Taubenfeld provide an algorithm that limits the number of operations by a process to depend only on the number of processes concurrently accessing the critical region. However, in both of these cases, the number of shared registers the algorithm requires is still at least equal to the total number of processes in the system. Also, using randomization, and based on the work of Lynch and Saias [13], Kushilevits and Rabin [14] offer a new (but rather involved) algorithm that employs randomization to achieve fair mutual exclusion using a single O(log log n)-bit shared register. However, this solution uses a powerful n-process Test-and-Set shared variable, not a read/write register.

∗This work was supported by ONR contracts N00014-85-K-0168 and N00014-91-J-1046, by NSF grants CCR-8611442 and CCR-8915206, by DARPA contracts N00014-87-K-0825 and N00014-89-J-1988, and by Draper Laboratories grant DL-H-441640

†Laboratory for Computer Science, MIT, Cambridge, MA 02139.

‡Laboratory for Computer Science, MIT, and Tel-Aviv University, Tel-Aviv 69978, Israel.

In this paper, we consider the mutual exclusion problem in a real-time setting. More particularly, we examine the benefits that can be obtained by using available timing information in mutual exclusion algorithms.

Fischer [10] appears to have been the first to propose overcoming the Burns-Lynch lower bound of n shared registers for deadlock-free mutual exclusion by assuming timing constraints. He has presented a truly simple mutual exclusion algorithm that uses only a single shared multi-writer register. However, his algorithm has a major drawback: it fails to guarantee mutual exclusion if the timing constraints are not met. This is also the drawback of the elegant timing-based algorithm of Alur and Taubenfeld [6]. Ideally, a timing-based algorithm should not depend on its timing constraints to guarantee basic safety properties, but only to ensure liveness and performance properties.

In this paper, we give a simple and efficient timing-based mutual exclusion algorithm that always guarantees mutual exclusion (i.e., even when run asynchronously), and also avoids deadlock in case certain inexact timing constraints are met. Specifically, we assume that the times between successive steps of the same process are always in some known interval, [c_{1}, c_{2}], of real times. This assumption is realistic in the real-time setting, if processes do not get swapped out during the time when they are executing the protocol, or even if they do get swapped out, but the underlying processor scheduling algorithm ensures approximately predictable execution speeds. (In fact, the algorithms we present require that processes do not get swapped out only between two specific lines of code, and not throughout the complete protocol.) The algorithm uses only two shared read/write registers (a total of log n + 1 shared bits), thus “overcoming” the n register lower bound for asynchronous algorithms. We also prove that the problem cannot be solved with only one shared register, so that our algorithm is optimal in terms of the number of registers.

Next, we prove a lower bound for the time complexity of any deadlock-free mutual exclusion protocol, as a function of the number of shared registers it employs. The proof uses the techniques of [3], extended to the real-time setting. This bound shows that our algorithm is near optimal, in terms of time complexity.

Finally, we show that two natural ways of weakening the timing assumptions lead, unfortunately, to an n register lower bound. Specifically, if we assume that the time bounds [c_{1}, c_{2}] are fixed, and always hold, but are unknown to the processes, or that the timing conditions are only eventually met, then we obtain a lower bound of n on the number of read/write registers required.

All of the results are presented formally, in terms of the timed automaton model of Merritt, Modugno and Tuttle [7].

[[[We also show that n read/write registers are necessary if one replaces the timing assumptions by other well established assumptions such as the availability of coins (randomization), or stochastic assumptions on scheduling (as in exponential backoff schemes [?]). I will leave this additional stuff out regarding randomization etc, but in the summer I will try to add them in to make the story complete]]]

2 I/O Automata Protocols and Time

[[[ Comment: I have decided to slice here and leave it all to the full paper. Since I cut out most of the proofs, we are OK for the abstract. ]]]

[[[ old comment by Nir: In this section, we present the definitions for the underlying formal model. In

Process i: repeat forever

remainder region trying region critical region exit region

end repeat;

Figure 1: Program of Process i.

particular, we define I/O automata and timed automata. We also show how we model shared memory protocols. [[[ Comment: Nancy, I agree with the idea of using a definition of Timed I/O Automata that has regular automata as a special case. However, it would be best, at least in the extended abstract, to limit the model to half-3/4 ofa page. I will try to now create a truely UNCLEAN variant of what I mean, that takes little space (after all, cutting down space is what this paper is all about, ha ha). If I have time I will get back to cleaning it.]]]

We begin by summarizing some of the key definitions for the I/O automaton model. We refer the reader to [8, 9] for a complete presentation of the model and its properties.

An I/O automaton, A, consists of the following pieces: acts(A), a set of actions, classified as output, input and internal (input and output actions are called external); states(A), a set of states, including a distinguished subset, start(A), of start states; steps(A), a set of steps, where a step is defined to be a (state, action, state) triple; and part(A), a partition of the locally controlled (output and internal) actions into equivalence classes; the partition groups together actions that are to be thought of as under the control of the same underlying process.

An action π is said to be enabled in a state s′ provided that there is a step of the form (s′, π, s). An automaton is required to be input enabled, which means that every input action must be enabled in every state. [[[To model time, we define a boundmap mapping b for an I/O automaton A, associating a [[[]]] subinterval of [0, ∞) with the class of operations of any process, representing the range of possible lengths of time between successive times when this process “gets a chance” to perform an action.]]] [[[ add something to say non-zero]]]

[[[A timed execution fragment of an I/O automaton A is a (finite or infinite) sequence of alternating states and (action,time) pairs,

s_{0}, (π_{1}, t_{1}), s_{1}, (π_{2}, t_{2}), ... ,

where for every i, (s_{i−1}, (π_{i}, t_{i}), s_{i}) ∈ steps(A), the times t_{1}, t_{2},... are successively nondecreasing nonnegative real numbers, and if the sequence is finite, then it ends with a state.]]] An execution is an execution fragment with s_{0} ∈ start(A). Two events The schedule of an execution α is the subsequence of α consisting of all the events appearing in α, and the behavior of α is the subsequence consisting of all the external events. The schedules and behaviors of A are just those of the executions of A.

[[[Ordinary I/O automata are just a special case of timed automata, where the boundmap provides all intervals of the form [0, ∞) [?]. ]]] Concurrent systems are modeled [[[in the natural way as]]] compositions of I/O automata [8, 9].

2.1 Timed Automata

[[[Taken from mappings paper with Hagit.]]]

In this subsection, we augment the I/O automaton model to allow discussion of timing properties. The treatment here is similar to the one described in [?] and is a special case of the definitions proposed in [?].

A boundmap for an I/O automaton A is a a mapping that associates a closed subinterval of [0, ∞] with each class in part(A), where the lower bound of each interval is not ∞ and the upper bound is nonzero.^{1} Intuitively, the interval associated with a class C by the boundmap represents the range of possible lengths of time between successive times when C “gets a chance” to perform an action. We sometimes use the notation b_{ℓ}(C) to denote the lower bound assigned by boundmap b to class C, and b_{u}(C) for the corresponding upper bound. A timed automaton is a pair (A, b), where A is an I/O automaton and b is a boundmap for A.

We require notions of “timed execution”, “timed schedule” and “timed behavior” for timed automata, corresponding to executions, schedules and behaviors for ordinary I/O automata. These will all include time information. We begin by defining the basic type of sequence that underlies the definition of a timed execution.

De finition 2.1 A timed sequence (for an I/O automaton A) is a (finite or infinite) sequence of alternating states and (action,time) pairs,

s_{0}, (π_{1}, t_{1}), s_{1}, (π_{2}, t_{2}), ... ,

satisfying the following conditions.

1. The states s_{0}, s_{1}, ... are in states(A).

2. The actions π_{1}, π_{2},... are in acts(A).

3. The times t_{1}, t_{2},... are successively nondecreasing nonnegative real numbers.

4. If the sequence is finite, then it ends in a state s_{i}.

5. If the sequence is infinite then the times are unbounded.

For a given timed sequence, we use the convention that t_{0} = 0. For any finite timed sequence α, we define tend(α) to be the time of the last event in α, if α contains any (action,time) pairs, or 0, if α contains no such pairs. Also, we define send(α) to be the last state in α. We denote by ord(α) (the “ordinary” part of α) the sequence

s_{0}, π_{1}, s_{1}, π_{2}, ... ,

i.e., α with time information removed.

If i is a nonnegative integer and C ∈ part(A), we say that i is an initial index for C in α if s_{i} ∈ enabled(A, C) and either i = 0 or s_{i−1} ∈ disabled(A, C) or π_{i} ∈ C. Thus, an initial index for class C is the index of an event at which C becomes enabled; it indicates a point in α from which we will begin measuring upper and lower time bounds.

De finition 2.2 Suppose (A, b) is a timed automaton. Then a timed sequence α is a timed execution of (A, b) provided that ord(α) is an execution of A and α satisfies the following conditions, for each class C ∈ part(A) and every initial index i for C in α.

1In [?] the model is defined in a more general manner, to allow for open or semi-open intervals as the boundmaps.

1. If b_{u}(C) < ∞ then there exists j > i with t_{j} ≤ t_{i} + b_{u}(C) such that either π_{j} ∈ C or s_{j} ∈ disabled(A, C).

2. There does not exist j > i with t_{j} < t_{i} + b_{ℓ}(C) and π_{j} in C.

The first condition says that, starting from an initial index for C, within time b_{u}(C) either some action in C occurs or there is a point at which no such action is enabled. Note that if b_{u}(C) = ∞, no upper bound requirement is imposed. The second condition says that, again starting from an initial index for C, no action in C can occur before time b_{ℓ}(C) has elapsed. Note in particular that if a class C becomes disabled and then enabled once again, the lower bound calculation gets “restarted” at the point where the class becomes re-enabled.

[[[Here, we should look up MMT CONCUR 91, and generalize the definition to permit open intervals as bounds as well as closed intervals. With an upper-open interval with upper bound ∞, we can model eventual steps in the class.]]]

The timed schedule of a timed execution of a timed automaton (A, b) is the subsequence consisting of the (action,time) pairs, and the timed behavior is the subsequence consisting of the (action,time) pairs for which the action is external. The timed schedules and timed behaviors of (A, b) are just those of the timed executions of (A, b).

[[[Informally, our model of computation consists of a collection of sequential threads of control called processes that communicate through shared objects called registers. Formally, ]]]we model each timingdependent concurrent system as a single timed automaton (A, b), where A is a composition of ordinary I/O automata (possibly with some output actions hidden),[[[ and b is a boundmap. Details of the model will be presented in the full version of the paper. We refer the reader to [8, 9, 7, 20] for a complete presentation of the model and its properties.

[[[Comment: We need to define operations and say what it means for them to be concurrent and terminating.]]]

[[[Comment: Nancy, I do not agree that my way of stating all things in terms of separate automata has unfortunate consequences. One can easily enough define operations as pairs of invocation and matching response, and use tools such as sequential specification to formalize possible interactions. This would make our modeling of the system more ‘true to life.” However, it is not a big thing with me, and your proposal has proven itself in the past so why not.]]]

2 [[[I have not done anything above to model randomized algorithms. I suggest we not clutter up the main body of the paper with randomization issues - there is quite enough other stuff without it. Rather, let’s discuss extensions to the randomized case in the conclusions section (((((((OK, no problem))))))).]]]

3 The Mutual Exclusion Problem

We consider a system of n sequential threads of control called processes, which communicate through shared multi-writer, multi-reader atomic registers. Communication consists of read and write operations, each of which is assumed in this paper to be executed instantaneously. In the usual model for atomic registers each operation is separated into an invocation event and a response event, concurrent invocations are allowed, and it is assumed that every invocation eventually terminates in a matching response, in such a way as to produce the illusion of instantaneous operation. Our work applies to this setting, but we do not need to deal with this extra complication here.

2An equivalent way of looking at each system is as a composition of timed automata. An appropriate definition for a composition of timed automata is developed in [?], together with theorems showing the equivalence of the two viewpoints.

Formally, we model each such system as a single timed automaton [7] (A, b), where A is a composition of I/O automata [8], and b is a boundmap. We keep the discussion in this abstract informal and refer the interested reader to [8, 9, 7, 20] for a complete presentation of the model and its properties.

We view the program of every process as consisting of two distinguished regions: a remainder region and a critical region. Each process alternates between executing its remainder and its critical region. No process remains forever within any particular execution of its critical region, although it may remain forever in its remainder region. The mutual exclusion problem is to guarantee that the system does not enter a global state in which more than one process is executing its critical region [15].

To coordinate the entrance to the critical region, a trying region and an exit region of code are added to the program of each process as in Figure 1.

So, I let user_{i} be a timed automaton with states consisting of the value of one variable, called region, with values in {R, T, C, E}. There are outputs try_{i} and exit_{i}, and inputs crit_{i} and rem_{i}. The user respects the cyclic behavior (what should it do if the system does not respect the cyclic behavior?) In addition, there should be a liveness constraints: that a user in C eventually does an exit_{i}. We can do this using the upper bound of ∞, in a right-open interval, for the singleton class of exit_{i}. We don’t want to say that the user in R eventually does a try_{i}, however. Thus, the singleton class of try_{i} just has an interval [0, ∞] associated (meaning the action never has to occur. ]]]

The following safety property is required of any solution to the problem.

Mutual Exclusion: A system satisfies mutual exclusion if in any reachable system state, at most one user is in its critical region.

We also require that a process running alone will always get access to the critical region.

Weak Deadlock-Freedom: A system is weakly deadlock-free if in any execution, if a process’ trying region (resp. exit region) is concurrent only with other processes’ remainder regions, then its trying region (resp. exit region) terminates.

The following property guarantees progress, and will be required to hold only under certain conditions.

Deadlock-Freedom: A system is deadlock-free if the following are true in any execution.

1. If in some state, some user is in the trying region and no user is in the critical region, then subsequently some user enters the critical region.

2. If in some state, some user is in the exit region then subsequently some user enters the remainder region.

[[[The following lemma follows immediately from the above definitions:]]]

Lemma 3.1 If a system is deadlock-free then it is weakly deadlock-free.

We define a time-bounded version of the deadlock-freedom property. This involves putting an upper bound on the time processes can spend executing the added trying and exit regions of code. We define a number b to be an upper bound for a deadlock-free system providing that the deadlock freedom definition above holds if we replace “subsequently” with “within time at most b.”

1. If in some state, some user is in the trying region and no user is in the critical region, then within time at most b, some user enters the critical region.

2. If in some state, some user is in the exit region then within time at most b, some user enters the remainder region.

x, y: shared registers, initially y = 0;

repeat forever 0b: remainder exit_{i} L: x := i; 1: if y ≠ 0 then goto L; 2: y := 1; 3: if x ≠ i then goto L; 4a: critical entry_{i} 4b: critical exit_{i} 5: y := 0; 0a: remainder entry_{i} end repeat;

Figure 2: Algorithm 1: Lamport Style Mutual Exclusion – Code for Process i.

4 The Asynchronous Case

[[[(Formally,]]] the case where the system is a timed automaton with the boundmap assigning the interval [0, ∞] to all the processes.) The user automata also have this interval associated with the critical region. Note that the user automata will always have this interval, even later in the paper when the system has more interesting boundmap conditions.

4.1 Impossibility of Mutual Exclusion and Deadlock-Freedom, with Fewer than n Registers

The following theorem is due to Burns and Lynch [3].

Theorem 4.1 There is no asynchronous algorithm providing mutual exclusion with deadlock-freedom for n ≥ 2 processes, using fewer than n shared read/write registers.

4.2 A 2 Register Algorithm for Mutual Exclusion and Weak Deadlock-Freedom

Since Theorem 4.1 rules out asynchronous solutions for deadlock-free mutual exclusion with fewer than n shared registers, we will consider timing-based algorithms. A natural requirement for a timing-based mutual exclusion algorithm is that mutual exclusion and weak deadlock-freedom be guaranteed always, even if the timing assumptions are violated. We thus begin our development by showing that there exists an asynchronous 2-register algorithm for n ≥ 2, giving mutual exclusion and weak deadlock-freedom. This algorithm, which we call Algorithm 1, has a structure similar to some described by Lamport in [17]. The algorithm uses two shared registers, x and y. Each process P_{i} writes its index i into x, to indicate that it wishes to enter the critical region, and then checks register y to see if it might have just overwritten the value of some other process P_{j} that is attempting to enter. If there is such a process (i.e., if y = 1), P_{i} gives up, otherwise, it sets y for other processes and tests x to see if it has not been overwritten by some later process P_{j} attempting to enter the critical region. If x is still set to i, P_{i} enters the critical region, setting y to 0 before returning to the remainder region.

The code is presented in Figure 2, in a standard psuedo-code style. Translating this code into timed automata is a straightforward but tedious exercise. The other algorithms in this paper are also presented in the same style.

To aid in the proof, we describe the program states as a combination of program counter values as above, local variable values and shared register values. In any state of the algorithm, we define:

F 1: the set of process indices i such that x = i and pc(i) = 2,

F 2: the set of process indices i such that x = i and pc(i) = 3,

CR: the set of process indices i such that pc(i) ∈ {4a, 4b, 5}.

RM: the set of process indices i such that pc(i) ∈ {0a, 0b}.

We prove the following lemma by induction on the length of the execution.

Lemma 4.2 The following are true in any reachable state of Algorithm 1.

I1 : |F 1| + |F 2| + |CR| ≤ 1.

I2 : If |F 2| + |CR| > 0 then y = 1.

I3 : If y = 1 then some process i is not in RM.

Proof: [[[ Comment: Nancy, we need a line in the model section that says that since we use atomic read write registers, its enough to think of the execution as a sequence of none overlapping operations, this or something that captures it in terms of the global automaton.]]]

By induction on the length of an execution. Initially I1, I2 and I3 hold vacuously since all processes are in the remainder (pc(i) = 0), and y = 1. We assume that the invariants hold in some reachable state s, and for the inductive step, go over all the possible operations (or operation and pc change ) π_{i} of a process i, leading from s to a new state s′ in a given execution. We refer to these operations by their relative line numbers in the code. First note that in any state, there is at most one process i for which x = i, so |F 1| + |F 2| is always equal to 1.

Line L CR remains the same, and |F 1| and |F 2| can only decrease, so I1 holds in s′. Since y remains unchanged, and pc(i) = 1 following the operation, I2 and I3 hold.

Line 1 I3 holds since in s′ pc(i) is either L or 2. If x ≠ i both I1 and I2 hold immediately. The only state change is in pc(i). If x = i in s then it was the case that |F 1| + |F 2| = 0. From I2 we thus have that in s if |CR| > 0 then y = 1. If y was 1, then i reads y = 1 and in s′ i changes to pc(i) = L, implying that I1 and I2 continue to hold since F 1 and F 2 remain unchanged. If y was 0, process i will read y = 0 and in s′ pc(i) = 2, implying |F 1| = 1 and |F 2| = 0. Since by I2 this implies |CR| = 0 in s, |F 1| + |F 2| + |CR| ≤ 1 and I1 and I2 also hold.

Line 2 I2 holds since in s′ y = 1 and I3 holds since pc(i) = 3. If x ≠ i in s, I1 also holds immediately. If x = i, then in s |F 1| = 1 and |F 2| = 0, and in s′ |F 1| = 0 and |F 2| = 1, and I1 holds.

Line 3 I3 holds since in s′ pc(i) is either L or 4a. If x ≠ i in s, then F 1 and F 2 and CR remain unchaged implying that I1 and I2 hold. If x = i, then in s |F 1| = 0, |F 2| = 1, and |CR| = 0, and in s′ |F 1| = 0, |F 2| = 0 and |CR| = 1, so I1 holds. By I2 and |F 2| = 1 it must be that y = 1 in s and remains so in s′, implying I2.

Line 4 (a and b) I3 holds since in s′ pc(i) is 4b or 5. Both invariants hold immediately.

Line 5 I3 holds since in s′ y = 0. Since pc(i) = 4b in s, it follows by I1 that |CR| = 1 and by I2 that |F 1| + |F 2| = 0. Thus, since in s′ pc(i) = 0a, F 1 and F 2 remain unchanged, and |CR| = 0, implying that both I1 and I2 hold.

Line 0a All invariants hold immediately.

Line 0b Since in s′, i is not in RM, CR is unchanged and |F 1| and |F 2| can only decrease, all the invariants hold.

By I1 of Lemma 4.2 we have:

Lemma 4.3 Algorithm 1 has the mutual exclusion property.

Proof: By I1 of Lemma 4.2.

The following lemma follows from I3 and the fact that the executing the exit region takes a bounded nember of steps.

Lemma 4.4 Algorithm 1 is weakly deadlock-free.

Proof: [[[If some process enters when everyone else is in the remainder region, then I3 of Lemma 4.2 implies that y = 0 at that time, which allows the process to proceed directly to the critical region. The exit region is wait-free, so the second part of this claim follows immediately.]]]

We now show that Algorithm 1 optimal in terms of the number of registers.

Lemma 4.5 In any (timed or asynchronous) algorithm providing mutual exclusion and weak deadlockfreedom for n ≥ 2 processes, using a single shared register, every process that moves from its remainder to its critical region must perform at least one read followed by a write.

The proof follows since if a process does not write, other processes cannot tell that it has left the remainder, and if it does not read, it cannot tell if any one of them left the remainder. Both cases would lead to a violation of mutual exclusion.

Proof: Consider any two processes, say 1 and 2, and let us show that process 1 must have read and then written the register. From the system start state s, by the weak deadlock-freedom property, either process must be able, on its own, to complete an execution leading to a state in which it is in the critical region (call these executions e_{1} and e_{2} respectively [[[Comment: Nancy, execution fragments?]]]).

We claim that in e_{1} in which process 1 enters and proceeds to enter the critical region in state s′, it must have written the register. If it did not, then s and s′ differ only in the internal state of process 1, and extending e_{1} by e_{2} yields an execution in which process 2 behaves just as if it were on its own, resulting in a state in which both processes are in the critical region, a violation of mutual exclusion. So process 1 must write the register in e_{1}.

We further claim that in e_{1} it must have read the register before writing it. If it did not, then as above executing e_{2} followed by e_{1} generates an execution which process 1 cannot distinguish from the execution of only e_{1}, resulting in a state in which both processes are in the critical region. So process 1 must read the register in e_{1} prior to writing it.

Theorem 4.6 There is no asynchronous algorithm providing mutual exclusion with weak deadlockfreedom for n ≥ 2 asynchronous processes, using only one shared read/write register.

Proof: Assume by way of contradiction that there exists a one register algorithm for the problem. Consider two processes, say 1 and 2. From the system start state s, by the weak deadlock-freedom property, either process must be able, on its own, to complete an execution leading to a state in which it is in the critical region; call these executions e_{1} and e_{2} respectively. By Lemma 4.5, each of the two processes must write the register during its execution.

Now we construct a bad execution. Run process 1 in e_{1} just until the first state s′ at which it is about to write the register, and let it pause without doing so. States s and s′ differ only in the internal state of process 1. Then extend the execution by e_{2}, in which process 2 behaves just as if it were on its own, eventually entering the critical region. Next, process 1 continues its execution of e_{1}, first performing its write to the register, which overwrites whatever process 2 has written. Following this operation, the state of the system differs from the corresponding state in e_{1} only in the internal state of process 2, and so process 1 goes critical, violating mutual exclusion. This is a contradiction.

[[[Comment: Nancy, I would leave this to the conclusions section only. Faith observed that we could strengthen the WDA assumption to a WDA(k) assumption, where k is any positive integer. This strengthened assumption would say that k-bounded concurrency still guaranteed progress (our definition corresponds to k = 1). Then it appears that the Burns-Lynch impossibility proof extends to k variables. I have no idea whether the algorithm above extends correspondingly to a k + 1-variable algorithm. Probably make this a remark here, and an open question in the conclusions section.]]]

[[[Comment: I agree, we should make this remark in the proof section of the impossibility result. Faith also suggested that we make a remark, here or somewhere, about where the 2-variable impossibility proof breaks down, with just the WDA assumption. The key is in constructing a spine involving 2 processes. Inductively, we are able to bring them in to nullify two variables. But then when we want to let them write, then send them back to the remainder region, bring them back in, etc., we don’t have the right progress assumption to do this. (They are aware of each other’s overlapping execution.)]]]

5 The Timing-Based Case

In this section, we consider the real-time version of the problem, where we assume bounds in the interval [c_{1}, c_{2}] for the time between successive steps of a process, when it is in its trying or exit region. We assume that 0 < c_{1} ≤ c_{2} < ∞. Let C = c_{2}/c_{1}; C is a measure of the timing uncertainty. Define a process i to be slow (respectively, fast) in an execution or execution fragment if the time for any step when the process is in its trying or exit region is exactly c_{2} (resp., c_{1}).

5.1 A 1 Register Algorithm for Mutual Exclusion and Deadlock Freedom

We begin by presenting, in Figure 3, a timing-based mutual exclusion algorithm due to Mike Fischer [10]; we call this Algorithm 2. Algorithm 2 has the property that if the timing constraints are met, and the value of the delay parameter is chosen to be strictly greater than the timing uncertainty C, then mutual exclusion and deadlock-freedom are guaranteed. However, it has the drawback that if the constraints are not met, then many processes may enter the critical region concurrently.

The key idea behind Algorithm 2 is to delay each process i for a period greater than C · c_{1} after it has written x in Line 1 and before testing it in Line 3. Thus, by the time process i has reached Line 3, any process j that has passed the test in Line L and might overwrite x = i with x = j, has already done so

x: shared register initially 0; delay: positive integer constant;

repeat forever 0b: remainder exit_{i} L: if x ≠ 0 then goto L; 1: x := i; 2: pause(delay); 3: if x ≠ i then goto L; 4a: critical enter_{i} 4b: critical exit_{i} 5: x := 0; 0a: remainder enter_{i} end repeat;

Figure 3: Algorithm 2: Fischer’s Timed Mutual Exclusion – Code for Process i.

since C · c_{1} ≥ c_{2}, the longest time such a step might take. If i reads x = i in Line 3, it can safely enter the critical region, since all other processes are either before Line L and will not pass it, or after Line 1 with their index in x overwritten by process i, so they will fail the test on Line 3. To implement the delay, the procedure pause(delay) causes the process to delay by some number of steps, where a delay of 1 means skipping no steps at all, and a delay of k amounts to doing k − 1 dummy steps. Specifically, let pause(k) be a shorthand for a sequence of (k − 1) lines of code, each a no-op operation, and let us accordingly assign program counter values 2.1, 2.2, …, 2.(k − 1) to those (k − 1) lines.

We now outline the correctness proof of the algorithm. Let Algorithm 2’ be the same as Algorithm 2 but asynchronous . The following lemma follows by induction on the length of the execution.

Lemma 5.1 Then in any reachable state of Algorithm 2’:

If x = i ≠ 0 then pc_{i} ∈ {2, 3, 4a, 4b, 5}.

Proof: By induction on the length of the execution. Initially the claim holds vacuously since x = 0. We assume it holds in any reachable state s, and for the inductive step, go over all the possible operations (or operation and pc(i) change ) π_{i} of a process i, leading from s to a new state s′ in any given execution. We refer to these operations by their relative line numbers in the code.

Lines 0a,0b,L: Holds since x remains 0 in s′.

Line 1: Holds since in s′ x = i and pc(i) = 2.

Line 2: In s′ pc(i) = 3 so if x = i we are done, and if x = j, j ≠ i the claim follows from the inductive hypothesis given that x remains unchanged.

Line 3: If in s x = i then in s′ pc(i) = 4a and the claim holds. If x ≠ i then it holds in s′ by the inductive hypothesis applied to s and the fact that x remains unchanged.

Lines 4a,4b: The claim follows from the inductive hypothesis on s given that

Line 5: In s′ x = 0 and the claim follows immediately.

[[[Nancy comment: Now some assertions for the timed version of the algorithm. These will be in the style of those I did with Hagit, involving state components that predict the time until the following step. Here, the state components involving time are exactly: now, representing the current real time, and for each process i, ftime(i) and ltime(i), representing the first and last (absolute) time that the next step of process i is allowed to occur. For now, I am not considering the individual steps within the pause statement, but just making the prediction times for the completion of that statement equal to the bounds for the entire pause statement to execute. E.g., when control first reaches point 2, I set ftime = delayc_{1} and ltime = delayc_{2}. Before the ltime elapses, the algorithm must do the statement at line 3, thereby passing to line 4. Come to think of it, this means that the way I am modeling it, the pc value is never actually at 3 - it just goes directly from 2 to 4 after the time specified in the statement. Need to fix this later. The invariants below are adapted from the Abadi-Lamport REX paper, “An Old-Fashioned Recipe for Real Time”. Note that the algorithm there is slightly different, so the invariants and proof need to be redone in our setting.

Note that your extra x = i condition, which you stated in a funny operational way previously, is now part of the following invariant assertion.]]]

To aid in the main proof, let us define several state components involving time: now, representing the current real time, and for each process i, ftime(i) and ltime(i), representing the first and last (absolute) time that the next step of process i is allowed to occur. Note that by the construction of the timed From our definitions, it follows that if pc(i) ∉ {0b, 4b} then ltime(i) ≤ now + c_{2}.

Let CR be defined similarly to before. We prove the following collection of invariants by induction on the number of steps in an execution. They are similar to those proposed in [19] for a weaker form of the mutual exclusion problem. Note that the only executions that are considered here are those in which the timing assumptions are satisfied; the timing assumptions are required to guarantee these key properties.

Lemma 5.2 In any reachable state of Algorithm 2, the following are true.

I1: If i ∈ CR then

1. x = i, and

2. for all j, pc(j) ≠ 1.

I2: If pc(i) = 2.d, x = i and pc(j) = 1 then ltime(j) < ftime(i) + (delay − d)c_{1}.

I3: If pc(i) = 3, x = i and pc(j) = 1 then ltime(j) < ftime(i).

Proof: By induction on the length of the execution. Initially all three invariants hold vacously since all processes are in the remainder regions. We assume they hold in any reachable state s, and for the inductive step, go over all the possible operations (or operation and pc(i) change ) π_{i} of a process i, leading from s to a new state s′ in any given execution. As before, we refer to these operations by their relative line numbers in the code.

Lines 0a,0b,L: Holds since x remains 0 in s′. [[[to be completed]]]

From I1 of Lemma 5.2 we have:

Lemma 5.3 Algorithm 2 has the mutual exclusion property.

Proof: By Lemma 5.2, Part 5.2.

We prove the following based on Lemma 5.1.

Lemma 5.4 Algorithm 2’ is deadlock-free.

Proof: [[[Consider any reachable state s in which some process is in the trying region and no process is in the critical region, and assume by way of contradiction that no process goes critical after that state. Since there are at most n processes, after some state s′ in this execution, there are no processes with pc ∈ {4a, 4b, 5}, and no additional processes enter the trying region. We can without loss of generality assume this holds throughout the execution.

We claim that x eventually reaches a state s′′ following which in all states x = i for some i ∈ {1..n}, that is, the index of some process. Since there is at least one process in the trying region and all the processes in the trying region keep taking steps, and never reach the critical region, it must be that they all repeatedly execute Line L. Then if any process i ever reads x = 0 in Line L, it sets x = i in Line 1. Since Line 5 is never executed, there is a state s′′ following which in every state, x ≠ 0. But any process that executes Line L following s′′, remains in Line L, implying that there is a state s′′′ following which Line 1 is never executed (i.e. there are no further assignments to x). Since x ≠ 0, it must be that x = i for some i ∈ {1..n}.

Lemma 5.1 implies that process i has pc_{i} ∈ {2, 3, 4a, 4b, 5} in s′′′. But we have assumed that no process has pc_{i} ∈ {4a, 4b, 5} following s, so it must be that pc_{i} ∈ {2, 3}. But then there is nothing stopping i from reading x = i in Line 3, and executing the critical region, a contradiction.]]]

The following is an almost tight upper bound on the time b for some process to enter the critical region. (It can be made tighter by a slight modification to Algorithm 2, which we will describe in the full version of the paper.)

Lemma 5.5 Suppose that delay = C + 1. Then Algorithm 2 has an upper bound of (2C + 7)c_{2}.

Proof: [[[Consider any reachable state s in which some process is in the trying region and no process is in the critical region (Lines 4a and 4b). Then within c_{2} time there is a state s′ in which either a process is in the critical region or no processes are with pc ∈ {4a, 4b, 5}. By Lemma 5.4, there must be a process i that executes the critical region next.

Assume x ≠ 0 in state s′. By the above, pc(i) ≠ L in any state following s′. Thus, i cannot be in the remainder and since pc(i) ∈ {1, 2, 3}, and i never executes Line L again, within (C + 3)c_{2} time it will enter the critical region.

Assume x = 0 in state s′. Since there is some process in the remainder, within (C +2)c_{2} some process sets x ≠ 0 or some process is in Line 4a in a new state s′′. In the latter case, a process enters the critical region in c_{2} additional time. In the former case, since in s′′ x ≠ 0, the above argument implies that within (C + 3)c_{2} time some process will enter the critical region.

Summing it all up, within at most (2C + 7)c_{2} time from the time the system is in state s, some process enters the critical region.

[[[Comment by Nancy: Actually, I realized this morning that the algorithm has an easy modification that gets the bound back down to Cc_{2} + 3c_{2} (or some constant other than 3. The trick is just to replace the pause statement by an explicit repeated read of x (to be done approximately C times (maybe it’s C − 1, I can’t get the boundary condition right). If x is ever seen ≠ i, then process i immediately goes back to L, without waiting for the full number of reads to be completed. I have not changed the algorithm above in this way, because I don’t know exactly how the change might affect the later argument about the hybrid algorithm. It probably doesn’t matter there, but I’m not certain. ]]]

5.2 Lower Bound of Cc_{2} for Mutual Exclusion and Weak Deadlock- Freedom With 1 Register

The following theorem proves the near optimality of the time complexity of Algorithm 2. Our original bound of Cc_{2} was strengthened by Faith Fich [11].

Theorem 5.6 There is no [c_{1}, c_{2}] timed algorithm providing mutual exclusion with weak deadlockfreedom for n ≥ 2 asynchronous processes, that uses only one shared read/write register, and that takes time b < (C + 3)c_{2}.

Proof: (Sketch) Consider two processes, say 1 and 2. From the system start state s, by the weak deadlock-freedom property, either process must be able, on its own, to complete an execution leading to a state in which it is in the critical region. Call these executions e_{1} and e_{2}, respectively. By Lemma 4.5 each process must first read and then write the shared register in its execution. Let r_{1} and r_{2} be the number of steps prior to the first write of the shared register in e_{1} and e_{2}, respectively (by Lemma 4.5, r_{1} and r_{2} are greater than 0).

Suppose that one of these executions, say e_{1}, contains at most C steps after its first write to the shared register. Let t = max{c_{1}(r_{1} + 1), c_{2}(r_{2})} and consider the execution e formed by running e_{1} fast starting at time t − c_{1}(r_{1} + 1) and running e_{2} slowly starting at time t − c_{2}(r_{2}). In e, the r_{2}th step of e_{2} occurs at time t, followed immediately (at the same real time) by the first write of e_{1}, then the rest of e_{1} until time t + Cc_{1} and finally the rest of e_{2}, starting with the first write in e_{2}.

In e, all of e_{1} occurs before the first write of e_{2}. Therefore process 1 cannot distinguish between executions e and e_{1}. Furthermore, all of the writes of e_{1} occur between the first write of e_{2} and the read that precedes it. Thus process 2 cannot distinguish between executions e and e_{2}. But e violates mutual exclusion.

It follows that both e_{1} and e_{2} contain at least C + 3 steps. Then if either execution is run slowly by itself, at least (C + 3)c_{2} time will elapse before the critical region is entered.

6 The Combined Algorithm

In this section we give our first main result: we show how to overcome the drawbacks of the Fischer algorithm, Algorithm 2, providing an algorithm that always provides mutual exclusion and weak deadlock-freedom, and also provides deadlock-freedom if the timing constraints [c_{1}, c_{2}] are met. The algorithm that accomplishes this uses only two shared registers and has a “nice” time bound close to that of Algorithm 2.

By combining Algorithms 1 and 2, one can create an algorithm that uses three shared registers. The way to do this is to replace the critical region of Algorithm 2, by Algorithm 1. However, it is also possible to get a two register algorithm, by combining the two algorithms in a more elaborate way, as seen in Figure 4. The construction is based on the observation, implied immediately by Lemma 5.2, that in Algorithm 2, once a process i enters the critical region, the register x remains equal to i. This implies that the test of x in Algorithm 1 will not fail if it is embedded in Algorithm 2’s critical region even if Algorithm 2 allows processes to set the same register.

x, y: shared registers initially 0; delay: positive integer constant;

repeat forever 0b: remainder exit_{i} L: if x ≠ 0 then goto L; 1: x := i; 2: pause(delay); 3: if x ≠ i then goto L;

% Start of Fischer Critical Region 4: if y ≠ 0 then goto L; 5: y := 1; 6: if x ≠ i then goto L; 7a: critical enter_{i} 7b: critical exit_{i} 8: y := 0;

% End of Fischer Critical Region 9: x := 0; 0a: remainder enter_{i} end repeat;

Figure 4: Algorithm 3: Combined Exclusion Algorithm – Code for process i.

We prove the following by induction on the length of the execution. [[[ Comment: nancy, I think we should get WND from the Lamport simulation by adding the invariant I stated below together with the Lamport proof invariant I3.]]]

Lemma 6.1 Let Algorithm 3’ be the asynchronous version of Algorithm 3. Then in any reachable state of Algorithm 3’, the following are true.

1. If |RM| = n then x = y = 0.

2. If all processes [[[i outside]]] of RM have pc(i) = 9, then y = 0.

Proof: By induction. [[[needs doing]]]

Proof: [[[Nir to work on this]]] Uses Lemma 6.2. WDA follows easily, since when a process enters alone in the situation where x = y = 0, it will zip right through.

Now we define an invariant for the 2V algorithm:

I. If no process is either in the critical region (the real critical region, that is) or just at the point of checking x = i before the critical region, then y = 0.

I think we can do one big induction, proving at the same time (a) that there is a timed forward simulation from 2V to Fischer and (b) that 2V satisfies Invariant I. In this simulation, we have to allow the real critical region of 2V to correspond to the real critical region of Fischer, so that we will show that the extra steps (those involving y, and the extra test for x = i) simulate no-ops in Fischer.

Consider the inductive step. E.g., suppose the 2V algorithm does a step where pi tests the value of y. If it found y = 1, then that would be bad, because the resulting jump back to L would not simulate any allowed step of Fischer. But mutual exclusion of the Fischer algorithm in the pre-state and the definition of the mapping implies that pi is the only process in the “Fischer critical region” part of the 2V code; therefore, no process is either in the (real) critical region of 2V nor just at the point of checking x = i before the critical region. Then invariant I in the pre-state implies that y = 0 in the pre-state, a contradiction.

Also e.g., suppose the 2V algorithm does a step where pi tests the value of x just before entering the critical region, finding it unequal to i. Again, the resulting jump back to L would not simulate Fischer correctly. But pi is in the “Fischer critical region” part of the 2V code in the pre-state, so that by Lemma 5.2, part 5.2 and the correspondence, it must be that x = i in the pre-state. This is a contradiction.

Thus, it looks like all the steps correspond properly. Now consider preserving Invariant I. The only steps that need to be considered here are the step that sets y to 1 and the steps that cause a process to leave the designated portion of the code. The step that sets y to 1 simultaneously puts a process in the designated portion of the code, so it cannot cause a problem. Also, if a process leaves the designated portion by means of a normal exit, then it simultaneously sets y to 0, so it cannot cause a problem. The only remaining possibility is that a process pi leaves the designated portion of code by finding x ≠ i in the test just prior to the critical region. But we argued above that this cannot occur.

Therefore, we have the simulation, and Invariant I.

Now we complete the proof of timed ND. [[[Actually, maybe this is not needed at all. If we show a timed simulation of Fischer, and Fischer has the time bound property, then I think it may carry over to this algorithm without any further work. Sound right? We need to take into account the fact that the time blows up somewhat in the simulation.]]]

Here, I will proceed for now somewhat operationally. First, if anyone is in the exit region (that must be between the two assignments restoring the 0 values) then there is nothing preventing it from moving to the remainder region. So we consider the trying region.

Suppose we are in a timed execution alpha in which, from some point on, at least one process is in T, no one is in C, and no process moves from T to C. Then after some point t in alpha, no process changes regions at all, and there is no one in the exit region - there are just some bunch of processes in T, continually taking steps and getting nowhere. Since no one goes to C and everyone continues taking steps, they must all be continually dropping back to L.

Consider any time when x has value 0 in alpha. I claim that there must be some later time when some process sets x to its index (because it reaches L and sees x = 0). But past time t, if a process sets x to its index, then x can never be set back to 0 (since x only gets set to 0 when a region change occurs). So there is some last time when x has value 0, after which it only has values that are process indices. Thus, eventually in alpha, no process will be able to get past statement L, because they will all see x ≠ 0. This implies that there is some last time, say t′, that x gets a value assigned to it. Let i be the last index assigned to x. (Note that this time t′ could be before or after t.)

Now, register x keeps value i from time t′ on, for the rest of the infinite execution alpha. Then F1 implies that process pi is one of the processes that stays in the trying region after point t. But consider pi just after it assigns x := i at time t′. I claim there is nothing preventing pi from advancing to the (real) critical region. Since this is the last assignment to x, when pi tests x (both times), it must find x = i. Also, when pi reaches the test of y, it is in the “Fischer critical region” portion of the 2V code, so as in the simulation proof above, y = 0. This means that pi has a clear path to the (real) critical region, since all its tests come out right. This contradicts the fact that pi is one of the looping processes.

A little ugliness here: This is not quite a contradiction. Process pi could have gone to its critical region and then come back in, before time t. But if it did this, then it would set x := 0 when it exited, and we have assumed that there are not further assignments to x.

Ugh! Operational proofs aren’t nice. Maybe later, we will want to do this ND proof via a mapping, proving a time bound rather than an “eventually” result.

[[[ Nancy, I suggest that we do the proofs here at this stage by repeating the invariants and proofs of the Fischer and Lamport. We should later, in the final version, do it all with mappings. ]]] To prove correctness of Algorithm 3, we let Algorithm 3’ be the same as Algorithm 3, but without the timing constraints. We show the following by induction on the length of the computation.

Lemma 6.2 In any reachable state of Algorithm 3’, the following are true.

1. I1: If |RM| = n then x = y = 0.

2. I2: If all processes i ∉ RM have pc(i) = 9, then y = 0.

Then we define a forward simulation mapping [12] from Algorithm 3’ to Algorithm 1. From this we prove that:

Lemma 6.3 Algorithm 3’ satisfies the mutual exclusion and weak deadlock-freedom properties.

That is, Algorithm 3 has these properties even if the timing constraints are not satisfied.

Proof: The same three invariants as in the proof of Lamport’s algorithm seem to hold for this algorithm. [[[Need to be careful about making the right redefinitions for the sets CR, RM, etc.]]] The proof is by induction just as before, and mutual exclusion follows from 1.

Alternatively, I think we could prove ME by producing a mapping from the 2V algorithm to the Lamport algorithm. But in order to do this, we would probably have to add some more nondeterministic choices to the Lamport algorithm. E.g., we would need to add an option of going back to L after setting x to i and before seeing y = 0, if x is detected as unequal to i. With such additional nondeterminism, the original ME proof (using the invariants above) should still work. Then a forward simulation mapping of the usual sort might work out OK. (The value x = 0 in the 2V algorithm would probably need to correspond to arbitrary values of x in the Lamport algorithm.) I think that your Lemma 1.1 could probably (and profitably) be restated in this mapping style. [[[ Nir to work on this]]]

We prove the following two lemmas by defining a timed forward simulation [12] from Algorithm 3 (with the timing constraints) to the Fischer algorithm, Algorithm 2, and then proving it and the following invariant by induction on the length of the computation:

I3: If for all i, pc(i) ∉ {6, 7a, 7b, 8} then y = 0.

Lemma 6.4 Algorithm 3 (with the timing constraints) is deadlock-free.

Proof: [[[This is just a collection of various remarks. They begin with some of Nancy’s old remarks, probably prior to the lengthy sketch that was presented above.]]]

As in the proof of the Fischer algorithm, the state needs to be augmented with timing predictions for the times until the next steps of each process. Maybe operational is a little easier for now, here. But at any rate, we probably want to prove invariant 4 from the Fischer algorithm again, for this algorithm. Then ND should follow from timed ND and timed ME of Fischer.

[[[What follows now is some suggestions by Nir.]]]

[[[ I suggest that we prove by a mapping to Fischer and Lemma 5.3 we are guaranteed that one, and no more than one process i will concurrently execute the “Fischer critical region,” and that while it is executing it, x = i.

Now prove the invariant that if y = 1 there is a process between y := 1 and y := 0. So i must read x = i and y = 0 and thus it will enter the critical region.]]]

In the mapping proof to the Fischer algorithm of Figure 3 (in which he step in Line 4a is replaced by 3 steps) and Lemma 5.5, we have:]]]

Lemma 6.5 Algorithm 3 (with the timing constraints) has an upper bound of (2C + 10)c_{2} time.

7 Adding More Registers

In this section, we present our second main result, a lower bound on the time complexity of any deadlockfree mutual exclusion algorithm, in the timed setting. Our lower bound is expressed as a function of the number k of shared registers used by the algorithm. Specifically, it is of the form e(k)Cc_{2}, where e(k) is a function of k. The value of e(k) decreases rapidly with k. Thus, the bound is probably only interesting when k is small and when C, the timing uncertainty, is large. Note that we do not yet have any corresponding upper bounds that decrease similarly with increasing k; finding algorithms exhibiting such upper bounds (or removing the dependency of the lower bound on the number of registers) remains as future work.

For a particular k, we define e(k) by means of a recursive definition of a fast-growing function f(j, k), 1 ≤ j ≤ k. Specifically, we define f(1, k) = 1, and f(j+1, k) = (\binom{k}{j}+1)f(j, k)+\binom{k}{j}(2j+1), 1 ≤ j ≤ k−1. Then we define e(k) = 1/(f(k, k) + 1). Thus, e(k) is a rapidly-decreasing function of k.

Lemma 7.1 1 ≥ f(j, k)e(k) + e(k) for all j, 1 ≤ j ≤ k.

Proof: By definition of e, we have e(k) = 1/(f(k, k) + 1), i.e., that 1 = f(k, k)e(k) + e(k). Since f(j, k) is a monotone nondecreasing function of j, the result follows.

Theorem 7.2 Suppose C ≥ 2. There is no [c_{1}, c_{2}] timed algorithm providing mutual exclusion with deadlock-freedom for n ≥ 2 asynchronous processes, that uses only k < n shared read/write register, and that takes time b < e(k)Cc_{2}.

Proof: (Sketch) Suppose there is such an algorithm, with time bound b < e(k)Cc_{2}. We follow the main ideas of the construction of Burns and Lynch [3], for the asynchronous impossibility proof (of our Theorem 4.1) to construct a bad execution. This time, however, the bad execution, as well as the auxiliary executions used along the way, must satisfy the timing constraints, which makes the construction considerably harder than before.

The construction we carry out involves only k + 1 of the n processes, those numbered p_{1}, p_{2}, …, p_{k+1}. We carry out a recursive construction similar to the one in [3]. This time, For any j = 1, …, k, starting from any configuration in which all processes are in their remainder regions, we obtain a finite timed execution of p_{1}, …, p_{j} only, satisfying the timing constraints, and leading to a point at which p_{1}, …, p_{j} “nullify” j distinct registers. (The definition of a process p_{i} “nullifying” a register v is as in [3]: p_{i} is about to write register v at its next step, and moreover, anything process p_{i} has written since last leaving its remainder region has already been overwritten without being read by other processes.) Moreover, the execution has the additional timing property that for all i, 1 ≤ i ≤ j, ltime(i) ≥ now + e(k)c_{2} and ftime(i) ≤ now. Here, now denotes the current time at the designated point in the execution, and ftime(i) and ltime(i) denote the first and last times at which the next step of process i might occur. That is, the timing constraints permit process i to wait at least time e(k)c_{2} before taking its next step, but do not impose any lower bound on the time at which it might take that step. Furthermore, the total time required for the execution is at most f(j, k)e(k)c_{2}.

We apply this result for the special case where j = k. obtaining a finite timed execution of p_{1}, …, p_{k} only, satisfying the timing constraints, leading to a point where p_{1}, …, p_{k} nullify all k registers, and for all i, 1 ≤ i ≤ k, ltime(i) ≥ now + e(k)c_{2} and ftime(i) ≤ now.

We apply this result for the special case where j = k. Now let the last process, p_{k+1}, enter the system, taking steps as fast as it can. We claim it should be able to proceed to its critical region before any of the other processes take their next steps. This is because of the upper bound on the algorithm, the fact that p_{k+1} cannot tell that any other process is outside its remainder region, and the fact that ltime(i) ≥ now + e(k)c_{2} for all i, 1 ≤ i ≤ k. (The upper bound is e(k)Cc_{2} for all computations that satisfy the timing constraints; we can stretch the given fast computation of p_{k+1} so that the time between its steps is always c_{2}, and an upper bound of e(k)Cc_{2} for this slower computation implies an upper bound of e(k)c_{2} on the fast computation.) But then we can let p_{k+1} remain in its critical region while the rest of the processes proceed normally, still observing the timing assumptions. We first allow all the processes to write the registers they are nullifying. The timing assumptions allow this round-like behavior, because once one process takes a step, the upper bound for its next step is c_{2}, which is at least as great as any other process’ new value of last. Once they have done this, they have hidden all information about p_{k+1} being in the critical region, so some other process will eventually proceed into its critical region, thereby violating mutual exclusion. This is a contradiction.

It remains to carry out the recursive construction. Basis: j = 1. Just let p_{1} enter, going fast. Within time at most e(k)c_{2}, it must go to the critical region, and in order to do so, it must write some register, say v. (If it does not, it is hidden while in the critical region and this can cause a violation of mutual exclusion.) [[[Need to put a lemma in here. Maybe merge with prior lemma 3.5.]]] Let p_{1} stop at a particular point in this interval, when it is about to write some v for the first time. It is hidden, and ready to write, so it nullifies v. Moreover, stopping just when time c_{1} has elapsed after the prior step ensures that ftime(1) ≤ now, and since ltime(1) = now + c_{2} − c_{1}, since C ≥ 2 we also have ltime(1) ≥ now + e(k)c_{2}. The total time required for this is at most e(k)c_{2} = f(1, k)e(k)c_{2}, which suffices.

Inductive step: Suppose we have the result for j ≤ k − 1. starting from any configuration in which all processes are in their remainder regions, there is a finite timed execution of p_{1}, …, p_{j}, satisfying the timing constraints, and leading to a point at which p_{1}, …, p_{j} nullify j distinct registers, and moreover, for all i, 1 ≤ i ≤ j, ltime(i) ≥ now + e(k)c_{2} and ftime(i) ≤ now. Finally, the total time required for the execution is at most f(j, k)e(k)c_{2}. Starting from any configuration in which all processes are in their remainder regions, we wish to obtain the analogous timed execution for p_{1}, …, p_{j+1}. That is, we want a finite timed execution of p_{1}, …, p_{j+1}, satisfying the timing constraints, and leading to a point at which p_{1}, …, p_{j+1} nullify j + 1 distinct registers, and moreover, for all i, 1 ≤ i ≤ j + 1, ltime(i) ≥ now + e(k)c_{2} and ftime(i) ≤ now. Finally, the total time required for the execution should be at most f(j + 1, k)e(k)c_{2}. As in [3], we construct a “spine” execution; this time, the spine execution will satisfy the timing constraints. Constructing the spine involves applying the inductive hypothesis to get p_{1}, …, p_{j} nullifying j registers, with all ltime values at least now + e(k)c_{2} and all ftime at most now, all within time at most f(j, k)e(k)c_{2}. Then we repeatedly do the following:

Allow all of p_{1}, …, p_{j} to write at time exactly e(k)c_{2} after the stopping point, with no other intervening steps. Then use the deadlock-freedom hypothesis to allow all these processes to proceed to their critical regions, one at a time, and from there, to their remainder regions. (Each will only spend time 0 in the critical region.) Do this using a fast execution fragment, so the upper bound for each process to go critical is e(k)c_{2}, and then to go to its remainder region is another e(k)c_{2}. After some time, all will be back in their remainder region. Then apply the inductive hypothesis once again to get p_{1}, …, p_{j} nullifying j registers, with all ltime values at least now + e(k)c_{2} and all ftime values at most now, again within time at most f(j, k)e(k)c_{2}.

So, we repeatedly have p_{1}, …, p_{j} nullifying a set of j registers. Sometime within the first \binom{k}{j} + 1 times this happens, the same set of j registers will be nullified. Call this set V. We claim that the time until the second point where V is nullified is at most (\binom{k}{j} + 1)f(j, k)e(k)c_{2} + \binom{k}{j}(2j + 1)e(k)c_{2}. The first term in this sum describes the total time taken for all the uses of the inductive hypothesis. The second term describes the total time for the processes to overwrite and then to proceed back to their remainder regions. Note that by definition of f, this time bound expression is equal to f(j + 1, k)e(k)c_{2}.

Now we use this spine to help us construct the desired execution of p_{1}, …, p_{j+1}. We run the spine just until the first time V described above is nullified. Then we insert some steps of p_{j+1}, running fast, just until it is about to write something not in V. This must happen within time e(k)c_{2}, since p_{j+1} doesn’t know there is anyone else there and must go critical by e(k)c_{2} in a fast execution in which it operates alone. It must write something not in V, since otherwise its writes could be overwritten by the nullifying processes p_{1}, …, p_{j}, who would thereby hide p_{j+1} in the critical region and lead to a violation of mutual exclusion. Just before it writes something not in V, we stop p_{j+1} and now allow the rest of the spine to proceed as before, just until the second time that V is nullified. We claim that we are allowed to stop p_{j+1} for that length of time, because the length of time for the spine is at most f(j + 1, k)e(k)c_{2}, the upper bound on step time for p_{j+1} is c_{2}, and f(j + 1, k)e(k)c_{2} ≤ c_{2}. (This latter fact follows from the fact that 1 ≥ f(j + 1, k)e(k), which in turn follows from Lemma 7.1.)

We claim that the resulting execution has the required properties. The inductive hypothesis already tells us that the ftime and ltime values for processes p_{1}, … p_{j} are as required. We must show that the values for p_{j+1} are also appropriate. Since at least two steps have occurred for some particular process since p_{j+1} was stopped, it must be that ftime(j + 1) ≤ now. It remains to consider the value of ltime(j+1). To see that ltime(j+1) ≥ now+e(k)c_{2}, it suffices to show that c_{2} ≥ f(j+1, k)e(k)c_{2}+e(k)c_{2}. But Lemma 7.1 implies that 1 ≥ f(j + 1, k)e(k) + e(k), which immediately implies this inequality.

8 Weaker Timing Assumptions

We show that weakening the timing model by assuming that the bounds [c_{1}, c_{2}] are unknown, or that the timing conditions are only eventually met, leads to a lower bound of n on the number of read/write registers required, just as in the asynchronous case.

In the resilient timing model, we again consider a fixed pair, [c_{1}, c_{2}], of bounds for the time between steps in the trying or exit region, as in the timed model. However, now we only consider those executions in which the time bounds hold eventually. We prove the following theorem by a variation of the [3] proof.

8.0.1 Impossibility of Mutual Exclusion and Deadlock-Freedom with Fewer than n Registers

Theorem 8.1 There is no [c_{1}, c_{2}] resilient algorithm providing mutual exclusion with deadlock-freedom for n ≥ 2 asynchronous processes that uses fewer than n shared read/write registers.

Proof: Another variant of the BL proof. This time, we show inductively on j that, from any system state in which everyone is in the remainder region, there is some prefix of an execution of the algorithm (note there are no timing requirements for a prefix) that leads to j processes nullifying j registers.

For the base, j = 1, just allow process 1 to enter, with the time bounds satisfied, and use deadlockfreedom to have it reach the critical region; on the way, it must write a register, as usual. [[[Gee, we could use some general theorems about stuff like this, since right now I am having to re-think the little arguments over and over for all the models. So far, I don’t know how to do this, since each case seems to be just a little bit different.]]]

For the inductive step, for j+1, we proceed by constructing a spine as usual. This time, the spine gets constructed by using the inductive hypothesis to bring in the j processes, then having them all write, then having the execution continue with the time bounds satisfied, so that we can use the deadlockfreedom hypothesis to get all the j processes return to their remainder region. Then we repeat this as usual, until a set V repeats.

Now we consider the side execution of process j + 1 from the first of the two points where processes 1, …, j are paused ready to write V. If we consider the values of all the shared registers at this point, they are consistent with all processes being in their remainder regions. Let s be the analogous state in which all processes are in their remainder regions and the registers have the same values. Then from s, there is an execution of process j + 1 in which it goes on its own to the critical region. (Consider an execution satisfying the timing constraints and use deadlock-freedom to show this.) Also, we claim that process j + 1 must write some register not in V along the way. If not, then the same kind of contradiction as before arises: here, process j + 1 can execute a “sped-up” version of this execution starting from the point where processes 1, …, j are paused at V, getting all the way to its critical region (this may violate the timing constraints, but is still an allowable prefix of an execution); then processes 1, … j can continue the spine, overwriting everything written by process j + 1, thereby hiding it in the critical region.

Now construct the main execution by inserting the sped-up steps of process j + 1, just up to the point where it is about to write a register not in V, into the spine as usual. This involves not only speeding up process j + 1 for a while, to squeeze its steps in before the other processes write, but then also pausing process j + 1 for a long time while the spine executes. Thus, the time constraints are not necessarily satisfied in the execution being constructed. However, p_{j+1} is hidden from all the others, so they will still continue to execute the spine as before, and will wind up with j + 1 registers nullified.

The special case of the inductive step for j = n clearly implies the need for n registers.

[[[Whew! There was more going on above than I thought. We probably need some general lemmas that cover several models, because the arguments seem repetitive.]]]

Remark 8.1 It seems that the proof above still holds in case the executions are slightly further restricted, ensuring that even in the portion of the of execution where the bounds are not observed, there is not occurrence of two consecutive steps of the same process having exactly the same associated real time. This remark gets used in the following subsection. We might change the definition of this resilient model just to rule out 0-time steps, because we only have a lower bound result for this case, and it is a stronger result when stated for the more restricted set of executions.

In the unknown bound timing model, we consider those executions in which there exist some time bounds [c_{1}, c_{2}], 0 < c_{1} ≤ c_{2} < ∞, that hold throughout the execution. However, the time bounds are allowed to be different in different executions, in other words, unknown to the processes. We prove the following theorem by a reduction from the previous result.

8.0.2 Impossibility of Mutual Exclusion and Deadlock-Freedom with Fewer than n Registers

Theorem 8.2 There is no unknown bound algorithm providing mutual exclusion with deadlock-freedom for n ≥ 2 asynchronous processes that uses fewer than n shared read/write registers.

Proof: This follows by a reduction from the previous result. Suppose for the purpose of contradiction that we have an algorithm A that has the properties above, for its “unknown bound” executions. Now fix any [c_{1}, c_{2}], where 0 < c_{1} ≤ c_{2} < ∞. Then we claim that A also has the same properties for its “[c_{1}, c_{2}]-resilient” executions. (Here, we have to use the stronger definition of “[c_{1}, c_{2}]-resilient execution” alluded to in Remark ??, where 0 time between steps of the same process is not permitted.)

For, consider any [c_{1}, c_{2}]-resilient execution α. Past some point in α, the bounds [c_{1}, c_{2}] are always observed. There are only a finite number of events occurring before the bounds start to hold. So there exist [d_{1}, d_{2}], 0 < d_{1} ≤ d_{2} < ∞, such that the entire execution α observes the bounds [d_{1}, d_{2}]. This means that α is an “unknown bound” execution. Thus, we have actually shown that any [c_{1}, c_{2}]-resilient execution of A is also an unknown bound execution of A.

Since we have assumed that the unknown bound executions of A all have the desired properties, this implies that all the [c_{1}, c_{2}]-resilient execution of A also satisfy the properties. But then A’s existence is in contradiction to Theorem 8.1.

8.1 Randomized Models

[[[Comment: Nancy: This is Nir’s. I haven’t thought about this. Nir: Yes, this is Nir’s but not for the abs, its for the summertime, when the livin is easy...]]]

We also show that [[[n]]] read/write registers are necessary if one replaces the timing assumptions by other well established assumptions such as the availability of coins (randomization), or stochastic assumptions on scheduling (as in exponential backoff schemes [?]).

[[[ Nancy, variations on the BL should give us this. I think your method can also be extended to the randomized case, since as far as I can tell, you do not need to assume that the scheduler knows where a process is about to write. Nir]]]

9 Further Work

9.1 Summary of Results

[[[To be written.]]]

There are many directions in which this work should be extended. Both the upper and lower bounds should be tightened, and time bounds should be proven for asynchronous mutual exclusion, where the number of shared registers is at least as great as the number of processes. Other directions would be an analysis of the effects of randomization on our upper and lower bounds, consideration of fairness properties rather than just deadlock-freedom, and the introduction of contention on the shared registers as a factor in the analysis.

Work that remains to be done includes the following.

1. Strengthening either the upper or the lower bounds, to better understand the dependency of the time complexity of timing-based mutual exclusion on the number of shared registers.

2. Obtaining time bounds for asynchronous mutual exclusion algorithms, in the case where the number of shared registers is at least as great as the number of processes.

3. Extending the results to include consideration of fairness properties rather than just deadlockfreedom.

4. Considering the impact on the complexity and possibility results of allowing randomization in the algorithms.

5. Considering alternative architectures; for example, we have assumed that only the contending processes are allowed to participate in the algorithm. What is the impact on the results, as well as the practical feasibility, of allowing the critical region to be allocated by a special “supervisor” process running on a dedicated processor? What is the impact of taking contention on the shared registers into account?

9.2 Strengthening the Results

[[[The upper and lower bounds are not that tight. E.g., for the 2-register case, there is a substantial difference between the constants in the lower and upper bounds. (around 1/10 vs. 1?) It would be nice to close this gap further.

Also, note that the lower bound degrades badly as I increase the number of registers. Yet we have no such tradeoff for the upper bound. Is there some way to take advantage of the existence of more registers to cut down the running time?]]]

9.3 Randomization

[[[To be written.]]]

9.4 Time Complexity for the Asynchronous Case

[[[It would be nice to be able to say something about the time complexity for the asynchronous case, with n registers and n processes. The algorithm in the BL paper uses time approx. nc_{2}, I believe. This has no dependence on C, of course, but does have a dependence on n. Is this necessary? Can this problem be solved in approx. c_{2}, without the n? If not, then in approx. (logn)c_{2}? Remember, that we are allowed to use multi-writer, multi-reader registers, whereas the algorithm in [BL] was for the single-writer case.

This reminds me of the place we got stuck trying to prove a big lower bound, in our paper with Hagit. Does Cook-Dwork-Reischuk say anything about this kind of problem? Is there an easy or known solution? ]]] [[[ Comment: Yes, very interesting, since the question you really want an answer to is whether needing registers means each process has to read them all. ]]]

9.5 Supervisor Model

[[[ Comment: Answer to supervisor model. Nancy, the current trend in hardware and parallel systems is for fast MIMD parallel machines that multiplex many processes and tasks, using a distributed OS, in order not to waste CPU cycles. The supervisor model defeats this purpose. Either process p_{0} is multiplexed, or it is a single phisical processor. In the first case the alg cannot be used on OS level, since it assumes lower level mutex by the multiplexing OS (and generates an overhead of context switching and swapping). In the second case, the dedicated processor will be *wasting* zillions of CPU cycles reading shared vaiables if there is a low demand for mutex. Thus, the response time will be low, but the total number of operation per entry truely impractical. To get best utilization of the CPU’s, one should have processes spend mutex cycles only when they wish to perform mutex. So the supervisor model is of no interest given the problem we wish to solve and today’s machines. ]]] [[[I’m not so sure about this. What’s wrong with wasting one processor? I don’t think processor utilization ought to be that important in the long run. N.]]]

In the olden days, the assumption we have made in this paper, that processes can only participate when in their trying and exit regions, was common, and was based on the realities of time-shared single-processor machines. For ***????true parallel????*** processors, this assumption is no longer so reasonable.

If we drop this assumption, then all our impossibility results fall apart. In fact, it seems that some simple and efficient algorithms become possible. E.g., suppose we have a separate process p_{0} that is always around, and functions as a scheduler. Then other processes, when they arrive, could keep trying to record this fact in register x. The supervisor

********keeps reading x******* (BAD BAD BAD)

till it sees some index i there, and then informs i it can go critical by writing i into register y. When a process leave the critical region, it writes 0 into x and y. Needs work, but that’s the idea. Takes only constant times c_{2}, even in asynchronous case, and satisfies DA.

What about one register here? –¿ only without deadlock freedom.

What is actually wrong with such algorithms? Maybe they do indicate that our other results are really only of theoretical interest. Is there a practical (patentable?) algorithm we can get using a supervisor? (A joke, a joke.).]]]

9.6 Fairness

[[[Extend some of these results to consider various fairness properties such as no-lockout.]]]

10 Acknowledgments

Many thanks go to Faith Fich for her interest and attention, and for many helpful suggestions on the results and proofs. We also thank Victor Luchangco who helped with the proof of Lemma 5.2.

References

[1] M. R. MacBlane. Source level atomic test-and-set for the TUXEDO system source product. UNIX System Laboratories, May 14, 1991.

[2] TUXEDO System Release 4.0 – Product Overview. AT&T, 1990.

[3] J. Burns and N. Lynch. Mutual exclusion using indivisible reads and writes. In Proceedings of 18th Annual Allerton Conference on Communications, Control and Computing, 1989, pages 833-842.

[4] E. Styer. Improving fast mutual exclusion. Manuscript.

[5] M. Merritt and G. Taubenfeld. Speeding Lamport’s fast mutual exclusion algorithm. Manuscript.

[6] R. Alur and G. Taubenfeld. Results about fast mutual exclusion In Proceedings of Real Time Systems Symposium, Pheonix, Arizona, 1992.

[7] M. Merritt, F. Modugno and M. Tuttle. Time-Constrained Automata. In Proceedings of 2nd CONCUR, Amsterdam, The Netherland, August, 1991, Springer-Verlag LNCS 527, pp. 408-423.

[8] N. Lynch and M. Tuttle. Hierarchical correctness proofs for distributed algorithms. In Proceedings of the 6th PODC, August 1987, pp. 137-151.

[9] N. Lynch and M. Tuttle. An introduction to Input/Output Automata. CWI-Quarterly, No. 3, Vol. 2, September, 1989, pp. 219-246.

[10] M. Fischer. Personal communication.

[11] F. Fich. Personal communication.

[12] N. Lynch and F. Vaandrager. Forward and backward simulations for timing-based systems. In Proceedings of REX Workshop “Real-Time: Theory in Practice,” Mook, The Netherland, 1992. Springer-Verlag LNCS 600.

[13] N. Lynch and I. Saias. Proving probabilistic correctness statements: the case of Rabin’s algorithm for mutual exclusion. In Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, 1992.

[14] E. Kushilevits and M. Rabin. Randomized mutual exclusion algorithms revisited. In Proceedings of the 11th PODC, 1992.

[15] E.W. Dijkstra. Solution of a problem in concurrent programming control. Communications Of The ACM, 8:165, 1965.

[16] H. Katseff. A new solution to the critical section problem. In Proceedings of the 10^{th} Annual ACM Symposium on Theory of Computing, pages 86–88. ACM, 1978.

[17] L. Lamport. A fast mutual exclusion algorithm. ACM Trans. on Comp. Systems, 5(1):1-11, Feb. 87.

[18] L. Lamport. A new solution of Dijkstra’s concurrent programming problem. Communications of the ACM, 78(8):453– 455, 1974.

[19] M. Abadi and L. Lamport. An old fashioned Recipe for Real Time In Real Time: Theory in Practice, REX Workshop, Springer Verlag, pp. 1-27, 1991.

[20] H. Attiya and N. Lynch. Time bounds for real-time process control in the presence of timing uncertainty. In Proceedings of the 10th RTSS, Santa-Monica, December 1989, pp. 268–284.