resulting from the execution of line ln:a30-51 by $s_{t}$ for $op$, or in the
configuration resulting from the execution of line ln:a30h-31 by $s_{t}$ for
$op$. Notice that either of these lines is executed after the request by $c$
is received, i.e. after $c$ invokes ClientEnqueue, and thus, after the
execution interval of $op$ starts.

By definition, the execution interval of $op$ terminates in the configuration
resulting from the execution of line ln:cl-enq:03. By inspection of the
pseudocode, this line is executed after line ln:cl-enq:02, i.e. after $c$
receives a response by some server. In the following, we show that the
linearization point of $op$ occurs before this response is sent to $c$.

Let $s_{j}$ be the server that $c$ initially sends the request for $op$ to. By
observation of the pseudocode, we see that $c$ may either receive a response
from $s_{j}$ if $s_{j}$ executes lines ln:a30-62 or ln:a30-51, or if $s_{j}$
executes lines ln:a30-28-ln:a30-29 or lines ln:a30-31-ln:a30-32, or if $s_{j}$
executes line ln:a30-1. To arrive at a contradiction, assume that either of
these lines is executed in $\alpha$ before the configuration in which the
linearization point of $op$ is placed. Thus, a tail token server $s_{t}$
executes lines ln:a30-61, ln:a30h-31, or ln:a30-51 in a configuration
following the execution of lines ln:a30-62, or ln:a30-51, or
ln:a30-28-ln:a30-29 or ln:a30-31-ln:a30-32, or line ln:a30-1 by $s_{j}$. Since
the algorithm is event-driven, inspection of the pseudocode shows that in
order for a tail token server to execute these lines, it must receive a
message containing he request for $op$ either from a client or from another
server.

Assume first that a tail token server executes the algorithm after receiving a
message containing a request for $op$ from a client. This is a contradiction,
since, on one hand, $c$ blocks until receiving a response, and thus, does not
sent further messages requesting $op$ or any other operation, and since $op$
terminates after $c$ receives the response by $s_{j}$, and on the other hand,
any other request from any other client concerns a different operation
$op^{\prime}$.

Assume next that a tail token server executes the algorithm after receiving a
message containing the request for $op$ from some other server. This is also a
contradiction since inspection of the pseudocode shows that after $s_{j}$
executes either of the lines that sends a response to $c$, it sends no further
message to some other server and instead, terminates the execution of that
instance of the algorithm.

The argumentation regarding dequeue operations is analogous. ∎

Denote by $L$ the sequence of operations which have been assigned
linearization points in $\alpha$ in the order determined by their
linearization points. Let $C_{i}$ be the configuration at which the $i$-th
operation $op_{i}$ of $L$ is linearized. Denote by $\alpha_{i}$, the prefix of
$\alpha$ which ends with $C_{i}$ and let $L_{i}$ be the prefix of $L$ up until
the operation that is linearized at $C_{i}$. Denote by $Q_{i}$ the sequence of
values that a sequential queue contains after applying the sequence of
operations in $L_{i}$, in order, starting from an empty queue; let
$Q_{0}=\epsilon$, i.e. $Q_{0}$ is the empty sequence. In the following, we
denote by $s_{t_{i}}$ the tail token server at $C_{i}$ and by $s_{h_{i}}$ the
head token server at $C_{i}$.

######  Lemma 36.

For each $i$, $i\geq 0$, if $lq_{i}^{j}$ are the contents of the local queue
of server $s_{j}$ at $C_{i}$, $h_{i}\leq j\leq t_{i}$, at $C_{i}$, then it
holds that $Q_{i}=lq_{i}^{h_{i}}\cdot lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot
lq_{i}^{t_{i}}$ at $C_{i}$.

###### Proof.

We prove the claim by induction on $i$. The claim holds trivially at $i=0$.

Fix any $i\geq 0$ and assume that at $C_{i}$, it holds that $Q_{i}$ =
$lq_{i}^{h_{i}}\cdot lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot lq_{i}^{t_{i}}$. We
show that the claim holds for $i+1$.

First, assume that $op_{i+1}$ is an enqueue operation by client $c$.
Furthermore, distinguish the following two cases:

  * •

Assume that $t_{i}=t_{i+1}$. Then, by the induction hypothesis,
$Q_{i}=lq_{i}^{h_{i}}\cdot lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot lq_{i}^{t_{i}}$.
In case the local queue of $s_{t_{i}}$ is not full, $s_{t_{i}}$ enqueues the
value $v_{i+1}$ of the $data$ field of the request for $op_{i+1}$ in the local
queue (line ln:a30-61 or line ln:a30h-31). Notice that, by Observation 33
changes on the local queues of servers occur only on token servers. Notice
also that those changes occur only in a step that immediately precedes a
configuration in which an operation is linearized. Thus, no further change
occurs on the local queues of $s_{h_{i}},s_{{h_{i}}+1},\ldots,s_{t_{i}}$
between $C_{i}$ and $C_{i+1}$, other than the enqueue on $lq_{i}^{t}$. Then,
it holds that $Q_{i+1}=Q_{i}\cdot v_{i+1}=lq_{i}^{h_{i}}\cdot
lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot lq_{i}^{t_{i}}\cdot
v_{i+1}=lq_{i}^{h_{i}}\cdot lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot
lq_{i+1}^{t_{i}}=lq_{i+1}^{h_{i}}\cdot lq_{i+1}^{{h_{i}}+1}\cdot\ldots\cdot
lq_{i+1}^{t_{i}}$, and if the head token server does not change between
$C_{i}$ and $C_{i+1}$, then $h_{i+1}=h_{i}$ and
$Q_{i+1}=lq_{i+1}^{h_{i+1}}\cdot lq_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot
lq_{i+1}^{t_{i+1}}$ and the claim holds. If the head token server changes,
i.e., if $h_{i+1}\neq h_{i}$, then by Observation 32,
$lq_{i+1}^{h_{i}}=\emptyset$ and the claim holds again.

In case the local queue of $s_{t_{i}}$ is full and since by assumption,
$s_{t_{i}}=s_{t_{i+1}}$, it follows by inspection of the pseudocode (line
ln:a30-5) and the definition of linearization points, that
$s_{t_{i+1}}=s_{h_{i+1}}$. In this case, $s_{t_{i+1}}$ responds with a NACK to
$c$ and the local queue remains unchanged. Since no token server changes
between $C_{i}$ and $C_{i+1}$, $Q_{i+1}=Q_{i}=lq_{i}^{h_{i}}\cdot
lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot lq_{i}^{t_{i}}=lq_{i+1}^{h_{i+1}}\cdot
lq_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot lq_{i+1}^{t_{i+1}}$ and the claim
holds.

  * •

Next, assume that $t_{i}\neq t_{i+1}$. This implies that the local queue of
$s_{t_{i}}$ is full just after $C_{i}$. Observation 32 implies that
$s_{t_{i}}$ forwarded the token to $s_{t_{i}+1}$ in some configuration between
$C_{i}$ and $C_{i+1}$. Notice that then, $s_{t_{i}+1}=s_{t_{i+1}}$. If the
local queue of $s_{t_{i+1}}$ is not full, then the condition of line ln:a30-6
evaluates to true and therefore, line ln:a30-61 is executed, enqueueing value
$v_{i+1}$ to it. Then at $C_{i+1}$, $lq_{i+1}^{t_{i+1}}=v_{i+1}$. By
definition, $Q_{i+1}=Q_{i}\cdot v_{i+1}$, and therefore,
$Q_{i+1}=lq_{i}^{h_{i}}\cdot lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot
lq_{i}^{t_{i}}\cdot v_{i+1}=lq_{i+1}^{h_{i+1}}\cdot
lq_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot lq_{i+1}^{t_{i}}\cdot
v_{i+1}=lq_{i+1}^{h_{i+1}}\cdot lq_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot
lq_{i+1}^{t_{i}}\cdot lq_{i+1}^{t_{i+1}}$ and the claim holds. If the local
queue of $s_{t_{i+1}}$ is full, then the condition of line ln:a30-6 evaluates
to false and therefore, line ln:a30-7.1 is executed. The operation is
linearized in the resulting configuration and NACK is sent to $c$. Notice that
in that case, the local queue of the server is not updated. Then,
$Q_{i+1}=Q_{i}=lq_{i}^{h_{i}}\cdot lq_{i}^{{h_{i}}+1}\cdot\ldots\cdot
lq_{i}^{t_{i}}\cdot lq_{i+1}^{t_{i+1}}=lq_{i+1}^{h_{i+1}}\cdot
lq_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot lq_{i+1}^{t_{i}}\cdot
lq_{i+1}^{t_{i+1}}$, and the claim holds.

The reasoning for the case where $op_{i+1}$ is an instance of a dequeue
operation is symmetrical. ∎

From the above lemmas and observations we have the following theorem.

######  Theorem 37.

The token-based distributed queue implementation is linearizable. The time
complexity and the communication complexity of each operation $op$ is $O({\tt
NS})$.

###  6.3 Token-Based Double Ended Queue (Deque)

The dequeue implementation is a natural generalization of the stack and queue
implementations described previously. The deque implementation is analogous to
the queue implementation described in section 6.2. To provide a deque, we add
actions to the queue’s design to support the additional operations supported
by a deque. We retain the static ordering of the servers and the head and tail
tokens. Again, each server uses a local data structure, this time a deque, on
which the server is allowed to execute enqueues or dequeues to the appropriate
end, only if it has either the tail token or the head token. The head and tail
tokens are initially held by $s_{0}$, but can be reassigned to other servers
during the execution.

####  6.3.1 Algorithm Description

Algorithm 17 presents the events triggered in a server $s$ and $s$’s actions
for each event. Each server, in addition to its id ($my\\_sid$), maintains a
local deque ($ldeque$) to store elements of the implemented deque. For the
token management, each server has two boolean flags ($hasHead$ and $hasTail$),
which are initialized true for the server $s_{0}$, and false for the rest.
Furthermore, the servers maintain a $fullDeque$ flag, similar to the
$fullQueue$ flag in Algorithm 13 of Section 6.2. Finally, the servers maintain
a local array (called $s$’s $clients$ array) for storing the requests they
receive directly from clients, which is used in a similar way as in Section
6.2.

Algorithm 17 Events triggered in a server 1 |  int $my\\_sid$;
---|---
2 |  LocalDeque $ldeque=\varnothing$;
3 |  LocalArray $clients=\varnothing$; /* Array of three values ¡op, data, isServed¿ */
4 |  boolean $fullDeque$ = false;
| /* True when tail and head are in the same server and tail is before head */
5 |  boolean $hasHead$; /* Initially hasHead and hasTail are true in server 0, and false in the rest */
6 |  boolean $hasTail$;
|
7 |  a message $\langle op,data,cid,sid,tk\rangle$ is received:
8 |  if (clients[$cid$] $\neq\bot$ AND clients[$cid$].$isServed$) $\\{$ /* If request was served earlier. */
9 |  send($cid$, $\langle{\tt ACK},$ clients[$cid$].$data,my\\_sid\rangle$);
10 |  clients[$cid$] = $\bot$;
11 |  $\\}$ else $\\{$
12 |  switch ($op$) $\\{$
13 |  case ENQ_T:
14 |  ServerEnqueueTail($op,data,cid,sid,tk$);
15 |  break;
16 |  case DEQ_T:
17 |  ServerDequeueTail($op,cid,sid,tk$);
18 |  break;
19 |  case ENQ_H:
20 |  ServerEnqueueHead($op,data,cid,sid,tk$);
21 |  break;
22 |  case DEQ_H:
23 |  ServerDequeueHead($op,cid,sid,tk$);
24 |  break;
25 |  case ACK:
26 |  clients[$cid$] = $\bot$;
27 |  send($cid,\langle{\tt ACK},data,sid\rangle$);
28 |  break;
29 |  case NACK:
30 |  clients[$cid$] = $\bot$;
31 |  send($cid,\langle{\tt NACK},\bot,sid\rangle$);
32 |  break;
|  $\\}$
|  $\\}$

The types of messages a server $s$ can receive are ENQ_T, DEQ_T for enqueuing
at and dequeuing from the tail, ENQ_H, DEQ_H for enqueuing at and dequeuing
from the head, and ACK or NACK sent by other servers as responses to $s$’s
forwarded messages. Every message $m$ a server receives, contains five fields:
(1) the $op$ field that represents the type of the request, (2) a $data$
field, that contains either the data to be enqueued or $\bot$, (3) a $cid$
field that contains the client id that requested the operation $op$, (4) a
$sid$ field that contains the id of the server which started forwarding the
request, and -1 otherwise, and (5) a $tk$ field, a flag used to pass tokens
from one server to another. The values that $tk$ can take are either
HEAD_TOKEN for the head token transition, TAIL_TOKEN for the tail token
transition, or $\bot$ for no token transition.

When server $s$ receives the head token, that means that $s$ can serve all
operations in its client array regarding the head endpoint (EnqueueHead(),
DequeueHead()). In analogous way, when server $s$ receives the token for the
tail, that means that $s$ can serve all operations in its client array for the
tail (EnqueueTail(), DequeueTail()). For this purpose, we use two functions,
ServeOldHeadOps() and ServeOldTailOps(). The clients whose requests are
served, are not informed until server $s$ receives their requests completes a
round-trip on the ring and returns back to $s$.

When a message is received (line ln:a32-18), server $s$ checks if the message
is stored in its $client$ array (line ln:a32-19). If it is, $s$ sends an ACK
message to client with $cid$ (line ln:a32-1) and removes the entry in the
$clients$ array (line ln:a32-2). If it is not, $s$ checks the message’s
operation code and acts accordingly (line ln:a32-9). Messages with operation
code ENQ_T, DEQ_T, ENQ_H, DEQ_H (lines ln:a32-10, ln:a32-12, ln:a32-14 and
ln:a32-16, respectively) are handled by functions ServerEnqueueTail() (line
ln:a32-11), ServerDequeueTail() (line ln:a32-13), ServerEnqueueHead() (line
ln:a32-15) and ServerDequeueHead() (line ln:a32-17), respectively. These
functions are presented in Algorithms 18-21. If the message is of type ACK
(line ln:a32-3) or NACK (line ln:a32-6), $s$ sets the $cid$ entry of the
clients array to $\bot$ (lines ln:a32-4, ln:a32-7), and sends an ACK (line
ln:a32-5) or NACK (line ln:a32-8) to the client.

Algorithm 18 presents pseudocode for function ServerEnqueueTail(), which is
called by a server $s$ when an ENQ_T message is received. First, $s$ checks
whether the $tk$ field of the message contains TAIL_TOKEN (line ln:a33-1). In
such a case, the message received by $s$ denotes a tail token transition. So,
$s$ sets its $hasTail$ flag to true (line ln:a33-2) and if it also had the
head token from a previous round, it sets its $fullDeque$ flag to true (line
ln:a33-3). At this point, $s$ has just received the global deque’s tail, so it
must serve all old operations that clients have requested directly from this
server to be performed in the deque’s tail. For that purpose, the server calls
the ServeOldTailOps() function (line ln:a33-4). Then, the server checks
whether the global deque is full and also the $ldeque$ is full and if it is
full, means that there is no free space left for the operation, thus $s$
responds to the request with with a NACK (lines ln:a33-5, ln:a33-6).
Otherwise, if the server can serve the request, it enqueues the received data
to the tail of $ldeque$ (line ln:a33-7) and responds with an ACK (lines
ln:a33-8, ln:a33-9). In any other case, $s$ cannot serve the request received,
but some other server might be capable to do so, so the message must be
forwarded. Server $s$ finds the next server (line ln:a33-10) and if $s$
handles the global deque’s tail, turns its flags ($hasTail$ and $fullDeque$)
to false (line ln:a33-11) and marks the token as TAIL_TOKEN for the token
transition (line ln:a33-12). If the message was send by a client, $s$ stores
the request to the $clients$ array (line ln:a33-13). Finally, $s$ forwards the
message to the next server (lines ln:a33-14, ln:a33-15).

