Anonymous Read/Write Memory: Leader Election and De-anonymization

Abstract

Anonymity has mostly been studied in the context where processes have no identity. A new notion of anonymity was recently introduced at PODC 2017, namely, this notion considers that the processes have distinct identities but disagree on the names of the read/write registers that define the shared memory. As an example, a register named A by a process p and a shared register named B by another process q may correspond to the very same register X, while the same name C may correspond to different registers for p and q.

Recently, a memory-anonymous deadlock-free mutual exclusion algorithm has been proposed by some of the authors. This article addresses two different problems, namely election and memory de-anonymization. Election consists of electing a single process as a leader that is known by every process. Considering the shared memory as an array of atomic read/write registers $SM [1..m]$, memory de-anonymization consists in providing each process $p_i$ with a mapping function $\mathsf{{map}}_i()$ such that, for any two processes $p_i$ and $p_j$ and any integer $x\in [1..m]$, $\mathsf{{map}}_i(x)$ and $\mathsf{{map}}_j(x)$ allow them to address the same register.

Let n be the number of processes and $\alpha$ a positive integer. The article presents election and de-anonymization algorithms for $m=\alpha ~ n +\beta$ registers, where $\beta$ is equal to 1, $n-1$, or belongs to a set denoted M(n) (which characterizes the values for which mutual exclusion can be solved despite anonymity). The de-anonymization algorithms are based on the use of election algorithms. The article also shows that the size of the permanent control information that, due to de-anonymization, a register must save forever, can be reduced to a single bit.

1 Anonymous Memory, Model, and Aim of the Article

1.1 Anonymous Memory

Memory Anonymity. While the notion of process anonymity has been studied for a long time from an algorithmic and computability point of view, both in message-passing systems (e.g., [1, 4, 17]) and shared memory systems (e.g., [3, 5, 8]), the notion of memory anonymity has been introduced only very recently by [15]. (See also [11] for an introductory survey on process and memory anonymity.)

Let us consider a shared memory $SM$ made up of m atomic read/write registers. Such a memory can be seen as an array with m entries, namely $SM [1..m]$. In a non-anonymous memory system, for each index x, the name $SM [x]$ denotes the same register whatever the process that invokes the address $SM [x]$. As stated in  [15], in the classical system model, there is an a priori agreement on the names of the shared registers. This a priori agreement facilitates the implementation of the coordination rules the processes have to follow to progress without violating the safety (consistency) properties associated with the application they solve [10, 14].

This a priori agreement does no longer exist in a memory-anonymous system. In such a system the very same identifier $SM [x]$ invoked by a process $p_i$ and invoked by a different process $p_j$ does not necessarily refer to the same atomic read/write register. More precisely, a memory-anonymous system is such that:

• prior the execution, an adversary defined, for each process $p_i$, a permutation $f_i()$ over the set $\{1,2,\cdots ,m\}$, such that when $p_i$ uses the address $SM [x]$, it actually accesses $SM [f_i(x)]$, and

• no process knows the permutations.

The read/write registers of a memory-anonymous system are necessarily MWMR.

Results on Memory Anonymity in Mutual Exclusion. The work described in [15] on anonymous read/write memory addressed mutual exclusion, consensus, election and renaming, problems for which it presented algorithms and impossibility results. The consensus, election and renaming algorithms in [15] satisfy the starvation-freedom progress condition, namely, if a process executes alone during a long enough period, it eventually decides. This progress condition is different from the one considered in this article.

Among the results from [15], one states a condition on the size m of the anonymous memory which is necessary for any symmetric deadlock-free algorithm, where symmetric means that process identities can only be compared with equality (hence, there is no notion of a total order on process identities). More precisely, given an n-process system where $n\ge 2$, there is no deadlock-free mutual exclusion algorithm if the size m does not belong to the set $M(n)= \{~m~ \text{ such } \text{ that } \forall ~ \ell :~ 1 < \ell \le n$: $\mathsf{{gcd}}(\ell ,m)=1\} \setminus \{1\}$.

Recently, it has been shown in [2] that the condition $m\in M(n)$ is also a sufficient condition for symmetric deadlock-free mutual exclusion in read/write anonymous memory systems.

1.2 Computing Model

