Search

This article unifies and generalizes fundamental results related to $n$-process asynchronous crash-prone distributed computing. More precisely, it proves that for every $0\leq k \leq n$, assuming that process failures occur only before the number of participating processes bypasses a predefined threshold that equals $n-k$ (a participating process is a process that has executed at least one statement of its code), an asynchronous algorithm exists that solves consensus for $n$ processes in the presence of $f$ crash failures if and only if $f \leq k$. In a very simple and interesting way, the "extreme" case $k=0$ boils down to the celebrated FLP impossibility result (1985, 1987). Moreover, the second extreme case, namely $k=n$, captures the celebrated mutual exclusion result by E.W. Dijkstra (1965) that states that mutual exclusion can be solved for $n$ processes in an asynchronous read/write shared memory system where any number of processes may crash (but only) before starting to participate in the algorithm (that is, participation is not required, but once a process starts participating it may not fail). More generally, the possibility/impossibility stated above demonstrates that more failures can be tolerated when they occur earlier in the computation (hence the title)., Comment: 10 pages

In an anonymous shared memory system, all inter-process communications are via shared objects; however, unlike in standard systems, there is no a priori agreement between processes on the names of shared objects [14,15]. Furthermore, the algorithms are required to be symmetric; that is, the processes should execute precisely the same code, and the only way to distinguish processes is by comparing identifiers for equality. For such a system, read/write registers are called anonymous registers. It is known that symmetric deadlock-free mutual exclusion is solvable for any finite number of processes using anonymous registers [1]. The main question left open in [14,15] is the existence of starvation-free mutual exclusion algorithms for two or more processes. We resolve this open question for memoryless algorithms, in which a process that tries to enter its critical section does not use any information about its previous attempts. Almost all known mutual exclusion algorithms are memoryless. We show that (1) there is a symmetric memoryless starvation-free mutual exclusion algorithm for two processes using $m \geq 7$ anonymous registers if and only if $m$ is odd; and (2) there is no symmetric memoryless starvation-free mutual exclusion algorithm for $n\geq 3$ processes using (any number of) anonymous registers. Our impossibility result is the only example of a system with fault-free processes, where global progress (i.e., deadlock-freedom) can be ensured, while individual progress to each process (i.e., starvation-freedom) cannot. It complements a known result for systems with failure-prone processes, that there are objects with lock-free implementations but without wait-free implementations [2,5]., Comment: DISC 2023 version

In agreement problems, each process has an input value and must choose a decision (output) value. Given $n\geq 2$ processes and $m \geq 2$ possible different input values, we want to design an agreement algorithm that enables as many processes as possible to decide on the (same) input value of one of the processes, in the presence of $t$ crash failures. Without communication, when each process simply decides on its input value, at least $\lceil (n-t)/m \rceil$ of the processes are guaranteed to always decide on the same value. Can we do better with communication? For some cases, for example when $m=2$, even in the presence of a single crash failure, the answer is negative in a deterministic asynchronous system where communication is either by using atomic read/write registers or by sending and receiving messages. The answer is positive in other cases., Comment: 18 pages

This article addresses election in fully anonymous systems made up of $n$ asynchronous processes that communicate through atomic read-write registers or atomic read-modify-write registers. Given an integer $d\in\{1,\dots, n-1\}$, two elections problems are considered: $d$-election (at least one and at most $d$ processes are elected) and exact $d$-election (exactly $d$ processes are elected). Full anonymity means that both the processes and the shared registers are anonymous. Memory anonymity means that the processes may disagree on the names of the shared registers. That is, the same register name $A$ can denote different registers for different processes, and the register name $A$ used by a process and the register name $B$ used by another process can address the same shared register., Comment: Full version (17 pages) of a SIROCCO 2022 paper

