Improved implementations of binary universal operations.
We present an algorithm for implementing binary operations (of any type) from unary load-linked (LL) and store-conditional (SC) operations. The performance of the algorithm is evaluated according to its sensitivity, measuring the distance between operations in the graph induced by conflicts, which guarantees that they do not influence the step complexity of each other. The sensitivity of our implementation is O(log&ast; n), where n is the number of processors in the system. That is, operations that are (log&ast; n) apart in the graph induced by conflicts do not delay each other. Constant sensitivity is achieved for operations used to implement heaps and array-based linked lists.We also prove that there is a problem which can be solved in O(1) steps using binary LL/SC operations, but requires O(log log&ast; n) operations if only unary LL/SC operations are used. This indicates a non-constant gap between unary and binary, LL/SC operations.
Introduction
An algorithm is non-blocking if a processor is delayed only when some other processor is making
progress. Non-blocking algorithms avoid performance bottlenecks due to processors' failures
or delay. In asynchronous shared memory systems, non-blocking algorithms require the use of
universal operations such as load-linked (LL) and store-conditional (SC) [14].
For ease of programming, it is more convenient to write non-blocking algorithms using
universal operations that can access several memory words atomically [4, 13, 18, 22]. However,
most existing commercial architectures provide only unary operations which access a single
memory word [23, 26]. Multi-word operations can be implemented using unary universal
operations, e.g., [14, 15], but these implementations are not very efficient.
The efficiency of an implementation can be evaluated in isolation, i.e., when there is no
interference from other operations contending for the same memory words [19]. However, this
provides no indication of the implementation's behavior in the presence of contention, i.e.,
when other operations compete for access to the same memory words. Clearly, if we have a
"hot spot", i.e., a memory word for which contention is high, then in any implementation,
some operations trying to access this word will be delayed for a long time. One can even argue
that in this case, operations will be delayed even when they are supported in hardware [5, 24].
However, such a hot spot should not delay "far away" operations.
This paper proposes to evaluate implementations by their sensitivity , measuring to what
distance a hot spot influences the performance of other operations. Roughly stated, the sensitivity
is the longest distance from one operation to another operation that influences its
performance, e.g., change the number of steps needed in order to complete the operation.
We concentrate on implementations of binary operations from unary LL/SC.
Binary operations induce a conflict graph, in which nodes represent memory words and
there is an edge between two memory words if and only if they belong to the data set of an
operation, i.e., they are the pair of memory words accessed by the operation. A hot spot
corresponds to a node with high degree. It is required that two operations whose distance in
the conflict graph is larger than the sensitivity do not interfere; that is, their step complexity
is the same whether they execute in parallel or not.
We present an algorithm for implementing arbitrary binary operations from unary LL and
SC operations with sensitivity O(log   n).
Our algorithm uses LL/SC for convenience, and since they are supported by several contemporary
architectures, e.g., [23, 26]. The algorithm can be extended to rely on other unary
universal operations; in particular, the O(1) implementation of LL/SC from compare&swap [3]
can be employed.
The core of the algorithm implements the binary operation in a manner similar to known
algorithms [3, 7, 19, 25, 27]: A processor locks the words in the data set of the binary operation,
applies the operation, and then unlocks the data set. Operations help each other to complete,
thus ensuring that the algorithm does not block. The new feature of our algorithm is that a
processor may lock its data set in two directions-either starting with the low-address word or
starting with the high-address word.
The sensitivity of the core algorithm depends on the orientation of the conflict graph
according to locking directions. For two common data structures-an array-based linked list
and a heap-we can a priori determine locking directions which induce constant sensitivity. In
general, however, processors have to dynamically decide on locking directions. This is achieved
by encapsulating the core algorithm with a decision algorithm, coordinating the order in which
processors lock their data sets (low-address word first or high-address word first).
We first present a decision algorithm based on the deterministic coin tossing technique of
Cole and Vishkin [9] for the simplified case where the conflict graph is a path. Then, we show
a synchronization method that breaks a conflict graph with arbitrary topology into paths, to
which the adapted deterministic coin tossing technique can be applied.
Combined with the previous algorithm, this is an implementation of arbitrary binary operations
from unary LL/SC with O(log   n) sensitivity.
We also show that there is a problem which can be solved in O(1) steps using binary LL/SC
operations, but requires O(log log   n) steps if only unary operations (of any type) are used.
The proof adapts a lower bound of Linial [20], which shows that in a message passing model
a maximal independent set in an n-ring can not be found in less than \Omega\Gammaan/   n) rounds. This
lower bound indicates that any implementation of binary LL/SC from unary operations will
have to incur a non-constant overhead.
Following the original publication of this work [6, 10], Afek, Merritt, Taubenfeld and
Touitou [1] presented an algorithm for implementing any k-word object from unary oper-
ations; the algorithm is wait-free, guaranteeing that every operation eventually terminates.
Their algorithm uses algorithmic ideas from our implementation, and in addition, employs it
as a base case in a recursive construction.
Herlihy and Moss [16] introduce transactional memory, a hardware-based scheme for implementing
arbitrary multi-word operations.
Three schemes [3, 19, 25] present software implementations of transactional memory from
single-word atomic operations: Israeli and Rappoport [19] and Shavit and Touitou [25] present
non-blocking implementations of arbitrary multi-word operations using unary LL/SC, while
Anderson and Moir [3] give a wait-free implementation of k-compare&swap and k-SC. Shavit
and Touitou [25] present simulation results indicating that their algorithm performs well in
practice; Israeli and Rappoport [19] analyze the step complexity of an operation; Anderson and
Moir [3] measure the step complexity of k-compare&swap and k-SC operations. Analysis of all
three implementations shows that they are very sensitive to contention by distant operations.
For example, two operations executing on two ends of a linked list can increase each other's
step complexity.
Turek, Shasha and Prakash [27] show a general method for transforming a concurrent implementation
of a data structure into a non-blocking one; their method employs compare&swap.
A process being blocked due to some lock held by another process helps the blocking process
until it releases its lock; help continues recursively if the blocking process is also blocked by
another process. Barnes [7] presents a general method for constructing non-blocking implementations
of concurrent data structures; in this method, only words needed by the operation
are cached into a private memory. Thus, operations can access the data structure concurrently
if they do not contend. These methods are similar to software transactional memory [3, 19, 25],
and their sensitivity is high.
Our algorithm uses helping, as in [3, 7, 19, 25, 27], but decreases the sensitivity and increases
parallelism by minimizing the distance to which an operation helps.
Herlihy [15] introduces a general method for converting a sequential data structure into
a shared wait-free one. Both Herlihy's method and its extension, suggested by Alemany and
Felten [2], do not allow "parallelism" between concurrent operations and are inherently sequential