Processes. The system is composed of a finite set of $n\ge 2$ asynchronous processes denoted $p_1$, .., $p_n$. The subscript i in $p_i$ is only a notation convenience, which is not known by the processes. Asynchronous means that each process proceeds to its own speed, which can vary with time and remains always unknown to the other processes. Initially, each process $p_i$ knows only its identity $id_i$, the total number of processes n, and the fact that no two processes have the same identity. It is assumed that there are no process failures. Furthermore, unlike the mutual exclusion model where a process may never leave its remainder region, it is assumed that all the processes must participate in the algorithm.

Anonymous Shared Memory. The shared memory is made up of m atomic anonymous read/write registers denoted $SM [1...m]$. As a system composed of a single atomic register is not anonymous, it is assumed that $m>1$. Hence, all registers are anonymous. As already indicated, when a process $p_i$ invokes the address $SM [x]$, it actually accesses $SM [f_i(x)]$, where $f_i()$ is a permutation statically defined once and for all by an external adversary. We will use the notation $SM _i[x]$ to denote $SM [f_i(x)]$, to stress the fact that no process knows the permutations. It is assumed that all the registers are initialized to the same value. Otherwise, thanks to their different initial values, it would have been possible to distinguish different registers, which consequently will no longer be fully anonymous.

Symmetry Constraint on the Algorithms. A symmetric algorithm is an “algorithm in which the processes are executing exactly the same code and the only way for distinguishing processes is by comparing identifiers. Identifiers can be written, read, and compared, but there is no way of looking inside an identifier. Thus it is not possible to know whether an identifier is odd or even” [15]. Furthermore, the only comparison that can be applied to identifiers is equality. There is no order structuring the identifier name space. (Other notions of symmetry are described in [6, 9]). Let us notice that as all the processes have the same code and all the registers are initialized to the same value, process identities become a key element when one has to design an algorithm in such a constrained context.

1.3 Problems Addressed in This Article

Leader Election. In this problem, the input of each process $p_i$ is its identity $id_i$. Its output will be deposited in a write-once local variable $leader_i$. The aim is to design an algorithm that provides the local variable $leader_i$ of each process $p_i$ with the same process identity. The only process such that $leader_i=id_i$ is the elected process.

Anonymous Memory De-anonymization. In this problem, as before, the input of each process $p_i$ is its identity $id_i$. The aim is for each process $p_i$ to compute an addressing function $\mathsf{{map}}_i()$, which is a permutation over the set of the memory indexes $\{1,\cdots ,m\}$, such that the two following properties are satisfied.

• Safety. Let $y \in \{1,\cdots ,m\}$. For any process $p_i$: $SM _i[\mathsf{{map}}_i(y)]= SM [y]$.

• Liveness. There is a finite time after which all the processes have computed their addressing function $\mathsf{{map}}_i()$.

The safety property states that once a process $p_i$ has computed $\mathsf{{map}}_i()$, its local anonymous memory address $SM _i[x]$, where $x=\mathsf{{map}}_i(y)$, denotes the shared register $SM [y]$.

1.4 Content

This article presents first an impossibility result. Then, it presents symmetric algorithms solving the two previous problems in a system where the process cooperate through m atomic anonymous read/write registers. As already indicated, it is assumed that all the processes participate in the algorithms, and the size of the memory is $m=\alpha ~n +\beta$, where $\alpha$ is a positive integer and $\beta$ can take the following values:

• $\beta =1$. The size of the anonymous memory is then $m=\alpha ~ n +1$.

• $\beta =n-1$. The size of the anonymous memory is then $m=\alpha ~ n + (n-1)$.

• $\beta \in M(n)$ where M(n) is as defined above. Namely, M(n) is the set of values for which deadlock-free mutual exclusion can be solved [2, 15]. This is due to the fact that when $\beta \in M(n)$, the algorithms use a deadlock-free mutual exclusion algorithm to solve conflicts - which do not exist when $\beta =1$ or $\beta =n-1$). In this specific case, $\alpha$ can also be 0.

Find a characterization of the set of the values of m for which leader election can be solved in a memory anonymous system remains an open problem (see the Conclusion section).

2 An Impossibility Result

Theorem 1

There is neither a de-anonymizing algorithm nor an election algorithm for n processes using m anonymous registers, where $m= \alpha ~n$ and $\alpha$ is a positive integer.