Algorithm 18 Server helping function for handling an enqueue request to the global deque’s tail 33 |  void ServerEnqueueTail(int $op$, Data $data$, int $cid$, int $sid$, enum $tk$) $\\{$
---|---
34 |  if ($tk=={\tt TAIL\\_TOKEN}$) $\\{$
35 |  $hasTail$ = true;
36 |  if ($hasHead$) $fullDeque$ = true;
37 |  ServeOldTailOps($clients,fullDeque$);
|  $\\}$
38 |  if ($fullDeque$ AND IsFull($ldeque$)) $\\{$ /* Deque is full, can’t enqueue */
39 |  if ($sid==-1$) /* From client */
40 |  send($id,\langle{\tt NACK},\bot,my\\_sid\rangle$);
41 |  else /* From server */
42 |  send($sid,\langle{\tt NACK},\bot,cid,my_{s}id,\bot\rangle$);
43 |  $\\}$ else if ($hasTail$ AND !IsFull($ldeque$)) $\\{$ /* Server can enqueue */
44 |  enqueue_tail($deque,data$);
45 |  if ($sid==-1$) /* From client */
46 |  send($cid,\langle{\tt ACK},\bot,my\\_sid\rangle$);
47 |  else /* From server */
48 |  send($sid,\langle{\tt ACK},\bot,cid,my\\_sid,\bot\rangle$);
49 |  $\\}$ else $\\{$ /* Server can’t enqueue and global deque is not full */
50 |  $nsid$ = find_next_server($my\\_sid$);
51 |  if ($hasTail$) $\\{$
52 |  $hasTail$ = false;
53 |  $fullDeque$ = false;
54 |  $tk={\tt TAIL\\_TOKEN}$;
55 |  $\\}$ else $\\{$
56 |  $tk=\bot$;
|  $\\}$
57 |  if ($sid==-1$) $\\{$ /* From client */
58 |  clients[$cid$] = $\langle{\tt ENQ\\_T},data,false\rangle$;
59 |  send($nsid,\langle{\tt ENQ\\_T},data,cid,my\\_sid,tk\rangle$);
60 |  $\\}$ else $\\{$ /* From server */
61 |  send($nsid,\langle{\tt ENQ\\_T},data,cid,sid,tk\rangle$);
|  $\\}$
|  $\\}$
|  $\\}$

Algorithm 19 presents pseudocode for function ServerDequeueTail(), which is
called by a server $s$ when a DEQ_T message is received. First, $s$ checks
whether the $tk$ field of the message contains TAIL_TOKEN (line ln:a34-1). In
such a case, the message received by $s$, denotes a tail token transition. So,
$s$ sets its $hasTail$ flag to true (line ln:a34-2). then, $s$ serves all old
operations that clients have requested directly from this server to be
performed in the deque’s tail. For that purpose, the server calls
ServeOldTailOps() (line ln:a34-3). Afterwards, $s$ checks if the “global”
deque is empty and if it is empty, $s$ responds with a NACK (lines ln:a34-4,
ln:a34-5). Otherwise, if $s$ can serve the request, it dequeues the data from
the tail of its local deque (line ln:a34-6), and sends them to the appropriate
server or client with an ACK (lines ln:a34-7, ln:a34-8). In any other case,
$s$ cannot serve the request received, but some other server might be capable
to do so, thus the message must be forwarded. Server $s$ finds the previous
server $s_{prev}$ (line ln:a34-9) and if $s$ handles the global deque’s tail,
turns its flag for the tail to false (line ln:a34-10) and marks $tk$ as
TAIL_TOKEN for the token transition (line ln:a34-11). If the message received
was send by a client, $s$ stores the request to its $clients$ array (line
ln:a34-12). Finally, $s$ forwards the message to the previous server (lines
ln:a33-13, ln:a33-14).

Algorithm 19 Server helping function for handling an dequeue request to the global deque’s tail 62 |  void ServerDequeueTail(int $op$, int $cid$, int $sid$, enum $tk$) $\\{$
---|---
63 |  if ($tk=={\tt TAIL\\_TOKEN}$) $\\{$
64 |  $hasTail$ = true;
65 |  ServeOldTailOps($clients,fullDeque$);
|  $\\}$
66 |  if ($hasHead$ AND $hasTail$ AND $!fullDeque$ AND IsEmpty($ldeque$)) $\\{$
|  /* Deque is empty, can’t dequeue */
67 |  if ($sid==-1$) /* From client */
68 |  send($cid,\langle{\tt NACK},\bot,my\\_sid\rangle$);
69 |  else /* from server */
70 |  send($sid,\langle{\tt NACK},\bot,cid,my\\_sid,\bot\rangle$);
71 |  $\\}$ else if ($hasTail$ AND !IsFull($ldeque$)) $\\{$ /* Server can dequeue */
72 |  $data$ = dequeue_tail($ldeque$);
73 |  if ($sid==-1$) /* From client */
74 |  send($cid,\langle{\tt ACK},data,my\\_sid\rangle$);
75 |  else /* from server */
76 |  send($sid,\langle{\tt ACK},data,cid,my\\_sid,\bot\rangle$);
77 |  $\\}$ else $\\{$ /* Server can’t dequeue and global deque is not empty. */
78 |  $psid$ = find_previous_server($my\\_sid$);
79 |  if ($hasTail$) $\\{$
80 |  $hasTail$ = false;
81 |  $tk$ = ${\tt TAIL\\_TOKEN}$;
82 |  $\\}$ else $\\{$
83 |  $tk=\bot$;
|  $\\}$
84 |  if ($sid==-1$) $\\{$ /* From client */
85 |  clients[$cid$] = $\langle{\tt DEQ\\_T},\bot,{\tt false}\rangle$;
86 |  send($psid,\langle{\tt DEQ\\_T},\bot,cid,my\\_sid,tk\rangle$);
87 |  $\\}$ else $\\{$ /* from server */
88 |  send($psid,\langle{\tt DEQ\\_T},\bot,cid,sid,tk\rangle$);
|  $\\}$
|  $\\}$
|  $\\}$

Algorithm 20 presents pseudocode for function ServerEnqueueHead(), which is
called by a server $s$ when an ENQ_H message is received. First, $s$ checks if
it has the token for global deque’s head (line ln:a35-1) and if this is the
case, the server sets its $hasHead$ flag to true (line ln:a35-2). If $s$
already has the token for the global deque’s tail, it sets its $fullDeque$
flag to true (line ln:a35-3). At this point, $s$ has just received the global
deque’s head, so it must serve all old operations that clients have requested
directly from this server to be performed in the deque’s head. For that
purpose, server $s$ calls ServeOldHeadOps() (line ln:a35-4), which iterates
$s$’s $clients$ array and serves all operations for the deque’s head. Then,
the server checks whether the global deque is full and also the $ldeque$ is
full and if it is full, means that there is no free space left for the
operation, thus $s$ responds to the request with with a NACK (lines ln:a35-5,
ln:a35-6). Otherwise, if the server can serve the request, it enqueues the
received data to the deque’s head (line ln:a35-7) and responds with an ACK
(lines ln:a35-8, ln:a35-9). In any other case, $s$ cannot serve the request
received, but some other server might be capable to do so, so the message must
be forwarded. Server $s$ finds the previous server (line ln:a35-10) and if $s$
handles the global deque’s head, turns its flags ($hasHead$ and $fullDeque$)
to false (line ln:a35-11) and marks the $tk$ as HEAD_TOKEN for the token
transition (line ln:a35-12). If the message received was send by a client, $s$
stores the request to its $clients$ array (line ln:a35-13). Finally, $s$
forwards the message to the previous server (lines ln:a35-14, ln:a35-15).

Algorithm 20 Server helping function for handling an enqueue request to the global deque’s head 89 |  void ServerEnqueueHead(int $op$, Data $data$, int $cid$, int $sid$, enum $tk$) $\\{$
---|---
90 |  if ($tk=={\tt HEAD\\_TOKEN}$) $\\{$
91 |  $hasHead$ = true;
92 |  if ($hasTail$) $fullDeque$ = true;
93 |  ServeOldHeadOps(clients);
|  $\\}$
94 |  if ($fullDeque$ AND IsFull($ldeque$))$\\{$ /* Deque is full, can’t enqueue */
95 |  if ($sid==-1$) /* From client */
96 |  send($cid,\langle{\tt NACK},\bot,my\\_sid\rangle$);
97 |  else /* from server */
98 |  send($sid,\langle{\tt NACK},\bot,cid,my\\_sid,\bot\rangle$);
99 |  $\\}$ else if ($hasHead$ AND !IsFull($ldeque$)) $\\{$ /* Server can Server can enqueue. */
100 |  enqueue_head($ldeque,data$);
101 |  if ($sid==-1$) /* From client */
102 |  send($cid,\langle{\tt ACK},\bot,my\\_sid\rangle$);
103 |  else /* from server */
104 |  send($sid,\langle{\tt ACK},\bot,cid,my\\_sid,\bot\rangle$);
105 |  $\\}$ else $\\{$ /* Server can’t dequeue and global deque is not full. */
106 |  $psid$ = find_previous_server($my\\_sid$);
107 |  if ($hasHead$) $\\{$
108 |  $hasHead$ = false;
109 |  $fullDeque$ = false;
110 |  $tk$ = HEAD_TOKEN;
111 |  $\\}$ else $\\{$
112 |  $tk=\bot$;
|  $\\}$
113 |  if ($sid==-1$) $\\{$ /* From client */
114 |  clients[$cid$] = $\langle{\tt ENQ\\_H},data,{\tt false}\rangle$;
115 |  send($psid,\langle{\tt ENQ\\_H},data,cid,my\\_sid,tk\rangle$);
116 |  $\\}$ else $\\{$ /* from server */
117 |  send($psid,\langle{\tt ENQ\\_H},data,cid,sid,tk\rangle$);
|  $\\}$
|  $\\}$
|  $\\}$

Algorithm 21 presents pseudocode for function ServerDequeueHead(), which is
called by a server when a DEQ_H message is received by some server $s$. First,
$s$ checks if it has the token for global deque’s head (line ln:a36-1) and if
this is the case, the server sets its $hasHead$ flag to true (line ln:a36-2).
At this point, server $s$ has just received the global deque’s head, so it
must serve all old operations that clients have requested directly from this
server to be performed in the deque’s head. For that purpose, the server calls
the ServeOldHeadOps() routine (line ln:a36-4), which iterates $s$’s $clients$
array and serves all operations for the deque’s head. Then, the server checks
if the global deque is empty and if it is, $s$ responds to the request with a
NACK (lines ln:a36-5, ln:a36-6). Otherwise, if the server can serve the
request, it dequeues the data from the head (line ln:a36-7) and sends them to
the sender or client together with an ACK (lines ln:a36-8, ln:a36-9). In any
other case, $s$ cannot serve the request received, but some other server might
be capable to do so, so the message must be forwarded. Server $s$ finds the
next server (line ln:a36-10) and if $s$ has the token for the global head,
turns its flag for the head to false (line ln:a36-11) and and marks the $tk$
as HEAD_TOKEN for the token transition (line ln:a36-12). If the message
received was send by a client, $s$ stores the request to its $clients$ array
(line ln:a36-13). Finally, $s$ forwards the message to the next server (lines
ln:a36-14, ln:a36-15).

Algorithm 21 Server helping function for handling an dequeue request to the global deque’s head 118 |  void ServerDequeueHead(int $op$, int $cid$, int $sid$, enum $tk$) $\\{$
---|---
119 |  if ($tk=={\tt HEAD\\_TOKEN}$) $\\{$
120 |  $hasHead$ = true;
121 |  ServeOldHeadOps(clients);
|  $\\}$
122 |  if ($hasHead$ AND $hasTail$ AND $!fullDeque$ AND IsEmpty($ldeque$))$\\{$
|  /* Deque is empty, can’t dequeue */
123 |  if ($sid==-1$) /* From client */
124 |  send($cid,\langle{\tt NACK},\bot,my\\_sid\rangle$);
125 |  else /* from server */
126 |  send($sid,\langle{\tt NACK},\bot,cid,my\\_sid,\bot\rangle$);
127 |  $\\}$ else if ($hasHead$ AND !IsFull($ldeque$)) $\\{$ /* Server can Server can enqueue. */
128 |  $data$ = dequeue_head($ldeque$);
129 |  if ($sid==-1$) /* From client */
130 |  send($cid,\langle{\tt ACK},data,my\\_sid\rangle$);
131 |  else /* from server */
132 |  send($sid,\langle{\tt ACK},data,cid,my\\_sid,\bot\rangle$);
133 |  $\\}$ else $\\{$ /* Server can’t dequeue and global deque is not empty. */
134 |  $nsid$ = find_next_server($my\\_sid$);
135 |  $hasHead$ = false;
136 |  $tk$ = ${\tt HEAD\\_TOKEN}$;
137 |  $\\}$ else $\\{$
138 |  $tk=\bot$;
|  $\\}$
139 |  if ($sid==-1$) $\\{$ /* From client */
140 |  clients[$cid$] = $\langle{\tt DEQ\\_H},\bot,{\tt false}\rangle$;
141 |  send($nsid,\langle{\tt DEQ\\_H},\bot,cid,my\\_sid,tk\rangle$);
142 |  $\\}$ else $\\{$ /* from server */
143 |  send($nsid,\langle{\tt DEQ\\_H},\bot,cid,sid,tk\rangle$);
|  $\\}$
|  $\\}$
|  $\\}$

Algorithm 22 presents pseudocode for the client functions. These are
EnqueueTail(), DequeueTail(), EnqueueHead(), DequeueHead(). All clients have
two local variables, $head\\_sid$ and $tail\\_sid$, to store the last known
server to have the head token and the tail token, respectively. These
variables initially store the id of the server zero, but may change values
during runtime. The messages received by clients contain two fields: $status$
which contains either the data from a dequeue operation, or $\bot$ in case of
an enqueue, and $tail\\_sid$ or $head\\_sid$, depending on the function, which
contains the id of the server that currently holds the token.

Algorithm 22 Enqueue and dequeue operations for a client of the token-based deque.  144 |  int $tail\\_sid$ = 0, $head\\_sid$ = 0;
---|---
|
145 |  Data EnqueueTail(int $cid$, Data $data$) $\\{$
146 |  send($tail\\_sid,\langle{\tt ENQ\\_T},data,cid,-1,\bot\rangle$);
147 |  $\langle status,tail\\_sid\rangle$ = receive();
148 |  return $status$;
|  $\\}$
|
149 |  Data DequeueTail(int $cid$) $\\{$
150 |  send($tail\\_sid,\langle{\tt DEQ\\_T},\bot,cid,-1,\bot\rangle$);
151 |  $\langle status,tail\\_sid\rangle$ = receive();
152 |  return $status$;
|  $\\}$
|
153 |  Data EnqueueHead(int $cid$, Data $data$) $\\{$
154 |  send($head\\_sid,\langle{\tt ENQ\\_H},data,cid,-1,\bot\rangle$);
155 |  $\langle status,head\\_sid\rangle$ = receive();
156 |  return $status$;
|  $\\}$
|
157 |  Data DequeueHead(int $cid$) $\\{$
158 |  send($head\\_sid,\langle{\tt DEQ\\_H},\bot,cid,-1,\bot\rangle$);
159 |  $\langle status,head\\_sid\rangle$ = receive();
160 |  return $status$;
|  $\\}$

For enqueuing at the deque’s tail, clients calls EnqueueTail() (line
ln:a37-1). This function sends an ENQ_T message to the last known server,
which has the token for the global tail (line ln:a37-2). The server with the
tail token may have changed, but the client is still unaware of the change. In
that case, server $s$, which received the message, stores this message in its
$clients$ array and then forwards the message to the next server in the order,
as described in Algorithm 18. During this time, the client blocks waiting for
a server’s response. Once the client receives the response (line ln:a37-3), it
returns the contents of the $status$ variable (line ln:a37-4).