Anderson and Moir [3] present a universal construction that allows operations to access
multiple objects atomically. Their implementation uses multi-word operations and it can be
employed to efficiently implement certain large shared objects, where it saves copying and
allows parallelism.
Non-blocking implementations of multi-word operations induce solutions to the well-known
resource-allocation problem; these solutions have short waiting chains and small failure locality
[8]. Additional discussion of the relations between the two problems appears in [1].
Preliminaries
2.1 The Asynchronous Shared-Memory Model
In the shared-memory model, processors communicate by applying memory access
operations (in short, operations) to a set of memory words,
Each processor p i is modeled as a (possibly infinite) state machine with state set Q i ,
containing a distinguished initial state, q 0;i .
A configuration is a vector is a local state of processor
is the value of memory word m j . In the initial configuration, all processors are in
their (local) initial states and memory words contain a default value.
Each operation has a type, which defines the number of input and output arguments, their
allowable values, and the functional dependency between the inputs, the shared-memory state
and the processor state, on one hand, and the output arguments and the new states of the
processor and the memory, on the other hand. Each operation is an instance of some operation
type; the data set of an operation is the set of memory words it accesses.
For example, unary LL and SC are defined as follows:
return the value of m
SC(m, new)
if no write or successful SC to m since your previous LL(m) then
new
return success
else return failure
An event is a computation step by a single processor and is denoted by the index of the
processor. In an event, a processor determines the memory operation to perform according to
its local state, and determines its next local state according to the value returned by operation.
Operations are atomic; that is, each operation seems to occur at a certain point, and no
two operations occur at the same point. Therefore, computations in the system are captured
by sequences of configurations, where each configuration is obtained from the previous one by
an event of a single processor.
In more detail, an execution segment ff is a (finite or infinite) sequence
where for every is a configuration, OE k is an event, and the application of OE k to
results in C k+1 ; that is, if OE is the result of applying p i 's transition function
to p i 's state in C k , and applying p i 's memory access operation to the memory in C k .
An execution is an execution segment C which C 0 is the initial
configuration. There are no constraints on the interleavings of events by different processors,
manifesting the assumption that processors are asynchronous and there is no bound on their
relative speeds.
An implementation of a high-level operation type H from low-level operations of type L, is
a procedure using operations of L. Intuitively, processors can not distinguish between H and
its implementation by L.
Assume processor p i invokes a procedure implementing an operation op which terminates;
let OE f and OE l be the first and the last events, respectively, executed by processor p i in the
procedure for op; the interval of op is the execution segment
the operation does not terminate, its interval is the infinite execution segment
Two operations overlap if their intervals overlap.
An invocation of an operation may result in different intervals, depending on the context
of its execution. For example, two intervals of the same operation may differ and even return
different values if the first is executed in isolation, while the second overlaps other operations.
Let ff be an interval of p i ; the step complexity of ff, denoted step(ff), is the number of
events of p i in ff.
op op 3

Figure