Proof

First, we observe that once de-anonymizing is solved using $m= \alpha ~n$ registers, it is straightforward to solve election using $m= \alpha ~n$ registers. First, run the de-anonymizing algorithm to get $m=\alpha ~ n$ non-anonymous registers. Then, using these registers, simply run the symmetric mutual exclusion algorithm from [13] which uses exactly n registers, and let the first process to enter its critical section be the leader. Thus, to prove the theorem, we only need to prove that it is impossible to solve election using $m= \alpha n$ registers.

Assume to the contrary, that there is a symmetric election algorithm for n processes using $m= \alpha ~ n$ registers where $\alpha$ is a positive integer. Let us arrange the m registers on a ring with m nodes where each register is placed on a different node. Let us call the n processes $p_0,...,p_{n-1}$. To each one of the n processes, we assign an initial register (namely, the first register that the process accesses) such that for every two processes $p_i$ and $p_{i+1~(mod~n)}$, the distance between their initial registers is exactly $\alpha$ when walking on the ring in a clockwise direction. Here we use the assumption that $m= \alpha ~ n$.

The lack of global names allows us to assign for each process an initial register and an ordering which determines how the process scans the registers. An execution in which the n processes are running in lock steps, is an execution where we let each process take one step (in the order $p_0,...,p_{n -1}$), and then let each process take another step, and so on. For process $p_i$ and integer k, let $order(p_i, k)$ denote the $k^{th}$ new register that $p_i$ accesses during an execution where the n processes are running in lock steps, and assume that we arrange that $order(p_i, k)$ is the register whose distance from $p_i$’s initial register is exactly $(k-1)$, when walking on the ring in a clockwise direction.

We notice that $order(p_i, 1)$ is $p_i$’s initial register, $order(p_i, 2)$ is the next new register that $p_i$ accesses and so on. That is, $p_i$ does not access $order(p_i, k+1)$ before accessing $order(p_i, k)$ at least once, but for every $j\le k$, $p_i$ may access $order(p_i, j)$ several times before accessing $order(p_i, k+1)$ for the first time.¹

With this arrangement of registers, we run the n processes in lock steps. Since only comparisons for equality are allowed, and all registers are initialized to the same value –which (to preserve anonymity) is not a process identity– processes that take the same number of steps will be at the same state, and thus it is not possible to break symmetry. It follows that either all the processes will be elected, or no process will be elected. A contradiction.    $\square _{Theorem 1}$

3 Memory Anonymous Leader Election When $m=\alpha ~n +1$

3.1 Algorithm

Local Variables. In addition to $leader_i$, each process $p_i$ manages the following local variables: $towrite _i$, $overwritten _i$, $written _i$, which contain sets of memory indexes, $last _i$ which is a memory index, and $nb_i$ which is a non-negative integer. The meaning of these variables will appear clearly in the text of Algorithm 1.

First Part of the Algorithm: Lines 1–12. Each anonymous register $SM [x]$ is initialized to $\langle \mathtt{{start}},\bot \rangle$, where $\bot$ is default value, which can be compared (with equality) with any process identity.

When it invokes $\mathsf{{election}}(id_i)$, a process $p_i$ first writes the pair $\langle start,id_i\rangle$ in the first (from its point of view) $\alpha$ registers, namely, $SM _i[1]$, ..., $SM _i[\alpha ]$ (line 3). Then, it waits until all the registers (except one) are tagged $\mathtt{{start}}$, or a register in which it wrote $\langle \mathtt{{start}},id_i\rangle$ has been overwritten. There are consequently two cases.

• If registers in which $p_i$ wrote $\langle start,id_i\rangle$ have been overwritten (the first part of the predicate of line 5 is then satisfied), $p_i$ updates its local variables $overwritten _i$, $nb_i$, $towrite _i$ and $last _i$, and re-enters the repeat loop, the goal being to have $\alpha$ registers containing $\langle start,id_i\rangle$.

• If all the registers except one (i.e., exactly $m-1=\alpha ~n$ registers) are tagged $\mathtt{{start}}$, $p_i$ exits the loop.