Algorithm 23 Auxiliary functions for a server of the token-based deque. 161 |  void ServeOldTailOps(void) $\\{$
---|---
162 |  LocalSet $eliminated=\emptyset$
|
163 |  for each $cid1\not\in eliminated$ such that clients[$cid1$].$op=={\tt ENQ\\_T}\ \\{$
164 |  if there is $cid2\not\in eliminated$ such that clients[$cid2$].$op=={\tt DEQ\\_T}\ \\{$
165 |  clients[$cid2$].$data$ = clients[$cid1$].$data$;
166 |  clients[$cid1$].$isServed$ = true;
167 |  clients[$cid2$].$isServed$ = true;
168 |  $eliminated=eliminated\cup\\{cid1,cid2\\}$;
|  $\\}$
|  $\\}$
169 |  if (!$fullDeque$) $\\{$
170 |  for each $cid$ such that clients[$cid$].$op=={\tt ENQ\\_H}\ \\{$
171 |  if (!IsFull($ldeque$)) $\\{$
172 |  enqueue_tail($ldeque$, clients[$cid$].$data$);
173 |  clients[$cid$].$isServed$ = true;
|  $\\}$
|  $\\}$
|  $\\}$
174 |  for each $cid$ such that clients[$cid$].$op=={\tt DEQ\\_T}\ \\{$
175 |  if (!IsEmpty($ldeque$)) $\\{$
176 |  clients[$cid$].$data$ = dequeue_tail($ldeque$);
177 |  clients[$cid$].$isServed$ = true;
|  } } }
|
|
178 |  void ServeOldHeadOps(void) $\\{$
179 |  LocalSet $eliminated=\emptyset$
|
180 |  for each $cid1\not\in eliminated$ such that clients[$cid1$].$op=={\tt ENQ\\_H}\ \\{$
181 |  if there is $cid2\not\in eliminated$ such that clients[$cid2$].$op=={\tt DEQ\\_H}\ \\{$
182 |  clients[$cid2$].$data$ = clients[$cid1$].$data$;
183 |  clients[$cid1$].$isServed$ = true;
184 |  clients[$cid2$].$isServed$ = true;
185 |  $eliminated=eliminated\cup\\{cid1,cid2\\}$;
|  $\\}$
|  $\\}$
186 |  if (!$fullDeque$) $\\{$
187 |  for each $cid$ such that clients[$cid$].$op=={\tt ENQ\\_H}\ \\{$
188 |  if (!IsFull($ldeque$)) $\\{$
189 |  enqueue_head($ldeque$, clients[$cid$].$data$);
190 |  clients[$cid$].$isServed$ = true;
|  $\\}$
|  $\\}$
|  $\\}$
191 |  for each $cid$ such that clients[$cid$].$op=={\tt DEQ\\_H}\ \\{$
192 |  if (!IsEmpty($ldeque$)) $\\{$
193 |  clients[$cid$].$data$ = dequeue_head($ldeque$);
194 |  clients[$cid$].$isServed$ = true;
|  } } }

The enqueuing at the deque’s head is symmetrical to this approach and is
achieved with the function EnqueueHead() (line ln:a37-9). The only difference
is that the server which is send the message to, is the server with id
$head\\_sid$ (line ln:a37-10) and the message’s operation code is ENQ_H
instead of ENQ_T.

For dequeuing at the deque’s tail, clients call DequeueTail() (line ln:a37-5).
This function sends a DEQ_T message to the last known server which has the
token for the global tail (line ln:a37-6). Then, the client waits for server
to respond. Once the client receives the response (line ln:a37-7), it returns
the contents of the $status$ variable (line ln:a37-8).

The dequeuing at the deque’s head is symmetrical to this approach and is
achieved with the function DequeueHead() (line ln:a37-11). The only difference
is that the server, to whom the message was sent, is the server with id
$head\\_sid$ (line ln:a37-12) and the message’s operation code is DEQ_H
instead of DEQ_T.

####  6.3.2 Proof of Correctness

Let $\alpha$ be an execution of the token-based deque algorithm presented in
Algorithms 17, 18, 19, 20, 21, 22, and 23.

Each server maintains local boolean variables $hasHead$ and $hasTail$, with
initial values false. Whenever some server $s_{i}$ receives a TAIL_TOKEN
message, i.e. a message with its $tk$ field equal to TAIL_TOKEN (line
ln:a33-1, line ln:a34-1), the value of $hasTail$ is set to true (line
ln:a33-2, line ln:a34-2). By inspection of the pseudocode, it follows that the
value of $hasTail$ is set to false if the local deque of $s_{i}$ is full (line
ln:a33-11, line ln:a34-10); then, a TAIL_TOKEN message is sent to the next or
previous server (line ln:a33-15, line ln:a34-14). The same holds for $hasHead$
and HEAD_TOKEN messages, i.e. messages with their $tk$ field equal to
HEAD_TOKEN. Thus, the following observations holds.

######  Observation 38.

At each configuration in $\alpha$, there is at most one server for which the
local variable $hasHead$ ($hasTail$) has the value true.

######  Observation 39.

In some configuration $C$ of $\alpha$, a TAIL_TOKEN message is sent from a
server $s_{j}$, $0\leq j<{\tt NS}-1$, to a server $s_{k}$, where
$k=(j+1)\mod{{\tt NS}}$, only if the local deque of $s_{j}$ is full in $C$. A
TAIL_TOKEN message is sent from a server $s_{j}$, $0\leq j<{\tt NS}-1$, to a
server $s_{k}$, where $k=(j-1)\mod{{\tt NS}}$, only if the local deque of
$s_{j}$ is empty in $C$.

Similary, a HEAD_TOKEN message is sent from $s_{j}$ to $s_{k}$, where
$k=(j+1)\mod{{\tt NS}}$, only if the local deque of $s_{j}$ is empty in $C$.
HEAD_TOKEN message is sent from $s_{j}$ to $s_{k}$, where $k=(j-1)\mod{{\tt
NS}}$, only if the local deque of $s_{j}$ is full in $C$.

By inspection of the pseudocode, we see that a server performs an enqueue
(dequeue) back operation on its local deque $ldeque$ either when executing
line ln:a33-7 (line ln:a34-6.1) or when it executes ServeOldTailOps. Further
inspection of the pseudocode (lines ln:a33-1-ln:a33-3, line ln:a33-6.1, as
well as lines ln:a34-1-ln:a34-3, line ln:a34-6), shows that these lines are
executed when $hasTail={\tt true}$. By inspection of the pseudocode, the same
can be shown for $hasHead$. Then, the following observation holds.

######  Observation 40.

Whenever a server $s_{j}$ performs an enqueue or dequeue back (front)
operation on its local deque, it holds that its local variable $hasTail$
($hasHead$) is equal to true.

If $hasTail={\tt true}$ ($hasHead={\tt true}$) for some server $s$ in some
configuration $C$, then we say that $s$ has the tail (head) token. The server
that has the tail token is referred to as tail token server. The server that
has the head token is referred to as head token server.

By a straight-forward induction, the following lemma can be shown.

######  Lemma 41.

The mailbox of a client in any configuration of $\alpha$ contains at most one
incoming message.

Let $op$ be any operation in $\alpha$. We assign a linearization point to $op$
by considering the following cases:

  * •

If $op$ is an enqueue back operation for which a tail token server executes an
instance of Algorithm 17, then it is linearized in the configuration resulting
from the execution of either line ln:a33-5, or line ln:a33-7, or line
ln:a38h-23, or line ln:a38h-81, whichever is executed for $op$ in that
instance of Algorithm 17 by the tail token server.

  * •

If $op$ is a dequeue back operation for which a head token server executes an
instance of Algorithm 17, then it is linearized in the configuration resulting
from the execution of either line ln:a34-4, or line ln:a34-6.1, or line
ln:a38h-23, or line ln:a38h-51, whichever is executed for $op$ in that
instance of Algorithm 17 by the tail token server.

  * •

If $op$ is an enqueue front operation for which a tail token server executes
an instance of Algorithm 17, then it is linearized in the configuration
resulting from the execution of either line ln:a35-5, or line ln:a35-7, or
line ln:a38h-13, or line ln:a38h-31, whichever is executed for $op$ in that
instance of Algorithm 17 by the head token server.

  * •

If $op$ is a dequeue front operation for which a head token server executes an
instance of Algorithm 17, then it is linearized in the configuration resulting
from the execution of either line ln:a36-5, or line ln:a36-7, or line
ln:a38h-13, or line ln:a38h-61, whichever is executed for $op$ in that
instance of Algorithm 17 by the head token server.

######  Lemma 42.

The linearization point of an enqueue (dequeue) operation $op$ is placed in
its execution interval.

###### Proof.

Assume that $op$ is an enqueue back operation and let $c$ be the client that
invokes it. After the invocation of $op$, $c$ sends a message to some server
$s$ (line ln:a37-2) and awaits a response. Recall that routine receive() (line
ln:a37-3) blocks until a message is received. The linearization point of $op$
is placed in the configuration resulting from the execution of either line
ln:a33-5, or line ln:a33-7, or line ln:a38h-23, or line ln:a38h-81 by $s_{t}$
for $op$. Notice that since the execution of Algorithm 17 by $s_{t}$ is
triggered by a message that contains the request for $op$, either of these
lines is executed after the request by $c$ is received, i.e. after $c$ invokes
EnqueueTail, and thus, after the execution interval of $op$ starts.

By definition, the execution interval of $op$ terminates in the configuration
resulting from the execution of line ln:a37-4. By inspection of the
pseudocode, this line is executed after line ln:a37-3, i.e. after $c$ receives
a response by some server. In the following, we show that the linearization
point of $op$ occurs before this response is sent to $c$.

Let $s_{j}$ be the server that $c$ initially sends the request for $op$ to. By
observation of the pseudocode, we see that $c$ may either receive a response
from $s_{j}$ if $s_{j}$ executes lines ln:a32-1, or ln:a33-5, or ln:a33-8.

To arrive at a contradiction, assume that either of these lines is executed in
$\alpha$ before the configuration in which the linearization point of $op$ is
placed. Thus, a tail token server $s_{t}$ executes lines line ln:a33-5, or
line ln:a33-7, or line ln:a38h-23, or line ln:a38h-81, in a configuration
following the execution of lines ln:a32-1, or ln:a33-5, or ln:a33-8 by
$s_{j}$. Since the algorithm is event-driven, inspection of the pseudocode
shows that in order for a tail token server to execute these lines, it must
receive a message containing the request for $op$ either from a client or from
another server.

Assume first that a tail token server executes the algorithm after receiving a
message containing a request for $op$ from a client. This is a contradiction,
since, on one hand, $c$ blocks until receiving a response, and thus, does not
sent further messages requesting $op$ or any other operation, and since $op$
terminates after $c$ receives the response by $s_{j}$, and on the other hand,
any other request from any other client concerns a different operation
$op^{\prime}$.

Assume next that a tail token server executes the algorithm after receiving a
message containing the request for $op$ from some other server. This is also a
contradiction since inspection of the pseudocode shows that after $s_{j}$
executes either of the lines that sends a response to $c$, it sends no further
message to some other server and instead, terminates the execution of that
instance of the algorithm.

The argumentation regarding dequeue back, enqueue front, and dequeue front
operations is analogous. ∎

Denote by $L$ the sequence of operations which have been assigned
linearization points in $\alpha$ in the order determined by their
linearization points. Let $C_{i}$ be the configuration at which the $i$-th
operation $op_{i}$ of $L$ is linearized. Denote by $\alpha_{i}$, the prefix of
$\alpha$ which ends with $C_{i}$ and let $L_{i}$ be the prefix of $L$ up until
the operation that is linearized at $C_{i}$. Denote by $D_{i}$ the sequence of
values that a sequential deque contains after applying the sequence of
operations in $L_{i}$, in order, starting from an empty deque; let
$D_{0}=\epsilon$, i.e. $D_{0}$ is the empty sequence. In the following, we
denote by $s_{t_{i}}$ the tail token server at $C_{i}$ and by $s_{h_{i}}$ the
head token server at $C_{i}$.

######  Lemma 43.

For each $i$, $i\geq 0$, if $ld_{i}^{j}$ are the contents of the local deque
of server $s_{j}$ at $C_{i}$, $h_{i}\leq j\leq t_{i}$, at $C_{i}$, then it
holds that $D_{i}=ld_{i}^{h_{i}}\cdot ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot
ld_{i}^{t_{i}}$ at $C_{i}$.

###### Proof.

We prove the claim by induction on $i$. The claim holds trivially at $i=0$.

Fix any $i\geq 0$ and assume that at $C_{i}$, it holds that $D_{i}$ =
$ld_{i}^{h_{i}}\cdot ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot ld_{i}^{t_{i}}$. We
show that the claim holds for $i+1$.

Assume that $op_{i+1}$ is an enqueue back operation by client $c$.
Furthermore, distinguish the following two cases:

  * •

Assume that $t_{i}=t_{i+1}$. Then, by the induction hypothesis,
$D_{i}=ld_{i}^{h_{i}}\cdot ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot ld_{i}^{t_{i}}$.
In case the local queue of $s_{t_{i}}$ is not full, $s_{t_{i}}$ enqueues the
value $v_{i+1}$ of the $data$ field of the request for $op_{i+1}$ in the local
deque (line ln:a33-7 or line ln:a38h-81). Notice that, by Observation 40
changes on the local deques of servers occur only on token servers. Notice
also that those changes occur only in a step that immediately precedes a
configuration in which an operation is linearized. Thus, no further change
occurs on the local deques of $s_{h_{i}},s_{{h_{i}}+1},\ldots,s_{t_{i}}$
between $C_{i}$ and $C_{i+1}$, other than the enqueue on $ld_{i}^{t}$. Then,
it holds that $D_{i+1}=D_{i}\cdot v_{i+1}=ld_{i}^{h_{i}}\cdot
ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot ld_{i}^{t_{i}}\cdot
v_{i+1}=ld_{i}^{h_{i}}\cdot ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot
ld_{i+1}^{t_{i}}=ld_{i+1}^{h_{i}}\cdot ld_{i+1}^{{h_{i}}+1}\cdot\ldots\cdot
ld_{i+1}^{t_{i}}$, and if the head token server does not change between
$C_{i}$ and $C_{i+1}$, then $h_{i+1}=h_{i}$ and
$D_{i+1}=ld_{i+1}^{h_{i+1}}\cdot ld_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot
ld_{i+1}^{t_{i+1}}$ and the claim holds. If the head token server changes,
i.e., if $h_{i+1}\neq h_{i}$, then by Observation 39,
$ld_{i+1}^{h_{i}}=\emptyset$ and the claim holds again.

In case the local deque of $s_{t_{i}}$ is full and since by assumption,
$s_{t_{i}}=s_{t_{i+1}}$, it follows by inspection of the pseudocode (line
ln:a30-5) and the definition of linearization points, that
$s_{t_{i+1}}=s_{h_{i+1}}$. In this case, $s_{t_{i+1}}$ responds with a NACK to
$c$ and the local deque remains unchanged. Since no token server changes
between $C_{i}$ and $C_{i+1}$, $D_{i+1}=D_{i}=ld_{i}^{h_{i}}\cdot
ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot ld_{i}^{t_{i}}=ld_{i+1}^{h_{i+1}}\cdot
ld_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot ld_{i+1}^{t_{i+1}}$ and the claim
holds.

  * •