A distributed computing system is a collection of processors that communicate either by reading and writing from a shared memory or by sending messages over some communication network. Most prior biologically inspired distributed computing algorithms rely on message passing as the communication model. Here we show that in the process of genome-wide epigenetic modifications cells utilize their DNA as a shared memory system. We formulate a particular consensus problem, called the epigenetic consensus problem, that cells attempt to solve using this shared memory model, and then present algorithms, derive expected run time and discuss, analyze and simulate improved methods for solving this problem. Analysis of real biological data indicates that the computational methods indeed reflect aspects of the biological process for genome-wide epigenetic modifications.

Process anonymity has been studied for a long time. Memory anonymity is more recent. In an anonymous memory system, there is no a priori agreement among the processes on the names of the shared registers they access. This article introduces the fully anonymous model, namely a model in which both the processes and the memory are anonymous. It is shown that fundamental problems such as mutual exclusion, consensus, and its weak version called set agreement, can be solved despite full anonymity, the first in a failure-free system, the others in the presence of any number of process crashes., Comment: Full version of SSS2019 BA

Anonymous shared memory is a memory in which processes use different names for the same shared read/write register. As an example, a shared register named $A$ by a process $p$ and a shared register named $B$ by another process $q$ can correspond to the very same register $X$, and similarly for the names $B$ at $p$ and $A$ at $q$ which can correspond to the same register $Y\neq X$. Hence, there is a permanent disagreement on the register names among the processes. This new notion of anonymity was recently introduced by G. Taubenfeld (PODC 2017), who presented several memory-anonymous algorithms and impossibility results. This paper introduces a new problem (new to our knowledge), that consists in "desanonymizing" an anonymous shared memory. To this end, it presents an algorithm that, starting with a shared memory made up of $m$ anonymous read/write atomic registers (i.e., there is no a priori agreement on their names), allows each process to compute a local addressing mapping, such that all the processes agree on the names of each register. The proposed construction is based on an underlying deadlock-free mutex algorithm for $n\geq 2$ processes (recently proposed in a paper co-authored by some of the authors of this paper), and consequently inherits its necessary and sufficient condition on the size $m$ of the anonymous memory, namely $m$ must belongs to the set $M(n)=\{m:~$ such that $\forall~ \ell: 1<\ell \leq n:~ \gcd(\ell,m)=1\}\setminus \{1\}$. This algorithm, which is also symmetric in the sense process identities can only be compared by equality, requires the participation of all the processes; hence it can be part of the system initialization. Last but not least, the proposed algorithm has a first-class noteworthy property, namely, its simplicity.

The notion of an anonymous shared memory (recently introduced in PODC 2017) considers that processes use different names for the same memory location. Hence, there is permanent disagreement on the location names among processes. In this context, the PODC paper presented -among other results- a symmetric deadlock-free mutual exclusion (mutex) algorithm for two processes and a necessary condition on the size $m$ of the anonymous memory for the existence of a symmetric deadlock-free mutex algorithm in an $n$-process system. This condition states that $m$ must be greater than $1$ and belong to the set $M(n)=\{m:\forall~\ell:1<\ell\leq n:~\gcd(\ell,m)=1\}$ (symmetric means that, while each process has its own identity, process identities can only be compared with equality). The present paper answers several open problems related to symmetric deadlock-free mutual exclusion in an $n$-process system ($n\geq 2$) where the processes communicate through $m$ registers. It first presents two algorithms. The first considers that the registers are anonymous read/write atomic registers and works for any $m$ greater than $1$ and belonging to the set $M(n)$. It thus shows that this condition on $m$ is both necessary and sufficient. The second algorithm considers anonymous read/modify/write atomic registers. It assumes that $m\in M(n)$. These algorithms differ in their design principles and their costs (measured as the number of registers which must contain the identity of a process to allow it to enter the critical section). The paper also shows that the condition $m\in M(n)$ is necessary for deadlock-free mutex on top of anonymous read/modify/write atomic registers. It follows that, when $m>1$, $m\in M(n)$ is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the anonymous registers read/write or read/modify/write.