As we will see in the proof, it follows from this collective behavior of the processes that there is time at which exactly one register still contains its initial value $\langle \mathtt{{start}},\bot \rangle$, while for each $j\in \{1,\cdots ,n\}$, exactly $\alpha$ registers contain $\langle \mathtt{{start}},id_j \rangle$ (this property is named P1 in the algorithm).

Second Part of the Algorithm: Lines 13–18. As just seen, the previous part of the algorithm has identified a single register of the anonymous memory, namely the only one containing $\langle \mathtt{{start}},\bot \rangle$. This register is known by all the processes, more precisely, it is known as $SM _i[\ell _i]$ by $p_i$, $SM _j[\ell _j]$ by $p_j$, etc.

So, to become the leader, each process $p_i$ writes the pair $\langle \mathtt{{leader}},id_i\rangle$ in this register (known as $SM _i[\ell _i]$ by $p_i$, line 14). It follows that the last process that will write this register will be the leader. There are then two cases.

• If $p_i$ discovers it has not been elected (we have then $SM _i[\ell _i]\ne \langle \mathtt{{leader}},id_i\rangle$, first predicate of line 15), it resets all the registers containing its tagged identity ($\langle \mathtt{{start}},id_i\rangle$) to the value $\langle \mathtt{{done}},id_i\rangle$ (line 16). Then, $p_i$ waits until all registers except one are tagged $\langle \mathtt{{done}},-\rangle$.

• If $p_i$ is the last process to write in the single register locally known as $SM _i[\ell _i]$, it waits until all the other processes have written $\langle \mathtt{{done}},-\rangle$ in the registers containing their identity (second part of the predicate of line 15). When this is done, the elected process $p_i$ writes $\langle \mathtt{{done}},id_i\rangle$ in all the registers containing its identity (line 16), which allows each other process not to remain blocked at line 17 and progress to the last line of the algorithm. When this occurs, each process can assign the identity of the leader to its local variable $leader_i$ (line 18).

As before, we will see in the proof, that there is a time from which there is exactly one index $\ell \in \{1,\cdots ,n\}$ such that a register contains $\langle \mathtt{{leader}},id_\ell \rangle$, and, for each $j\in \{1,\cdots ,n\}$, there are $\alpha$ registers containing $\langle \mathtt{{done}},id_j\rangle$ (This property is named P2 in the algorithm).

3.2 Proof of Algorithm 1

Lemma 1

(Property P1) . Before a process executes line 14, there is a finite time at which one register contains $\langle \mathtt{{start}}, \bot \rangle$, and, for each $j\in \{1,\cdots ,n\}$, $\alpha$ registers contain $\langle \mathtt{{start}}, id_j\rangle$.

Proof

Considering time instants before a process executes line 14, we have the following.

• Let us first observe that the order on the entries of $SM [1..m]$ in which $p_i$ writes them has been statically predefined by the adversary (namely, according to the –unknown– permutation $f_i()$: $SM _i[x]$ is actually $SM [f_i(x)]$). The important point is that a process $p_i$ never backtracks while scanning $SM [1..m]$, and its successive accesses are $SM [f_i(1)]$, $SM [f_i(2)]$, etc.

• The first writes of a process $p_i$ involve the registers $SM _i[1]$, ..., until $SM _i[\alpha ]$ (lines 1 and 3). Then, as indicated above, its next writes in $SM$ follows a statically predefined order. The process $p_i$ issues a write of $\langle \mathtt{{start}},id_i \rangle$ in a register it has not yet written, for each of its previous writes that have been overwritten by another process (line 4). These writes by $p_i$ concern entries of $SM _i[1..n]$ in which it has not yet written (management of the local variables $towrite _i$, $overwritten _i$, $written _i$, and $last _i$, at lines 1,4, and 8–10). As $p_i$ writes only in new registers, it follows that, for any $p_i$ we have $|\{ x \text{ such } \text{ that } SM [x]=\langle \mathtt{{start}},id_i\rangle \}|\le \alpha$, and from a global point of view we have

  $$\sum _{i=1}^{n} \big (|\{ x \text{ such } \text{ that } SM [x]=\langle \mathtt{{start}},id_i\rangle \}|\big ) \le n \alpha .$$