Next, assume that $t_{i}\neq t_{i+1}$. This implies that the local deque of
$s_{t_{i}}$ is full just after $C_{i}$. Observation 39 implies that
$s_{t_{i}}$ forwarded the token to $s_{t_{i}+1}$ in some configuration between
$C_{i}$ and $C_{i+1}$. Notice that then, $s_{t_{i}+1}=s_{t_{i+1}}$. If the
local deque of $s_{t_{i+1}}$ is not full, then the condition of line
ln:a33-6.1 evaluates to true and therefore, line ln:a33-7 is executed,
enqueueing value $v_{i+1}$ to it. Then at $C_{i+1}$,
$ld_{i+1}^{t_{i+1}}=v_{i+1}$. By definition, $D_{i+1}=D_{i}\cdot v_{i+1}$, and
therefore, $D_{i+1}=ld_{i}^{h_{i}}\cdot ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot
ld_{i}^{t_{i}}\cdot v_{i+1}=ld_{i+1}^{h_{i+1}}\cdot
ld_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot ld_{i+1}^{t_{i}}\cdot
v_{i+1}=ld_{i+1}^{h_{i+1}}\cdot ld_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot
ld_{i+1}^{t_{i}}\cdot ld_{i+1}^{t_{i+1}}$ and the claim holds. If the local
deque of $s_{t_{i+1}}$ is full, then the condition of line ln:a33-6.1
evaluates to false and therefore, line ln:a33-5 is executed. The operation is
linearized in the resulting configuration and NACK is sent to $c$. Notice that
in that case, the local deque of the server is not updated. Then,
$D_{i+1}=D_{i}=ld_{i}^{h_{i}}\cdot ld_{i}^{{h_{i}}+1}\cdot\ldots\cdot
ld_{i}^{t_{i}}\cdot ld_{i+1}^{t_{i+1}}=ld_{i+1}^{h_{i+1}}\cdot
ld_{i+1}^{{h_{i+1}}+1}\cdot\ldots\cdot ld_{i+1}^{t_{i}}\cdot
ld_{i+1}^{t_{i+1}}$, and the claim holds.

The reasoning for the case where $op_{i+1}$ is an instance of a dequeue back,
enqueue front, or enqueue back operation is symmetrical. ∎

From the above lemmas and observations we have the following theorem.

######  Theorem 44.

The token-based distributed deque implementation is linearizable. The time
complexity and the communication complexity of each operation $op$ is $O({\tt
NS})$.

###  6.4 Hierarchical approach.

In this section, we outline how the hierarchical approach, described in
Section LABEL:sec:impl-paradigms, is applied to the token-based designs.

Only the island masters play the role of clients to the algorithms described
in this section. So, it is each island master $m_{i}$ that keeps track of the
last server(s), which responded to its batches of requests. In the stack and
deque implementations, $m_{i}$ performs elimination before contacting a
server. In the queue implementation, batching is done by having each batch
containing requests of the same type. In the deque implementation, each batch
contains requests of the same type that are to be applied to the same
endpoint. A batch can be sent to a server using DMA; the same could be done
for getting back the responses. A server that does not hold the appropriate
token to serve a batch of requests, forwards the entire batch to the next (or
previous) server. Since token-based algorithms exploit locality, a batch of
requests will be processed by at most two servers.

###  6.5 Dynamic Versions of the Implementations

Algorithm 24 Events triggered in a server of a dynamic token-based deque. 1 | a message $\langle op,data,cid,sid,tk\rangle$ is received:
---|---
2 |  if (!clients[$cid$] AND clients[$cid$].$isServed$) $\\{$
|  /* If message has been served earlier. */
3 |  send($cid,\langle{\tt ACK},$ clients[$cid$].$data,\ my\\_sid\rangle$);
4 |  clients[$cid$] = $\bot$;
5 |  $\\}$ else $\\{$
6 |  switch ($op$) $\\{$
7 |  case ENQ:
8 |  if ($tk$ == TAIL_TOKEN) $\\{$
9 |  $hasTail$ = true;
10 |  ServeOldEnqueues();
|  $\\}$
11 |  if (!$hasTail$) $\\{$ /* Server does not have token */
12 |  $nsid$ = find_next_server($my\\_sid$);
13 |  if ($sid==-1$) $\\{$ /* From client. */
14 |  clients[$cid$] = $\langle{\tt ENQ},data,{\tt false}\rangle$;
15 |  send($nsid,\langle{\tt ENQ},data,cid,my\\_sid,\bot\rangle$);
16 |  $\\}$ else $\\{$ /* From server. */
17 |  send($nsid,\langle{\tt ENQ},data,cid,sid,\bot\rangle$);
|  $\\}$
18 |  $\\}$ else if (!IsFull($lqueue$)) $\\{$
19 |  enqueue($lqueue,data,tail\\_round$);
20 |  if ($sid==-1$) /* From client. */
21 |  send($cid,\langle{\tt ACK},\bot,my\\_sid\rangle$);
22 |  else /* From server. */
23 |  send($sid,\langle{\tt ACK},\bot,cid,my\\_sid,\bot\rangle$);
24 |  $\\}$ else $\\{$ /* Server moves the tail token */
25 |  $nsid$ = find_next_server($my\\_sid$);
26 |  send($nsid,\langle op,data,cid,my\\_sid,{\tt TAIL\\_TOKEN}\rangle$);
27 |  $tail\\_round++$;
28 |  allocate_new_space($lqueue,tail\\_round$);
29 |  $hasTail$ = false;
|  $\\}$
30 |  break;
31 |  case DEQ:
---|---
32 |  if ($tk$ == HEAD_TOKEN) $\\{$
33 |  $hasHead$ = true;
34 |  ServeOldDequeues();
|  $\\}$
35 |  if (!$hasHead$) $\\{$
36 |  $nsid$ = find_next_server($my\\_sid$);
37 |  if ($sid==-1$) $\\{$ /* From client */
38 |  clients[$cid$] = $\langle{\tt DEQ},\bot,{\tt false}\rangle$;
39 |  send($nsid,\langle{\tt DEQ},\bot,cid,my\\_sid\rangle$);
40 |  $\\}$ else $\\{$ /* From server */
41 |  send($nsid,\langle{\tt DEQ},\bot,cid,sid,\bot\rangle$);
|  $\\}$
42 |  $\\}$ else if (!IsEmpty($lqueue$)) $\\{$ /* can dequeue. */
43 |  $data$ = dequeue($lqueue,head\\_round$);
44 |  if ($sid==-1$) /* From client */
45 |  send($cid,\langle{\tt ACK},data,my\\_sid\rangle$);
46 |  else /* From server */
47 |  send($sid,\langle{\tt ACK},data,cid,my\\_sid,\bot\rangle$);
48 |  $\\}$ else if ($tail\\_round==head\\_round$) $\\{$
49 |  $tail\\_round=head\\_round=0$;
50 |  if ($sid==-1$) /* empty to client */
51 |  send($cid,\langle{\tt NACK},\bot,my\\_sid\rangle$);
52 |  else /* empty to server */
53 |  send($sid,\langle{\tt NACK},\bot,cid,my\\_sid,\bot\rangle$ );
54 |  $\\}$ else $\\{$ /* Move the head token to next */
55 |  $nsid$ = find_next_server($my\\_sid$);
56 |  send($nsid,\langle op,\bot,cid,my\\_sid,{\tt HEAD\\_TOKEN}\rangle$);
57 |  $head\\_round++$;
58 |  $hasHead$ = false;
|  $\\}$
59 |  break;
60 |  case ACK:
61 |  clients[$cid$] = $\bot$;
62 |  send($cid,\langle{\tt ACK},data,sid\rangle$);
63 |  break;
64 |  case NACK:
65 |  clients[$cid$] = $\bot$;
66 |  send($cid,\langle{\tt NACK},\bot,sid\rangle$);
67 |  break;
|  $\\}$
|  $\\}$

The implementations presented above (in Section 6) are static. Their dynamic
versions retain the placement of servers in a logical ring, and the token that
renders the server able to execute operations in its local partition. In the
static versions of the algorithms, when the servers consume all their
predefined space for the data structure, the global (implemented) data
structure is considered full, and the token server was sending NACK to clients
to notify them of this event.

In the dynamic version, though, there is no upper bound to the number of
elements that can be stored in the data structure. In order to modify the
static version of the structures of this section, we remove the mechanism that
sends NACK messages to clients. Instead, every time a server $s$ receives the
token (regarding inserts), it allocates an additional chunk of memory for its
local partition. Because of this circular movement of the token, the elements
are stored along a spiral path, that spans over all servers. Each chunk is
marked with a sequence number, associated with the coil of the spiral, to
distinguish the order of allocation.

An example of the transformation of a static algorithm to a dynamic is the
dynamic version of the queue algorithm, presented in Algorithm 24. In this
design a server $s$ uses two tokens, the head and tail token. In analogy, $s$
deploys two variables ($tail\\_round$ and $head\\_round$) to count the times
the tokens have come to its possession. When a server $s$ receives an ENQ
message (line ln:alg30d-1) but has no space left to store the element (line
ln:alg30d-2), it forwards the request along with the token to the next server
in the ring. Afterwards, $s$ increases by one the variable $tail\\_round$ and
allocates a new memory chunk, by calling allocate_new_space(), to be used
during the next time the token comes to its possession.

For the DEQ operation, the server performs additional actions concerning the
empty queue state (line ln:alg30d-5), where after responding with a NACK, it
re-initializes $tail\\_round$ and $head\\_round$ to be equal to zero (line
ln:alg30d-6). An empty queue implies that the allocated chunks for lqueue are
also empty, hence they can be recycled and be used again anew. During the head
token transition, $s$ increases $head\\_round$ by one chunk (line
ln:alg30d-7), so that when the head token comes to its possession to dequeue
from the next memory.

The double ended queue (deque) algorithm is going to work verbatim after these
modifications. For the stack implementation the modifications are analogous.
In this design there is one token, hence each server associates one counter
with the token rounds. Each time a server $s$ moves the token to another
server because the local stack is full, it increases the counter and allocates
a new chunk for future use, and $s$ moves the token due to an empty stack, the
counter is decreased by one. However, the dynamic design for the stack would
introduce the termination problem described for queues. Nevertheless, the
problem can be solved by applying the same technique of using client arrays as
we did to solve the problem in the queue implementation.

##  7 Distributed Lists

A list is an ordered collection of elements. It can either be sorted, in which
case the elements appear in the list in increasing (or decreasing) order of
their keys, or unsorted, in which case the elements appear in the list in some
arbitrary order (e.g. in the order of their insertion). A list $L$ supports
the operations Insert, Delete, and Search. Operation Insert(L, k, I) inserts
an element with key $k$ and associated info $I$ to $L$. Operation Delete(L, k)
removes the element with key $k$ from $L$ (if it exists), while operation
Search(L, k) detects whether an element with key $k$ is present in $L$ and
returns the information $I$ that is associated with $k$.

In this section, we first provide an implementation of an unsorted distributed
list in which we follow a token-based approach for implementing $Insert$. In
this implementation, Search and Delete are highly parallel. We then build on
this approach in order to get a distributed implementation of a sorted list.

###  7.1 Unsorted List

The list state is stored distributedly in the local memories of several of the
available servers, potentially spreading among all of them, if its size is
large enough. The proposed implementation follows a token-based approach for
implementing insert. Thus, we assume that the servers are arranged on a
logical ring, based on their ids.

Algorithm 25 Events triggered in a server of the distributed unsorted list. 1 |  List $llist$ = $\varnothing$;
---|---
2 |  int $my\\_id$, $next\\_id$, $token$ = $0$, $round$ = $0$;
|
|
3 |  a message $\langle op,cid,key,data,mloop,tk\rangle$ is received:
4 |  switch ($op$) $\\{$
5 |  case INSERT:
6 |  if ($tk$ == TOKEN) $\\{$
7 |  $token$ = $my\\_id$;
8 |  allocate_new_memory_chunk($llist,round$);
|  $\\}$
9 |  $status_{1}$ = search($llist$, $key$);
10 |  if ($status_{1}$) send($cid$, NACK);
11 |  else $\\{$
12 |  if ($token\neq my\\_id$) $\\{$
13 |  $next\\_id$ = get_next($my\\_id$);
14 |  if ($my\\_id\neq{\tt NS}-1$) $\\{$
15 |  send($next\\_id$, $\langle op,cid,key,data,mloop,tk\rangle$);
16 |  $\\}$ else send($next\\_id$, $\langle op,cid,key,data,{\tt true},tk\rangle$);
17 |  $\\}$ else $\\{$
18 |  if (($my\\_id\neq{\tt NS}-1$) AND ($round>0$) AND !($mloop$)) $\\{$
19 |  $next\\_id$ = get_next($my\\_id$);
20 |  send($next\\_id$, $\langle op,cid,key,data,mloop,tk\rangle$);
21 |  $\\}$ else $\\{$
22 |  $status_{2}$ = insert($llist,round,key,data$);
23 |  if ($status_{2}$ == false) $\\{$
24 |  $round++$;
25 |  $token$ = get_next($my\\_id$);
26 |  send($token$, $\langle op,cid,key,data,mloop,{\sf TOKEN}\rangle$);
27 |  $\\}$ else send($cid$, ACK);
|  $\\}$
|  $\\}$
|  $\\}$
28 |  break;
29 |  case SEARCH:
30 |  $status_{1}$ = search($llist$, $key$);
31 |  if ($status_{1}$) send($cid$, $\langle{\tt ACK},my\\_id\rangle$);
32 |  else send($cid$, $\langle{\tt NACK},my\\_id\rangle$);
33 |  break;
34 |  case DELETE:
35 |  $status_{1}$ = delete($llist$, $key$);
36 |  if ($status_{1}$) send($cid$, ACK);
37 |  else send($cid$, NACK);
38 |  break;
|  $\\}$

At each point in time, there is a server (not necessarily always the same),
denoted by $s_{t}$, which holds the insert token, and serves insert
operations. Initially, server $s_{0}$ has the token, thus the first element to
be inserted in the list is stored on server $s_{0}$. Further element
insertions are also performed on it, as long as the space it has allocated for
the list does not exceed a threshold. In case server $s_{0}$ has to service an
insertion but its space is filled up, it forwards the token by sending a
message to the next server, i.e. server $s_{1}$. Thus, if server $s_{i}$,
$0\leq i<{\tt NS}$, has the token, but cannot service an insertion request
without exceeding the threshold, it forwards the token to server
$s_{(i+1)\mod{\tt NS}}$. When the next server receives the token, it allocates
a memory chunk of size equal to threshold, to store list elements. When the
token reaches $s_{{\tt NS}-1}$, if $s_{{\tt NS}-1}$ has filled all the local
space up to a threshold, it sends the token again to $s_{0}$. Then, $s_{0}$
allocates more memory (in addition to the memory chunk it had initially
allocated for storing list elements) for storing more list elements. The token
might go through the server sequence again without having any upper-bound
restrictions concerning the number of round-trips. In order for a server to
know whether the token has performed a round-trip on the ring, and hence all
servers have stored list elements, it deploys a variable to count the number
of ring round-trips it knows that the token has performed.

Algorithm 26 Insert, Search and Delete operation for a client of the distributed list. 39 |  boolean ClientInsert(int $cid$, int $key$, data $data$) {
---|---
40 |  boolean $status$;
|
41 |  send($0$, $\langle{\tt INSERT},cid,key,data,{\tt false},-1\rangle$);
42 |  $status$ = receive();
43 |  return $status$;
| }
|
44 |  boolean ClientSearch(int $cid$, int $key$) {
45 |  int $sid$;
46 |  int $c$ = $0$;
47 |  boolean $status$;
48 |  boolean $found$ = false;
|
49 |  send_to_all_servers($\langle{\tt SEARCH},cid,key,\bot,{\tt false},-1\rangle$);
50 |  do {
51 |  $\langle status,sid\rangle$ = receive();
52 |  if ($status$ == ACK) $found$ = true;
53 |  $c++$;
54 |  } while ($c<{\tt NS}$);
55 |  return $found$;
| }
|
56 |  boolean ClientDelete(int $cid$, int $key$) {
57 |  int $sid$;
58 |  int $c$ = $0$;
59 |  boolean $status$;
60 |  boolean $deleted$ = false;
|
61 |  send_to_all_servers($\langle{\tt DELETE},cid,key,\bot,{\tt false},-1\rangle$);
62 |  do {
63 |  $\langle status,sid\rangle$ = receive();
64 |  if ($status$ == ACK) $deleted$ = true;
65 |  $c++$;
66 |  } while ($c<{\tt NS}$);
67 |  return $deleted$;
| }