1: A simple conflict graph.
An execution fi is linearizable [17] if there is a total ordering of the implemented operations
in fi, preserving the order of non-overlapping operations, in which each response satisfies the
semantics of H , given the responses of the previous operations in the total order.
An implementation is non-blocking if at any point, some processor with a pending operation
completes within a bounded number of steps.
2.2 Sensitivity
The conflict graph of an execution segment ff represents the dependencies between the data
sets of operations in ff; it is an undirected graph, denoted G ff . A node in G ff represents a
memory word, m i . An edge between two nodes m i and m j corresponds to an operation with
data set fm whose interval overlaps ff. G ff may contain parallel edges, if ff contains
several operations with the same data set. 1
Example 1 Let ff be a finite interval of an operation op(m which is overlapped by
shows G ff .
Next, we consider the conflict graph of an interval of some operation op, and measure the
distance between edges representing op and operations that delay the execution of op. The
maximum distance measured in all intervals of an implementation determines its sensitivity.
In more detail, assume ff is the interval of some operation op, and let op i
be an operation
in op's connected component in G ff . The distance between op and op i
in ff is the number of
edges in the shortest path in G ff whose endpoints are the edges representing op i
and op.
Intuitively, the sensitivity measures the minimum distance guaranteeing that two operations
do not "interfere" with each other. Below, we say that an operation op 2 does not interfere with
operation op 1
, if the step complexity of op 1
is the same, whether op 2
is executed in parallel
or not. The definition can be modified so that the sensitivity depends on other complexity
measures, e.g., the set of memory words accessed.
An earlier version of this work [6, 10] defined the contention graph of an execution, in which nodes represent
operations and edges represent the memory words in their data sets; it is the dual of the conflict graph. The
contention graph captures the dependencies between operations somewhat more accurately, but the conflict
graph is easier to work with.
An interval ff of some operation op is sensitive to distance ' if there is an interval ff 0 of op,
such
has exactly one more operation (i.e., an edge) than G ff , at distance ' from the edge
representing op, and
That is, the step complexity of op increases when a single operation is added to ff at distance
' from op.
The sensitivity of an interval ff is the maximum s such that ff is sensitive to distance s.
This means that the step complexity of op does not increase when a single operation is added
to ff at distance s + 1. If this maximum does not exist, then the sensitivity is 1.
The sensitivity of an implementation is the maximum sensitivity over all its intervals.
The sensitivity captures non-interference between operations in the following sense: If the
sensitivity of an implementation is s and the distance between two operations in the conflict
graph is d ? s, then the step complexity (or any other measure we consider) of the operations
is the same whether they execute in parallel or not.
2.3 Related Complexity Measures
Disjoint-access parallelism [19] requires an operation to complete in a constant number of steps,
if no other operations contend for the same memory words. Sensitivity strengthens this notion
and allows to evaluate the behavior of an implementation also in the presence of contention.
Afek et al. [1] suggest two other complexity measures:
1. An algorithm has d-local step complexity if the number of steps performed in an interval
ff is bounded by a function of the number of operations within distance d in G ff .
2. An algorithm has d-local contention if two operations access the same memory word only
if their distance in the conflict graph of their (joint) interval is at most d.
Clearly, sensitivity d+ 1 implies d-local step complexity; however, the converse is not true.
For example, suppose the data set of an operation op contains a hot spot m, accessed by '
other operations; suppose that m is also on a path of operations with length '. Sensitivity 1
does not allow operations on the path to influence op's performance, while with 1-local step
complexity, op may still have to help distant operations on the path.
Local contention is orthogonal to sensitivity and local step complexity, and can be evaluated
in addition to either of them. However, if operations access only memory words associated with
operations they help, then d-local contention follows from sensitivity d + 1. (The contention
locality of our algorithm is discussed at the end of Section 4.)
Dwork, Herlihy and Waarts [12] suggest to measure the step complexity of algorithms while
taking contention into account, by assuming that concurrent accesses to the same memory
words are penalized by delaying their response. This is a good complexity measure to evaluate
solutions for specific problems; however, implementations of multi-word operations inevitably
result in concurrent accesses to the same words, creating hot spots. The complexity measure we
propose, sensitivity, is appropriate for evaluating multi-word implementations, as it measures
the influence of hot spots.
3 The Left-Right Algorithm
A general scheme for implementing multi-word operations [3, 7, 19, 25, 27] is that an operation
"locks" the pair of memory words before executing the operation, and "helps" stuck operations
to avoid blocking.
In this section, we introduce a variant of this scheme, the left-right algorithm, in which
operations lock memory words in different orders. We show that the sensitivity and liveness
of the left-right algorithm depend on the orientation of the conflict graph induced by locking
orders for overlapping operations.
At the end of this section, we discuss data structures in which operations have inherent
asymmetry; for such data structures, the left-right algorithm can be directly applied to achieve
constant sensitivity. In the next section, we show how to break symmetry in general situations
so as to govern the locking directions and reduce sensitivity.
3.1

Overview

A known scheme for implementing multi-word operations from unary operations [7, 19, 25, 27]
requires each processor to go through the following stages:
Locking: Lock the memory words.
Execution: Apply the operation to the memory words.
Unlocking: Unlock the memory words.
Each operation is assigned a unique identifier. A memory word is locked by an operation
if the operation's id is written in the word; the word is unlocked if it contains ?. If a memory
word is locked by an operation, then no other operation modifies the memory word until it is
unlocked.
An operation is blocked if it finds that some of the words it needs are locked by another,
blocking operation. In this case, the processor executing the blocked operation helps the
blocking operation.

Figure

2: A scenario with high sensitivity.
In order to be helped, the operation's details are published when it is invoked and its
state is maintained during its execution. Helping implies that more than one processor may
execute an operation. The initiating processor is the processor invoking the operation, while
the executing processors are the processors helping it to complete. Although more than one
processor can perform an operation, only the most advanced processor at each point of the
execution performs the operation, and other executing processors have no effect.
The blocking operation being helped can be either in its own locking stage or already in
the execution stage or the unlocking stage. An operation in its execution or unlocking stages
has already locked its words; once an operation has locked its data set, it will never be blocked
again. Therefore, an operation helping a blocking operation which has passed the locking
stage is guaranteed not to be blocked. In contrast, an operation still in its locking stage can be
blocked by a third operation, which in turn can be blocked by a fourth operation, and so on.
Therefore, help for a blocking operation in its locking stage may have to continue transitively.
A non-blocking implementation guarantees that some operation eventually terminates and
transitive helping stops; yet, the sensitivity can be very high, as illustrated by the next example.
Example 2 Consider a scenario with n overlapping operations, op
; the data set of
op i is fm Assume every operation op i locks its low-address word,
tries to lock its high-address word m 2 , while op
are delayed.
locked by op 2 , op 1 has to help op 2 ; since the high-address word of op 2 is locked by
has to recursively help op 3 , etc. Thus, the sensitivity of this simple implementation is
at least n \Gamma 1.
In Example 2, operations are symmetric and try to lock memory words in the same order
(low-address word first). The main idea of the left-right algorithm is that when implemented
operations are binary, asymmetry can be introduced by having the operations lock their memory
words in two directions: Either from left to right-low-address word first, or from right to
left-high-address word first.
Example 3 Consider Example 2 again, and assume odd-numbered operations, op
lock their low-address word first, while even-numbered operations, op
address word first. If op i
(for odd i) locks its low-address word, m i , and finds its high-address
locked by another operation (which must be op i+1 ), then op i+1 has already locked
all its data set. Therefore, op i
will only have to help op i+1
in its execution or unlocking stage
but no further operations.
An operation decides on its locking direction before the locking stage. After an operation
terminates its unlocking stage, it resets the shared-memory areas that were used in the decision
algorithm. Thus we have two new stages, decision and post-decision, encapsulating the
algorithm. In this section, we focus on the locking and unlocking stages, leaving the decision
and post-decision stages algorithms to the next section.
3.2 The pseudocode
To simplify the code and the description, a separate shared-memory area is used for the locking
and unlocking stages. The size of this area is the same as the size of the data area; memory
word i in the locking area corresponds to memory word i in the data area.
The algorithm uses a shared array, op-details, in which each initiating processor publishes
its operation's description when the operation starts. The initiating processor also sets an
operation id (op-id) to be used in later stages; the op-id is composed from the id of the initiating
processor and a timestamp generated by a timestamp function which returns a unique id each
time it is invoked.
The algorithm follows the general scheme discussed earlier, except that locking is done
either from left to right or from right to left. If an operation discovers that a word is locked by
another operation, it helps the blocking operation by executing all its stages until it unlocks
its words; then, the operation tries again.
The pseudocode appears in Algorithm 1.
The locking and unlocking stages can be executed by several processors on behalf of the
same operation. Therefore, synchronization is needed to ensure that no errors are caused by
concurrent processors executing the same operation.
Algorithm 2 presents the details of the shared procedures used for locking and unlocking.
The user is responsible for avoiding synchronization errors in the execution stage. The same
local variable tmp is used in all procedures, and it holds the last value read from the shared
memory.
The main synchronization mechanism-guaranteeing that only the most advanced executing
processor actually makes progress-is the timestamp part of the operation id. This field
is written by the initiating processor at the beginning of the operation and is cleared at the
beginning of the unlocking stage. An operation is valid if its timestamp is set; it is invalid
if its timestamp is not set. An executing processor finding that the operation is invalid (its
timestamp is not set) skips directly to the unlocking stage. This ensures that once a memory
word is unlocked by an operation, it will not be locked again by this operation. Similar
considerations apply when unlocking the word.
Each memory word is initially ?; when locked by some operation it contains its id.
Procedure lock locks the two memory words in the order they are given as parameters. A
single memory word is locked by cell-lock, which attempts to lock the word, if the operation is
Algorithm 1 The left-right algorithm: Code for processor p i .
record
low-word, high-word // the data set
ts // timestamp
direction // locking direction
shared state op-details[N ]
procedure
atomically write to op-details[i] // publish
ts
decide(m decide on locking direction
help(op-id) // help yourself
procedure help(op-id)
locking stage
if ( op-details[op-id.pid].direction == left ) then lock(low, high, op-id) // left to right
else lock(high, left, op-id) // right to left
execution(low, high, op-id) // execution stage
unlock(low, high, op-id) // unlocking stage
post-decision(low, high, op-id) // clean memory
still valid and the word is not locked by another operation. The procedure then re-reads the
word: If the word is locked by the operation, the procedure returns true; if the word is locked
by another operation, the executing processor helps the blocking operation and tries again. If
the operation becomes invalid, the procedure returns false.
To help another operation, the blocked operation invokes help with the blocking opera-
tion's id as argument. The blocked operation becomes an executing processor of the blocking
operation and goes through all its stages.
Procedure unlock invalidates the operation by resetting its ts field; this prevents other
executing processors from locking the words again. Then, it unlocks the two memory words
with cell-unlock, which unlocks a single word only if it is still locked by the operation. The
success of SC is not checked; if it fails, the word has already been unlocked by another executing
processor.
Procedure validate compares the timestamp passed in the operation id with the timestamp
in the ts field of the operation's entry in op-details; the operation is valid if they are equal.
Algorithm 2 The left-right algorithm: Shared procedures for processor p i .
procedure lock(x, y, op-id)
cell-lock(x, op-id)
cell-lock(y, op-id)
procedure cell-lock(addr, op-id)
try to lock
locked
if ( tmp == op-id ) then return true
else help(tmp)
if ( not validate(op-id) ) then return false // check if operation ended
procedure validate(op)
if ( op-details[op.pid].ts == op.ts ) then return true
else return false
procedure unlock(x, y, op-id)
invalidate the operation
cell-unlock(x, op-id) // unlock the words
cell-unlock(y, op-id)
procedure cell-unlock(addr, op-id)
procedure decide(m
The function decide makes sure that only the first executing processor to return from
decision (which is left unspecified for now) writes its decision in the operation's details. 2
As mentioned before, it is the responsibility of the user to avoid synchronization errors in
the execution stage. The user can use the timestamp of the operation and may add more state
information, if necessary. For example, if the implemented operation is SC2, we only need to
check before each write that the operation is still valid, in a manner similar to cell-lock.
This function is not needed at this point, when the decision stage is executed only by the initiating processor.
3.3 Proof of Correctness
The proof that the algorithm is linearizable follows as in other general schemes, e.g., [7, 19,
25, 27], once locking and unlocking are shown to behave correctly. Thus, we only show that
the data set of an operation is locked during the execution stage and is unlocked after the
operation terminates.
An executing processor returns from cell-lock either when the memory word is locked by
the operation, or when the operation is invalid. The operation becomes invalid only when
some executing processor reaches the unlocking stage, previously completing the locking stage.
Therefore, when the first executing processor returns from cell-lock, the word is locked by the
operation. This proves the next lemma:
Lemma 3.1 The data set of an operation op is locked when the first executing processor of op
completes the locking stage.
Procedure cell-unlock checks the word first. Thus, a word is unlocked only by an executing
processor of the operation which locked it, implying the following lemma:
Lemma 3.2 The data set of an operation op remains locked until the first executing processor
of op reaches the unlocking stage.
The next lemma proves that if some executing processor unlocks a memory word, then no
other executing processor locks it again.
Lemma 3.3 If m is in the data set of an operation op, then m remains unlocked after the
first executing processor of op reaches the unlocking stage.
Proof: An executing processor of op starts the unlocking stage by initializing the timestamp
field in op-details, thus invalidating op, then it performs LL(m) and SC(?,m). Another executing
processor of op which tries to lock m afterwards, validates op after performing LL(m).
If it finds that the operation is valid, then the value read from m is not ?, and the executing
processor does not try to lock m again. Thus, the lock field of a locked word is written only
in order to unlock it.
This implies two things: First, the SC in cell-unlock fails only if another executing processor
unlocked m. Second, no executing processor will lock m again.
3.4 Progress and Sensitivity
The liveness properties of the algorithm and its sensitivity depend on the orientation of the
conflict graph according to the locking directions.

Figure

3: Reducing sensitivity with helping directions.
Let ff be an interval of some operation op. The helping graph of ff, H ff , is a mixed graph
representing helping among operations overlapping ff. The nodes of H ff are the memory words
accessed by the operations overlapping ff. There is an edge e between nodes m 1 and m 2 if they
constitute the data set of some operation in ff; the direction of e is operations
in ff with data set fm the direction of e is operations in
ff with data set fm otherwise, e is undirected. H ff is a partially oriented
version of G ff , the conflict graph of ff.
Lemma 3.4 Let fi be an execution of the left-right algorithm in which no operation completes.
Then the helping graph of some interval in fi contains either an undirected edge or a directed
cycle.
Proof: There must be a point in fi from which no operation completes. Let ff be the interval
of some blocked operation, op, in fi. By the left-right algorithm, op is blocked if it can not lock
its data set. Since op does not terminate, the blocking operation is itself blocked by another
blocked operation. Since the number of processors is finite and each processor has at most one
pending operation, the number of blocked operations in fi is also finite. Therefore, there is a
cycle of blocked operations, op
2. By the algorithm, a blocked operation helps
the blocking operation.
then we have two operations blocking and helping each other. This implies they
have the same data set, but lock it in different directions, and there is an undirected edge in
H ff . If l ? 2, then we have three or more operations blocking and helping each other, and
there is a directed cycle in H ff
We next analyze the sensitivity of the algorithm.
Consider two operations, op 1 with data set fm and op 2 with data set fm g.
Assume a helping graph in which the edge between m 1 and m 2 is directed to m 2 , and the edge
between m 2 and m 3 is also directed to m 2 (see Figure 3). If op 1 helps op 2 , then by the code
of cell-lock, m 2 is locked by op 2
. However, op 2 locks m 3 before locking m 2 , and has passed its
locking stage; thus, op 1 helps op 2 only in its execution or unlocking stages. This argument is
generalized in the next lemma.
Lemma 3.5 Let ff be an interval of an operation op i , and let op j
be an overlapping operation.
If there is no directed path from a memory word of op i to a memory word of op j in H ff , then
there exists another interval of op i , ff 0 , with the same overlapping operations except op j , such
that
Proof: Let OP be the set of operations that op i
helps; there are directed paths from op i
to
the operations in OP. This implies that there is no directed path from a memory word of an
operation in OP to a memory word of op j
in H ff , since there is no directed path from a memory
word of op i to a memory word of op j in H ff . Thus, the operations in OP do not help op j
, as
argued before the lemma.
We construct an execution ff 0 without op j
. In ff 0 , op i performs the same sequence of steps
as in ff, and moreover, all the operations in OP lock their words in the same order as in ff.
If ff 0 is not an execution of the left-right algorithm, then let op k
be the first operation in
OP which locks a word in ff and can not do it in ff 0 . By the algorithm, this happens only if
another operation holds a lock on this word. However, we do not add new operations in ff 0
(only omit op j
) and the sequence of locking until op k
's locking in ff 0 is the same as in ff. Thus,
if the word is unlocked in ff it is also unlocked in ff 0 , and op k
succeeds in locking the word.
performs the same sequence of steps in ff and in ff 0 ,
If the length of directed paths in H ff
is bounded by d, then operations at distance d+ 1 (or
more) do not increase the number of steps taken by the operation, by Lemma 3.5.
Lemma 3.6 Let ff be an interval of the left-right algorithm. If the length of a directed path in
H ff is at most d, then the sensitivity of ff is at most d + 1.
3.5 Data Structures with Constant Sensitivity
We discuss two data structures in which the memory access patterns of operations are very
structured and therefore, locking directions can be determined a priori to obtain constant
sensitivity.
A linked list: If a linked list is implemented inside an array, then the data set of each
operation is m i and m i+1 , for some i. Let the locking direction of the operation be determined
by the parity of its low-address word; that is, the locking direction of an operation accessing
some i, is "left" if i is even, and "right", if i is odd. Clearly, neighboring
operations in the conflict graph lock in opposite directions. Therefore, the maximum length of
a directed path is one. By Lemma 3.4, the implementation is non-blocking, and by Lemma 3.6,
its sensitivity is two.
v a v b

Figure

4: Binary operations on a heap: v g is at even depth.
A heap: Israeli and Rappoport [18] present an implementation of a heap supporting a bubble
up and bubble down using unary LL and binary SC2 operations. In this implementation, the
data set of a binary operation is always a parent node and one of its children.
In order to implement the binary operations, we use the left-right algorithm, and let the
locking direction of an operation be the parity of the depth of the higher node it has to lock.
Clearly, operations with the same data set have the same locking direction.
To see that the length of a directed path is at most two, let v g , v f , v a and v b be four nodes
in a heap where v g is the parent node of v f , and v f is the parent node of v a and of v b (see

Figure

4). Two kinds of paths can be formed by contending operations. In the first kind,
the depths are monotone, e.g., In this case, neighboring
operations lock in opposite directions, and hence no directed path from v a to v g or from v b to
v g can be formed. In the second kind, the depths are not monotone, e.g., In
this case, neighboring operations lock in the same direction (determined by the depth of v f ),
and no directed path is formed between v a and v b .
Therefore, the longest directed path is of length one. By Lemma 3.4, the algorithm is
non-blocking; by Lemma 3.6, its sensitivity is two.
4 The Decision Algorithm
When access patterns are not known in advance, processors have to dynamically decide on
locking directions. In this section, we present an algorithm for choosing locking directions after
gathering some information about the memory access patterns, so as to minimize sensitivity.
For simplicity, a separate shared-memory area is used for the decision stage. The size of
this area is the same as the size of the locking area (or the data area); memory word i in the
decision area corresponds to word i in the locking or data areas.
op op

Figure

5: Locking directions: High-address word is equal to low-address word.
op op

Figure

Locking directions: Low-address words are equal.
Consider a simple example, where the data set of op is fm and the data set of op 0 is
assume that their data sets intersect. If
(the high-address word of op is
the low-address word of op 0 ) then the locking directions of op and op 0 have to be different in
order to avoid a directed path (see Figure 5). If
(the low-address word of op is the
low-address word of op 0 ) then the locking directions of op 1
and op 2
have to be equal in order
to avoid a directed path (see Figure 6) and similarly when
(the high-address word of
op is the high-address word of op 0 ).
This example leads us to concentrate on monotone paths, in which the high-address word of
one operation is the low-address word of another operation (as in Figure 5). In this situation,
we want neighboring operations to lock in different directions (as much as possible).
We first describe the algorithm for the restricted case of a single monotone path, and then
handle the general case, by decomposing an arbitrary conflict graph into monotone paths.
4.1 Monotone Paths
be operations, such that op i is initiated with processor id pid i
and data set
). For op i
, the operations with lower indices, op
, are called downstream
neighbors; the operations with higher indices, op are called upstream neighbors.
(This situation is similar to the one depicted in Figure 2.)
Assume that an operation chooses its locking direction according to the following rule:
is smaller than the pid of the upstream neighbor, pid i+1
, then op i decides left;
otherwise, op i decides right.
An edge operation, with no upstream neighbor, decides left.
Under this rule, directed paths correspond to ascending or descending chains of pid's; for
example, if all operations decide left, then pid's appear in ascending order. The key insight
is that the length of the longest chain of ascending or descending pid's depends on the range
of pid's. If the range of pid's can be reduced, while ensuring that adjacent operations have
different pid's, then Rule ( ) guarantees short directed paths.
We reduce the range of pid's using the ``deterministic coin tossing technique'' of Cole and
Vishkin [9]. This is a symmetry breaking algorithm for synchronous rings, which we adapt to
monotone paths in an asynchronous system.
The Cole-Vishkin algorithm works in phases. In each phase, the range is reduced by a
logarithmic factor, until the range is small. After the range is reduced, Rule ( ) is applied.
Although the new pid's are not unique any more, the fact that the pid's of adjacent operations
are different ensures that operations can decide on their locking directions.
As we see below, in order to perform k range reduction phases, an operation has to know
the pid's of k operations. Operations without k neighbors decide
left and are called edge operations. 3
The algorithm guarantees the alternation property-adjacent pid's are not equal.
Assume that the pid's after phase k are in the range lg. By the alternation property,
the length of an ascending or descending sequence of pid's is at most l. However, since there
are there may be a chain of l operations with the same locking
direction.
For monotone paths, we simplify the description by assuming that (a) all operations start
together, and (b) an operation waits after the locking stage, until all operations finish their
locking stage. Later, we will remove these assumptions.
We first describe a single phase of the algorithm, reducing the range of pid's to O(log n),
with few memory operations. Applying these ideas repeatedly, reduces the range to O(log   n),
using O(log   n) memory operations.
4.1.1 A Single Phase
An operation begins the phase by writing its pid into its low-address word. Since all operations
start together, all memory words are written together; since each operation waits until all
operations finish their locking stage, memory words are not over-written while some operation
is choosing its direction.
The pid's induce pointers between consecutive words in the path: The pid in the low-address
word leads to the operation's details record, where the high-address word of the operation can
be found.
3 Edge operations may also decide according to the parity of their distance from the end of the path.

Figure

7: Reduction of pid's in a single phase.
Assume op i
reads three pid's: From m i (its own pid), from m i+1 and from m i+2 , denoted
respectively. The binary representations of processors' pid's
are strings of length dlog ne, where the bits are numbered from 0 to dlog ne \Gamma 1, going from
least significant bit to most significant bit.
Let j be the index of the least significant (rightmost) bit in which the binary representations
of pid 0 (i) and pid 0 (i can be represented as a binary string of length dlog log ne.
to be the concatenation of the binary representation of j and b j , the value of
the jth bit in pid 0 (i).
Note that the length of pid 1
is dlog log ne
In a similar manner, op i
computes pid
Example 4 Consider Figure 7. In this example, pid 0 (i) is 01010101 (= 85), pid
11111101 (= 254), and pid 0 (i+2) is 01111101 (= 126). The index of the rightmost bit in which
differ is 3 and the value in pid 0 (i) is 0; thus, pid 1 (i) is 0110 (= 6).
The index of the rightmost bit in which pid 0 (i differ is 7 and the value in
pid
Since no memory word is modified during the decision stage, both op i
and op i+1
use pid 0 (i+
1). This implies that a single phase is consistent-the
new pid computed for an operation op by itself is equal to the new pid computed for op by its
downstream neighbor-as stated in the next lemma.
Lemma 4.1 If op i
and op i+1
are neighboring operations on the path, then they calculate the
same value for pid 1 (i 1).
Thus, we can refer to pid 1 (i) without mentioning which processor calculates it.
As described, pid 1 (i) is composed from a bit part, denoted pid 1 (i):bit, and an index part,
denoted pid 1 (i):index.
If pid 1
Thus, pid 0 (i) and pid 0 (i have the same bit in position pid 1
contradicting the fact that pid 1 (i):index is the rightmost bit in which pid 0 (i) and pid 0 (i
differ. This proves the following lemma:
Lemma 4.2 If op i
and op i+1
are neighboring operations on the path and pid 0 (i) 6= pid
Since the initial pid's are distinct, the lemma implies that consecutive values of pid 1 are
not equal, proving the alternation property.
4.1.2 The Multi-Phase Algorithm
We now describe how the above idea is applied repeatedly to reduce the pid's to be at most
three bits long; this guarantees that the longest monotone sequence of pid's contains at most
eight operations.
Denote '(0; n) = dlog ne, and let '(j
f(n) be the smallest integer j such that '(j; n) - 3; note that
An operation starts by writing its pid in its low-address word; then it reads
upstream memory words. An edge operation, without neighbors, chooses
left, without any further calculation.
Let the pid's read by op i
be pid 0 (i); pid 0 (i 1). By iterating on
the operation computes pid k (j) from pid k\Gamma1 (j) and pid 1), for every j,
as in the single-phase algorithm (Section 4.1.1).
Lemma 4.1 immediately implies that the algorithm is consistent.
Lemma 4.3 If op i
and op i+1
are neighboring operations on the path, then they calculate the
same value for pid k (i + 1), for every k,
The alternation property is proved by induction, applying Lemma 4.2 for every iteration.
Lemma 4.4 If op i and op i+1 are neighboring operations on the path such that pid 0 (i) 6=
pid
Proof: The proof is by induction on the phases of the local computation, denoted k, 0 -
f(n). In the base case, 1), by the assumption.
For the induction step, assume the lemma holds for phase k,
every consecutive pair of pid k have different values. Since each iteration is the same as the
one-phase algorithm, Lemma 4.2 implies that pid k+1 (i) 6= pid
can be represented with less than three bits, and thus,
has to be represented with more than three bits; however, for any x - 3,
This shows that after each iteration, the pid's length is strictly reduced.
After f(n) iterations the length is at most three, showing that every value of pid f(n)\Gamma1 is at
most three bits long. Thus, there are at most eight consecutive operations with ascending or
descending pid f(n) values.
After the range of pid's is reduced, an operation chooses a locking direction by comparing
its pid and the pid of its upstream neighbor, following Rule ( ). Edge operations, without
neighbors, decide left. At most 8 consecutive operations decide left, and at
most eight consecutive operations decide right. This proves the following theorem:
Theorem 4.5 The length of a directed path is at most 8
4.2 General Topology
In order to apply the range reduction technique of the previous section in general topologies,
we "disentangle" an arbitrary combination of overlapping and contending operations into a
collection of monotone paths. To achieve this, an operation first checks whether its data set
may create a non-monotone path: If it does, then the operation stalls while helping other
operations; otherwise, it applies the algorithm for a monotone path.
To explain this idea further, we need to define monotone paths more precisely. Assume
memory words l form an undirected path in some conflict graph. Memory word m i ,
local minimum if m it is a local maximum if
local minimum is created when two operations have the same
low-address word (as in Figure 6); a local maximum is created when two operations have the
same high-address word. A path is monotone if it does not contain local minima or maxima.
The decision stage of each operation is preceded with a separate marking stage. In the
marking stage, operations check the memory access patterns before trying to lock their memory
words, to detect local minima or maxima and avoid non-monotone paths. Only one of the
operations forming a local minimum or a local maximum continues and the others stall.
The marking stage maintains a variant of the conflict graph in the shared memory. Nodes
are marked memory words; a word can be either marked low, if it is the low-address word of
some operation, or marked high, if it is the high-address word of some operation. A word can
be marked as both low and high, if it is the low-address word of one operation and the high-
address word of another operation. A marked memory word is in the data set of an operation
which is not stalled.
An operation starts by trying to mark its low-address and high-address words. If marking
succeeds, then the operation's data set is on a monotone path and the operation decides on
a locking direction in a manner similar to Section 4.1. If marking fails, then the operation's
data set creates a non-monotone path; the operation stalls while helping other operations.
A word has two special fields-for low marking and for high marking. An operation marks
a word by writing its id instead of a ? in the low/high field; marking fails if the relevant field
is not ?. If an operation succeeds in marking the low field of its low-address word, then it
tries to mark the high field of its high-address word.
An operation unmarks its data set after unlocking it.
A word cannot be marked as high twice, or as low twice, implying that if two overlapping
operations have the same high-address word or the same low-address address word, only one
of them succeeds in marking the word while the other stalls. Consequently, there are no local
minima or maxima, avoiding non-monotone paths.
An operation can mark a memory word as low even if the word is already marked high by
another operation. In this respect, marking is different than locking since a word can not be
locked by two different operations, but it can be marked by two different operations.
Two problems arise due to the dynamic nature of the conflict
1. If new operations join the end of a marked path after the locking stage starts, then an
edge operation may help upstream operations after it finds the end of the path.
This can increase the sensitivity during the locking stage.
2. An operation may unmark its data set and then another operation with the same data
set may take its place.
This can yield inconsistencies, if some downstream operations use the first operation's
pid for their local computations, while other downstream operations use the second
operation's pid.
Both problems are handled by the same mechanism:
An operation finding the end of a path, prunes the path by placing a special end symbol
in the low field of the last word of the path. No operation can later mark the last word as low,
and hence no new operation can be "appended" at the end of the path.
When an operation unmarks its data set, it replaces its id with end in the low field of its
low-address word, if this word is marked high (i.e., if it has a downstream neighbor). In this
way, the path is "cut" at the word where the data set was unmarked; new operations will not
be able to mark this word and confuse the downstream operations.
When the high field is unmarked and the low field is marked end, both fields are cleared
and set to ?.
4.2.1 The Pseudocode
Each memory word contains two fields for marking, low and high, which may contain an
operation id, end or ?; both are initially ?.
A binary intersection field is added to the record containing the operation's details; this
field is set when the operation is intersected, i.e., its high-address word is already marked high
by another operation and is part of another monotone path. The intersection field is cleared
at the beginning of the marking stage; if it is set during the operation, then it is not cleared
until the operation terminates.
Each operation holds a local array, id-array, in which the pids of its upstream operations
are collected for the local computation (as in the monotone path algorithm of Section 4.1). The
tmp variable contains the last value read by the low- and high-level functions. The functionality
of other local variables should be clear from the code.
The high-level procedures for the decision and the post-decision stages appear in Algorithm
3. Algorithms 4 and 5 detail the code for synchronizing access to the shared data
structures.
An operation starts by initializing the local variables (see the code) and clearing the
intersection field. Then, the operation tries to mark its low-address word, using first. If
marking fails in first, then the operation helps the operation whose id is marking the word as
low until the word is unmarked, and tries again; if marking succeeds, the operation continues.
To advance to the next memory word, the operation extracts the initiating processor's id
from the operation id in the current word, and reads the high-address word from its record in
the op-details array. This is the next word on the monotone path. The operation also stores
the initiating processor's id in id-array for the local computation.
An operation marks its high-address word using next. If both the high and low fields are
empty, then the operation tries to mark the high field of the word and put the end mark in the
low field; if this is successful, the operation has just marked the end of the path, and it returns
as left. If the high field is empty and the low field is not, then it tries to mark the high field of
the word; if successful, it continues to the upstream words. Otherwise, this is an intersection
with another path; the operation sets the intersection flag, unmarks its low-address word, helps
the operation which is written in the high field of the word and starts again. An intersected
operation first unmarks its low-address word so that operations helping it will not continue to
help its upstream operations.
An operation op i uses next to access upstream words. The parameters passed to next are the
address of the last word accessed by op i , the current address, and op j , the id of the operation
whose high-address word it is. Hence, op i helps op j to mark its high-address word.
Note that if op i finds that op j is intersected, then op i acts as if it discovers the end of the
path, since op j is going to unmark its low-address word.
The operation unmarks its low-address word with unmark-low and its high-address word
with unmark-high. Procedure unmark-low replaces its id with end in the low field of its low-
address word, if the high field of its low-address address word is not ?, i.e., it has a downstream
neighbor; otherwise, it clears the low field.
Algorithm 3 The general algorithm: Decision and post-decision stages.
local id my-op-id // id of the operation being executed
local id last-op-id // id of the last operation read
local id id-array[f(n)+2] // for local computation of reduced id
local addr current, prev // current and previous addresses
local int index // index to id-array
local addr tmp // persistent, used to advance
procedure decision(m
op-details[op-id.pid].intersecting
low-address word
while advance to the next word
tmp.low // tmp is set in first or inside
current
if ( next(prev, current, op-id) ) then return left // an edge operation
return according to local computation on id-array // as in monotone path algorithm
procedure first(addr, op-id)
repeatedly try to mark the low-address word
if mark-low(addr, op-id) then return
else help(addr.low)
procedure next(prev, addr, op-id)
repeatedly try to mark upstream words
if mark-end(addr, op-id) then return true // an edge operation
if mark-high(addr, op-id) then return false // continue to next word on the path
if set-intersection(addr, op-id) then // intersected operation
initiating processor
unmark-word(prev) // unmark the low-address word
get the op-id of intersected operation
restart the operation // get a new timestamp and clear the intersection flag
else return true // not the initiating processor
if ( not validate(op-id) ) then return true // an edge operation
procedure post-decision(m
Algorithm 4 The general algorithm: Low-level procedures for the decision stage.
procedure mark-low(addr, op-id)
if ( tmp.low == op-id) then return true // marking is successful
else if ( tmp.low 6= ?) then return false // marked by another operation
procedure mark-end(addr, op-id)
if ( not check-intersection(op-id) ) then // not intersected
SC(addr,(op-id, end)) // mark as ending
if ( tmp.high == op-id ) then return true // marking is successful
else if ( tmp.high 6= ? ) then return false // marked by another operation
procedure mark-high(addr, op-id)
if ( not check-intersection(op-id) ) then // not intersected
if ( tmp.high == op-id ) then return true // marking successful
else if ( tmp.high 6= ? ) then return false // marked by another operation
procedure check-intersection(op-id)
SC(op-details[op-id.pid].intersection, tmp) // "touch" the intersection flag
else return false
procedure set-intersection(addr, op-id)
SC(op-details[op-id.pid].intersection, true)
return( op-details[op-id.pid].intersection
Algorithm 5 The general algorithm: Low-level procedures for the post-decision stage.
procedure unmark-low(addr, op-id)
if ( tmp.low == op-id) then
there are downstream operations
ending mark in low
else SC(addr,(?, ?))
else return
procedure unmark-high(addr, op-id)
if ( tmp.high == op-id) then
if ( tmp.low == end ) then // edge operation
ending mark
else SC(addr,(?, tmp.low)) // unmark high field
else return
4.2.2 Proof of Correctness
The proof of correctness concentrates on properties of the marking stage: We prove that the
data set of an operation is marked when the first executing operation enters the locking stage,
and unmarked when the first executing processor completes the operation.
An operation marks its low-address word in first, and tries to mark its high-address word
in the first call to next. A non-intersected operation returns from next only after it marks the
word passed as the parameter; an intersected operation restarts an does not return from next
at all. Therefore, the high-address word is marked when the first call to next returns. This
implies the next lemma:
Lemma 4.6 The data set of an operation op is marked when the first executing processor of
op enters the locking stage.
A word is unmarked only when the post-decision stage is reached, or when the initiating
processor finds that the operation is intersected (in next), and restarts the operation. This
implies the next lemma:
Lemma 4.7 The data set of an operation remains marked until the operation completes.
Next, we prove that the data set of the operation remains unmarked after the operation
completes. A problem may occur if some executing processors set the intersection flag, while
other executing processors mark the high-address word.
set-intersection write to high
mark-high
read(intersection)

Figure

8: Illustration for the proof of Lemma 4.8, Case 1.
Lemma 4.8 The intersection flag of an operation is set if and only if its high-address word is
not marked.
Proof: Three procedures access the high field-mark-end, mark-high and unmark-high. Procedure
unmark-high does not mark an unmarked word. Therefore, only mark-end and mark-high
can mark a previously unmarked operation.
We only consider mark-high; the same proof applies to mark-end, which has the same synchronization
structure. Let m be the high-address word of some operation op; consider the
memory accesses in set-intersection and in mark-high, with the call to check-intersection expanded

set-intersection mark-high
H5: SC(m.high)
Case 1: Suppose that m is marked as high after m.intersection is set (that is, S3 precedes
H5). SC(m.high) in mark-high (H5) is reached only if read(m.intersection) in mark-high (H4)
returns ?, hence, H4 precedes SC(m.intersection) in set-intersection (S3). Since LL(m.high)
in mark-high (H1) returns ? it precedes read(m.high) in set-intersection (S2) which returns
a non-? value. (See Figure 8.) Therefore, there is an intervening write to m.high between
LL(m.high) and the matching SC(m.high) in mark-high, so the SC fails.
Case 2: Suppose that m.intersection is set after m is marked as high (that is, H5 precedes
S3). SC(m.intersection) in set-intersection (S3) succeeds only if SC(m.intersection) in mark-high
precedes LL(m.intersection) in set-intersection (S1). (See Figure 9.) Since LL(m.high) in
mark-high returns ? and read(m.high) in set-intersection (S2) returns a non-? value,
there is an intervening write to m.high between LL(m.high) and the matching SC(m.high) in
mark-high, so the SC fails.
set-intersection write to high
mark-high

Figure

9: Illustration for the proof of Lemma 4.8, Case 2.
Lemma 4.9 The data set of an operation op remains unmarked after op terminates.
Proof: If m is the low-address word of op then m is marked only by the initiating processor
of op, before any processor starts executing op. Thus, no executing processor of op marks m
after it is unmarked, which proves the lemma when m is the low-address word of op.
Assume m is the high-address word of op. If op terminates at the post-decision stage,
then op is invalidated (its ts field is reset) and its data set is unmarked by unmark-word. If
op terminates since it is intersected (in next), the intersection flag is set until the operation is
invalidated by the initiating processor. By Lemma 4.8, a memory word is not marked if the
intersection flag is set.
Therefore, we only have to prove that an unmarked high-address word is not marked again
when op is invalid. Only mark-end and mark-high mark the high-address word; as in the proof
of Lemma 4.8, we only consider mark-high.
Assume, by way of contradiction, that mark-high marks m and then after it is unmarked,
and that op is invalid. Since mark-high validates the operation before marking, op is invalidated
between the validation and the SC(m.high) operation in mark-high. Moreover, the LL operation
in mark-high reads ? from m.low and m.high. By Lemma 4.6, m is marked when the first
executing processor of op reaches the locking stage and is unmarked only after the operation is
invalidated. Thus, m is marked with a write to m.high between LL(m.high) and its matching
SC(m.high) in mark-high, so the SC fails.
4.2.3 Analysis of the Algorithm
Lemma 4.10 Only monotone paths exist during the locking stage.
Proof: The data set of an operation is marked when the first executing process enters the
locking stage (Lemma 4.6) and remains marked until the first executing process completes the
post-decision stage (Lemma 4.7).
A memory word can not be marked low twice or marked high twice, by different operations,
by the code of mark-low, mark-high and mark-end. Thus, two operations with the same low-
address or high-address words cannot be in their locking stage together. That is, there are no
local minima or maxima and only monotone paths exist during the locking stage.
Lemma 4.11 Let op i be a downstream neighbor of op i+1 , and assume op i and op i+1 decide by
local computation. The last f(n) entries in id-array i
are the first f(n) entries in id-array i+1
Proof: By Lemma 4.10, the data sets of op i
and op i+1
are on a monotone path,
and op i+1
read different values from some memory word, m j , then some
operation unmarked m j between the reads from m j .
Without loss of generality, let op i
be the operation that reads from m j after it is unmarked.
We argue that op j
exits as only as an edge operation, by induction on the distance between
in the conflict graph. This contradicts the assumption that op i
and op i+1
decide
by local computation, and proves the lemma.
In the base case, if the distance is 1, then is in the data set of op i
. If op i
marks m j as an ending word, then op i
is an edge operation and the claim is proved. If another
operation op 0 marks m j as an ending word, then since the low-address word is marked before the
high-address word, m i is also marked by op 0 . Thus, op j
does not mark its data set; therefore,
stalls and the claim follows.
For the induction step, assume the lemma holds when the distance between m i and m j is
assume that distance is l. If op i
reads end from m j
, then op i
is an edge operation
and the claim follows. Since m j is unmarked before op i
reads from it, some operation op writes
marked end before op i
it, then the
claim follows by the induction hypothesis. Otherwise, op i
finds that op is
invalid. Therefore, next returns true and op i
exists as an edge operation.
The decision algorithm for a monotone path and the general decision algorithm differ only
in the marking phase. Lemma 4.11 implies that the new pid computed for an operation op
by itself is equal to the new pid computed for op by its downstream neighbor. Since both
algorithms have the same local computation, Theorem 4.5 implies:
Lemma 4.12 The length of a directed path of non-edge operations is at most eight.
The end of the path is at most f(n)+1 operations from an edge operation. New operations
can not join the end of the path by marking the low field of the last word, since it contains
end. Therefore, an edge operation helps only operations with distance smaller than or equal
to f(n) + 1.
Lemma 4.13 An edge operation does not help upstream operations with distance larger than
Theorem 4.14 The sensitivity of the decision stage and the locking stage is O(log   n).
Proof: The sensitivity of the decision stage is at most f(n) since an operation advances
at most f(n) words on the path in the conflict graph which contains its high-address word.
If there is a directed path of length nine in the locking stage in which operations lock from
right to left, then they all decide by local computation, which contradicts Lemma 4.12.
If there is a directed path of length 9 in the locking stage in which operations lock
from left to right, then there is an edge operation on the path with distance larger than f(n)+1
from the end of the path, by Lemma 4.12. This contradicts Lemma 4.13.
By Lemma 3.6, the sensitivity of the locking stage is at most f(n)
The algorithm does not guarantee local contention, as defined in [1]: Two operations may
access the same entry in op-details for different operations of the same processor, although
they are far away in the conflict graph. This happens since the op-details array is indexed by
processors' ids; this can be easily fixed by indexing op-details with operations' ids (as was done
in [1]).
5 The Step Complexity of Implementing Binary LL/SC
In this section, we prove an
\Omega\Gamma/22 log   n) lower bound on the number of steps required for
implementing a binary SC operation using unary operations. The lower bound is proved by
showing a problem which can be solved in O(1) operations using binary LL/SC, but requires
\Omega\Gammaequ log   n) operations if only unary operations (of any type) are used.
The "separating problem" is a variant of the maximal independent set (MIS) problem which
is defined as follows: A set of n processors, organized in a virtual ring; processor
assigned an initialized memory word m i , and gets as input the address of the memory
word of its clockwise neighbor, m next i
. Every processor has to terminate either as a member
or as a non-member; it is required that: (a) no two consecutive processors are members, and
(b) each non-member processor has at least one neighbor that will halt as a member.
The problem can be trivially solved with binary synchronization operations, LL and SC2:
Processor
load-links
and then load-links m next i
if they are both ? then
tries to SC2
its pid, atomically, into m i and m next i
. If p i succeeds, it exists as a member; otherwise, it
exists as a non-member.
Next, we show that any maximal independent set algorithm which uses only unary operations
has execution in which some processor performs at least \Omega\Gammaast log   n) operations. Linial
has proved that \Omega\Gammaat/   n) rounds are required to solve the MIS problem in the message-passing
model [20]. We modify this proof to the shared-memory model, but we get a smaller bound.
Linial uses the fact that in the message-passing model, by round t, a processor knows only
the addresses and the pid's of processor that are at distance t from it. This is not true in the
shared-memory model. Assume that the computation proceeds in rounds, and in each round
a processor performs a single memory operation. If each processor knows the addresses of its
neighbors after t rounds, and during round t processor accesses the memory word of
the processor at distance k from it, than it knows the addresses of its k neighbors after
1. However, the next lemma proves that this is the best that may happen:
Lemma 5.1 At round t, each processor on the ring knows the pid's and the addresses of
processors with distance 2 t from itself.
Proof: The lemma is proved by induction on t, the round number. The base case is
In this round, each processor knows only what it receives as input, that is, the addresses of its
two words. That is, it knows the address of its clockwise neighbor.
For the induction step, we assume the lemma holds for round t, and prove the lemma for
1. By the induction assumption, after round t processor p i
knows the pid's and the
addresses of processors with distance 2 t from it. Thus, in round t + 1, a processor p i can access
a single processor at distance - 2 t from it. That is, it can learn the pid's and the addresses
that processor knows. Therefore, it can know the pid's and the addresses of processors with
distance it.
The rest of the proof closely follows Linial [20].
We first argue that an algorithm finding a maximal independent set in a ring can be
converted into a 3-coloring algorithm in one more operation. After a processor decides on its
membership, it checks the decision of its right neighbor: If both decide non-members, it picks
color decides member and its neighbor decides non-member, it picks color 2; otherwise,
it picks color 3.
Let V be the set of all vectors (v and the v i are mutually distinct
processors' ids. A 3-coloring algorithm is a mapping c from V to f1,2,3g.
We construct a graph B x;n , whose set of nodes is V . All edges of B x;n are in the form:
(v
nodes and is a regular graph with degree
The mapping is a 3-coloring of B x;n . To see this, suppose c maps
(v to the same color. Then the 3-coloring algorithm for the
ring fails when the labeling happens to contain the segment (u; v
By a result of Linial [20], the chromatic number of B x;n
n). Therefore, to color
x;n with at most three colors, we must have x
=\Omega\Gamma323   n), that is, t
log   n).
This implies that \Omega\Gammaat/ log   n) steps are needs in order to solve the MIS problem. Together
with the O(1) algorithm which solves the MIS problem using binary LL/SC, this proves the
following theorem.
Theorem 5.2 An implementation of binary LL/SC operations from unary operations must
have
\Omega\Gammae/1 log   n) step complexity.
6 Discussion
This paper defines the sensitivity of implementing binary operations from unary operations;
the sensitivity is the distance, in terms of intersecting data sets, between two concurrent
operations that guarantees they do not interfere with each other. Clearly, if the sensitivity of
an implementation is low, then more operations can execute concurrently with less interference.
In our context, we say that one operation "interfere" with an other operation if one of them is
delayed because of the other. However, the notion of interference can be modified; for example,
one can add the requirement that the set of memory words accessed by an operation does not
change when it executes concurrently with another operation.
We present an algorithm for implementing a binary operation (of any type) from unary LL
and SC operations, with sensitivity O(log   n). The algorithm employs a symmetry breaking
algorithm based on "deterministic coin tossing" [9]. For practical purposes, a simple non-deterministic
symmetry breaking technique could be employed; however, care should be taken
to avoid deadlocks in this scheme.
Interestingly, our core algorithm-locking memory words in two directions-is similar to the
left-right dining philosophers algorithm (cf. [21, pp. 344-349]). In this problem, n philosophers
sit around a table and there is a fork between any pair of philosophers; from time to time, a
philosopher gets hungry and has to pick the two forks on both sides in order to eat. In the
left-right dining philosophers algorithm, a philosopher sitting in an odd-numbered place first
picks the left fork, while a philosopher sitting in an even-number place, first picks the right
fork. As in our implementation of a linked list, this guarantees short waiting chains when
many philosophers are hungry.
We also prove that any implementation of binary LL/SC from unary operations will have
to incur non-constant overhead in step complexity. This lower bound is not tight, since the
the step complexity of the wait-free extension of our algorithm [1] is at least O(log   n).

Acknowledgments

: The authors thank Shlomo Moran, Lihu Rappoport and Gadi Tauben-
feld for helpful comments on a previous version of the paper.



--R

Disentangling multi-object opera- tions
Performance issues in non-blocking synchronization on shared-memory multiprocessors
Universal constructions for multi-object operations
Primitives for asynchronous list compression.
The performance of spin lock alternatives for shared-memory multipro- cessors
Universal operations: Unary versus binary.
A method for implementing lock-free data structures
Localizing failures in distributed synchronization.
Deterministic coin tossing with applications to optimal parallel list ranking.
Universal operations: Unary versus binary.
Alpha Architecture Handbook.
Contention in shared memory systems.
The synergy between non-blocking synchronization and operating system structure

A methodology for implementing highly concurrent data objects.
Transactional memory: Architectural support for lock-free data structures
A correctness condition for concurrent objects.
Efficient wait-free implementation of a concurrent priority queue

Locality in distributed graph algorithms.
Distributed Algorithms.

The PowerPC Architecture: A Specification for a New Family of RISC Processors.
"Hot spot"
Software transactional memory.
Alpha AXP architecture.
Locking without blocking: Making lock based concurrent data structure algorithms nonblocking.
--TR
Deterministic coin tossing with applications to optimal parallel list ranking
Linearizability: a correctness condition for concurrent objects
Wait-free synchronization
Locality in distributed graph algorithms
Performance issues in non-blocking synchronization on shared-memory multiprocessors
Locking without blocking
Alpha AXP architecture
A methodology for implementing highly concurrent data objects
Transactional memory
A method for implementing lock-free shared-data structures
The PowerPC architecture
Primitives for asynchronous list compression
Disjoint-access-parallel implementations of strong shared memory primitives
The synergy between non-blocking synchronization and operating system structure
Localizing Failures in Distributed Synchronization
Universal operations
Disentangling multi-object operations (extended abstract)
Contention in shared memory algorithms
Universal Constructions for Large Objects
Distributed Algorithms
The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors
Efficient Wait-Free Implementation of a Concurrent Priority Queue
universal operations;deterministic coin tossing;load-linked/store-conditional operations;wait-free algorithms;asynchronous shared-memory systems;contention-sensitive algorithms