• It follows from $m=\alpha ~n+1$ and the previous inequality, that there is enough room in the array $SM [1..m]$ for each process $p_i$ to write n times the pair $\langle \mathtt{{start}},id_i\rangle$. Consequently, there is time after which the first predicate of line 5 is false for each process $p_i$, and as $m=n \alpha +1$, the remaining entry of $SM [1..m]$ has still its initial value, namely $\langle \mathtt{{start}},\bot \rangle$, from which we conclude that a process neither remains forever blocked at line 4, nor forever executes the “repeat” loop (lines 2–12).

It follows from the previous observations that before a process executes line 14, there is a time at which, for each identity $id_i$, the pair $\langle \mathtt{{start}},id_i\rangle$ is present in $\alpha$ entries of $SM [1..m]$, and an entry of $SM [1..m]$ has still its initial value, which concludes the proof of the lemma.    $\square _{Lemma 1}$

The Number of Write Accesses Between Line 3 and Line 12. When considering the proof of Lemma 1, it is easy to count the number of writes in the anonymous memory. In the best case, the (unknown) permutations assigned by the adversary to the processes are such that no process overwrites the pairs written by the other processes. In this case, line 2 generates $\alpha ~ n$ writes into the shared memory.

In the worst case, the permutations assigned by the adversary, and the asynchrony among the processes are such that the first $\alpha$ writes of a process are overwritten $(n-1)$ times, the first $\alpha$ writes of another process are overwritten $(n-2)$ times, etc., until a last process whose none of its first $\alpha$ writes are overwritten. In this case, line 2 generates $\alpha \frac{n(n+1)}{2}$ writes into the anonymous shared memory.

Lemma 2

(Property P2) . There is a finite time from which there is $\ell \in \{1,\cdots ,n\}$ such that exactly one register contains $\langle \mathtt{{leader}}, id_\ell \rangle$, and, for each $j\in \{1,\cdots ,n\}$, there are $\alpha$ registers containing $\langle \mathtt{{done}},id_j\rangle$.

Proof

It follows from Lemma 1 that no process blocks or loops forever in the “repeat” loop (2–12). Hence, each process eventually executes lines 13–14. Let $p_\ell$ the last process that executes line 14. This means that after it executed this line, we have $SM _i[\ell _i]=\langle \mathtt{{leader}},id_\ell \rangle$ for any process $p_i$ (namely, $p_\ell$ is the process that has been elected). There are two cases.

• A process $p_i$ that is not the leader, is such that $SM _i[\ell _i]\ne \langle \mathtt{{leader}},id_i\rangle$. Consequently, it cannot be blocked at line 15. So, such a process $p_i$ eventually writes $\langle \mathtt{{done}},id_i\rangle$ in the $\alpha$ registers containing $\langle \mathtt{{start}},id_i\rangle$ (line 16). Let us recall that, due to Property P1, these exactly $\alpha$ registers do exist. When the $(n-1)$ processes that are not leader have executed line 16, there are $\alpha (n-1)$ registers containing $\langle \mathtt{{done}},-\rangle$, $\alpha$ registers containing $\langle \mathtt{{start}},id_\ell \rangle$, and one register containing $\langle \mathtt{{leader}},id_\ell \rangle$.

• As far as the leader process $p_\ell$ is concerned, we have the following. Due to the previous item, the second predicate of line 15 is eventually satisfied. When this occurs, $p_\ell$ writes $\langle \mathtt{{done}},id_\ell \rangle$ in the $\alpha$ registers containing $\langle \mathtt{{start}},id_\ell \rangle$ (line 16) and, from then on, a single register is not tagged $\langle \mathtt{{done}},-\rangle$, namely the one containing $\langle \mathtt{{leader}},id_\ell \rangle$.

The lemma follows directly from the two previous items.    $\square _{Lemma 2}$

Theorem 2

Algorithm 1 solves the election problem.

Proof

Once Property P2 is satisfied, no non-leader process is blocked at line 17, and each process eventually execute line 18. When this occurs, they all agree on the very same leader, namely the only process $p_\ell$ whose identity is tagged $\mathtt{{leader}}$.    $\square _{Theorem 2}$

4 From Leader Election to De-anonymization When $m=\alpha ~n +1$

4.1 A Simple Leader-Based De-anonymization Algorithm