Event-driven code for the server is presented in Algorithm 25. Each server $s$
maintains a local list ($llist$ variable) allocated for storing list elements,
a $token$ variable which indicates whether $s$ currently holds the token, and
a variable $round$ to mark the ring round-trips the token has performed;
$round$ is initially $0$, and is incremented after every transmission of the
token to the next server.

Each message a server receives has five fields: (1) $op$ that denotes the
operation to be executed, (2) $cid$ that holds the id of the client that
initiated a request, (3) $key$ that holds the value to be inserted, (4)
$mloop$ stands for “message loop”, a boolean value that denotes if the message
has traversed the whole server sequence and (5) $tk$ that is set when a
forwarded message also denotes a token transition from one server to the
other.

When a message is received, the server $s$ first checks its type. If the
message is of type INSERT (line code:ser:ins1), $s$ first checks whether the
message has the $tk$ field marked. If it is marked (line code:ser:tok1), $s$
sets a local variable $token$ equal to its own id (line code:ser:tok2) and
allocates additional space for its local part of the list (line
code:ser:tok3).

Afterwards, $s$ searches the part of the list that it stores locally, for an
element with the same key ($key$ variable in the algorithm) as the one to be
inserted (line code:ser:ins2). Searching $llist$ for the element has to be
performed independently of whether the server holds the token or not. Since
this design does not permit duplicate entries, if such an element is found,
the server responds with NACK to the client (line code:ser:ins3). Otherwise
(line code:ser:ins4), $s$ checks whether the new element can be stored in
$llist$.

In case $s$ does not hold the token (line code:ser:ins5), it is not allowed to
perform an insertion, therefore it must forward the message to the next server
in the ring. If $s$ is not $s_{{\tt NS}-1}$ (line code:ser:ins6), it forwards
to the next server the request (code:ser:ins8). In case $s$ is $s_{{\tt
NS}-1}$, it means that all servers have been searched for the element and the
element was not found. Server $s$ sends the message to the next server (in
order to eventually reach the token server), after marking the $mloop$ field
of the message as true, to indicate that the message has completed a full
round-trip on the ring (line code:ser:ins9).

On the other hand, if $s$ holds the token (line code:ser:ins10), it must first
check whether there is room in $llist$ to insert the element in it. If there
is room in $llist$ and the local variable $round$ of $s$ equals to false
(which means that the list does not expand to the next servers) or the message
has already performed a round-trip on the ring, then $s$ inserts the element
and returns ACK. If however, $round>0$ and the message has not performed a
round trip on the ring ($mloop=={\tt false}$), $s$ continues forwarding the
message.

If the token server’s local memory is out of sufficient space (line
code:ser:ins16) (i.e. the insert() function was unsuccessful), $s$ forwards
the message to the next server the $tk$ field with TOKEN (line code:ser:ins21)
to indicate that this server will become the new token server after $s$. Also,
$s$ increments $round$ by one to count the number of times the token has
passed from it. The $round$ variable is also used by function
allocate_new_memory_chunk() that allocates additional space for the list (line
code:ser:tok3).

Notice that, contrary to other token-based implementations presented in
previous sections, the token server of the unsorted list does not need to rely
on client tables in order to stop a message from being incessantly forwarded
from one server to another, without ever being served. By virtue of having
clients always sending their insert requests to $s_{0}$, an insert request
$r_{j}$ that arrives at $s_{0}$ before some other insert request $r_{k}$, is
necessarily served before $r_{k}$. The scenario where insert requests
constantly arrive at the token server before $r_{j}$, making the token travel
to the next server before $r_{j}$ can be served, is thus avoided.

Upon receiving a SEARCH request from a client (line code:ser:srch1), a server
searches for the requested element in its local list (line code:ser:srch2) and
sends ACK to the server if the element is found (line code:ser:srch4) and NACK
otherwise (line code:ser:srch6).

Upon receiving a DELETE request from a client (line code:ser:del1), a server
attempts to delete the requested element from its local list (line
code:ser:del2) and sends ACK to the server if the deletion was successful
(line code:ser:del4). Otherwise it sends NACK (line code:ser:del6).

The pseudocode of the client is presented in Algorithm 26. Notice that insert
operations in the proposed implementation are executed in sequence and must
necessarily pass through server $0$ and be forwarded through the server ring,
if necessary due to space constraints. Search and Delete operations, on the
contrary, are executed in parallel.

In order to execute an insertion, a client calls ClientInsert() (line
code:ins:0) which sends an INSERT message (line code:ins:1) to server $0$,
regardless of which server holds the token in any given configuration, and
then blocks waiting for a response (line code:ins:2). If the client receives
ACK from a server, then the element was inserted correctly. If the client
receives NACK, then the insertion failed, due to either limited space, or the
existence of another element with the same key value.

For a search operation the client calls ClientSearch() (line code:srch:0). The
client sends a SEARCH request to all servers (line code:srch:1) and waits to
receive a response message (line code:srch:3) from each server (do while loop
of lines code:srch:2-code:srch:6). The requested element is in the list if the
client receives ACK from some server (line code:srch:4). A delete operation
proceeds similarly to ClientSearch(). It is initiated by a client by sending a
DELETE request to all servers (line code:del:1). The client then waits to
receive a response message (line code:del:3) from each server (do while loop
of lines code:del:2-code:del:6). The requested element has been found in the
list of some client and deleted from there, if the client receives ACK from
some server $s$.

####  7.1.1 Proof of Correctness

We sketch the correctness argument for the proposed implementation by
providing linearization points. Let $\alpha$ be an execution of the
distributed unsorted list algorithm presented in Algorithms 25 and 26. We
assign linearization points to insert, delete and search operations in
$\alpha$ as follows:

  * •

Insert. Let $op$ be any instance of ClienInsert for which an ACK or a NACK
message is sent by a token server. Then, if ACK is sent by a token server for
$op$ (line code:ser:ins22), the linearization point is placed in the
configuration resulting from the execution of line code:ser:ins15 that
successfully inserted the required element into the server’s local list. If
NACK is sent for $op$ (line code:ser:ins3), then the linearization point is
placed in the configuration resulting from the execution of line
code:ser:ins2, where the search operation on the local list of the server
returned true.

  * •

Let $op$ be any instance of ClientDelete for which an ACK or a NACK message is
sent by a server. Then, if ACK is sent by a server $s$ for $op$, the
linearization point is placed in the configuration resulting from the
execution of line code:ser:del2 by the server that sent the ACK. Otherwise, if
the key $k$ that $op$ had to delete was not present in any of the local lists
of the servers in the beginning of the execution interval of $op$, then the
linearization point of $op$ is placed at the beginning of its execution
interval. Otherwise, if $k$ was present but was deleted by a concurrent
instance $op^{\prime}$ of ClientDelete, then the linearization point is placed
right after the linearization point of $op^{\prime}$.

  * •

Let $op$ be any instance of ClientSearch for which an ACK or a NACK message is
sent by a server. Then, if ACK is sent by a server $s$ for $op$, the
linearization point is placed in the configuration resulting from the
execution of line code:ser:srch2 by the server that sent the ACK. Otherwise,
if the key $k$ that $op$ had to find was not present in the list in the
beginning of its execution interval, then the linearization point is placed
there. Otherwise, if $k$ was present but was deleted by a concurrent instance
$op^{\prime}$ of ClientDelete, then the linearization point is placed right
after the linearization point of $op^{\prime}$.

######  Lemma 45.

Let $op$ be any instance of an insert, delete, or a search operation executed
by some client $c$ in $\alpha$. Then, the linearization point of $op$ is
placed in its execution interval.

###### Proof.

Let $op$ be an instance of an insert operation invoked by client $c$. A
message with the insert request is sent on line code:ins:1, after the
invocation of the operation. Recall that routine receive() blocks until a
message is received. Notice that both line code:ser:ins15 as well as line
code:ser:ins2 are executed by a server before it sends a message to the
client. Therefore, whether $op$ is linearized at the point some server sends
it a message on line code:ser:ins22 or on line code:ser:ins3, it terminates
only after receiving it. Notice also that the operation terminates only after
the client receives it. Thus, the linearization point is included in its
execution interval.

By similar reasoning, if $op$ is an instance of a delete operation that is
linearized in the configuration resulting from the execution of line
code:ser:del2 or a search operation that is linearized in the configuration
resulting from the execution of line code:ser:srch2, then the linearization
point is included in the execution interval of $op$.

Let $op$ be an instance of a delete operation that deletes key $k$ and that
terminates after receiving only NACK messages on line code:del:3. If $k$ is
not present in the list in the beginning of the execution interval of $op$,
then $op$ is linearized at that point and the claim holds.

Consider the case where $k$ is included in the list when $op$ is invoked. By
observation of the pseudocode (lines code:ser:del1-code:ser:del7), we have
that when a server receives a delete request by a client, it traverses its
local part of the list and deletes the element with key equal to $k$ (line
code:ser:del2), if it is included in it. By further observation of the
pseudocode (lines code:del:1-code:del:7), we have that after $c$ invokes $op$,
it sends a delete request to all servers (line code:del:1) and then awaits for
a response from all of them (do while loop of lines code:del:2-code:del:6). By
assumption, all servers responds with NACK. Notice that this implies that
between the execution of line code:del:3 and code:del:5 the element with key
$k$ is removed from the local list of $s$ because of some other concurrent
delete operation $op^{\prime}$ invoked by some client $c^{\prime}$. By
scrutiny of the pseudocode, we have that a server that deletes an element from
its local list, does so on line code:ser:del2, which occurs before the server
sends a response to the delete request. By definition, then, $op^{\prime}$ is
linearized at the point $s$ executes line code:ser:del2, before it sends an
ACK message to $c^{\prime}$. Since $op^{\prime}$ causes the element with key
$k$ to be removed from the local list of $s$ between the execution of lines
code:del:3 and code:del:5 by $c$, its linearization point is included in the
execution interval of $op$. Since we place the linearization point of $op$
right after the linearization point of $op^{\prime}$, the claim holds.

The argument is similar for when $op$ is an instance of a search operation for
key $k$ that terminates after receiving a NACK message from all the servers on
lines code:srch:2-code:srch:6. ∎

Each server maintains a local variable $token$ with initial value $0$. Let
some server $s$ receive a message $m$ in some configuration $C$. If the field
tk of $m$ is equal to TOKEN, we say that receives a token message. Observe
that when $s$ receives a token message (line ln:60), the value of $token$ is
set to $s$. Furthermore, when $s$ executes line code:ser:ins18, where the
value of $token$ changes from $s$ to $s+1$, $s$ also sends a token message to
$s+1$ (line code:ser:ins21). Notice that $s$ can only reach and execute this
line if the condition of the if clause of line code:ser:ins5 evaluates to
false, i.e. if $token$ = $s$. Then, the following holds:

######  Observation 46.

At each configuration in $\alpha$, there is at most one server $s$ for which
the local variable $token$ has the value $s$.

This server is referred to as token server. By the pseudocode, namely the if
else clause of lines code:ser:ins5, code:ser:ins10, and by line
code:ser:ins15, the following observations holds.

######  Observation 47.

A server $s$ performs insert operations on its local list in $\alpha$ only
during those subsequences of $\alpha$ in which it is the token server.

Each server maintains a local list collection, $llist$. By observation of the
pseudocode, lines code:ser:ins2 and code:ser:ins3, we have that if an insert
operation attempts to insert key $k$ in either of the lists of a server $s$,
but an element with that key already exists, then no second element for $k$ is
inserted and the operation terminates. Thus, the following holds:

######  Observation 48.

The keys contained in the list collection of $s$ in any configuration $C$ of
$\alpha$ form a set.

We denote this set by $ll^{s}$. By scrutiny of the pseudocode, we see that a
new list object is allocated in $llist$ each time a server receives a token
message (lines code:ser:tok1-code:ser:tok3). The new object is identified by
the value of local variable $round$. By observation of the pseudocode, we
further have that each time a server inserts a key into $ll^{s}$, it does so
on the list object identified by $round$ (line code:ser:ins15). We refer to
this object as current list object. Then, based on lines
code:ser:ins16-code:ser:ins21 we have the following:

######  Observation 49.

A token message is sent from a server $s$ to a server $((s+1)\mod{\tt NS})$ in
some configuration $C$ only if the current local list object of server $s$ is
full at $C$.

Further inspection of the pseudocode shows that the local list object of a
server is only accessed by the execution of line code:ser:ins2,
code:ser:ins15, code:ser:srch2, or code:ser:del2. From this, we have the
following observation.

######  Observation 50.

If an operation $op$ modifies the local list object of some server, then this
occurs in the configuration in which $op$ is linearized.

Let $C_{i}$ be the configuration in which the $i$-th linearization point in
$\alpha$ is placed. Denote by $\alpha_{i}$, the prefix of $\alpha$ which ends
just after $C_{i}$ and let $L_{i}$ be the sequence of linearization points
that is defined by $\alpha_{i}$. Denote by $S_{i}$ the set of keys that a
sequential list contains after applying the sequence of operations that
$L_{i}$ imposes. Denote by $S_{i}=\epsilon$ the empty sequence (the list is
empty).

######  Lemma 51.

Let $k$ be the token server in some configuration $C$ in which it receives a
message $m$ for an insert operation $op$ with key $k$ invoked by client $c$.
Then at $C$, no element with key $k$ is contained in the local list set of any
other server $s\neq k$.

###### Proof.

By inspection of the pseudocode, when a client $c$ sends a message $m$ to some
server either on line code:ins:1, line code:srch:1, line code:del:1, or line
code:del:5, the $mloop$ field of $m$ is equal to false. This field is set to
true when server $s_{{\tt NS}-1}$ executes line code:ser:ins9. Notice that in
the configuration in which this line is executed by $s_{{\tt NS}-1}$, it is
not the token server (otherwise the condition of line code:ser:ins5 would not
evaluate to true and the line would not be executed).

Consider the case where $m$ reaches a server $s$ at some configuration $C$ and
let $ll^{s}$ contain an element with key $k$ in $C$. By inspection of the
pseudocode (lines code:ser:ins2-code:ser:ins3) we have that in that case, $m$
is not forwarded to a subsequent server.

Furthermore, by lines code:ser:ins5-code:ser:ins9, we have that if $s$ is not
the token server and not $s_{{\tt NS}-1}$, and provided that $ll^{s}$ does not
contain an element with key $k$, then $s$ forwards $m$ without modifying the
$mloop$ field. This implies that the $mloop$ field of $m$ is changed at most
once in $\alpha$ from false to true, and that by server ${\tt NS}-1$, in a
configuration $C^{\prime}$ in which $k$ is not contained in $ll^{{\tt NS}-1}$.
∎

######  Lemma 52.

Let $C_{i}$, $i\geq 0$, be a configuration in $\alpha$ in which server
$s_{t_{i}}$ is the token server. Let $ll_{i}^{j}$ be the local list set of
server $s_{j}$, $0\leq j<{\tt NS}$, in $C_{i}$. Then it holds that
$S_{i}=\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}$.

###### Proof.

We prove the claim by induction on $i$.

Base case (i = 0). The claim holds trivially at $C_{0}$.

Hypothesis. Fix any $i>0$ and assume that at $C_{i}$, it holds that $S_{i}$ =
$\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}$. We show that the claim holds for
$i+1$.

Induction step. Let $op_{i+1}$ be the operation that corresponds to the
linearization point placed in $C_{i+1}$. We proceed by case study.

Let $op_{i+1}$ be an insert operation for key $k$. Assume first that the
linearization point of $op_{i+1}$ is placed at the execution of line
code:ser:ins2 by $s_{t_{i+1}}$ for it. Notice that when this line is executed,
$k$ is searched for in the local list of $s_{t_{i+1}}$. Recall that, by the
way linearization points are assigned, the client $c$ that invoked $op_{i+1}$
receives NACK as response. Notice also that $s_{t_{i+1}}$ sends NACK as a
response to $c$ if $k$ is present in the local list of $s_{t_{i+1}}$, and thus
$status_{1}={\tt true}$. In that case, lines code:ser:ins5 to code:ser:ins22
are not executed, and therefore, no new element is inserted into the local
list of $s_{t_{i+1}}$ (line code:ser:ins15). Thus
$ll_{i+1}^{s_{t_{i+1}}}=ll_{i}^{s_{t_{i+1}}}$. By the induction hypothesis,
$S_{i}$ = $\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}$. By Observation 50 it follows
that for any other server $s_{j}$, where $j\neq t_{i+1}$,
$ll_{i+1}^{s_{j}}=ll_{i}^{s_{j}}$ as well. Then, $\bigcup_{j=0}^{{\tt
NS}-1}ll_{i+1}^{j}=\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}$. Notice that since
the server responds with NACK, $S_{i+1}=S_{i}$ by definition. Thus,
$S_{i+1}=\bigcup_{j=0}^{{\tt NS}-1}ll_{i+1}^{j}$ and the claim holds.

Now, assume that $op_{i+1}$ is linearized at the execution of line
code:ser:ins15 by the token server for it. By the way linearization points are
assigned, this implies that when this line is executed, $status_{2}={\tt
true}$, and the insertion of an element with key $k$ into the local list of
$s_{t}$ was successful. This in turn implies that at $C_{i+1}$,
$ll_{i+1}^{s_{t}}=ll_{i}^{s_{t}}\cup\\{k\\}$. By Observation 50 it follows
that for any other server $s_{j}$, where $j\neq t_{i+1}$,
$ll_{i+1}^{s_{j}}=ll_{i}^{s_{j}}$ as well. Notice that since the server
responds with ACK, by definition the insertion is successful and thus
$S_{i+1}=S_{i}\cup\\{k\\}$. Since by the induction hypothesis, $S_{i}$ =
$\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}$, it holds that
$S_{i+1}=\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}\cup\\{k\\}=\bigcup_{j=0}^{{\tt
NS}-1}ll_{i+1}^{j}$, thus, the claim holds.

Now consider that $op_{i+1}$ is a delete operation for key $k$. Assume first
that some server $s_{d}$ responds with ACK, by executing line code:ser:del4,
to the client $c$ that invoked $op_{i+1}$. Then $op_{i+1}$ is linearized at
the execution of this line by $s_{d}$. Notice that this line is executed by a
server if $status_{1}={\tt true}$, i.e. if the server was successful in
locating and deleting an element with key $k$ from its local list. Thus,
$ll_{i+1}^{s_{t}}=ll_{i}^{s_{t}}\setminus\\{k\\}$. Furthermore, by definition,
$S_{i+1}=S_{i}\setminus\\{k\\}$. By the induction hypothesis, $S_{i}$ =
$\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}$ and since by Observation 50 no other
modification occurred on the local list of some other server between $C_{i}$
and $C_{i+1}$, it follows that $S_{i+1}=S_{i}\setminus\
\\{k\\}=\bigcup_{j=0}^{{\tt
NS}-1}ll_{i}^{j}\setminus\\{k\\}=\bigcup_{j=0}^{{\tt NS}-1}ll_{i+1}^{j}$.

Assume now that $op_{i+1}$ is a delete operation for which no server responds
with ACK to the invoking client. Recall that in this case, by definition,
$S_{i+1}=S_{i}$. By inspection of the pseudocode, it follows that no server
finds an element with key $k$ in its local list when it is executing line
code:ser:del2 for $op_{i+1}$. We examine two cases: (i) either no element with
key $k$ is contained in any local list of any server in the beginning of the
execution interval of $op_{i+1}$, or (ii) an element with key $k$ is contained
in the local list of some server $s_{d}$ in the beginning of $op_{i+1}$’s
execution interval, but $s_{d}$ deletes it while serving a different delete
operation $op^{\prime}$, before it executes line code:ser:del2 for $op_{i+1}$.

Assume that case (i) holds. Then, the linearization point is placed in the
beginning of the execution interval of $op_{i+1}$. Notice that in this case,
the invocation (nor in fact the further execution) of $op_{i+1}$ has no effect
on the local list of any server. Thus, between $C_{i}$ and $C_{i+1}$ no server
local list is modified and, by the induction hypothesis, the claim holds.

Assume now that case (ii) holds. By Lemma 45, we have that a concurrent delete
operation $op^{\prime}$ removes the element with key $k$ from the local list
of $s_{d}$ during the execution interval of $op_{i+1}$. By the assignment of
linearization points, Observation 50 and Lemma 45, it further follows that
$op^{\prime}=op_{i}$. Notice that in this case (ii) also, $op_{i+1}$ has no
effect on the local list of any server. Thus, since by the induction
hypothesis it holds that $S_{i}=\bigcup_{j=0}^{{\tt NS}-1}ll_{i}^{j}$, it also
holds that $S_{i}=\bigcup_{j=0}^{{\tt NS}-1}ll_{i+1}^{j}$, and since
$S_{i}=S_{i+1}$, the claim holds.

Since a search operation does not modify the local list of any server, the
argument is analogous as for the case of the delete operation. ∎

From the above lemmas and observations, we have the following.

######  Theorem 53.

The distributed unsorted list is linearizable. The insert operation has time
and communication complexity $O({\tt NS})$. The search and delete operations
have communication complexity $O(1)$.

####  7.1.2 Alternative Implementation

At each point in time, there is a server (not necessarily always the same),
denoted by $s_{t}$, which holds the insert token, and serves insert
operations. Initially, server $s_{0}$ has the token, thus the first element to
be inserted in the list is stored on server $s_{0}$. Further element
insertions are also performed on it, as long as the space it has allocated for
the list does not exceed a threshold. In case server $s_{0}$ has to service an
insertion but its space is filled up, it forwards the token by sending a
message to the next server, i.e. server $s_{1}$. Thus, if server $s_{i}$,
$0\leq i<{\tt NS}$, has the token, but cannot service an insertion request
without exceeding the threshold, it forwards the token to server
$s_{(i+1)\mod{\tt NS}}$. When the next server receives the token, it allocates
a memory chunk of size equal to threshold, to store list elements. When the
token reaches $s_{{\tt NS}-1}$, if $s_{{\tt NS}-1}$ has filled all the local
space up to a threshold, it sends the token again to $s_{0}$. Then, $s_{0}$
allocates more memory (in addition to the memory chunk it had initially
allocated for storing list elements) for storing more list elements. The token
might go through the server sequence again without having any upper-bound
restrictions concerning the number of round-trips.

Event-driven code for the server is presented in Algorithm 27. Each server $s$
maintains a local list ($llist$ variable) allocated for storing list elements,
a $token$ variable which indicates whether $s$ currently holds the token, and
a variable $round$ to mark the ring round-trips the token has performed;
$round$ is initially $0$, and is incremented after every transmission of the
token to the next server. The pseudocode of the client is presented in
Algorithm 28.

A client $c$ sends an insert request for an element with key $k$ to all
servers in parallel and awaits a response. If any of the servers contains $k$
in its local list, it sends ACK to $c$ and the insert operation terminates. If
no server finds $k$, then all reply NACK to $c$. In addition, the token server
$s_{t}$ encapsulates its id in the NACK reply. After that, $c$ sends an insert
request for $k$ to $s_{t}$ only. If $s_{t}$ can insert it, it replies ACK to
$c$. If $k$ has in the meanwhile been inserted, $s_{t}$ replies NACK to $c$.
If $s_{t}$ is no longer the token server, it forwards the request along the
server ring until it reaches the current token server. Servers along the ring
should check whether they contain $k$ or not, and if some server does, then it
replies NACK to $c$. Let $s_{t}^{\prime}$ be a token server that receives such
a request. It also checks whether it contains $k$ or not. If not, it attempts
to insert $k$ into its local list. Otherwise it replies NACK. When attempting
to insert the element in the local list, it may occur that the allocated space
does not suffice. In this case, the server forwards the request as well as the
token to the next server in the ring, and increments the value of $round$
variable. If the insertion at a token server is successful, the server then
replies ACK to $c$.

To perform a search for an element $e$, a client $c$ sends a search request to
all servers and awaits their responses. A server $s$ that receives a search
request, checks whether $e$ is present in its local part of the list and if
so, it responds with ACK to $c$. Otherwise, the response is NACK. If all
responses that $c$ receives are NACK, $e$ is not present in the list. Notice
that if $e$ is contained in the list, exactly one server responds with ACK.
Delete works similarly; if a server $s$ responds with ACK, then $s$ has found
and deleted $e$ from its local list. Given that communication is fast and the
number of servers is much less than the total number of cores, forwarding a
request to all servers does not flood the network.

Algorithm 27 Events triggered in a server of the distributed unsorted list. 1 |  List $llist$ = $\varnothing$;
---|---
2 |  int $my\\_id$, $next\\_id$, $token$ = $0$, $round$ = $0$;
|
|
3 |  a message $\langle op,cid,key,data,tk\rangle$ is received:
4 |  switch ($op$) $\\{$
5 |  case INSERT:
6 |  if ($tk$ == TOKEN) $\\{$
7 |  $token$ = $my\\_id$;
8 |  allocate_new_memory_chunk($llist,round$);
|  $\\}$
9 |  $status_{1}$ = search($llist$, $key$);
10 |  if ($tk$ == $-2$) $\\{$
11 |  if ($status_{1}$) $\\{$
12 |  if ($token==my\\_id$) send($cid$, $\langle{\tt ACK},{\tt true}\rangle$);
13 |  else send($cid$, $\langle{\tt ACK},{\tt false}\rangle$);
14 |  $\\}$ else $\\{$
15 |  if ($token==my\\_id$) send($cid$, $\langle{\tt NACK},{\tt true}\rangle$);
16 |  else send($cid$, $\langle{\tt NACK},{\tt false}\rangle$);
|  $\\}$
17 |  $\\}$ else $\\{$
18 |  if ($status_{1}$) send($cid$, NACK);
19 |  else $\\{$
20 |  if ($token\neq my\\_id$) $\\{$
21 |  $next\\_id$ = get_next($my\\_id$);
22 |  send($next\\_id$, $\langle op,cid,key,data,tk\rangle$);
23 |  $\\}$ else $\\{$
24 |  $status_{2}$ = insert($llist,round,key,data$);
25 |  if ($status_{2}$ == false) $\\{$
26 |  $round++$;
27 |  $token$ = get_next($my\\_id$);
28 |  send($token$, $\langle op,cid,key,data,{\sf TOKEN}\rangle$);
29 |  $\\}$ else send($cid$, ACK);
|  $\\}$
|  $\\}$
|  $\\}$
30 |  break;
31 |  case SEARCH:
32 |  $status_{1}$ = search($llist$, $key$);
33 |  if ($status_{1}$) send($cid$, $\langle{\tt ACK},my\\_id\rangle$);
34 |  else send($cid$, $\langle{\tt NACK},my\\_id\rangle$);
35 |  break;
36 |  case DELETE:
37 |  $status_{1}$ = delete($llist$, $key$);
38 |  if ($status_{1}$) send($cid$, ACK);
39 |  else send($cid$, NACK);
40 |  break;
|  $\\}$
Algorithm 28 Insert, Search and Delete operation for a client of the distributed list. 41 |  boolean ClientInsert(int $cid$, int $key$, data $data$) {
---|---
42 |  boolean $status$;
43 |  boolean $found$ = false;
44 |  int $tid$;
|
45 |  send_to_all_servers($\langle{\tt INSERT},cid,key,\bot,-2\rangle$);
46 |  do {
47 |  $\langle status,sid,is\\_token\rangle$ = receive();
48 |  if ($status$ == ACK) $found$ = true;
49 |  if ($is\\_token$) $tid=sid$;
50 |  $c++$;
51 |  } while ($c<{\tt NS}$);
52 |  if ($found$ == true) return false;
53 |  send($tid$, $\langle{\tt INSERT},cid,key,data,-1\rangle$);
54 |  $status$ = receive();
55 |  if ($status$ == NACK) return false;
56 |  else return true;
|  }
|
57 |  boolean ClientSearch(int $cid$, int $key$) {
58 |  int $sid$;
59 |  int $c$ = $0$;
60 |  boolean $status$;
61 |  boolean $found$ = false;
|
62 |  send_to_all_servers($\langle{\tt SEARCH},cid,key,\bot,-1\rangle$);
63 |  do {
64 |  $\langle status,sid\rangle$ = receive();
65 |  if ($status$ == ACK) $found$ = true;
66 |  $c++$;
67 |  } while ($c<{\tt NS}$);
68 |  return $found$;
|  }
|
69 |  boolean ClientDelete(int $cid$, int $key$) {
70 |  int $sid$;
71 |  int $c$ = $0$;
72 |  boolean $status$;
73 |  boolean $deleted$ = false;
|
74 |  send_to_all_servers($\langle{\tt DELETE},cid,key,\bot,-1\rangle$);
75 |  do {
76 |  $\langle status,sid\rangle$ = receive();
77 |  if ($status$ == ACK) $deleted$ = true;
78 |  $c++$;
79 |  } while ($c<{\tt NS}$);
80 |  return $deleted$;
|  }

###  7.2 Sorted List

Algorithm 29 Events triggered in a server of the distributed sorted list. 81 |  List $llist=\varnothing$;
---|---
82 |  int $my\\_id$, $next\\_id$, $k_{max}$, $cv[MC]$, $nbr\\_cv[MC]$;
83 |  data[$0\ldots CHUNKSIZE$] $chunk1$, $chunk2$;
84 |  boolean $status$ = false, $served$ = false;
|
|
85 |  a message $\langle op,cid,key,data\rangle$ is received:
86 |  switch ($op$) $\\{$
87 |  case $REQC$:
88 |  send($cid$, $cv$);
89 |  $chunk2$ = receive($cid$);
90 |  if (not enough free space in local list to fit elements of $chunk2$ ) $\\{$
91 |  if ($my\\_sid$ == ${\tt NS}-1$) $status$ = false;
92 |  else $\\{$
93 |  $chunk1$ = getChunkOfElementsFromLocalList($llist$);
94 |  $status$ = ServerMove($next\\_id$, $chunk1$);
|  $\\}$
95 |  $\\}$ else $status$ = true;
96 |  if ($status$ == true) $\\{$
97 |  insertChunkOfElementsInLocalList($llist,chunk2$);
98 |  send($cid$, ACK);
99 |  $\\}$ else send($cid$, NACK);
100 |  break;
101 |  case $INSERT$:
102 |  while ($served\neq{\tt true}$) {
103 |  $k_{max}$ = find_max($llist$);
104 |  if ($k_{max}>key$ and isFull($llist$) $\neq$ true) {
105 |  status = insert($llist,key,data$);
106 |  send($cid$, $status$);
107 |  $served$ = true;
108 |  } else if ($k_{max}>key$) {
109 |  $chunk1$ = getChunkOfElementsFromLocalList($llist$);
110 |  $status$ = ServerMove($next\\_id$, $chunk1$);
111 |  if ($status$ == true) {
112 |  removeChunkOfElementsFromLocalList($llist$, $chunk1$);
113 |  } else {
114 |  send($cid$, NACK);
115 |  $served$ = true;
|  }
116 |  } else {
117 |  if ($my\\_id\neq{\tt NS}-1$) send($next\\_id$, $\langle{\tt INSERT},cid,key,data\rangle$);
118 |  else send($cid$, NACK);
119 |  $served$ = true;
|  }
|  }
120 |  break;
121 |  case $SEARCH$:
122 |  $cv[cid]++$;
123 |  $status$ = search($llist,key$);
124 |  if ($status$ == ${\tt false}$) send($cid$, NACK));
125 |  else send($cid$, ACK);
126 |  break;
127 |  case $DELETE$:
128 |  $cv[cid]++$;
129 |  status = search($llist,key$);
130 |  if ($status=={\tt true}$) {
131 |  delete($llist$, $key$);
132 |  send($cid$, ACK);
133 |  } else send($cid$, NACK);
134 |  break;
|  }