As soon as a process has been elected, it is easy to de-anonymize the anonymous memory. To this end, the elected process $p_\ell$ imposes its mapping function to all the processes.

Algorithm 2 is such a de-anonymization algorithm, which relies on Property P2. Each process $p_i$ invokes the operation $\mathsf{{election}}(id_i)$ (line 1). Then for each register $SM _\ell [x]$, the elected process $p_\ell$ writes the pair $\langle \mathtt{{desa}},x\rangle$ in $SM _\ell [x]$ (line 3). Hence, its mapping function is $\forall ~ x\in \{1,\cdots ,m\}$: $\mathsf{{map}}_i(x)=x$. On the other side, any non-leader process $p_i$ waits until all the registers are tagged $\mathtt{{desa}}$ (line 4). When this occurs, $p_i$ computes its own mapping function (line 5), which is such that $\mathsf{{map}}_i(y)= x$, where $SM _i[x]=\langle \mathtt{{desa}},y\rangle$. The proof of this algorithm is easy and left to the reader.

As a simple example see Fig. 1, where $p_\ell$ has been elected as leader, and $f_\ell ()$ is the permutation defined by the adversary for $p_\ell$ (this permutation remains always unknown to the processes). $SM _i[x]=\langle \mathtt{{desa}},y\rangle$, and $SM _j[z]=\langle \mathtt{{desa}},y\rangle$ address the same register, which is $SM _\ell [y]$. Hence, this register is locally known as $SM _i[\mathsf{{map}}_i(y)]$ by $p_i$, $SM_j[\mathsf{{map}}_j(y)]$ by $p_j$, and $SM _\ell [\mathsf{{map}}_\ell (y)]= SM _\ell [y]$ by $p_\ell$.

Fig. 1.

An example of de-anonymization, $n=4$ and $m=2n+1$

4.2 Using the De-anonymized Memory

When a process $p_i$ returns from Algorithm 2, it knows that all the processes will share the same index for the same register (i.e., if $SM _i[x]=\langle \mathtt{{desa}},y\rangle$, then $SM_i[\mathsf{{map}}_i(y)]$ is $SM _i[x]$). When this occurs, process $p_i$ could start executing its local algorithm defined by the upper layer application, but if it writes an application-related value in some of these registers, this value can overwrite a pair tagged $\mathtt{{desa}}$ stored in a register not yet read by other processes. A way to prevent this problem from occurring consists in tagging all the values written by a process at the application level by the tag $\mathtt{{apply}}$, and include a field containing the common index y associated with this register. Hence, at the application level, a register will contain $\langle \mathtt{{apply}}(y),v\rangle$. In this way, despite asynchrony, any process $p_j$ will be able to compute its local mapping function $\mathsf{{map}}_j()$, and start its upper layer application part, as soon as it has computed $\mathsf{{map}}_j()$.

Let us notice that one bit is needed to distinguish the tag $\mathtt{{desa}}$ and the tag $\mathtt{{apply}}$. Hence each of a pair $\langle \mathtt{{desa}},y\rangle$ and a pair $\langle \mathtt{{apply}}(y),-\rangle$ requires $(1+\mathsf{{log}}_2~m)$ control bits.

4.3 Reducing the Size of the Permanent Control Information

Aim and Additional Assumption. This section shows that, at the price of an additional synchronization phase, the control information that each register must forever contain can be reduced from $(1+\mathsf{{log}}_2~m)$ to a single bit.

To this end, we assume now that each atomic read/write register $SM [x]$ is composed of two parts $SM [x]{.}{{BIT}}$ and $SM [x]{.}{{RM}}$ (i.e., $SM [x]=\langle SM [x]{.}{{BIT}}, SM [x]{.}{{RM}}\rangle$). $SM [x]{.}{{BIT}}$ is for example the leftmost bit of $SM [x]$, and $SM [x]{.}{{RM}}$ the other bits. The meaning and use of $SM [x].{{RM}}$ are exactly the same as $SM [x]$ in Algorithms 1 and 2. For each x, $SM [x]{.}{{BIT}}$ is initialized to 0, while $SM [x]{.}{{RM}}$ is initialized to $\langle \mathtt{{start}},\bot \rangle$. We assume that the previous algorithms are appropriately updated so that they do not modify the bits $SM [x]{.}{{BIT}}$.

Not to overload the presentation, the following notation shortcuts are used in Algorithm 3.

• The read of $SM _i[x]$ at lines 3 and 4 concerns the field $SM _i[x]{.}{{RM}}$.

• The write of $SM _i[x]$ at lines 2 and 4 writes 0 in its leftmost bit (which actually is not modified).

• The statement “${{BIT}}_i[x] \leftarrow 1$” at line 6, means that only the leftmost bit of $SM _i[x]$ is modified. As this statement is issued by the leader process only, this process can first read $SM _i[x]$, prefix it by 1, and rewrite this new value so that only the leftmost bit $SM _i[x]$ is modified.

• The statement “${{BIT}}_i{.}\mathsf{{scan}}()$” stands for “$SM _i{.}\mathsf{{scan}}()$” from which only the leftmost bits are extracted.

After they return from $\mathsf{de}{\text {-}}\mathsf{anonymize}()$, the processes execute the same synchronization pattern as lines 14–17 of Algorithm 1 where the tag $\mathtt{{start}}$ is replaced by the tag $\mathtt{{desa}}$. As the reader can see, at this time the tag $\mathtt{{done}}$ is no longer present in a register, so it can be re-used. Moreover, as the type “process identity” and the type “integer” are different, any integer x is considered as a synonym of $\bot$ when looking at a pair $\langle \mathtt{{desa}}, x\rangle$ (which now is a synonym of $\langle \mathtt{{start}}, x\rangle$).

It follows that we have then the property P1’: there is a time at which exactly one register contains $\langle \mathtt{{start}}, z\rangle$ where z is an integer and, for each $j\in \{1,\cdots ,n\}$, $\alpha$ registers contain $\langle \mathtt{{start}}, id_j\rangle$. Here, the important point is that the process previously elected as a leader knows that any process $p_j$ knows its mapping function $\mathsf{{map}}_j()$. So, it can inform of it the other processes. This is done at lines 6–9 of Algorithm 3. As soon as a process $p_j$ sees the leftmost bit of all the registers equal to 1, it knows that each process knows its mapping function, and $p_j$ can consequently start writing application-related values in the other bits of the registers.

The lines 2–9 of Algorithm 3 and the code of Algorithm 1 are nearly the same. More precisely, they differ in the fact that Algorithm 1 elects a leader at lines 13–14, while Algorithm 3 uses at line 3 the leader that has been previously been elected. It follows that the proof of Algorithm 3 is very close to the proof of Algorithm 1, and is left to the reader.

5 Memory Anonymous Leader Election When $m=\alpha ~n +(n-1)$

Leader Election. Algorithm 1, which solves the election problem for a system of $m=\alpha ~ n +1$ anonymous registers, is based on the fact that each process can write its identity in $\alpha$ registers that – after some finite time – will not be overwritten, and when this occurred, the single remaining not yet written anonymous register is used to elect the leader (which will be the last process that writes its identity in this register well-identified by each process).

The principle that underlies the election when there are $m=\alpha ~n +(n-1)$ anonymous registers is dual in the sense that each of the n processes can write its identity in $\alpha +1$ anonymous registers, except one which can write its identity in only $\alpha$ registers. When this occurs, the corresponding process becomes elected.

Algorithm. The operational view of this idea is captured by Algorithm 4, obtained from a simple adaptation of Algorithm 1 to the fact that the leader is selected from a memory occupation criterion (instead of a competition on a single read/write register, where the last writer is the winner). The main difference lies in the management of the local variables $towrite _i$, $overwritten _i$, $written _i$, $last _i$, and $nb_i$. Property P1” captures the result of the algorithm, namely, there is a time at which $\alpha$ registers contain the same pair $\langle start, id_\ell \rangle$, and for each $j\in \{1,\cdots ,n\}\setminus \{\ell \}$, $\alpha +1$ registers contain $\langle \mathtt{{start}}, id_j\rangle$. Its proof is a simple adaptation of the proof of Algorithm 1.

6 Election and De-anonymization for $m=\alpha ~n +\beta$, $\beta \in M(n)$

This section considers the case where an underlying mutex algorithm, suited to an anonymous memory, is used to elect a leader.