The proposed implementation is based on the distributed unsorted list,
presented in Section 7.1. Each server $s$ has a memory chunk of predetermined
size where it maintains a part of the implemented list so that all elements
stored on server $s_{i}$ have smaller keys than those stored on server
$s_{i+1}$, $0\leq i<{\tt NS}-1$. Because of this sorting property, an element
with key $k$ is not appended to the end of the list, so a token server is
useless in this case. This is an essential difference with the unsorted list
implementation.

Similarly to the unsorted case, a client sends an insert request for key $k$
to server $s_{0}$. The server searches its local part of the list for a key
that is greater than or equal to $k$. In case that it finds such an element
that is not equal to $k$, it can try to insert $k$ to its local list, $llist$.
More specifically, if the server has sufficient storage space for a new
element, it simply creates a new node with key $k$ and inserts it to the list.
However, in case that the server does not have enough storage space, it tries
to free it by forwarding a chunk of elements of $llist$ to the next server. If
this is possible, it serves the request. In case $s_{0}$ does not find a key
that is greater than or equal to $k$ in its $llist$, if forwards the message
with the insert request to the next server, which in turn tries to serve the
request accordingly. Notice that this way, a request may be forwarded from one
server to the next, as in the case of the unsorted list. However, for ease of
presentation, in the following we present a static algorithm where this
forwarding stops at $s_{{\tt NS}-1}$. In case that an element with $k$ is
already present in the $llist$ of some server $s$ of the resulting sequence,
then $s$ sends an NACK message to the client that requested the insert.

As in the case of the unsorted list, a client performs a search or delete
operation for key $k$ by sending the request to all servers. If not handled
correctly, then the interleaving of the arrival of requests to servers may
cause a search operation to “miss” the key $k$ that it is searching, because
the corresponding element may be in the process to be moved from one server to
a neighboring one. In order to avoid this, servers maintain a sequence number
for each client that is incremented at every search and delete operation.
Neighboring servers that have to move a chunk of elements among them, first
verify that the latest (search or delete) requests that they have served for
each client have compatible sequence numbers and perform the move only in this
case.

Event-driven code for the server is presented in Algorithms 29 and 30. The
clients access the sorted list using the same routines as they do in the case
of the unsorted list (see Algorithm 26).

When an insert request for key $k$ reaches a server $s$, $s$ compares the
maximal key stored in its local list to $k$. If $k$ is greater than the
maximal key and $s$ is not $s_{{\tt NS}-1}$, the request must be forwarded to
the next server (line code:ser-o:ins10.4). Otherwise, if $k$ is to be stored
on $s$, $s$ checks if $llist$ has enough space to serve the insert. If it
does, $s$ inserts the element and sends an ACK to the client (line
code:ser-o:ins3-code:ser-o:ins4). If $s$ does not have space for inserts, the
operation cannot be executed, hence $s$ must check whether a chunk of its
elements can be forwarded to the next server to make room for further inserts.
To move a chunk, $s$ calls ServerMove() (presented in Algorithm 30) (line
code:ser-o:ins5). If ServerMove() succeeds in making room in $s$’s $llist$,
the insert can be accommodated (line code:ser-o:ins6). In any other case, $s$
responds to the client with NACK (line code:ser-o:ins10.1).

A server process a search request as described for the unsorted list, but it
now pairs each such request with a sequence number (line code:ser-o:s1).
Delete is processed by a server in a way analogous to search.

In order to move a chunk of $llist$ to the next server, a server $s_{i}$
invokes the auxiliary routine ServerMove() (line code:ser-o:ins5).
ServerMove() sends a REQC message to server $s_{i+1}$ (line code:sm:1). When
$s_{i+1}$ receives this request, it sends its client vector to $s_{i}$ (line
code:ser-o:req1). Upon reception (line code:sm:2), $s_{i}$ compares its own
client vector to that of $s_{i+1}$ and as long as it lags behind $s_{i+1}$ for
any client, it services search and delete requests until it catches up to
$s_{i+1}$ (lines code:sm:3-code:sm:5). Notice that during this time, $s_{i+1}$
does not serve further client request, in order allow $s_{i}$ to catch up with
it. As soon as $s_{i}$ and $s_{i+1}$ are compatible in the client delete and
search requests that they have served, $s_{i}$ sends to $s_{i+1}$ a chunk of
the elements in its local list (lines code:sm:6-code:sm:7) and awaits the
response of $s_{i+1}$. We remark that in order to perform this kind of bulk
transfer, as the one carried out between a server executing line code:sm:8 and
another server executing line code:ser-o:req2, we consider that remote DMA
transfers are employed. This is omitted from the pseudocode for ease of
presentation.

If $s_{i+1}$ can store the chunk of elements, then it does so and sends ACK to
$s_{i}$. Upon reception, $s_{i}$ may now remove this chunk from its local list
(line code:ser-o:ins6) and attempt to serve the insert request. Notice that if
$s_{i+1}$ cannot store the chunk of elements of $s_{i}$, then it itself
initiates the same chunk moving procedure with its next neighbor (lines
code:req-o:0.2-code:ser-o:req5), and if it is successful in moving a chunk of
its own, then it can accommodate the chunk received by $s_{i}$. Notice that in
the static sorted list that is presented here, this protocol may potentially
spread up to server $s_{{\tt NS}-1}$ (line code:req-o:0.1). If $s_{{\tt
NS}-1}$ does not have available space, then the moving of the chunk fails
(line code:ser-o:ins6.2). The client then receives a NACK response,
corresponding to a full list.

We remark that this implementation can become dynamic by appropriately
exploiting the placement of the servers on the logical ring, in a way similar
to what we do in the unsorted version.

Algorithm 30 Auxiliary routine ServerMove for the servers of the distributed sorted list. 135 |  boolean ServerMove(int $cid$, data $chunk1$) {
---|---
136 |  boolean $status$;
137 |  data $chunk2$;
|
138 |  send($next\\_id$, $\langle REQC,cid,0,\bot\rangle$);
139 |  $nbr\\_cv$ = receive($next\\_id$);
140 |  while (for any element $i$, $cv[i]<nbr\\_cv[i]$) {
141 |  receiveMessageOfType($SEARCH$ or $DELETE$);
142 |  $service\ request$
|  }
143 |  $chunk2$ = getChunkOfElementsFromLocalList($llist$);
144 |  send($next\\_id$, $chunk2$);
145 |  $status$ = receive($next\\_id$);
146 |  if ($status$ == true) $\\{$
147 |  removeChunkOfElementsFromLocalList($llist$, $chunk2$);
148 |  insertChunkOfElementsInLocalList($llist,chunk1$);
149 |  return true;
|  $\\}$ else return false;
|  }

##  8 Details on Hierarchical Approach

We interpolate one or more communication layers by using intermediate servers
between the servers that maintain parts of the data structure and the clients.
The number of intermediate servers and the number of layers of intermediate
servers between clients and servers can be tuned for achieving better
performance.

For simplicity of presentation, we focus on the case where there is a single
layer of intermediate servers. We present first the details for a fully non
cache-coherent architecture.

For each island $i$, we appoint one process executing on a core of this
island, called the island master (and denoted by $m_{i}$), as the intermediate
server. Process $m_{i}$ is responsible to gather messages from all the other
cores of the island, and batch them together before forwarding them to the
appropriate server. This way, we exploit the fast communication between the
cores of the same island and we minimize the number of messages sent to the
servers by putting many small messages to one batch.We remark that each batch
can be sent to a server by performing Dma. In this case, $m_{i}$ initiates the
Dma to the server’s memory, and once the Dma is completed, it sends a small
message to the server to notify it about the new data that it has to process.

Algorithm 31 presents the events triggered in an island master $m_{i}$ and its
actions in order to handle them. $m_{i}$ receives messages from clients that
have type OUT (outgoing messages) and from servers that have type IN (incoming
messages). The outbatch messages are stored in the $outbuf$ array. Each time a
client from island $i$ wants to execute an operation, it sends a message to
$m_{i}$; $m_{i}$ checks the destination server id ($sid$), recorded in the
message, and packs this message together with other messages directed to $sid$
(lines ln:hier-outgoing1-ln:hier-outgoing2). Server $m_{i}$ has set a timer,
and it will submit this batch of messages to server $sid$ (as well as other
batches of messages to other servers), when the timer expires. When $m_{i}$
receives an incoming message from a server, it unpacks it, and sends each
message to the appropriate client on its island. When the timer is triggered,
$m_{i}$ places each batch of messages in an $outbuf$ array that $m_{i}$
maintains for the appropriate server. The transfer of all these messages to
the server may occur using Dma. For simplicity, we use two auxiliary
functions: add_message to add a message to an $outbuf$ buffer of $m_{i}$, and
split to split a batch of messages $msg$ that have arrived to the particular
messages of the batch which are then placed in the $inbuf$ buffer of $m_{i}$.

The code of the client does not change much. Instead of sending messages
directly to the server, it sends them to the board master.

Algorithm 31 Events triggered in an island master - Case of fully non cache-coherent architectures. 1 | LocalArray $outbuf=\varnothing$; /* stores outgoing messages */
---|---
2 | LocalArray $inbuf=\varnothing$; /* stores incoming messages */
|
3 | a message $\langle type,msg\rangle$ is received:
4 |  if($type$ == OUT) $\\{$
5 |  $sid$ = read field $sid$ from $msg$;
6 |  add_message($outbuf$, $sid$, $msg$);
7 |  $\\}$ else if ($op$ == IN) $\\{$ /* $m_{i}$ received a batch of messages from a server */
8 |  $inbuf$ = split($msg$); /* unbundle the message to many small ones */
9 |  for each message $m$ in $inbuf$ $\\{$ /* the batch is for all cores in the island */
10 |  $cid$ = read field $client$ from $msg$;
11 |  send($cid$, $msg$);
|  $\\}$
|  $\\}$
|
12 |  timer is triggered: /* Every timeout, $m_{i}$ sends outgoing messages */
13 |  for each batch of messages in $outbuf$ $\\{$ /* send a bach to a server */
14 |  send($sid$, batch); /* this send can be done using DMA */
15 |  delete($outbuf$, $sid$, batch);
|  $\\}$

We remark that in order to improve the scalability of a directory-based
algorithm, a locality-sensitive hash functions could be a preferable choice.
For instance, the simple currently employed $\mod$ hash function, can be
replaced by a hash function that divides by some integer $k$. Then, elements
of up to $k$ subsequent insert (i.e. push or enqueue) operations may be sent
to the same directory server. This approach suites better to bulk transfers
since it allows for exploiting locality. Specifically, consider that $m_{i}$
sends a batch of elements to be inserted to the synchronizer $s_{s}$ of a
directory-based data structure. Server $s_{s}$ unpacks the batch and processes
each of the requests contained therein separately. Thus, if $\mod$ is used,
each of these elements will be stored in different buckets (of different
directory servers). As a sample alternative, if the ${\tt div}$ hash function
is used, more than one elements may end up to be stored in the same bucket.
When later on a batch of remove (i.e. pops or dequeues) operations arrives to
$s_{s}$, it can request from the directory server that stores the first of the
elements to be removed, to additionally remove and send back further elements
with subsequent keys that are located in the same bucket. Notice that in this
case, the use of DMA can optimize these transfers.

We now turn attention to partially non cache-coherent architectures where the
cores of an island communicate via cache-coherent shared memory. Algorithm 32
presents code for the hierarchical approach in this case. For each island, we
use an instance of the CC-Synch combining synchronization algorithm, presented
in [15]. All clients of island $i$ participate to the instance of CC-Synch for
island $i$, i.e. each such client calls CC-Synch (see Algorithm 32) to execute
an operation.

Algorithm 32 Pseudocode of hierarchical approach - Case of partially non
cache-coherent architectures. struct Node {
---
|  Request req;
|  RetVal ret;
|  int id;
|  boolean wait;
|  boolean completed;
|  int sid;
|  Node *next;
|  };
|
| shared Node *Tail;
|  private Node *$node_{i}$;
|  LocalArray $outbuf=\varnothing$; /* stores outgoing messages */
|
|  RetVal CC-Synch(Request req) { /* Pseudocode for thread $p_{i}$ */
|  Node *nextNode, *tmpNode, *tmpNodeNext;
|  int counter = 0;
|
16 |  $node_{i}\rightarrow wait$ = true;
17 |  $node_{i}\rightarrow next$ = null;
18 |  $node_{i}\rightarrow completed$ = false;
19 |  $nextNode=node_{i}$;
20 |  $node_{i}=\textit{Swap}(Tail,node_{i})$;
21 |  $node_{i}\rightarrow req$ = req; /* $p_{i}$ announces its request */
22 |  $node_{i}\rightarrow sid$ = destination server;
23 |  $node_{i}\rightarrow next$ = nextNode;
24 |  while ($node_{i}\rightarrow wait$ == true) /* $p_{i}$ spins until it is unlocked */
|  nop;
25 |  if ($node_{i}\rightarrow completed$==true) /* if $p_{i}$’s req is already applied */
26 |  return $node_{i}\rightarrow ret$; /* $p_{i}$ returns its return value */
27 |  tmpNode = $node_{i}$; /* otherwise $p_{i}$ is the combiner */
28 |  while (tmpNode $\rightarrow$ next $\neq$ $null$ AND counter $<$ $h$){
29 |  counter = counter + 1;
30 |  tmpNodeNext=tmpNode$\rightarrow$next;
31 |  add_message($outbuf$, tmpNode$\rightarrow$sid, tmpNode$\rightarrow$req);
32 |  tmpNode = tmpNodeNext; /* proceed to the next node */
|  }
33 |  for each batch of messages in $outbuf$ $\\{$ /* send a batch of messages to servers */
34 |  send($sid$, batch of message); /* where $sid$ is the destination server for this batch */
35 |  delete($outbuf$, $sid$, $fatm$);
|  $\\}$
36 |  $inbuf$ = split(receive());
37 |  tmpNode = $node_{i}$;
38 |  while (counter $\geq$ 0) {
39 |  counter = counter - 1;
40 |  tmpNodeNext=tmpNode$\rightarrow$next;
41 |  tmpNode$\rightarrow$ret = find in $inbuf$ the response for tmpNode$\rightarrow$id;
42 |  tmpNode$\rightarrow$completed = true;
43 |  tmpNode$\rightarrow$wait = false; /* unlock the spinning thread */
44 |  tmpNode = tmpNodeNext;
|  }
45 |  tmpNode$\rightarrow$wait = false; /* unlock next node’s owner */
46 |  return $node_{i}\rightarrow$ret;
|  }

CC-Synch employs a list which contains one node for each client that has
initiated an operation; the last node of the list is a dummy node. After
announcing its request by by recording it in the last node of the list (i.e.,
in the dummy node) and by inserting a new node as the last node of the list
(which will comprise the new dummy node), a client tries to acquire a global
lock (line alg:ccsynch:swap) which is implemented as a queue lock. The client
that manages to acquire the lock, called the combiner, batches those active
requests, recorded in the list, that target the same server (lines
alg:ccsynch:combine-alg:ccsynch:combine_next) and forwards them to this server
(line alg:ccsynch:send_fat). Thus, at each point in time, the combiner plays
the role of the island master. When the island master receives (a batch of)
responses from a server, it records each of them in the appropriate element of
the request list to inform active clients of the island about the completion
of their requests (linesalg:ccsynch:while2-alg:ccsynch:combine_next2). In the
meantime, each such client performs spinning (on the element in which it
recorded its request) until either the response for its request has been
fulled by the island master or the global lock has been released (line
alg:ccsynch:spinning).

We use the list of requests to implement the global lock as a queue lock [62,
63]. The process that has recorded its request in the head node of the list
plays the role of the combiner.

##  9 Experimental Evaluation

We run our experiments on the Formic-Cube [4], which is a hardware prototype
of a $512$ core, non-cache-coherent machine. It consists of $64$ boards with
$8$ cores each (for a total of 512 cores). Each core owns $8$ KB of private L1
cache, and $256$ KB of private L2 cache. None of these caches is hardware
coherent. The boards are connected with a fast, lossless packet-based network
forming a 3D-mesh with a diameter of $6$ hops. Each core is equipped with its
own local hardware mailbox, an incoming hardware FIFO queue, whose size is $4$
KB. It can be written by any core and read by the core that owns it. One core
per board plays the role of the island master (and could be one of the
algorithm’s servers), whereas the remaining $7$ cores of the board serve as
clients.

Our experiments are similar to those presented in [64, 15, 10]. More
specifically, $10^{7}$ pairs of requests (PUSH and POP or ENQUEUE and DEQUEUE)
are executed in total, as the number of cores increases. To make the
experiment more realistic, a random local work (up to $512$ dummy loop
iterations) is simulated between the execution of two consecutive requests by
the same thread as in [64, 15, 10]. To reduce the overheads for the memory
allocation of the stack nodes, we allocate a pool of nodes (instead of
allocating one node each time).

In Figure 1.a, we experimentally compare the performance of the centralized
queue (CQueue) to the performance of its hierarchical version (HQueue), and to
those of the hierarchical versions of the directory-based queue (DQueue) and
the token-based queue (TQueue). We measure the average throughput achieved by
each algorithm. As expected, CQueue does not scale well. Specifically, the
experiment shows that for more than $16$ cores in the system, the throughput
of the algorithm remains almost the same. We remark that the clients running
on these $16$ cores do not send enough messages to fill up the mailbox of the
server. This allows us to conclude that when the server receives about $16$
messages or more, for reading these messages, processing the requests they
contain, and sending back the responses to clients, the server ends up to be
always busy. We remark that reading each message from the mailbox causes a
cache miss to the server. So, the dominant factor at the server side in this
case is to perform the reading of these messages from the mailbox.

These remarks are further supported by studying the experiment for the HQueue
implementation. Specifically, the throughput of HQueue does not further
increase when the number of cores becomes $64$ or more. Remarkably, the $64$
active cores are located in $8$ boards, so there exist $8$ island masters in
the system. Each island master sends two messages to the server – one for
batched enqueue and one for batched dequeue requests. So, again, the server
becomes saturated when it receives about $16$ messages. These messages are
read from the mailbox in about the same time as in the setting of CQueue with
$16$ running cores. However, in the case of HQueue, each message contains more
requests to be processed by the server. Therefore, the average time needed to
process a request is now smaller since the overhead of reading and processing
a message is divided over the number of requests it contains. Notice that now,
the server has more work to do in terms of processing requests. The experiment
shows that the time required for this is evened out by the time saved for
processing each request.

Similarly to CQueue and HQueue, the DQueue implementation uses a centralized
component, namely the synchronizer. However, contrary to the HQueue case, in
the DQueue, each island master sends one message instead of two, which
contains the number of both the enqueues and dequeues requests. Since we do
not see the throughput stop increasing at $128$ cores, we conclude that now
the dominant factor is not the time that the server requires to read the
messages from its mailbox. The DQueue graph of Figure 1.a shows that DQueue
scales well for up to $512$ cores. Therefore, in the DQueue approach, the
synchronizer does not pose a scalability problem. The reason for this is, not
only that the synchronizer receives a smaller number of messages, but also
that it has to do a simple arithmetic addition or subtraction for each batch
of requests that it receives. This computational effort is significantly
smaller than those carried out by the centralized component in the CQueue and
HQueue implementations. Therefore, it is important that the local computation
done by a server be small.

Figure 1: Performance evaluation of (a) distributed queue implementations, (b)
distributed queue implementations while executing different amounts of local
work ($512$ cores).

Figure 2: Performance evaluation of (a) distributed stack implementations with
elimination, (b) distributed stack implementations without elimination.

Notice that in the DQueue implementation, the actual request processing takes
place on the hash table servers. So, clients do not initiate requests as
frequently as in the previous algorithms, since they also have to communicate
with the hash table servers. Moreover, the processing in this case is shared
among the hash-table servers and therefore, this processing does not cause
scalability problems. It follows that load balancing is also an important
factor affecting scalability. In the case of the DQueue the local work on the
synchronizer is a linear function of the amount of island masters. On the
contrary, in the other two implementations, it is a function of the amount of
clients. It follows that this is another reason for the good scalability
observed on the DQueue implementation.

We remark that when the amount of clients, and therefore, of island masters,
is so large as to cause saturation on the synchronizer, a tree-like hierarchy
of island masters would solve the scalability problem. There, the DQueue
algorithm can offer a trade-off between overloaded activity of the centralized
component and the latency that is caused by the height of the tree hierarchy.

Figure 1.a further shows the observed throughput of TQueue. The behavior of
TQueue in terms of scalability follows that of HQueue. Notice that TQueue
works in a similar way as HQueue, with the difference that the identity of the
centralized component may change, as the token moves from server to server.
This makes TQueue more complex than HQueue. As a result, its throughput is
lower than that of HQueue. However, TQueue is a nice generalization of HQueue,
which can be used in cases where the expected size of the required queue is
not known in advance and where a moderate number of cores are active.

In Figure 1.b, we fix the number of cores to $512$ and perform the experiment
for several different random work values ($0$ \- $32$K). It is shown that, for
a wide range of values ($0$-$512$), we see no big difference on the
performance of each algorithm. This is so because, for this range of values,
the cost to perform the requests dominates the cost introduced by the random
work. When the random work becomes too high (greater than $32$K dummy loop
iterations), the throughput of all algorithms degrades and the performance
differences among them become minimal, since the amount of random work becomes
then the dominant performance factor.

In Figure 2.a, we experimentally compare the performance of the centralized
stack (CStack) with its hierarchical version where the island master performs
elimination (EStack), an improved version of EStack where the island master
performs batching (HStack), and the hierarchical versions of the directory-
based stack (DStack) and the token based-stack (TStack). As expected, the
centralized implementation does not scale for more than $16$ cores. All other
algorithms scale well for up to $512$ cores. This shows that the elimination
technique is highly-scalable. It is so efficient that it results in no
significant performance differences between the algorithms that apply it.

In order to get a better estimation of the effect that the elimination
technique has on the algorithms, we experimentally compared the performance
that CStack, EStack, HStack, TStack, and DStack can achieve, when they are not
performing elimination. Figure 2.b shows the obtained throughput. Notice that
the scalability characteristics of CStack, HStack, and TStack are similar to
those of CQueue, HQueue, and TQueue. This is not the case for DStack. The
reason for this is the following. In our experiment, each client performs
pairs of push and pops. By the way the synchronizer works, the push request
and the pop request of each pair are often assigned the same key. This results
in contention at the hash table. In an experiment where the number of pushes
is not equal to the number of pops, the observed performance would be much
better than that of other algorithms for all numbers of cores.

Figure 3.b shows the total number of messages sent in each experiment
presented in Figure 1.a. Remarkably, there is an inverse relationship between
these results and those of Figure 1.a. For instance, DQueue circulates the
largest number of messages in the system. However, DQueue is the
implementation that scales best. Thus, the total number of messages is not
necessarily an indicative factor of the actual performance. This is so because
a server may easily become saturated even by a moderate amount of messages, if
the required processing is important. This is for example the case in the
CQueue implementation. Therefore, in order to be scalable, an implementation
should avoid overloading the servers in this manner. Backed up by Figure 3.b,
becomes aparent that good scalability is offered when the implementation
ensures good load balancing between the messages that the servers have to
process.

Figure 3: Total number of messages received in the proposed implementations by
all servers in the system for $10^{7}$ operations. Figure 4: Scalability
factors of presented algorithms.

We distill the empirical observations of this section into a metric. As
observed, achieving load balancing in terms of evenly distributing both
messages and the processing of requests to servers is important for ensuring
scalability. If we fix an algorithm ${\cal A}$, this is reflected in the
number of messages received by each server $s$ for performing $m$ requests
when executing ${\cal A}$. By denoting this number as $msg_{s}$, we can define
the scalability factor $sf_{s}$ of a server $s$ as follows:

$sf_{s}=\lim_{m\rightarrow\infty}\frac{msg_{s}}{m}$ (1)

where we assume that a maximum number of clients repeatedly initiate requests
and these clients are scheduled fairly. We define the scalability factor $sf$
of ${\cal A}$ as the maximum of the scalability factors of all servers.

$sf=\max_{s}\\{sf_{s}\\}$ (2)

We remark that a low scalability factor indicates good scalability behavior.
The intuition behind this metric is that the lower the $sf_{s}$ fraction is,
the more requests are batched in a message that reaches a server.
Computational overhead for the reading, handling and decoding of a single
message is then spread over multiple requests. As a scalability indicator, the
scalability factor shows that it is of more interest to attempt not to
minimize the total number of messages that are trafficked in a system, but to
design implementations that minimize the total number of messages that a
server has to process. Figure 4 shows graphs of the scalability factors of the
the proposed implementations. The results agree with this theoretical
perception.

##  10 Implementation of Shared-Memory Primitives

In Java, synchronization primitives are provided as methods of the library
sun.misc.unsafe. In order to support most of the methods sun.misc.unsafe uses,
we need to implement the atomic updates, the compare-and-swap primitives, and
the pair of park()/unpark() methods used for thread synchronization. Once
these primitives have been supported, the implementations of several data
structures that are provided in java.util.concurrent will come for free.

In addition to these primitives, we have implemented the primitives fetch-and-
increment and swap, to implement numeric operations used by the methods of
package java.util.concurrent.atomic, described in Section 10, e.g.
getAndSet(). These primitives need to be implemented on a lower level than the
Java Virtual Machine, since sun.misc.unsafe mostly calls primitives that need
either to access the system or hardware resource.

We have to point out that Formic does support reads and stores to remote
memory locations but does not provide coherence. Thus, this remote store is
different from the atomic write primitive we want to implement, due to the
atomicity that the second provides. By adding this primitive, we aim to give
safety when simple writes occur concurrently with other atomic primitives,
such as CAS, etc..

Hence, we implemented the following atomic primitives:

  * •

Read, which taks as arguments a memory address and returns the value that is
stored in this address.

  * •

Write, which takes as arguments a memory address and a value, and stores the
new value to this address.

  * •

Fetch-And-Increment, which takes as arguments a memory address and a value,
and adds the new value to the existing one stored in the address. It then
returns the new value.

  * •

Swap, which takes as arguments a memory address, and a new value, and replaces
the stored value with the new one. It then returns the previous value.

  * •

Compare-And-Swap, which takes as arguments a memory address, an old value and
a new value. If the value stored in the memory address equals to the old
value, then it is replaced by the new value. Then, the function returns the
old value.

##  11 Atomic Accesses Support

The java.util.concurrent.atomic package provides a set of atomic types (as
classes). Instances of these classes must be atomically accessed. In shared-
memory architectures these classes are implemented by delegating the
complexity of synchronization handling to instructions provided by the
underlying architecture, e.g., memory barriers, compare and swap etc. In the
case of Formic, however, such instructions are not available. As a result the
atomic types need to be implemented in software.

A naive implementation is to delegate the handling of such operations to a
manager similar to the monitor manager, presented in Section 2.3 of
Deliverable 1.1. This manager would be responsible for holding the values
associated to instances of atomic types, as well as, for performing atomic
operations on them. Such a manager is capable of reducing the memory traffic
regarding synchronization in some cases.

Algorithm 33 Example of getAndSet implementation. 1 | public final int getAndSet(int newValue) {
---|---
2 |  for (;;) {
3 |  int current = get(); /* Synchronization point */
4 |  if (compareAndSet(current, newValue)) /* Synchronization point */
5 |  return current;
6 |  }
7 | }

For instance, in the implementation depicted in Algorithm 33, the JVM
constantly tries to set the value of the object to newValue before its value
changes between the get() and the compareAndSet invocations. This may result
in many failures and unnecessary synchronizations in case of high contention.
When using a manager there is no need for such a loop. Since the accesses are
only possible by the manager, the manager can assume that the value will never
change between the get() and a consequent set() invocation. As a result we
could implement the logic of the above function in the manager and avoid the
extra communication from the loop iterations. The equivalent algorithm in the
manager  is shown in Algorithm 34.

Algorithm 34 Implementation of getAndSet through the monitor manager. 8 | public final int getAndSet(int newValue) {
---|---
9 |  int current = get();
10 |  set(newValue);
11 |  return current;
12 |  }

A similar effect can be achieved by using the synchronized classifier. Since
the code inside a synchronized block or method can be seen as atomic we can
implement getAndSet as above but without the need of a centralized manager by
just adding synchronized to the method classifiers,  as shown in Algorithm 35.

Algorithm 35 Implementation of getAndSet using synchronized. 13 | public final synchronized int getAndSet(int newValue) {
---|---
14 |  int current = get();
15 |  set(newValue);
16 |  return current;
17 |  }

Note that, in shared-memory processors, this approach is probably less
efficient than the first one when there is no contention on the object. In the
lack of contention the first implementation would just perform a read
instruction and a compare and swap, while in the third implementation it would
also need to go through the monitor implementation of the virtual machine (at
minimum an extra compare and swap, and a write). On the Formic, however, where
there is no compare and swap instruction, the first implementation would
require at least two request messages (get and compareAndSet) to the manager
and the corresponding two replies per iteration. The third implementation
would also need two requests (a monitor acquire and a monitor release) and the
corresponding two replies but with the difference that it never needs to
repeat this process, resulting in reduced memory traffic.

To further improve this approach we avoid the use of regular monitors and
replace them with readers-writers monitors. This way in the case of contented
reads we do not restrict access to a single thread, allowing for increased
parallelism. As a further optimization we slightly change the semantics of
compareAndSet and make it lazely return False in case that the object is owned
by another writer. This behavior is based on the heuristic that if an object
is owned by a writer it is going to be written and the value will probably be
different than the one the programmer provided as expected to the
compareAndSet.

###  11.1 Readers-Writers Implementation

The readers-writers monitors are implemented using the same monitor manager,
presented in Section 2.3 of Deliverable 1.1, but with different operation
codes. We introduce four new operations code, READ_LOCK, WRITE_LOCK,
READ_UNLOCK, and WRITE_UNLOCK. For each readers-writers monitor we keep two
different queues, the readers queue and the writers queue. The readers queue
holds the thread IDs of the threads waiting to acquire a read-lock on the
monitor. Correspondingly, the writers queue holds the thread IDs of the
threads waiting to acquire a write-lock on the monitor.

When a monitor is read-locked we hold the count of threads sharing that read
monitor, while for write-locked monitors we hold the thread ID of the thread
owning that write monitor. As long as the writers lock is empty the monitor
manager services read-lock requests by increasing the counter and sending an
acknowledgement message to the requester. When a write-lock request arrives,
it gets queued to the writers queue and read-lock requests start being queued
in the readers-queue instead of being served, essentially giving priority to
the writer-lock requests. Eventually, when all the readers release the read-
locks they hold the write-lock requests will start being served, and read-lock
requests will be served again only after the writers-queue gets empty again.

We chose to give priority to the write locks since in most algorithms writing
a variable is less common than reading it (e.g., polling). In order to
implement a more fair mechanism we could set a threshold on the number of
read-lock and write-lock requests being served at each phase.

Finally, to support the lazy fail for compareAndSet we introduce another
operation code, the TRY_LOCK. This is a special write-lock request that if the
monitor is not free, it does not get queued in the write-queue, but a negative
acknowledgement is send back to the requester, notifying him that the monitor
is not free.

##  12 Conclusions

We have presented a comprehensive collection of data structures for future
many-core architectures. The collection could be utilized by runtimes of high-
productivity languages ported to such architectures. Our collection provides
all types of concurrent data structures supported in Java’s concurrency
utilities. Other high-level productivity languages that provide shared memory
for thread communication could also benefit from our library. Specifically, we
provide several different kinds of queues, including static, dynamic and
synchronous; our queue (or deque) implementations can be trivially adjusted to
provide the functionality of delay queues (or delay deques) [8]. We do not
provide a priority queue implementation, since it is easy to adopt a
simplified version of the priority queue presented in [65] in our setting. Our
list implementations provide the functionality of sets, whereas the simple
hash table that we utilize to design some of our data structures can serve as
a hash-based map.

We have outlined hierarchical versions of the data structures that we have