Mutual Exclusion in an Anonymous System. Mutual exclusion in memory anonymous systems was introduced in [15], which presents a symmetric deadlock-free mutex algorithm for two processes only, and a theorem stating that there no symmetric deadlock-free mutual exclusion algorithm if the size m does not belong to the set $M(n)= \{~m~ \text{ such } \text{ that } \forall ~ \ell :~ 1 < \ell \le n$: $\mathsf{{gcd}}(\ell ,m)=1\} \setminus \{1\}$. Recently, a symmetric deadlock-free mutual exclusion algorithm has been proposed, which works any numbernof processes and for any value $m\in M(n)$ [2], from which follows that $m\in M(n)$ is a necessary and sufficient condition for anonymous mutual exclusion.

Leader Election in a System of $m=\alpha ~ n +\beta$ Anonymous Registers. The idea is to rely on the underlying mutex algorithm to elect a leader. But, to this end, the processes have first to isolate a set of $\beta$ anonymous registers in order to be thereafter able to use a symmetric deadlock-free mutex algorithm accessing this subset of registers.

Algorithm 5 realizes this at lines 1–12, which are a simple adaptation of the same line numbers in Algorithms 1 and 4. When the processes exit the repeat loop (line 12), we have property P1”, namely, there is a time at which $\beta$ registers contain the pair $\langle start, \bot \rangle$ and, for each $j\in \{1,\cdots ,n\}$, $\alpha$ registers contain $\langle \mathtt{{start}}, id_j\rangle$. Hence, the set of $\beta$ registers define a common anonymous memory on top of which the n processes can execute a symmetric deadlock-free mutex algorithm. As $\beta \in M(n)$, such mutex algorithms do exist (e.g., [2]). Moreover, as the mutex algorithm is deadlock-free and each process invokes it once, each process eventually enters the critical. It is shown in [7] how a symmetric deadlock-free mutual exclusion algorithm can be used to allow a process to know it is the last that entered the critical section. Finally, the last process to enter is the elected process.

We point out that a memory de-anonymization algorithm is described in [7]. However, as it is based on an underlying mutual exclusion algorithm, it is a specific algorithm that works only for $m\in M(n)$, which is not the general case addressed here, namely $m=\alpha ~n+\beta$.

Memory De-Anonymization in a System of $m=\alpha ~ n +\beta$ Anonymous registers. The previous algorithm can be modified in order to solve de-anomymization. When the last process is inside the critical section, it can impose its mapping function to all the processes by executing lines 4–5 of Algorithm 2, while all the other processes execute lines 5–6 of this algorithm.

7 Conclusion

This article is on synchronization problems in an n-process system in which the communication is through m anonymous read/write registers only. In such a system there is no a priori agreement on the names of the registers: the same register name A used by several processes can head them to different registers. In such a context, the article addressed the following problems: leader election and memory de-anonymization. It was first shown that these problems are impossible to solve if $m=\alpha ~n$, where $\alpha$ is a positive integer. Then, considering $m=\alpha ~n+\beta$, it has presented election algorithms for $\beta =1$, $\beta =n-1$, and $\beta \in M(n)$ where M(n) is the set of the memory anonymous sizes for which symmetric deadlock-free mutual exclusion can be solved in n-process systems. De-Anonymization algorithms have also been presented, each based on an underlying election algorithm.

As stated in [15], the memory-anonymous communication model “enables us to better understand the intrinsic limits for coordinating the actions of asynchronous processes”. It consequently enriches our knowledge of what can be (or cannot be) done when an adversary replaced a common addressing function, by individual and independent addressing functions, one per process. Additional results regarding the computational power of anonymous and non-anonymous objects can be found in [16]. On a more practical side, it appears that the concept of an anonymous memory allows us to model epigenetic cell modifications [12].

On the open problems side, it seems that finding a characterization of all the values of m (the size of the read/write anonymous memory) for which leader election (and de-anonymization) can be solved in an n-process system is particularly important as soon as we want to understand the power and the limits of n-process memory anonymous systems. Finally, since we assume a model where participation is required, in the case where the mutex algorithm from [2] (which also works when participation is not required) is used, it might be possible to replace the algorithm from [2] with a simpler algorithm. In such a case we might not need to assume that $\beta \in M (n)$, but something weaker.