# Snap-Stabilizing Committee Coordination

Borzoo Bonakdarpour, Stéphane Devismes, Franck Petit

► To cite this version:

Borzoo Bonakdarpour, Stéphane Devismes, Franck Petit. Snap-Stabilizing Committee Coordination. Journal of Parallel and Distributed Computing, 2016, 87, pp.26-42. 10.1016/j.jpdc.2015.09.004. hal-01347461

HAL Id: hal-01347461

https://hal.sorbonne-universite.fr/hal-01347461

Submitted on 25 Aug 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Snap-Stabilizing Committee Coordination☆

Borzoo Bonakdarpour

Department of Computing And Software, McMaster University

Stéphane Devismes*

VERIMAG UMR 5104, Université Joseph Fourier, Grenoble

Franck Petit

LIP6 UMR 7606, UPMC Sorbonne Universités, Paris

**Abstract**

In the *committee coordination problem*, a committee consists of a set of professors and committee meetings are synchronized, so that each professor participates in at most one committee meeting at a time. In this paper, we propose two *snap-stabilizing* distributed algorithms for the committee coordination. *Snap-stabilization* is a versatile property which requires a distributed algorithm to efficiently tolerate transient faults. Indeed, after a finite number of such faults, a snap-stabilizing algorithm immediately operates correctly, without any external intervention. We design snap-stabilizing committee coordination algorithms enriched with some desirable properties related to *concurrency*, (*weak*) *fairness*, and a stronger synchronization mechanism called *2-Phase Discussion*. In our setting, all processes are identical and each process has a unique identifier. The existing work in the literature has shown that (1) in general, fairness cannot be achieved in committee coordination, and (2) it becomes feasible if each professor waits for meetings infinitely often. Nevertheless, we show that even under this latter assumption, it is impossible to implement a fair solution that allows *maximal concurrency*. Hence, we propose two orthogonal snap-stabilizing algorithms, each satisfying 2-phase discussion, and either maximal concurrency or fairness. The algorithm that implements fairness requires that every professor waits for meetings infinitely often. Moreover, for this algorithm, we introduce and evaluate a new efficiency criterion called the *degree of fair concurrency*. This criterion shows that even if it does not satisfy maximal concurrency, our snap-stabilizing fair algorithm still allows a high level of concurrency.

**Keywords:** Distributed algorithms, snap-stabilization, self-stabilization, committee coordination

☆ A preliminary version of this paper has been published in IPDPS’2011 [1].

*Corresponding author.

Email addresses: borzoo@mcmaster.ca (Borzoo Bonakdarpour), stephane.devismes@imag.fr (Stéphane Devismes), franck.petit@lip6.fr (Franck Petit)

URL: www.cas.mcmaster.ca/~borzoo/ (Borzoo Bonakdarpour), www-verimag.imag.fr/~devismes/ (Stéphane Devismes), http://pagesperso-systeme.lip6.fr/Franck.Petit/ (Franck Petit)
1. Introduction

Distributed systems are often constructed based on an asynchrony assumption. This assumption is quite realistic, given the principle that distributed systems must be conveniently expandable in terms of size and geographical scale. It is, nonetheless, inevitable that processes running across a distributed system often need to synchronize for various reasons, such as exclusive access to a shared resource, termination, agreement, rendezvous, etc. Implementing synchronization in an asynchronous distributed system has always been a challenge, because of obvious complexity and significant cost; if synchronization is handled in a centralized fashion using traditional shared-memory constructs such as barriers, it may turn into a major bottleneck, and, if it is handled in a fully distributed manner, it may introduce significant communication overhead, unfair behavior, and be vulnerable to numerous types of faults.

The classic *committee coordination problem* [2] characterizes a general type of synchronization called *n-ary rendezvous* as follows:

> "Professors in a certain university have organized themselves into committees. Each committee has an unchanging membership roster of one or more professors. From time to time a professor may decide to attend a committee meeting; he starts waiting and remains waiting until a meeting of a committee of which he is a member is started. All meetings terminate in finite time. The restrictions on convening a meeting are as follows: (1) meeting of a committee may be started only if all members of that committee are waiting, and (2) no two committees can meet simultaneously, if they have a common member. The problem is to ensure that (3) if all members of a committee are waiting, then a meeting involving some member of this committee is convened."

In the context of a distributed system, professors and committees can be mapped onto processes and synchronization events (e.g., rendezvous) respectively. Moreover, the three properties identified in this definition are known as (1) Synchronization, (2) Exclusion, and (3) Progress, respectively.

Most of the existing algorithms that solve the committee coordination problem [2, 3, 4, 5, 6, 7] overlook properties that are vital in practice. Examples include satisfying fairness or reaching maximum concurrency among convened committees and/or professors in a meeting. Moreover, to our knowledge, none of the existing algorithms is resilient to the occurrence of faults. These features are significantly important when a committee coordination algorithm is implemented to ensure distributed mutual exclusion in code generation frameworks, such as process algebras, e.g., CSP, Ada, and BIP [8].

With this motivation, in this paper, we propose **snap-stabilizing** [9, 10] distributed algorithms for the committee coordination problem, where all processes are identical and each process has a unique identifier. Snap-stabilization is a versatile property which requires a distributed algorithm to efficiently tolerate transient faults. Indeed, after a finite number of such faults (e.g., memory corruptions, message losses, etc.), a snap-stabilizing algorithm immediately operates correctly, without any external (e.g., human) intervention. A snap-stabilizing algorithm is also a *self-stabilizing*
[11] algorithm that stabilizes in 0 steps. In other words, our algorithms are optimal in terms of stabilization time, i.e., every meeting convened *after* the last fault satisfies every requirement of the committee coordination. By contrast, an algorithm that would be only self (but not snap) stabilizing only recovers a correct behavior in finite time after the occurrence of the last fault. Nevertheless, to the best of our knowledge, the committee coordination problem was never addressed in the area of self-stabilization. Therefore, the algorithms proposed in this paper are also the first self-stabilizing committee coordination protocols.

Our snap-stabilizing committee coordination algorithms are enriched with other desirable properties. These properties include *Professor Fairness*, *Maximal Concurrency*, and *2-Phase Discussion*. The former property means that every professor which requests to participate in a committee meeting that he is a member of, eventually does. Roughly speaking, the second of the aforementioned properties consists in allowing as many committees as possible to meet simultaneously. The latter (*2-Phase Discussion*) requires professors to collaborate for a minimum amount of time before leaving a meeting.

We first consider *Maximal Concurrency* and *Professor Fairness*. As in [7], to circumvent the impossibility of satisfying fairness [5], each time we consider professor fairness in the sequel of the paper, we assume that every professor waits for a meeting infinitely often. Under this assumption, we show that *Maximal Concurrency* and *Professor Fairness* are two mutually exclusive properties, i.e., it is impossible to design a committee coordination algorithm (even non-stabilizing) that satisfies both features simultaneously.

Consequently, we focus on the aforementioned contradictory properties independently by providing the two snap-stabilizing algorithms. The former maximizes concurrency at the cost of not ensuring professor fairness. On the contrary, the second algorithm maintains professor fairness, but maximal concurrency cannot be guaranteed. Both algorithms are based on the straightforward idea that coordination of the various meetings must be driven by a priority mechanism that helps each professor to know whether or not he can participate in a meeting. Such a mechanism can be implemented using a token circulating among the professors. To ensure fairness, when a professor holds a token, he has the higher priority to convene a meeting. He then retains the token until he joined the meeting. In that case, some neighbors of the token holder can be prevented from participating in other meetings so that the token holder eventually does. This results in decreasing the level of concurrency. In order to guarantee maximal concurrency (but at the risk of being unfair), a waiting professor must release the token if he is not yet able to convene a meeting to give a chance to other committees in which all members are already waiting.

Thus, in the first algorithm, we show the implementability of committee coordination with *Maximal Concurrency* even if professors are not required to wait for meetings infinitely often. To the best of our knowledge this is the first committee coordination algorithm that implements maximal concurrency. Moreover, the algorithm is *snap-stabilizing* and satisfies *2-Phase Discussion*.

We also propose a *snap-stabilizing* algorithm that satisfies *Fairness* on professors (respectively, committees) and respects *2-Phase Discussion*. As mentioned earlier, this algorithm assumes that every professor waits for a meeting infinitely often. Following our impossibility result, the algorithm does not satisfy *Maximal Concurrency*. However, we show that it still allows a high level of concurrency. We analyze this level of concurrency according to a newly defined criterion called
the degree of fair concurrency. We also study the waiting time of our algorithm.

*Organization.* The rest of the paper is organized as follows. In Section 2, we present the preliminary concepts. Section 3 is dedicated to definitions of Maximal Concurrency and Fairness in committee coordination. Then, in Section 4, we propose our first snap-stabilizing algorithm that satisfies both Maximal Concurrency and 2-phase Discussion. In Section 5, we present our snap-stabilizing algorithm that satisfies Fairness and 2-phase Discussion. Our analysis on level of concurrency and waiting time is also presented in this section. Related work is discussed in Section 6. Finally, we present concluding remarks and discuss future work in Section 7.

## 2. Background

### 2.1. *Distributed Systems as Hypergraphs*

Considering the committee coordination problem in the context of distributed systems, professors and committees are mapped onto processes and synchronization events (e.g., rendezvous) respectively. We assume that each process has a unique identifier and the set of all identifiers is a total order. We simply denote the identifier of a process *p* by *p*.

For the sake of simplicity, we assume that each committee has at least two members.<fnref n="1" /> Hence, we model a *distributed system* as a simple self-loopless hypergraph $\mathcal{H} = (V, \mathcal{E})$ where $V$ is a finite set of vertices representing processes and $\mathcal{E}$ is a finite set of *hyperedges* representing synchronization events, such that for all $\epsilon \in \mathcal{E}$, we have $\epsilon \in 2^V$, i.e., each hyperedge is formed by a subset of vertices.

Let $v$ be a vertex in $V$ and $\epsilon$ be a hyperedge in $\mathcal{E}$. We denote by $v \in \epsilon$ the fact that vertex $v$ is incident to hyperedge $\epsilon$. We denote the set of hyperedges incident to vertex $v$ by $\mathcal{E}_v$. We say that two distinct vertices $u$ and $v$ are *neighbors* if and only if $u$ and $v$ are incident to some hyperedge $\epsilon$; i.e., there exists $\epsilon \in \mathcal{E}$, such that $u, v \in \epsilon$. The set of all neighbors of $v$ is denoted by $N(v)$.

In the committee coordination problem, professors in the same committee need to communicate with each other. We assume that two processes can directly communicate with each other if and only if they are neighbors. This induces what we call an underlying communication network defined as follows: the *underlying communication network* of a distributed system $\mathcal{H} = (V, \mathcal{E})$ is an undirected simple connected graph $G_{\mathcal{H}} = (V, E_{\mathcal{H}})$, where $E_{\mathcal{H}} = \{\{p_1, p_2\} | p_1 \in V \land p_2 \in V \land p_1 \in N(p_2)\}$. Figure 1(b) shows the underlying communication network of the hypergraph given in Figure 1(a).

### 2.2. *Computational Model*

The communication between processes are carried out using *locally shared variables*. Each process owns a set of locally shared variables, henceforth referred to as *variables*. Each variable ranges over a fixed domain and the process can read and write them. Moreover, a process can also read variables of its neighbors.<fnref n="2" /> The state of a process is defined by the value of its variables. A

<footnote n="1">¹Adapting our results to take singleton committees into account is straightforward.</footnote>

<footnote n="2">²In particular, a process can read the identifiers of its neighbors.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: An example of a hypergraph and its underlying communication network.</figcaption></figure>

process can change its state by executing its local algorithm. The local algorithm of a process $p$ is described using a finite ordered list of guarded actions of the form:

$$ \langle label \rangle :: \langle guard \rangle \mapsto \langle statement \rangle. $$

The label of an action is only used to identify the action in discussions and proofs. The guard of an action of $p$ is a Boolean expression involving a subset of variables of $p$ and its neighbors. The statement of an action of $p$ updates a subset of variables of $p$. The order of the list follows the order of appearance of the actions in the code of the local algorithm and give priorities to actions: action $A$ has higher priority than action $B$ if and only if $A$ appears after $B$ in the code.

A configuration $\gamma$ in a distributed system is an instance of the state of its processes. We denote the set of all configurations of a distributed system $\mathcal{H}$ by $\Gamma_{\mathcal{H}}$. The concurrent execution of the set of all local algorithms defines a *distributed algorithm*. We say that an action of a process $p$ is enabled in a configuration $\gamma$ if and only if its guard is true in $\gamma$. By extension, process $p$ is said to be enabled in $\gamma$ if and only if at least one of its actions is enabled in $\gamma$. An action can be executed only if its guard is enabled. We denote by $\text{Enabled}(\gamma)$ the subset of processes that are enabled in configuration $\gamma$.

When the configuration is $\gamma$ and $\text{Enabled}(\gamma) \neq \emptyset$, a daemon (or scheduler) selects a non-empty set $\mathcal{X} \subseteq \text{Enabled}(\gamma)$; then every process of $\mathcal{X}$ atomically executes its priority enabled action, leading to a new configuration $\gamma'$, and so on. The transition from $\gamma$ to $\gamma'$ is called a step (of $\mathcal{A}$). The possible steps induce a binary relation over configurations of $\mathcal{A}$, denoted by $\mapsto$.

A computation of a distributed system is a maximal sequence of configurations $\gamma_0, \gamma_1, \dots$ such that (1) $\gamma_0$ is an arbitrary configuration, and (2) for each configuration $\gamma_i$, with $i \ge 0$, $\gamma_i \mapsto \gamma_{i+1}$. Maximality of a computation means that the computation is either infinite or eventually reaches a terminal configuration (i.e., a configuration where no action is enabled).

A daemon is defined as a predicate over computations. There exist several kinds of daemons. Here, we consider a *distributed weakly fair daemon*. Distributed means that, at each step, if one or
141

142

143

144

145

146

147

148

149

150

151

152

more processes are enabled, then the daemon selects at least one (maybe more) of these processes. *Weak fairness* means that every continuously enabled process is eventually selected by the daemon.

We say that a process *p* is *neutralized* in $\gamma_i \mapsto \gamma_{i+1}$, if *p* is *enabled* in $\gamma_i$ and not enabled in $\gamma_{i+1}$, but did not execute any action in $\gamma_i \mapsto \gamma_{i+1}$. To compute the time complexity, we use the notion of *round* [12]. This notion captures the execution rate of the slowest process in any computation. The first *round* of a computation *e* is the minimal prefix of *e*, $\gamma_0...\gamma_i$, containing the activation or the neutralization of every process that is enabled in the initial configuration. Let $e_{\gamma_i}$ be the suffix of *e* starting from $\gamma_i$ (the last configuration of the first round of *e*). The second *round* of *e* is the first round of $e_{\gamma_i}$, and so on.

The *fair composition* [13] of two algorithms $P_1$ and $P_2$ consists in running $P_1$ and $P_2$ in alternation in such a way that there is no computation suffix, where a process is continuously enabled w.r.t. $P_i$ ($i \in \{1, 2\}$) without executing any of its enabled actions w.r.t. $P_i$.

153

## 2.3. The Committee Coordination Problem

The original committee coordination problem is as follows [2]. Let $\mathcal{H} = (V, \mathcal{E})$ be a distributed system. Each process in $V$ represents a *professor* and each hyperedge in $\mathcal{E}$ represents a committee. We say that two committees $\epsilon_1$ and $\epsilon_2$ are *conflicting* if and only if $\epsilon_1 \cap \epsilon_2 \neq \emptyset$. A professor can be in anyone of the following three states: (1) *idle*, (2) *waiting*, and (3) *meeting*. A professor may remain in the idle state for an arbitrary (even infinite) period of time. An idle professor may start waiting for a committee meeting. A professor remains waiting until all participating professors of a committee, which he is a member of, agree on meeting. Moreover, a professor may leave a meeting, become idle, and subsequently be waiting for a new committee meeting.

154

155

156

157

158

159

160

161

Chandy, Misra [2], and Bagrodia [4] require that any solution to the problem must satisfy the following specification:

162

163

* (Exclusion) No two conflicting committees may meet simultaneously.

164

* (Synchronization) A committee meeting may convene only if all members of that committee are waiting.

165

166

* (Progress) If all members of a committee $\epsilon$ are waiting, then some professor in $\epsilon$ eventually goes to the meeting state.

167

168

## 2.4. 2-Phase Discussion

169

170

171

172

173

174

175

176

The original Committee Coordination problem specification does not constrain professors with respect to their time spent in a committee meeting in any ways. Thus, distributed algorithms for committee coordination have been developed regardless this issue. For instance, solutions proposed in [2, 4] that employ the dining philosophers problem [14] in order to resolve committee conflicts satisfy the specification presented in Subsection 2.3, but have the following shortcoming. Since a philosopher acquires and releases forks all at once, members of the corresponding committee have to leave the meeting all together.<fnref n="3" /> There are two problems with such a restriction: (1)

<footnote n="3">³The same argument holds for solutions based on the *drinking philosophers* [14] and tokens.</footnote>
177
178

an implicit strong synchronization is assumed on terminating a committee meeting, and (2) fast
professors have to wait for slow professors to finish the task for which they setup a rendezvous.

179

180

181

182

183

184

185

186

187

188

189

190

191

We constrain the specification such that upon agreement on a meeting, the meeting takes place until a professor unilaterally leaves (that is, without waiting for other professors) the meeting. The reason for this requirement is due to the fact that in practical settings, based upon the speed of processes (professors), the type of local computation, and required resources, each process may spend a different time period to utilize resources or execute a critical section. Nevertheless, we also require that each professor must spend a minimum amount of time to discuss issues in the meeting. The intuition for this constraint is that processes participate in a rendezvous to share resources or do some minimal computation and, hence, they should not be allowed to leave the meeting immediately after it convenes. Another reason for requiring this minimal discussion by all professors is inspired by the fact that in the recent applications of using rendezvous interactions to generate correct distributed and multi-core code, such interactions normally involve data transmission and even code execution at interaction level [15, 16]. The following definition elegantly captures this requirement.

192

193

**Definition 1 (2-Phase Discussion)** *We define the 2-phase discussion by the following two properties:*

194

195

196

* Phase 1. (Essential Discussion) Upon a meeting convenes, a first session of discussion should take place until each participating professor has the opportunity to execute a task involving information from all or part of the participants.

197

198

199

* Phase 2. (Voluntary Discussion) Upon a meeting convenes and after fulfilling the essential discussion, the discussion (and consequently the meeting) continues until a professor voluntarily terminates his/her discussion (and consequently the meeting).

200

201

In the following, we call 2-phase committee coordination problem the committee coordination problem enriched with the essential and voluntary discussions.

202

## 2.5. Snap-stabilization

203

204

205

206

207

Snap-stabilization [9, 10] is a versatile property which requires a distributed algorithm to efficiently tolerate transient faults. Indeed, after a finite number of such faults (e.g., memory corruptions), a snap-stabilizing algorithm immediately operates correctly, without any external (e.g. human) intervention. By contrast, the related concept of self-stabilization [11] only guarantees that the system eventually recovers to a correct behavior.

208

209

210

211

212

213

In (self- or snap-) stabilizing systems, we consider the system immediately after the occurrence of the *last* fault. That is, we study the system starting from an arbitrary configuration reached due to the occurrence of transient faults, but from which *no fault will ever occur*. By abuse of language, this configuration is referred to as initial configuration of the system in the literature. A snap-stabilizing algorithm then guarantees that *starting from any arbitrary initial configuration, any of its computations always satisfies the specification of the problem*.

214

215

216

This means, in particular, that in (self- or snap-) stabilizing systems there is no fault model in the literal sense. As we study the system after the *last* fault, we do not treat the faults but their consequences. The result of a finite number of transient faults being the arbitrary perturbation of the
system configuration, we consider any computation started in any arbitrary initialized configura-
tion, but in which there is no fault. So, for example, to show that our algorithms are snap-stabilizing
w.r.t the committee coordination problem, we have to show that the specification of the commit-
tee coordination problem (e.g., exclusion, progress, synchronization, etc) is always satisfied in all
possible (fault-free) computations starting from all possible (arbitrary) configurations.

It is important to note that snap-stabilizing algorithms are not insensitive to transient faults. Actually, a snap-stabilizing algorithm guarantees that any task execution started *after* the end of the faults operates correctly. However, there is no guarantees for tasks executed completely or in part during faults. By contrast, self- but not snap- stabilizing algorithms require to start task execution several times (yet a finite number of time) before correctly performing them (that is, w.r.t. their specification). Hence, snap-stabilization is a specialization of self-stabilization that offers stronger safety guarantees. For example, in the committee coordination problem, snap-stabilization ensures that every meeting convened after the last transient faults satisfies every requirement of the committee coordination problem. However, there is no guarantees for the meetings started during the transient faults, except that they do not interfere with the execution of the meetings that convened after the last fault.

3. Maximal Concurrency versus Fairness in Committee Coordination

3.1. *Definitions*

In practical applications, it is crucial to allow as many processes as possible to execute simul-
taneously without violating other correctness constraints. Although the level of concurrency has
significant impact on performance and resource utilization, it does not appear as a constraint in the
original committee coordination problem. Moreover, the solutions proposed by Chandy and Misra
[2] and Bagrodia [3, 4] result in decreasing the level of concurrency drastically, making them less
appealing for practical purposes. Examples include the circulating token mechanism among con-
flicting committees [3], and reduction to the dining philosophers problems, where a “manager”
handles multiple committees. Reduction to the drinking philosophers problem such as those in
[2, 4, 17] results in *more* concurrency, but not maximal. This is due to the fact that existing solu-
tions to the drinking philosophers problem try to achieve concurrency and fairness simultaneously,
which we will show is impossible in committee coordination.

We formulate the issue of concurrency, so that as many committees as possible meet simul-
taneously. Our definition of maximal concurrency is inspired by the efficiency property given in
[18]. Informally, we define maximal concurrency as follows: if there is at least one committee,
such that all its members are waiting, then eventually a new meeting convenes *even if no other
meeting terminates in the meantime*. In other words, while it is possible, new meetings should be
able to convene, regardless the duration of meetings that already hold. Now, to formally define
maximal concurrency we need, in particular, to express the constraint “regardless of the duration
of meetings that already hold”. For that purpose, we borrow the ideas of Datta *et al* [18] by us-
ing the following artefact: we let a professor (process) remains in the meeting state forever. We
emphasize that we make this assumption only to define our constraint; our results in this paper do
assume finite-time meetings as mentioned earlier.
**Definition 2 (Maximal Concurrency)** Assume that there is a set of professors $P_1$ that are all in infinite-time meetings. Let $P_2$ be a set of professors waiting to enter a committee meeting (Obviously, $P_1 \cap P_2 = \emptyset$ and idle processes are in neither $P_1$ nor $P_2$). Let $\Pi$ be the set of hyperedges having all their incident professors in $P_2$. If $\Pi \neq \emptyset$, then a meeting between every professor incident to some hyperedge $\epsilon \in \Pi$ eventually convenes.

We note that in Definition 2, we use the term “maximal”, because our intention is not to enforce the largest number of committees (i.e., maximum) to meet simultaneously, this latter problem is clearly *NP*-hard! In other words, committees convene until the systems is exhausted. This greedy approach does not always result in obtaining the maximum number of committees that can meet at the same time.

Following the results in [5], if a professor's status does not become waiting infinitely often, achieving fairness is impossible. Thus, we consider fairness assuming professors always eventually switch to the waiting status. In this context, we define fairness on professors (also called weak fairness, [6]) as follows.

**Definition 3 (Professor Fairness)** Every professor participates infinitely often in a committee meeting that he is a member of.

## 3.2. Negative Result

The next theorem shows that Maximal Concurrency and Professor Fairness are incompatible. Its proof follows ideas similar to the impossibility results of Joung [19] as well as Tsay and Bagrodia [5].

The idea behind this result is rather simple: Consider any process $p$. To satisfy professor fairness, a meeting having $p$ as member must eventually convene. To have such a guarantee, the algorithm may eventually have to prevent some neighbors of $p$ from participating in meetings until a meeting including them and $p$ can convene. These blockings may happen while no meeting including $p$ can be yet convened. This constraint then prevents some meetings from holding concurrently. That is, making maximal concurrency impossible.

**Theorem 1** Assuming that every professor waits for meetings infinitely often, it is impossible to design an algorithm (even non-stabilizing) for an arbitrary distributed system that solves the committee coordination problem and simultaneously satisfies Maximal Concurrency and Professor Fairness.

*Proof.* Suppose by contradiction that there exists an algorithm $\mathcal{A}$ (be it stabilizing or not) working in any topology that satisfies both Maximal Concurrency and Professor Fairness. Now, consider a computation of $\mathcal{A}$ on hypergraph $\mathcal{H} = (V, \mathcal{E})$ where $V = \{1, 2, 3, 4, 5\}$ and $\mathcal{E} = \{{\{1, 2\}, \{1, 3, 5\}, \{3, 4\}}\}$. Figure 2 shows three possible configurations $A, B$, and $C$ obtained by executing algorithm $\mathcal{A}$ on $\mathcal{H}$. In the figure, solid bold lines represent meetings that are currently being held. Also, a process that is not in a meeting is supposed to be waiting. For example, in configuration $A$, professors 1 and 2 are meeting and professors 3, 4, and 5 are waiting.

We first show that there are computations of $\mathcal{A}$ that eventually reach configuration $A$. As professors 1 and 2 wait for meetings infinitely often, by Professor Fairness, a meeting between
<figure><img src="image_3.png" /><figcaption>Figure 2: Impossibility of Maximal Concurrency and Professor Fairness.</figcaption></figure>

professors 1 and 2 eventually convenes. When this happens, if professors 3 and 4 are meeting, then their meeting can terminate before the one between 1 and 2. So, the system may reach a configuration where only 1 and 2 are meeting. After that, assuming that professors 3, 4, and 5 immediately go to the waiting state, then the system reaches configuration $A$.

From configuration $A$, if the committee $\{1, 2\}$ takes an arbitrary long (but finite) time, then a meeting of the committee $\{3, 4\}$ must eventually convene in order to satisfy Maximal Concurrency and the system reaches configuration $B$. Now, suppose meeting $\{1, 2\}$ terminates first and professors 1 and 2 immediately go to waiting state again. So, 1, 2, and 5 are waiting and 3 and 4 are in a meeting (configuration $C$). Following a similar reasoning, configuration $B$ can be reached from configuration $C$, and configuration $A$ can be reached from configuration $B$. By repeating this pattern infinitely many times, we obtain a possible computation of $A$, where professor 5 never participates in any meeting while being continuously waiting, which contradicts with Professor Fairness. □

Note that Maximal Concurrency and Professor Fairness can be simultaneously achieved in some particular networks, e.g., networks where no committees are in conflict, or networks where some professor belongs to all committees (e.g., a complete hypergraph, or a star topology). In the latter case, note that all committees are conflicting and so at most one can meet at a time.

We note that every algorithm that satisfies Professor Fairness also satisfies Progress. Also, observe that Professor Fairness does not imply that particular committees eventually convene. We define such a property as follows.

**Definition 4 (Committee Fairness)*** Every committee meeting convenes infinitely often.

Notice that since Committee Fairness implies Professor Fairness, impossibility of satisfying both Maximal Concurrency and Committee Fairness trivially follows.

**Corollary 1** Assuming that every professor waits for meetings infinitely often, it is impossible to design an algorithm (even non-stabilizing) for an arbitrary distributed system that solves the committee coordination problem and simultaneously satisfies Maximal Concurrency and Committee Fairness.

Theorem 1 shows that Professor Fairness and Maximal Concurrency are contradictory properties to satisfy. Thus, in order to satisfy one property, we have to omit the other. Omitting fairness results in an algorithm such as the one presented in Section 4. Omitting maximal concurrency results in an algorithm such as the one presented in Section 5.
Note that both algorithms use a single token circulation that ensures the progress in the former case and the fairness in the latter. As a matter of fact, they mainly differ in the way they handle the token. Concerning the second algorithm, one can suggest that the use of several tokens (e.g., the local mutual exclusion mechanism in [20]) instead of a single one would enhance the fairness guarantee. However, increasing the number of tokens results in decreasing the degree of (fair) concurrency,<fnref n="4" /> which is the target metric here. The key idea is that the token is used to give priority to convene a meeting. However, the token is not mandatory to join a meeting, unless a process is starved to join a meeting. Then, to guarantee fairness, it is mandatory that the token holder selects a committee and sticks with that committee until it meets, even if some members of that committee are currently participating in another meeting. In this case, every other waiting member of that committee has to wait until the meeting convenes while they may participate in a meeting of another committee. This results in decreasing the degree of concurrency (that is why our second algorithm does not satisfy Maximal Concurrency): every waiting member of the committee selected by the token holder is blocked until the committee is able to convene. Hence, increasing the number of tokens increases the number of blocked processes which in turn decreases the degree of concurrency. In other word, enforcing the fairness decreases concurrency.

### 3.3. Complexity Analysis of Fair Solutions

We now introduce and study two complexity measures: *degree of fair concurrency* and *waiting time*. First, in order to characterize the impact of fairness on reducing the number of processes that can run concurrently, we introduce the notion of *Degree of Fair Concurrency*. Roughly speaking, this degree is the minimum number of committees that can meet concurrently without compromising Professor Fairness.

**Definition 5 (Degree of Fair Concurrency)** *Let $\mathcal{A}$ be a committee coordination algorithm that satisfies Professor Fairness. Let professors remain in a meeting for infinite time.<fnref n="5" /> Under such an assumption the system reaches a quiescent state where the status of all professors do not change any more. The Degree of Fair Concurrency of $\mathcal{A}$ is then the minimum number of meetings held in a quiescent state.*

When considering fair solutions, it is of practical interest to evaluate the *Waiting Time*. In our context where processes are either waiting or meeting, we define waiting time as follows:

**Definition 6 (Waiting Time)** *The maximum time before a process participates in a committee meeting is waiting time.*

## 4. Snap-stabilizing 2-Phase Committee Coordination with Maximal Concurrency

In this section, we propose a Snap-stabilizing algorithm that satisfies Maximal Concurrency as well as the 2-Phase Discussion. We present our algorithm in Subsection 4.1. The correctness proof appears in Subsection 4.2.

<footnote n="4">⁴The term “degree of fair concurrency” is formally explained in Subsection 3.3</footnote>

<footnote n="5">⁵As in Definition 2, infinite meetings are used only for formalization.</footnote>
### 4.1. Algorithm

Our algorithm is a composition of two modules: (1) a Snap-stabilizing algorithm – denoted $CC1$ – that ensures Exclusion, Synchronization, Maximal Concurrency, and 2-Phase Discussion, and (2) a self-stabilizing module – denoted $TC$ – that manages a circulating token for ensuring Progress. Each process $p$ runs this algorithm, where the intention of $p$ in participating or leaving a committee are declared by truthfulness of input predicates $RequestIn(p)$ and $RequestOut(p)$, respectively.

**Remark 1** We emphasize that this composition is snap-stabilizing, as the self-stabilizing token circulation is not used to ensure any safety property.

**Token Circulation Module.** We assume that the token circulation module is a black box with the following property:

#### Property 1

* $TC$ contains one action to pass the token from neighbor to neighbor:

$$T :: \mathit{Token}(p) \mapsto \mathit{ReleaseToken}_p$$

* Once stabilized, every process executes action $T$ infinitely often, but when $T$ is enabled in a process, it is not enabled in any other process.

* $TC$ stabilizes independently of the activations of action $T$.

To obtain such a token circulation, one can compose a self-stabilizing leader election algorithm (e.g., in [21, 22, 23]) with one of the self-stabilizing token circulation algorithms in [24, 25, 26, 27] for arbitrary rooted networks. The composition only consists of two algorithms running concurrently with the following rule: if a process decides that it is the leader, it executes the root code of the token circulation. Otherwise, it executes the code of the non-root process.

**Composition.** The composition of $CC1$ and $TC$ is denoted by $CC1 \circ TC$. Actually, $CC1 \circ TC$ is a fair composition of $CC1$ and $TC$ that does not explicitly contain action $T$: in $CC1 \circ TC$, action $T$ is emulated by $CC1$, where predicate $Token(p)$ and the statement $ReleaseToken_p$ are given as inputs in $CC1$.

**Committee Coordination Module.** Algorithm $CC1$ is identical for all processes in the distributed system. Its code is given in Algorithm 1. Interactions between each professor $p$ and his local algorithm are managed using two input predicates: $RequestIn(p)$ and $RequestOut(p)$. These predicates express the fact that a professor autonomously decides to wait and leave a meeting, respectively. The predicate $RequestIn(p)$ holds when professor $p$ requests participation in a committee meeting. The predicate $RequestOut(p)$ holds when $p$ desires to stop discussing in a meeting. Thus, $p$ eventually satisfies $RequestOut(p)$ during the meeting or after some members left it. So, once $p$ has done its essential discussion, it can voluntary leave the meeting when it satisfies $RequestOut(p)$.

Each process $p$ maintains a status variable $S_p \in \{\text{idle}, \text{looking}, \text{waiting}, \text{done}\}$, a Boolean variable $T_p$, and an edge pointer $P_p$. We explain the goal of these variables below:
<caption>**Algorithm 1** Pseudo-code of CC1 for process *p*.</caption>

**Inputs:**
*RequestIn(p)* : Predicate: input from the system indicating desire for participating in a committee
*RequestOut(p)* : Predicate: input from the system indicating desire for leaving a committee
*Token(p)* : Predicate: input from *TC* indicating process *p* owns the token
*ReleaseToken(p)* : Statement: output from *TC* indicating process *p* releases the token

**Constants:**
*E*<sub>*p*</sub> : Set of hyperedges incident to process *p*

**Variables:**
*S*<sub>*p*</sub> ∈ {idle, looking, waiting, done} : Status
*P*<sub>*p*</sub> ∈ *E*<sub>*p*</sub> ∪ {⊥} : Edge pointer
*T*<sub>*p*</sub> : Boolean

**Macros:**
*FreeEdges*<sub>*p*</sub> = {ε ∈ *E*<sub>*p*</sub> | ∀q ∈ ε : *S*<sub>q</sub> = looking}
*FreeNodes*<sub>*p*</sub> = {q | ∃ε ∈ *FreeEdges*<sub>*p*</sub> : q ∈ ε}
*TFreeNodes*<sub>*p*</sub> = {q ∈ *FreeNodes*<sub>*p*</sub> | *T*<sub>q</sub>}
*Cands*<sub>*p*</sub> = if (*TFreeNodes*<sub>*p*</sub> ≠ ∅) then *TFreeNodes*<sub>*p*</sub> else *FreeNodes*<sub>*p*</sub> fi

**Predicates:**
*Ready(p)* ≡ ∃ε ∈ *E*<sub>*p*</sub> : ∀q ∈ ε : ((*P*<sub>q</sub> = ε) ∧ (*S*<sub>q</sub> ∈ {looking, waiting}))
*LocalMax(p)* ≡ *p* = max(*Cands*<sub>*p*</sub>)
*MaxToFreeEdge(p)* ≡ (*FreeEdges*<sub>*p*</sub> ≠ ∅) ∧ LocalMax(*p*) ∧ ¬Ready(*p*) ∧ (*P*<sub>*p*</sub> ∉ *FreeEdges*<sub>*p*</sub>)
*JoinLocalMax(p)* ≡ (*FreeEdges*<sub>*p*</sub> ≠ ∅) ∧ ¬LocalMax(*p*) ∧ ¬Ready(*p*) ∧ (∃ε ∈ *FreeEdges*<sub>*p*</sub> : (*P*<sub>max(*Cands*<sub>*p*</sub>)</sub> = ε) ∧ *P*<sub>*p*</sub> ≠ ε))
*Meeting(p)* ≡ ∃ε ∈ *E*<sub>*p*</sub> : ∀q ∈ ε : (*P*<sub>q</sub> = ε ∧ *S*<sub>q</sub> ∈ {waiting, done})
*LeaveMeeting(p)* ≡ ∃ε ∈ *E*<sub>*p*</sub> : ((*P*<sub>*p*</sub> = ε) ∧ (∀q ∈ ε : ((*P*<sub>q</sub> = ε) ⇒ (*S*<sub>*q*</sub> = done))))
*Useless(p)* ≡ *Token(p)* ∧ [(*S*<sub>*p*</sub> = idle) ∨ (*S*<sub>*p*</sub> = looking) ∧ *FreeEdges*<sub>*p*</sub> = ∅)]
*Correct(p)* ≡ [(*S*<sub>*p*</sub> = idle) ⇒ (*P*<sub>*p*</sub> = ⊥)] ∧
[(*S*<sub>*p*</sub> = waiting) ⇒ *Ready(p)* ∨ *Meeting(p)*] ∧
[(*S*<sub>*p*</sub> = done) ⇒ *Meeting(p)* ∨ *LeaveMeeting(p)*]

**Actions:**
*Step*<sub>1</sub> :: *RequestIn(p)* ∧ (*S*<sub>*p*</sub> = idle) ↦ *S*<sub>*p*</sub> := looking; *P*<sub>*p*</sub> := ⊥;
*Step*<sub>21</sub> :: MaxToFreeEdge(*p*) ↦ *P*<sub>*p*</sub> := ε, such that ε ∈ *FreeEdges*<sub>*p*</sub>;
*Step*<sub>22</sub> :: JoinLocalMax(*p*) ↦ *P*<sub>*p*</sub> := ε, such that (ε ∈ *E*<sub>*p*</sub> ∧ ε = *P*<sub>max(*Cands*<sub>*p*</sub>)</sub>);
*Token*<sub>1</sub> :: *Token(p)* ≠ *T*<sub>*p*</sub> ↦ *T*<sub>*p*</sub> := *Token(p)*;
*Token*<sub>2</sub> :: *Useless(p)* ↦ *ReleaseToken(p)*; *T*<sub>*p*</sub> := false;
*Step*<sub>31</sub> :: *Ready(p)* ∧ (*S*<sub>*p*</sub> = looking) ↦ *S*<sub>*p*</sub> := waiting;
*Step*<sub>32</sub> :: *Meeting(p)* ∧ (*S*<sub>*p*</sub> = waiting) ↦ (EssentialDiscussion); *S*<sub>*p*</sub> := done;
*Step*<sub>4</sub> :: *LeaveMeeting(p)* ∧ *RequestOut(p)* ↦ *S*<sub>*p*</sub> := idle; *P*<sub>*p*</sub> := ⊥; if *Token(p)* then *ReleaseToken(p)* fi; *T*<sub>*p*</sub> := false;
*Stab*<sub>1</sub> :: ¬*Correct(p)* ∧ (*S*<sub>*p*</sub> = idle) ↦ *P*<sub>*p*</sub> := ⊥;
*Stab*<sub>2</sub> :: ¬*Correct(p)* ∧ (*S*<sub>*p*</sub> ≠ idle) ↦ *S*<sub>*p*</sub> := looking; *P*<sub>*p*</sub> := ⊥;
1. When process $p$ is idle (that is $S_p = \text{idle}$) but desires to participate in a committee meeting (that is, if $RequestIn(p)$ is true), it changes its status from idle to looking and initializes its edge pointer $P_p$ to $\perp$ (action $Step_1$).

2. Next, process $p$ starts looking for an available committee to join. Process $p$ shows interest in joining a committee whose processes are all looking by setting its edge pointer $P_p$ to the corresponding hyperedge, if such a hyperedge exists (actions $Step_{21}$ and $Step_{22}$).

To obtain agreement on the committees to convene, we implement token-based priorities. When a looking process $p$ is the one with highest priority in its neighborhood, it points to an edge corresponding to a committee whose processes are all looking (if any) and sticks with it. Looking processes with low priorities select the committee chosen by their looking neighbor of highest priority, described next.

Each process $p$ maintains a Boolean variable $T_p$ which shows whether or not it owns a token. A token holder has a higher priority than its neighbors to convene a committee. In case of several token holders (only during the stabilization of token circulation), we give priority to the looking token holder with the maximum identifier.

A token holder releases its token in two cases: (1) when it leaves a meeting or (2) when it is currently not guaranteed to eventually convene a committee (that is, in each of its incident committees, at least one member is not looking). Note that the algorithm does not guarantee fairness because of this latter case.

In order to guarantee Maximal Concurrency, we have to authorize committees to meet when all members are looking and if there is no looking token holder in the neighborhood. In this case, among the looking processes we give priority to the looking process with the maximum identifier.

3. Once all processes of a hyperedge are looking and agree on that hyperedge, they are all ready to start their discussion. To this end, a process changes its status from looking to waiting<fnref n="6" /> to show that it is waiting for the committee to convene (action $Step_{31}$). A meeting of the committee convenes when all its members change their status to waiting. Then, each process executes its essential discussion and then switches its status to done (action $Step_{32}$).

4. Finally, a process is allowed to leave the committee meeting when all processes of that committee have fulfilled their essential discussion, i.e., they are all in the done status. In this case, the meeting takes place until a process $p$ unilaterally decides to leave it (that is, until $RequestOut(p)$ is true) after a finite period of voluntary discussion. To leave the committee meeting, it switches its status to idle again, resets its hyperedge pointer, and releases the token if it owns it (action $Step_4$). Then, the committee meeting is terminated, and every other member $q$ switches to idle since it satisfies $RequestOut(q)$.

The rest of actions of the algorithm deal with token circulation and snap-stabilization. In particular, action $Token_1$ deals with setting variable $T_p$ to true, so that neighboring processes realize that $p$ owns the token. If $p$ owns the token and has no desire to take part in a committee meeting, or, there does not exist an available committee for $p$ to participate, then it releases the

<footnote n="6">⁶Note that both looking and waiting status form the waiting state of the original problem specification [2].</footnote>
token (action *Token*₂). Finally, actions *Stab*₁ and *Stab*₂ correct the state of a process, if faults perturb the state of the process to a state where predicate *Correct* does not hold. Predicate *Correct* holds at states where (1) the process is *idle* and it has no interest in participating in a committee meeting, (2) it is *waiting* and interested in a committee whose processes are gathering to convene a meeting, and (3) it has fulfilled its essential discussion and other processes in the corresponding committee are either in {*waiting*, *done*} status, or, the meeting is terminated, that is some processes have left the meeting and the others are *done* in the meeting.

*Example.* In this paragraph, we illustrate the need of the token to ensure progress. Figure 3 provides an example of computation that starts from a configuration where each professor state is correct. In the figure, each circle represents a professor and arrows inside the circle represent the *P*-pointers (if a circle contains no arrow, this means that the corresponding professor *p* satisfies *P*<sub>*p*</sub>=⊥). Numbers represent identifiers. The status of the professors is given below the circles. The token holder is represented by a bold circle. A boxed “T” near a circle means that the corresponding professor *p* satisfies *T*<sub>*p*</sub>=*true*.

In this example, professors in the committee {5, 6} desire to participate in a meeting. So, at least one of them should eventually does, according to the progress property. Because they have low identifiers, we can prevent them from convening a meeting until at least one of them get the token.

In 3(a), two meetings are almost done: {9, 10} and {1, 2, 3}, that is, all involved professors are doing their voluntary discussion. Notice that Professor 1 holds the token and *T*₁ = *true*. Professor 4 is currently not interesting in convening any meeting. All other professors are looking for convening a meeting and point to their highest priority all-looking committee. Now, Professors 7 and 8 are agreeing to convene a meeting: they are both enabled to switch to the waiting status.

In Step 3(a)→3(b), all members of meetings {1, 2, 3} and {9, 10} simultaneously leave the meeting by executing *Step*₄. Moreover, Professor 8 switches to the waiting status by executing *Step*₃₁. Note in particular that Professor 1 releases the token and resets *T*₁ to false. Professor 2 is now the token holder. Since his status is *idle*, he is enabled to release the token. Professor 2 will release the token without setting *T*₂ to *true* in the meantime.

In Step 3(b)→3(c), Professor 7 switches to status *waiting*. So, the meeting {7, 8} convenes. In the meantime, both Professors 9 and 10 start again to look for a meeting by executing *Step*₁. Moreover, Professor 2 releases the token. So, in configuration 3(c), Professor 3 is the token holder and Professor 6 should look for another meeting. For Professor 6, the committee of highest priority is {6, 9}. Similarly, Professor 9 (resp. Professor 10) considers {9, 10} as the one of highest priority.

In Step 3(c)→3(d), Professor 3 releases the token, Professors 7 and 8 perform their essential discussion (*Step*₃₂), Professors 10 (*Step*₂₁) and 9 (*Step*₂₂) agree to convene a meeting, and Professor 6 points to Committee {6, 9}. Note that Professor 4 is the token holder in configuration 3(d), but he has no interest in convening any meeting so his action *Token*₂ is enabled.

In Step 3(d)→3(e), Professor 4 releases the token, Professors 8 and 9 leave their meeting (*Step*₄), and Professor 10 switches to the *waiting* status by executing *Step*₃₁. In configuration 3(e), Professor 6 is the token holder, consequently he has highest priority. However, meeting {8, 9} is ready to convene, so Professor 9, in particular, will not change his pointer *P*₉.

In Step 3(e)→3(f), Professor 9 switches to status *waiting*, so the meeting of Committee {9, 10} is
<figure><img src="image_4.png" /><figcaption>Figure 3: Example</figcaption></figure>

convenes. In the meantime, Professors 8 and 9 start again to look for a meeting by executing *Step*₁. Finally, Professor 6 executes *T*₆ ← *true* (*Token*₁) to inform all its neighbors that he is the token holder. In configuration 3(f), Professors 5, 6, 7, and 8 are all looking for a meeting like in configuration 3(a), but this time Committee {6, 7} has the highest priority.

In Step 3(f) → 3(g), Professors 9 and 10 perform their essential discussion (*Step*₃₂) and Professors 6 (*Step*₂₁) and 7 (*Step*₂₂) agree to convene a meeting (Professor 8 also executes *Step*₂₂).

In Step 3(g) → 3(h), the meeting of Committee {9, 10} ends because Professors 9 and 10 simultaneously leave it, and a meeting of Committee {6, 7} convenes because Processors 6 and 7 both execute *Step*₃₁.

In Step 3(h) → 3(i), Professors 6 and 7 perform their essential discussion (*Step*₃₂). Moreover, Professors 10 and 9 start again to look for a meeting by executing *Step*₁.
4.2. Correctness of Algorithm CC1 ◦ TC

We recall that in the following proofs, we assume that computations of CC1 ◦ TC start from
arbitrary configurations. First, we define the terminology used in the proofs.

We map the state of a professor defined in Section 2.3 to the status of a process defined in
Algorithm 1 as follows. We say that a process *p* is *idle* if and only if *S*<sub>*p*</sub> = *idle*. A process *p* is
*waiting* if and only if *S*<sub>*p*</sub> ∈ {*looking, waiting*}. If *p* is *waiting* and *P*<sub>*p*</sub> = *ε*, where *ε* ∈ *E*<sub>*p*</sub>, then we
say that *p* *attends* the committee *ε*. A committee *ε* *meets*, if and only if for every process *p* ∈ *ε*,
we have *P*<sub>*p*</sub> = *ε* and *S*<sub>*p*</sub> ∈ {*waiting, done*}. When a committee *ε* *meets*, every process *p* ∈ *ε* is
*participating in* *ε*. Let γ<sub>0</sub>γ<sub>1</sub>... be a computation. We say that a committee meeting *ε* *convenes* in
γ<sub>i</sub>, where *i* > 0, if and only if *ε* does not meet in γ<sub>i-1</sub>, but it meets in γ<sub>i</sub>. For all *i* > 0, we say that
a committee meeting *ε* *terminates* in γ<sub>i</sub>, if and only if *ε* meets in γ<sub>i-1</sub>, but does not meets in γ<sub>i</sub>. If
a committee meeting *ε* *terminates* in γ<sub>i</sub>, where *i* > 0, then there exists a process *p*, such that (i)
(*P*<sub>*p*</sub> = *ε* ∧ *S*<sub>*p*</sub> = **done**) in γ<sub>i-1</sub>, and (ii) (*P*<sub>*p*</sub> = ⊥ ∧ *S*<sub>*p*</sub> = **idle**) in γ<sub>i</sub>. In this case, we say that *p*
*leaves* the committee meeting *ε* on transition γ<sub>i-1</sub> ↦→ γ<sub>i</sub>.

For every process *p*, we assume the existence of two predicates: *RequestIn*(*p*) and *RequestOut*(*p*).
The predicate *RequestIn*(*p*) holds when *p* (or an application at *p*) requests the participation of *p* in
a committee meeting. When a committee involving *p* meets or *p* is still involved in a meeting that is
terminated (in this latter case the predicate *LeaveMeeting*(*p*) holds), the predicate *RequestOut*(*p*)
eventually holds, meaning that *p* wants to voluntarily stop discussing. Once *RequestOut*(*p*) is
*true*, it remains *true* until *p* becomes idle. Note also that, when necessary, we materialize the
assumption on infinite meetings by assuming that, for all processes *p*:

* If *p* satisfies *S*<sub>*p*</sub> = **done** but **Meeting**(*p*) holds, then the predicate *RequestOut*(*p*) eventu-
  ally holds. Indeed, in this case, the meeting involving *p* is already terminated.

* However, if *p* is involved in a meeting, then the meeting never ends. Consequently, *Meeting*(*p*)
  ⇒ **RequestOut**(*p*) forever.

**Remark 2** *Guards of actions Step<sub>1</sub>, Step<sub>21</sub>, Step<sub>22</sub>, Step<sub>31</sub>, Step<sub>32</sub>, and Step<sub>4</sub> are mutually exclusive at each professor.*

**Lemma 1** Every computation of CC1 ◦ TC satisfies Exclusion.

*Proof.* Let $\epsilon$ and $\epsilon'$ be two conflicting committees, i.e., $\epsilon \cap \epsilon' \neq \emptyset$. Let $p$ be a process in $\epsilon \cap \epsilon'$. By definition, if $\epsilon$ (respectively, $\epsilon'$) meets, then $P_p = \epsilon$ (respectively, $P_p = \epsilon'$). Hence, $\epsilon$ and $\epsilon'$ cannot meet simultaneously. $\square$

**Lemma 2** When committee meeting $\epsilon$ convenes, every process $p \in \epsilon$ satisfies ($P_p = \epsilon \land S_p = $ **waiting**).

*Proof.* Consider a committee *ε* that convenes in *γ*ᵢ. By definition, the committee *ε* meets in *γ*ᵢ, but not in *γ*ᵢ₋₁. Moreover, for every *p* ∈ *ε*, we have (*P*ₚ = *ε* ∧ *S*ₚ ∈ {*waiting, done*}) in *γ*ᵢ. Also, there must exist a process *q* in committee *ε*, such that *S*ₚ ∈ {*idle, looking*} or *P*ₚ ≠ *ε* in *γ*ᵢ₋₁. We now prove the lemma by contradiction. Assume that there exists process *r* ∈ *ε*, such that
$S_r$ = done in $\gamma_i$. Then, either (1) $S_r$ = done in $\gamma_{i-1}$, or (2) $r$ executes action $Step_{32}$ on transition $\gamma_{i-1} \mapsto \gamma_i$. In case (1), during $\gamma_{i-1} \to \gamma_i$, process $q$ cannot set $(S_q, P_q)$ to:

* (waiting, $\epsilon$), because of the state of $r$; or

* (done, $\epsilon$), because otherwise $S_q$ = waiting and $P_q = \epsilon$ in $\gamma_{i-1}$.

In case (2), $\epsilon$ already meets in $\gamma_{i-1}$ (see Predicate Meeting($r$)), which is a contradiction. Thus, for every $p \in \epsilon$, we have ($P_p = \epsilon \land S_p$ = waiting) in $\gamma_i$ and, hence, the lemma holds. $\square$

**Corollary 2** Every computation of CC1 ◦ TC satisfies Synchronization.

**Lemma 3** For every process $p$, if Correct($p$) holds, then Correct($p$) continues to hold forever.

*Proof.* We prove this lemma by showing that if a process $p$ satisfies Correct($p$) in some configuration $\gamma$, then $p$ satisfies Correct($p$) in configuration $\gamma'$ where $\gamma \mapsto \gamma'$ is a transition.

According to the definition of Correct, we distinguish the following four cases in $\gamma$:

(a) $S_p = \mathbf{idle} \land P_p = \perp$. Obviously, if $p$ does not modify $S_p$ or $P_p$ in the next step, then Correct($p$) holds in the next configuration step as well. Now, the only action modifying $S_p$ and/or $P_p$ that may be enabled in $p$ is Step$_1$. If $p$ executes action Step$_1$, then $P_p := \mathbf{looking}$ and Correct($p$) still holds in $\gamma'$.

(b) $S_p = \mathbf{looking}$. Obviously, if $p$ does not modify $S_p$ in the next step, then Correct($p$) holds in the next configuration step as well. Now, suppose that $p$ modifies $S_p$ on transition $\gamma \mapsto \gamma'$. In this case, $p$ has to execute Step$_{31}$. Consequently, in $\gamma$ we have $P_p = \epsilon$, where $\epsilon \in \mathcal{E}_p$, and, $\forall q \in \epsilon : (P_q = \epsilon \land S_q \in \{\mathbf{looking}, \mathbf{waiting}\})$. Now, in this case, every process $q \in \epsilon$ satisfies Ready($q$) and $\neg$Meeting($q$). So, no process $q \in \epsilon$ can modify $P_q$ on transition $\gamma \mapsto \gamma'$. Moreover, every process $q \in \epsilon$ can only execute Step$_{31}$ to modify $S_q$ on transition $\gamma \mapsto \gamma'$. Thus, in configuration $\gamma'$, the predicate $\forall q \in \epsilon : (P_q = \epsilon \land S_q \in \{\mathbf{looking}, \mathbf{waiting}\})$ still holds and, as a consequence, Correct($p$) holds as well.

(c) $S_p = \mathbf{waiting} \land P_p = \epsilon$, where $\epsilon \in \mathcal{E}_p$. In this case, Correct($p$) implies the following possible subcases in $\gamma$:

(1) $\forall q \in \epsilon : (P_q = \epsilon \land S_q \in \{\mathbf{looking}, \mathbf{waiting}\}) \land \exists r \in \epsilon : S_r = \mathbf{looking}$. In this subcase, every process $q \in \epsilon$ satisfies Ready($q$) and $\neg$Meeting($q$). So, no process $q \in \epsilon$ can modify $P_q$ on transition $\gamma \mapsto \gamma'$. Moreover, every process $q \in \epsilon$ can only execute Step$_{31}$ to modify $S_q$ on transition $\gamma \mapsto \gamma'$. Thus, the predicate ($\forall q \in \epsilon : (P_q = \epsilon \land S_q \in \{\mathbf{looking}, \mathbf{waiting}\})$) holds in $\gamma'$ and, as a consequence, Correct($p$) holds in $\gamma'$ as well.

(2) $\forall q \in \epsilon : (P_q = \epsilon \land S_q \in \{\mathbf{waiting}, \mathbf{done}\})$. In this subcase, because of the state of $p$, every process $q \in \epsilon$ satisfies Meeting($q$) and $\neg$LeaveMeeting($q$). So, no process $q \in \epsilon$ can modify $P_q$ on transition $\gamma \mapsto \gamma'$. Moreover, every process $q \in \epsilon$ can only execute Step$_{32}$ to modify $S_q$ on transition $\gamma \mapsto \gamma'$. Thus, the predicate ($\forall q \in \epsilon : (P_q = \epsilon \land S_q \in \{\mathbf{waiting}, \mathbf{done}\}$) still holds in $\gamma'$ and, as a consequence, Correct($p$) holds as well.
561
562

(d) $S_p = \mathbf{done} \wedge P_p = \epsilon$, where $\epsilon \in \mathcal{E}_p$. In this case, Correct($p$) implies the following possible subcases in $\gamma$:

563
564

(1) $\forall q \in \epsilon : (P_q = \epsilon \wedge S_q \in \{\mathbf{waiting}, \mathbf{done}\}) \wedge \exists r \in \epsilon : S_r = \mathbf{waiting})$. This subcase has been already considered in case (c).(2), so Correct($p$) holds in $\gamma'$.

565
566
567
568
569
570

(2) $\forall q \in \epsilon : (P_q = \epsilon \Rightarrow S_q = \mathbf{done})$. In this case, no process $q$ that satisfies $P_q \neq \epsilon$ can execute $P_q := \epsilon$, because $\epsilon \notin \text{FreeEdges}_q$. Also, a process $q$ that satisfies $P_q = \epsilon$ in $\gamma$ (e.g., $p$) can only modify $P_q$ and/or $S_q$ by executing action $\text{Step}_4$ on transition $\gamma \mapsto \gamma'$. In this case, $S_q := \text{idle}$ and $P_q := \perp$. As a consequence, in $\gamma'$ either $S_p := \text{idle}$ and $P_p := \perp$, or $P_p = \epsilon \wedge \forall q \in \epsilon : (P_q = \epsilon \Rightarrow S_q = \mathbf{done})$. Thus, Correct($p$) holds in $\gamma'$ as well.

571
572

Since in all possible cases, Correct($p$) is preserved by the algorithm's actions, the lemma holds. $\square$

573
574
575

It is straightforward to see that a process that satisfies $\neg \text{Correct}$ is enabled for either action $\text{Stab}_1$ or action $\text{Stab}_2$ (the priority actions). Moreover, since the daemon is weakly fair, Lemma 3 implies the following corollary:

576

**Corollary 3** After at most one round, every process $p$ satisfies Correct($p$) forever.

577
578

**Lemma 4** After committee $\epsilon$ convenes, the predicate $(\forall p \in \epsilon : (P_p = \epsilon \wedge S_p = \mathbf{done})$) eventually holds.

579
580
581
582
583
584
585
586

*Proof.* Consider a configuration $\gamma$ where every process $p \in \epsilon$ satisfies $(P_p = \epsilon \wedge S_p \in \{\mathbf{waiting}, \mathbf{done}\})$, and, there exists a process $q \in \epsilon$, such that $(P_q = \epsilon \wedge S_q = \mathbf{waiting})$. Then, every process $p \in \epsilon$ satisfies Correct($p$) in $\gamma$ and, by Lemma 3, (*) actions $\text{Stab}_1$ and $\text{Stab}_2$ are disabled forever at every $p \in \epsilon$ from $\gamma$. Now, in configuration $\gamma$, a process $p \in \epsilon$, where $S_p = \mathbf{done}$, cannot modify $P_p$ or $S_p$. Moreover, in $\gamma$, a process $q \in \epsilon$, where $(P_q = \epsilon \wedge S_q = \mathbf{waiting})$ cannot modify $P_q$ and can only set $S_q$ to done by executing action $\text{Step}_{32}$, which is continuously enabled. Since we assume a weakly fair daemon, $q$ eventually executes action $\text{Step}_{32}$ by (*) and Remark 2. Hence, the lemma holds. $\square$

587
588

**Corollary 4** Every computation of $\mathcal{CC}1 \circ \mathcal{T}\mathcal{C}$ satisfies the *Essential Discussion*.

*Proof.* The proof is trivial by Lemmas 2, 4, and action $\text{Step}_{32}$. $\square$

589
590
591
592
593
594
595

**Lemma 5** Every computation of $\mathcal{CC}1 \circ \mathcal{T}\mathcal{C}$ satisfies the *Voluntary Discussion*.

*Proof.* Let a committee $\epsilon$ convene in configuration $\gamma_i$. By Lemmas 2, every process $p \in \epsilon$ satisfies Correct($p$) in $\gamma_i$ and, by Lemma 3, (*) actions $\text{Stab}_1$ and $\text{Stab}_2$ are disabled forever at every $p \in \epsilon$. By Corollary 4, every process of committee $\epsilon$ eventually executes its essential discussion. Thus, following Lemmas 2 and 4, the system reaches a configuration $\gamma_j$ ($j > i$), where every process $p \in \epsilon$ satisfies $(P_p = \epsilon \wedge S_p = \mathbf{done})$. In such a configuration, a process $p$ in $\epsilon$ can update its $P_p$ and/or $S_p$ only if it satisfies the predicate $\text{RequestOut}(p)$. Now, by hypothesis it will happen, and in
this case, $Step_4$ will be the priority enabled action at $p$ (by (*) meaning that it voluntarily decides to leave the meeting. Moreover, by definition, since a process eventually satisfies *RequestOut* continuously and the daemon is weakly fair, the meeting eventually terminates due to execution of action $Step_4$ by some process. Therefore, the lemma holds. □

Observe that in the algorithm, a process that does not satisfy *Correct* can only execute either action *Stab*₁ or action *Stab*₂. Thus:

**Remark 3** If a process $p$ is waiting and satisfies $\neg Correct(p)$, it remains waiting (at least) until it satisfies *Correct*($p$).

**Lemma 6** Every computation of $CC1 \circ TC$ satisfies *Progress*.

*Proof.* We prove this lemma by contradiction. Suppose there exists a computation $c$ of $CC1 \circ TC$ that does not satisfy *Progress*.

Let $\mathcal{E}_{\gamma}^{\infty}$ be the subset of $\mathcal{E}$ such that $\forall \epsilon \in \mathcal{E}, \epsilon \in \mathcal{E}_{\gamma}^{\infty}$ if and only if for all processes $p \in \epsilon$, $p$ is waiting in $\gamma$, but will never more participate in a meeting during $c$. By definition, $\forall \gamma_i, \gamma_j$ such that $\gamma_j$ occurs after $\gamma_i$ in $c$, we have $\mathcal{E}_{\gamma_i}^{\infty} \subseteq \mathcal{E}_{\gamma_j}^{\infty}$. Moreover, the number of processes being finite, there exist configurations $\gamma_i$ in $c$ such that $\mathcal{E}_{\gamma_i}^{\infty} = \mathcal{E}_{\gamma_j}^{\infty}$, for every configuration $\gamma_j$ that occurs after $\gamma_i$ in $c$.

Let now consider such a configuration, say $\gamma^1$, and let $V^{\infty}$ be the subset of all processes that are incident to a hyperedge in $\mathcal{E}_{\gamma^1}^{\infty}$. We distinguish the following two cases in $\gamma^1$:

(a) There is a process $p \in V^{\infty}$ that eventually satisfies *Ready*($p$). This case implies that $P_p = \epsilon$, where $\epsilon \in \mathcal{E}_p$. By definition of *Ready*, every process $q \in \epsilon$ satisfies ($P_q = \epsilon \land S_q \in \{\text{looking, waiting}\}$), which in turns, implies *Correct*($q$). So, by Lemma 3, (*) actions *Stab*₁ and *Stab*₂ are disabled forever at every $q \in \epsilon$ from $\gamma^1$.

Now, observe that in configuration $\gamma^1$ a process $p$ in $\epsilon$, where $S_p = \text{waiting}$, cannot modify $P_p$ or $S_p$. Also, every process $q \in \epsilon$ such that ($P_q = \epsilon \land S_q = \text{looking}$) cannot modify $P_q$ and can only modify $S_q$ by action $Step_{31}$, which is its priority enabled action in $\gamma^1$ (by (*) and Remark 2). Hence, as the daemon is weakly fair, the committee meeting $\epsilon$ eventually convenes, which is a contradiction.

(b) No process $p$ of $V^{\infty}$ eventually satisfies *Ready*($p$). By Remark 3,

(1) Every $p$ of $V^{\infty}$ remains waiting forever.

(Indeed, the only way to lose the waiting status is to switch to the meeting status.)

Observe that by definition, we have

(2) $\text{FreeEdges}_p \neq \emptyset$.

Again, following Remark 3,

(3) $\text{FreeEdges}_p$ is fixed.

By Corollary 3, there exists a configuration $\gamma^2$ in $c$ after $\gamma^1$ where:
(4) All processes satisfy Correct forever.

By Property 1, eventually there exists a unique token in the network. If a process in $V^∞$ eventually gets the token, then it never releases it by (1), (2), and (3).

Assume now, by the contradiction, that no process in $V^∞$ eventually gets this token (from $\gamma^2$). Assume first that a token holder participates in a meeting. Then it eventually releases the token by Lemma 5. In contrast, if it never more participates in any meeting, then it has status idle forever, so its action $Token_2$ is continuously enabled. As the daemon being weakly fair and $Token_2$ is its priority enabled action (by (4)), the process eventually releases the token. Hence, there exists a configuration $\gamma^3$ in $c$ after $\gamma^2$ where:

(5) There exists a unique process $\ell \in V^∞$ that satisfies $Token(\ell)$ forever.

(6) Every process $p \in V \setminus \{\ell\}$ satisfies $\neg Token(p)$ forever.

Every process $p$ having status idle forever and that never gets the token has action $Token_1$ that is continuously enabled (its priority enabled action by (4))) if $T_p = true$. The daemon being weakly fair, eventually satisfies $T_p = false$ forever. Moreover, by definition every other process $q$ in $V \setminus V^∞$ convenes and terminates meetings infinitely often, and each time $q$ executes $Step_4$, $T_q$ is reset to $false$. Hence, from (5), we can deduce that there exists a configuration $\gamma^4$ in $c$ after $\gamma^3$ where:

(7) Every process $q$ in $V \setminus V^∞$ satisfies $\neg T_q$ forever.

By (4) and the fact that no process in $V^∞$ satisfies Ready, we have (in particular, from $\gamma^4$):

(8) all processes in $V^∞$ are in looking status.

Consider then a process $q$ in $V^∞$ such that $T_q \neq Token(q)$ (from $\gamma^4$). Then, $q$ is continuously enabled, by (5) and (6). So, it is eventually selected by the weakly fair daemon. Now, when selected, its actions $Stab_1$ and $Stab_2$ are disabled by (4). Moreover, $Step_{31}$, $Step_{32}$, and $Step_4$ are also disabled at $q$, otherwise $q$ will lose its looking status, a contradiction to (8). So, $q$ necessarily executes $Token_1$ (n.b., $Token_2$ is disabled at $q$ by (2), (3), and (8)) and there exists a configuration $\gamma^5$ in $c$ after $\gamma^4$ where:

(9) $\ell$ satisfies $T_\ell$ forever.

(10) Every process $q \in V \setminus \{\ell\}$ satisfies $\neg T_q$ forever.

In particular, (8), (9), and (10) hold for all processes incident to a hyperedge of $FreeEdges_\ell$. So, $LocalMax(\ell) = \ell$ and $LocalMax(r) = \ell$, where $r$ is any process incident to a hyperedge of $FreeEdges_\ell$. So, if $P_\ell \notin FreeEdges_\ell$, then action $Step_{21}$ is its priority enabled action (by (4) and Remark 2). $\ell$ remains enabled until it executes it. So, $\ell$ eventually does, because the daemon is weakly fair. Hence, eventually $P_\ell = \epsilon$ forever, where $\epsilon \in FreeEdges_\ell$. Then, every process $r \in \epsilon$, such that $P_r = \epsilon$ is disabled forever, because $\ell$ never satisfies Ready($\ell$), by hypothesis. Finally, action $Step_{22}$ is continuously enabled action at every process $s \in \epsilon$
such that $P_s \neq \emptyset$, moreover it is their priority enabled action by (4) and Remark 2. Again, because the daemon is weakly fair, every process $s$ eventually executes it. Hence, eventually $\ell$ satisfies Ready($\ell$), which is a contradiction.

665

666

667

☐

668

**Lemma 7** Every computation of CC1 ◦ TC satisfies Maximal Concurrency.

669

*Proof.* Assume there is a set $P_1$ of processes that are all in infinite-time meetings. Let $P_2$ be a set of processes waiting. Let $\Pi$ be the set of hyperedges whose all incident processes are in $P_2$. We now prove the lemma by contradiction. Suppose that $\Pi \neq \emptyset$ and no meeting between processes incident to a hyperedge in $\Pi$ eventually convenes. We distinguish the following two cases:

670

671

672

673

(a) There exists a process $p \in P_2$ that eventually satisfies Ready($p$). In this case, using the same reasoning as in case (a) in the proof of Lemma 6, we obtain a contradiction.

674

675

(b) No process in $P_2$ eventually satisfies Ready($p$). Let $p$ be a process in $P_2$. In this case, following Remark 3, $p$ must remain waiting forever (the only way to leave the waiting status is to switch to the meeting status). Observe that by definition, $\text{FreeEdges}_p \neq \emptyset$. Using the same reasoning as in case (b) of the proof of Lemma 6, there exists a configuration $\gamma$ in which:

676

677

678

679

680

(1) There exists a process $\ell$ that satisfies $T_\ell$ forever.

681

(2) Every process $q \in V \setminus \{\ell\}$ satisfies $\neg T_q$ forever.

682

(3) Every process in $V$ satisfies Correct forever.

683

Now, if $\ell \in P_2$, then using the same reasoning as in case (b) of the proof of Lemma 6, we reach a contradiction. If $\ell \notin P_2$, then, let $p_{max}$ be the process of $P_2$ having the greatest identifier. Then using the reasoning similar to the case (b) in the proof of Lemma 6 ($p_{max}$ has the same role as $\ell$ in the proof of Lemma 6), we reach a contradiction.

684

685

686

687

☐

688

**Theorem 2** The composition CC1 ◦ TC is a snap-stabilizing algorithm that solves the 2-phase committee coordination problem and satisfies Maximal Concurrency.

689

690

*Proof.* Given Lemmas 1-7, the proof of the theorem trivially follows.

☐

691
# 5. Snap-Stabilizing 2-Phase Committee Coordination with Fairness

We now consider the 2-phase committee coordination problem in systems where processes are waiting for meetings infinitely often. In such a setting, an idle process always eventually becomes waiting. Hence, for simplicity (and without loss of generality), we assume that processes are always requesting when they are not in a meeting. As a consequence, the predicate $RequestIn(p)$ and the state idle are implicit in the actions of the next algorithm. In Subsection 5.1, we present a snap-stabilizing algorithm that guarantees the properties of 2-phase committee coordination and **Professor Fairness**. The proof of correctness of the algorithm is presented in Subsection 5.2. Then, in Subsection 5.3, we analyze the complexity of our algorithm. Finally, we discuss **Committee Fairness** in Subsection 5.4.

## 5.1. *Algorithm*

Our algorithm is the composite algorithm $CC2 \circ TC$, where (1) $CC2$ is a Snap-stabilizing algorithm that ensures Exclusion, Synchronization, and 2-Phase Discussion, and (2) $TC$ is the same self-stabilizing module that manages a circulating token as in Section 4. It ensures Fairness, and consequently Progress.

Algorithm $CC2$ is identical for all processes in the distributed system. Its code is given in Algorithm 2. Similar to Algorithm $CC1$, each process $p$ maintains $S_p$, $P_p$, and $T_p$ with the same meaning. Also, the token defines priorities to convene committees. However, to guarantee fairness, in this algorithm, a token is released only when its holder leaves a meeting.

After receiving a token, a looking process $p$ selects a smallest (in terms of members) incident committee $\epsilon$ (this constraint is used only to slightly enhance the concurrency) using its edge pointer $P_p$ (*Step*$_{11}$). Note that unlike the previous algorithm, the members of the chosen committee are not necessarily all looking. Then, process $p$ sticks with committee $\epsilon$ until $\epsilon$ convenes. By assumption, other members of committee $\epsilon$ are eventually looking and, hence, $\epsilon$ is selected by action *Step*$_{12}$.

In order to obtain the best concurrency as possible (recall that maximal concurrency is impossible in this case), a process that is not in a committee $\epsilon$ must not wait for a process involved in $\epsilon$. To that goal, we introduce the Boolean variable $L$, which shows whether or not a process is *locked*. A locked process is one that is incident to a hyperedge that contains a process that (1) owns the token, (2) has set its pointer to that hyperedge, and (3) is looking to start a committee meeting. The locks are maintained using action *Lock*. Hence, processes that are not in $\epsilon$ try to convene committees that do not involve *locked* processes (*Step*$_{13}$ and *Step*$_{14}$). As in Algorithm $CC1$, we use the process identifiers to define priorities among the looking processes not in $\epsilon$. The rest of actions of the algorithm are similar to those of Algorithm $CC1$.

Figure 4 illustrates the need of the Boolean $L$. In this configuration, Professor 8 chooses the committee {1, 2, 5, 8} because Professor 1 has the token. Moreover, this committee cannot meet before the meeting of committee {3, 4, 5} terminates. Now, to ensure fairness, Professors 1, 2, and 8 should not change their $P$-pointers so that eventually a meeting of {1, 2, 5, 8} convenes. Furthermore, to obtain a better concurrency, Committee {6, 7, 9} should be allowed to meet. Now, for Professor 9, Committee {8, 9} has higher priority than Committee {6, 7, 9}. By definition, all members of Committee {1, 2, 5, 8} are locked. So, thank to the Boolean $L_8$, Professor 9 realizes
<caption>**Algorithm 2** Pseudo-code of CC2 for process *p*.</caption>

**Inputs:**
*RequestOut(p)* : Predicate: input from the system indicating desire for leaving a committee
*Token(p)* : Predicate: input from *TC* indicating process *p* owns the token
*ReleaseTokenp* : Statement: output to *TC* indicating process *p* releases the token

**Constant:**
*E*<sub>*p*</sub> : Set of hyperedges incident to *p*

**Variables:**
*T*<sub>*p*</sub>, *L*<sub>*p*</sub> : Booleans
*P*<sub>*p*</sub> ∈ *E*<sub>*p*</sub> ∪ {⊥} : Edge pointer
*S*<sub>*p*</sub> ∈ {looking, waiting, done} : Status

**Macros:**
*FreeEdges*<sub>*p*</sub> = {ε ∈ *E*<sub>*p*</sub> | ∀q ∈ ε : (*S*<sub>*q*</sub> = looking ∧ ¬*L*<sub>*q*</sub> ∧ ¬*T*<sub>*q*</sub>)}
*FreeNodes*<sub>*p*</sub> = {q | ∃ε ∈ *FreeEdges*<sub>*p*</sub> : q ∈ ε}
*TPointingEdges*<sub>*p*</sub> = {ε ∈ *E*<sub>*p*</sub> | ∃q ∈ ε : (*P*<sub>*q*</sub> = ε ∧ *T*<sub>*q*</sub> ∧ *S*<sub>*q*</sub> = looking)}
*TPointingNodes*<sub>*p*</sub> = {q | ∃ε ∈ *TPointingEdges*<sub>*p*</sub> : q ∈ ε}
*MinSize*<sub>*p*</sub> = min<sub>ε∈*E*<sub>*p*</sub></sub> |ε|
*MinEdges*<sub>*p*</sub> = {ε ∈ *E*<sub>*p*</sub> | |ε| = *MinSize*<sub>*p*</sub>}

**Predicates:**
*Locked(p)* ≡ *TPointingEdges*<sub>*p*</sub> ≠ ∅
*Ready(p)* ≡ ∃ε ∈ *E*<sub>*p*</sub> : ∀q ∈ ε : (*P*<sub>*q*</sub> = ε ∧ *S*<sub>*q*</sub> ∈ {looking, waiting})
*Meeting(p)* ≡ ∃ε ∈ *E*<sub>*p*</sub> : ∀q ∈ ε : (*P*<sub>*q*</sub> = ε ∧ *S*<sub>*q*</sub> ∈ {waiting, done})
*LeaveMeeting(p)* ≡ ∃ε ∈ *E*<sub>*p*</sub> : (*P*<sub>*p*</sub> = ε ∧ *S*<sub>*p*</sub> = done ∧ (∀q ∈ ε : (*P*<sub>*q*</sub> = ε ⇒ *S*<sub>*q*</sub> ≠ waiting)))
*LocalMax(p)* ≡ *p* = max(*FreeNodes*<sub>*p*</sub>)
*MaxToFreeEdge(p)* ≡ ¬*Token(p)* ∧ ¬*Locked(p)* ∧ *FreeEdges*<sub>*p*</sub> ≠ ∅ ∧ *LocalMax(p)* ∧ ¬*Ready(p)* ∧ *P*<sub>*p*</sub> ∉ *FreeEdges*<sub>*p*</sub>
*JoinLocalMax(p)* ≡ ¬*Token(p)* ∧ ¬*Locked(p)* ∧ *FreeEdges*<sub>*p*</sub> ≠ ∅ ∧ ¬*LocalMax(p)* ∧ ¬*Ready(p)* ∧ ∃ε ∈ *FreeEdges*<sub>*p*</sub> : (*P*<sub>max(*FreeNodes*<sub>*p*</sub>)</sub> = ε ∧ *P*<sub>*p*</sub> ≠ ε)
*TokenHolderToEdge(p)* ≡ *Token(p)* ∧ (*S*<sub>*p*</sub> = looking) ∧ ¬*Ready(p)* ∧ (*P*<sub>*p*</sub> ∉ *MinEdges*<sub>*p*</sub>)
*JoinTokenHolder(p)* ≡ ¬*Token(p)* ∧ (*S*<sub>*p*</sub> = looking) ∧ ¬*Ready(p)* ∧ *Locked(p)* ∧ (*P*<sub>*p*</sub> ∉ *TPointingEdges*<sub>*p*</sub>)
*Correct(p)* ≡ [(*S*<sub>*p*</sub> = waiting) ⇒ *Ready(p)* ∨ *Meeting(p)*] ∧ [(*S*<sub>*p*</sub> = done) ⇒ *Meeting(p)* ∨ *LeaveMeeting(p)*]

**Actions:**
*Lock* :: *Locked(p)* ≠ *L*<sub>*p*</sub> &rarr; *L*<sub>*p*</sub> := *Locked(p)*;
*Step*<sub>11</sub> :: *TokenHolderToEdge(p)* &rarr; *P*<sub>*p*</sub> := ε such that ε ∈ *MinEdges*<sub>*p*</sub>;
*Step*<sub>12</sub> :: *JoinTokenHolder(p)* &rarr; *P*<sub>*p*</sub> := ε such that ε ∈ *E*<sub>*p*</sub>, where *P*<sub>max(*TPointingNodes*<sub>*p*</sub>)</sub> = ε;
*Step*<sub>13</sub> :: *MaxToFreeEdge(p)* &rarr; *P*<sub>*p*</sub> := ε such that ε ∈ *FreeEdges*<sub>*p*</sub>;
*Step*<sub>14</sub> :: *JoinLocalMax(p)* &rarr; *P*<sub>*p*</sub> := ε such that ε ∈ *E*<sub>*p*</sub>, where *P*<sub>max(*FreeNodes*<sub>*p*</sub>)</sub> = ε;
*Token* :: *Token(p)* ≠ *T*<sub>*p*</sub> &rarr; *T*<sub>*p*</sub> := *Token(p)*;
*Step*<sub>2</sub> :: *Ready(p)* ∧ (*S*<sub>*p*</sub> = looking) &rarr; *S*<sub>*p*</sub> := waiting;
*Step*<sub>3</sub> :: *Meeting(p)* ∧ (*S*<sub>*p*</sub> = waiting) &rarr; (Essential Discussion); *S*<sub>*p*</sub> := done;
*Step*<sub>4</sub> :: *LeaveMeeting(p)* ∧ *RequestOut(p)* &rarr; *S*<sub>*p*</sub> := looking; *P*<sub>*p*</sub> := ⊥; *T*<sub>*p*</sub> := false;
if *Token(p)* then *ReleaseTokenp* fi;
*Stab* :: ¬*Correct(p)* &rarr; *S*<sub>*p*</sub> := looking; *P*<sub>*p*</sub> := ⊥;
732

that he should not give priority to {8, 9}. Consequently, he will select {6, 7, 9} by action *Step*<sub>13</sub>, improving concurrency.

733

<figure><img src="image_5.png" /><figcaption>Figure 4: Example of locked professors.</figcaption></figure>

734

## 5.2. Correctness of $CC_2 \circ TC$

735

736

737

We recall that in the following proofs, we assume that computations of $CC_2 \circ TC$ start from an arbitrary configuration. In the proofs below we use some notions and terminology already defined in Subsection 4.2.

738

739

Following a similar approach to the one used in Subsection 4.2, we have the following technical results:

740

741

**Remark 4** *Guards of actions* $Step_{11}$, $Step_{12}$, $Step_{13}$, $Step_{14}$, $Step_2$, $Step_3$, and $Step_4$ are mutually exclusive at each professor.*

742

**Lemma 8** *For every process p, if Correct(p) holds, then Correct(p) holds forever.*

743

**Corollary 5** *After at most one round, every process p satisfies Correct(p) forever.*

744

745

From these technical results, we can deduce the following lemma using the same reasoning as in Subsection 4.2.

746

**Lemma 9** *Every computation of $CC_2 \circ TC$ satisfies:*

747

1. *Exclusion,*

748

2. *Synchronization,*

749

3. *Essential Discussion, and*

750

4. *Voluntary Discussion.*

751

We now focus on the *Professor Fairness*.

752

753

754

**Lemma 10** *From any configuration where every process q satisfies Correct(q), we have: if a process p that satisfies Ready(p), Meeting(p), or $S_p = \text{done}$, then p eventually executes action *Step*<sub>4</sub>.*
Proof. Observe that from such a configuration, (*) every process $q$ satisfies Correct($q$) forever by Lemma 8. As a consequence, from that point every process $p$ that satisfies Ready($p$), Meeting($p$), or $S_p = \text{done}$ satisfies one of the following cases:

*   *LeaveMeeting($p$) holds.* In this case, $S_p = \text{done}$ and $P_p \neq \perp$. Let $\epsilon$ be the value of $P_p$. $S_p = \text{done}$ implies $\neg$Ready($p$). So, while $S_p = \text{done}$, no process $q$ can execute Step$_2$ to then satisfy $P_q = \epsilon \land S_q = \text{waiting}$. Also, every process $q$ that satisfies $P_q = \epsilon \land S_q = \text{done}$ can only update $S_q$ and/or $P_q$ by executing action Step$_4$ by (*), that is $S_q := \text{looking}$ and $P_q := \perp$. As a consequence, while $p$ does not execute action Step$_4$, LeaveMeeting($p$) holds. Now RequestOut($p$) eventually continuously holds, and, thus, action Step$_4$ is eventually continuously enabled at $p$. As the daemon is weakly fair, $p$ is eventually selected to execute an action, and this action is Step$_4$ by (*), which proves the lemma in this case.

*   *Meeting($p$) $\land \neg$LeaveMeeting($p$) holds.* Then, Meeting($p$) implies that $P_p \neq \perp$. Let $\epsilon$ be the value of $P_p$. No process $r \in \epsilon$ can update $P_r$. Moreover, for every process $r \in \epsilon$, $r$ can modify its status $S_r$ only if $S_r = \text{waiting}$. Now, Step$_3$ is enabled at every of those processes, and this action is their priority enabled action by (*) and Remark 4. Observe that $(\text{Meeting}(p) \land \neg\text{LeaveMeeting}(p))$ holds until all these processes have moved and, as the daemon is weakly fair, they eventually move. At this point this case can be reduced to the previous case, which proves the lemma in this case.

*   *Ready($p$) $\land \neg$Meeting($p$) holds.* Then, Ready($p$) implies that $P_p \neq \perp$. Let $\epsilon$ be the value of $P_p$. No process $r \in \epsilon$ can update $P_r$. Moreover, for every process $r \in \epsilon$, $r$ can modify its status $S_r$ only if $S_r = \text{looking}$. Now, Step$_2$ is enabled at every of those processes, and this action is their priority enabled action by (*) and Remark 4. Observe that Ready($p$) $\land \neg$Meeting($p$) holds until all these processes have moved and, as the daemon is weakly fair, they eventually move. At this point this case can be reduced to the previous case, which proves the lemma in this case.

Thus, in any case, $p$ eventually executes Step$_4$ and the lemma holds. $\square$

**Lemma 11** In every computation of $\mathcal{CC}^2 \circ \mathcal{T}\mathcal{C}$, no process can hold a token forever.

Proof. By Property 1, the system eventually reaches a configuration from which there is a unique token forever. Assume, by the contradiction, that after such a configuration, some process $\ell$ holds the unique token forever, i.e. $\text{Token}(\ell)$ holds forever and for every process $p \neq \ell$, $\neg$Token($p$) holds forever.

Then, using the same reasoning as in case (b) of the proof of Lemma 6, we can deduce that the system reaches a configuration $\gamma$ from which:

(1) $\ell$ satisfies $\text{Token}(\ell) \land T_\ell$ forever.

(2) Every process $p \neq \ell$ satisfies $\neg$Token($p$) $\land \neg T_p$ forever.

(3) Every process satisfies Correct forever.
791 Let us study the following two cases:

792 (a) *From* $\gamma$, $S_\ell = \mathbf{done}$, $\mathbf{Ready}(\ell)$, or $\mathbf{Meeting}(\ell)$ eventually holds. In this case, we obtain a contradiction by Lemma 10.

793 (b) *From* $\gamma$, $S_\ell \neq \mathbf{done}$, $\neg \mathbf{Ready}(\ell)$, and $\neg \mathbf{Meeting}(\ell)$ hold forever. We study the following two subcases:

796 $P_\ell \in \text{MinEdges}_\ell$. In this subcase, by (3), we deduce that $S_\ell = \mathbf{looking}$ and $P_\ell \in \text{MinEdges}_\ell$ hold forever.

797 Then, let $\epsilon$ be the hyperedge pointed by $P_\ell$. By (1) and (2), we have ($\mathbf{TPointingEdges}_p$, $\mathbf{Locked}(p)$) that is equal to $(\{\epsilon\}, \mathbf{true})$ forever for every process $p \in \epsilon$ such that $p \neq \ell$.

798 If $p$ satisfies ($S_p = \mathbf{looking} \wedge \neg \mathbf{Ready}(p)$), eventually $P_p = \epsilon$ because of the weakly fair daemon and action $\mathbf{Step}_{12}$ (by (3) and Remark 4, $p$ executes $\mathbf{Step}_{12}$ when selected by the daemon). Then, $p$ becomes disable forever because $\neg \mathbf{Ready}(\ell)$ holds forever.

800 If $p$ satisfies ($S_p \neq \mathbf{looking} \vee \mathbf{Ready}(p)$), then ($S_p = \mathbf{done} \vee \mathbf{Ready}(p) \vee \mathbf{Meeting}(p)$) holds by (3). By Lemma 10, $p$ eventually satisfies ($S_p = \mathbf{looking} \wedge \neg \mathbf{Ready}(p)$), and we retrieve the previous case. So eventually $P_p = \epsilon$ and $p$ becomes disabled forever.

801 Hence, we can conclude that eventually $P_p = \epsilon$ holds for every process $p \in \epsilon$, that is $\mathbf{Ready}(\ell)$, which is a contradiction.

802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
- $P_\ell \notin \text{MinEdges}_\ell$. In this subcase, by (3) and the fact that $S_\ell = \mathbf{done} \vee \mathbf{Ready}(\ell) \vee \mathbf{Meeting}(\ell)$ never holds, we can deduce that $S_\ell = \mathbf{looking}$ holds forever. Hence, by (1), action $\mathbf{Step}_{11}$ is continuously enabled at $\ell$, as the daemon is weakly fair, $\ell$ eventually executes an enabled action. This action is $\mathbf{Step}_{11}$ by (3) and Remark 4, and we retrieve the previous case, which leads to a contradiction.

☐

813
814 We now deduce the next corollary from Property 1 and Lemma 11:

815 **Corollary 6** In every computation of $\mathcal{CC}^2 \circ \mathcal{T}\mathcal{C}$, every process holds a token infinitely many times.

816 **Lemma 12** Every computation of $\mathcal{CC}^2 \circ \mathcal{T}\mathcal{C}$ satisfies *Professor Fairness*.

817 *Proof.* Assume by contradiction that eventually some process $p$ stops participating in any meeting. In this case, it no more executes action $\mathbf{Step}_3$. This means, in particular, that the process no more executes $S_p := \mathbf{done}$. As a consequence, it eventually no more executes action $\mathbf{Step}_4$. In particular, it eventually no more executes $\mathbf{ReleaseToken}_p$, which contradicts Property 1 and Corollary 6. $\square$

820
821 By Lemma 9, 12, and the fact that fairness implies progress, we have:

822
823
**Theorem 3** *The composition $\mathcal{CC}^2 \circ \mathcal{T}\mathcal{C}$ is a snap-stabilizing algorithm that solves the 2-phase committee coordination problem and satisfies *Professor Fairness*.*
### 5.3. Complexity Analysis

We now analyze the degree of fair concurrency of Algorithm CC2 ◦ TC. To this end, we recall some concepts from graph theory. A matching in a hypergraph $\mathcal{H} = (V, \mathcal{E})$ is a subset $S$ of hyperedges of $\mathcal{H}$, such that no two hyperedges in $S$ have a vertex in common. We denote by $\mathcal{M}_{\mathcal{H}}$ the set of all possible matchings of a hypergraph $\mathcal{H}$. The size of a matching is the number of hyperedges that it contains. A maximal matching of $\mathcal{H}$ is a matching of $\mathcal{H}$ that has no superset which is a matching of $\mathcal{H}$. We denote by $\mathcal{MM}_{\mathcal{H}}$ the set of all maximal matchings of a hypergraph $\mathcal{H}$. As $\mathcal{H}$ is clear from the context, we omit it from $\mathcal{M}$ and $\mathcal{MM}$. Obviously, $\mathcal{MM} \subseteq \mathcal{M}$.

Observe that by definition, the degree of fair concurrency $d$ satisfies $1 \le d \le \min_{\mathcal{MM}}$, where $\min_{\mathcal{MM}}$ is the size of the smallest maximal matching. The length of a hyperedge $\epsilon$ (denoted by $|\epsilon|$) is the number of nodes incident to $\epsilon$. For every process $p$, we denote by $\mathcal{E}_p^{\min}$ the subset of hyperedges incident to $p$ of minimum length, i.e., $\epsilon \in \mathcal{E}_p^{\min}$ if and only if $\epsilon \in \mathcal{E}_p$ and $\forall \epsilon' \in \mathcal{E}_p$, $|\epsilon| \le |\epsilon'|$. Let $\min_{\mathcal{E}_p}$ denote the minimum length of a hyperedge incident to $p$. Let $\text{MaxMin} = \max_{p \in V}(\mathcal{E}_p^{\min})$.

We denote by $\mathcal{H}_{\bar{Y}}$ the subhypergraph induced by $V \setminus Y$. Given a hyperedge $\epsilon$ and a vertex $p$, we define $Y_{\epsilon,p} = \{y \in 2^\epsilon \mid p \in y \wedge |y| < |\epsilon|\}$. Let $\text{Almost}(\epsilon, X)$, where $\epsilon$ is a hyperedge and $X$ is a set of vertices, be the set $\{m \in \mathcal{MM}_{\mathcal{H}_{\bar{X}}} \mid \forall q \in \epsilon \setminus X : q$ is incident to a hyperedge of $m\}$.
Let $\mathcal{AMM}(p) = \bigcup_{\epsilon \in \mathcal{E}_p^{\min}} \bigcup_{y \in Y_{\epsilon,p}} \text{Almost}(\epsilon, y)$, where $p$ is a vertex. Let $\mathcal{AMM} = \bigcup_{p \in V} \mathcal{AMM}(p)$.
Observe that $\mathcal{AMM}$ may be equal to the emptyset, e.g., when there is only one hyperedge in $\mathcal{H}$.

The set $\mathcal{AMM}$ as defined above characterizes the cases where Professor Fairness and Maximal Concurrency exhibit their conflicting natures. Consider the case where a process $p$ is the token holder and cannot participate in a meeting. In this case, there exists a neighbor of $p$, say $q$, in a smallest hyperedge $\epsilon$ incident to $p$, such that $q$ is participating in another committee meeting. It follows that processes in $\epsilon$ (including $p$) that are currently not meeting are blocked until $\epsilon$ convenes. This implies that the current setting does not form a maximal matching and, hence, maximal concurrency cannot be achieved. Thus, in order to analyze the Degree of Fair Concurrency, one needs to consider the set of all maximal matchings of the subhypergraph induced by removing those blocked processes.

We formally characterize the degree of fair concurrency of our algorithm in Theorem 4. We obtain this theorem thanks to several technical results proven below.

**Lemma 13** *If committee meetings never terminate, the system eventually reaches a configuration from which some process $p$ is the unique token holder forever.*

*Proof.* First, the system eventually reaches a configuration from which there is a unique token forever, by Property 1. Assume, by contradiction, that this token moves infinitely many times. Then, infinitely many actions $Step_4$ are executed. The number of processes being finite, there is a process $q$ that executes infinitely many actions $Step_4$. After executing $Step_4$, $S_q = \text{looking}$. Now, before executing $Step_4$ again, $q$ must execute $Step_2$ followed by $Step_3$ to go through status done. Now, in that case, a meeting of a committee whose $q$ is member convenes and that meeting never terminates, by hypothesis. So, $q$ cannot execute $Step_4$ ever in that case, because otherwise it would cause the termination of a meeting, and we obtain a contradiction. □
**Lemma 14** If committee meetings never terminate, the system eventually reaches a configuration $\gamma$ from which for every process $p$, $S_p = \mathbf{done} \Rightarrow \mathbf{Meeting}(p)$.

* There exists $i$ such that $\forall j \ge i, S_p = \mathbf{done} \wedge \neg \mathbf{Meeting}(p)$ in $\gamma_j$. Then, by Corollary 5, $p$ eventually satisfies $\mathit{Correct}(p)$ forever, which implies that $p$ eventually satisfies $\mathit{LeaveMeeting}(p)$ forever. Moreover, $p$ eventually satisfies $\mathit{RequestOut}(p)$ continuously. Hence, as the daemon is weakly fair, $p$ eventually executes $\mathit{Step}_4$, and we obtain a contradiction.

* There exists infinitely many steps $\gamma_i \mapsto \gamma_{i+1}$ of $c$ where $S_p = \mathbf{done} \wedge \neg \mathbf{Meeting}(p)$ in $\gamma_i$ and $S_p \ne \mathbf{done} \lor \mathbf{Meeting}(p)$ in $\gamma_{i+1}$. In this case, $p$ participates infinitely many times in meetings that convene and then terminate, a contradiction.

☐

Following a similar reasoning, we have:

**Lemma 15** If committee meetings never terminate, the system eventually reaches a configuration $\gamma$ from which for every process $p$, $S_p \ne \mathbf{waiting}$.

From Lemmas 14 and 15, we have the following corollary:

**Corollary 7** If committee meetings never terminate, the system eventually reaches a configuration $\gamma$ from which for every process $p$, either $S_p = \mathbf{looking}$ forever, or $S_p = \mathbf{done}$ forever.

**Lemma 16** If committee meetings never terminate, then the system eventually reaches a configuration $\gamma$ from which there is some process $\ell$ such that:

1. $\ell$ is the only token holder forever.

2. $T_\ell = \mathit{true}$ forever.

3. Every process $p \ne \ell$ satisfies $T_p = \mathit{false}$ forever.

4. There exists $\epsilon \in \mathcal{E}_\ell$ such that:

(a) $P_\ell = \epsilon$ forever.

(b) $\forall p \in \epsilon, L_p = \mathit{true}$ forever.

(c) $\forall p \in V \setminus \epsilon, L_p = \mathit{false}$ forever.

*Proof.* Case 1 follows from Lemma 13.

Consider Cases 2 and 3. From case 1, we know that for every process $p$, the value of $\mathit{Token}(p)$ does not change anymore. So, if $p$ satisfies $T_p \ne \mathit{Token}(p)$, then this remains true until $p$ executes action $\mathit{Token}$. Now, eventually actions $\mathit{Stab}$, $\mathit{Step}_2$, $\mathit{Step}_3$, and $\mathit{Step}_4$ are disabled forever at $p$ by Corollaries 5, 7, and Remark 4. So, eventually, $p$ is selected by the daemon to execute action $\mathit{Token}$. Hence, eventually, the value of $T_p$ is fixed and $T_p = \mathit{Token}(p)$ forever.
Consider now case 4a. Eventually the system reaches a configuration from which (*) every process $p$ satisfies Correct($p$) forever (by Corollary 5), $S_p = \text{done} \Rightarrow Meeting(p)$ (by Lemma 14), and either $S_p = \text{looking}$ forever, or $S_p = \text{done}$ forever (by Corollary 7).

From such a configuration:

* If $S_\ell = \text{done}$, then $\ell$ is in an infinite meeting and consequently, there exists $\epsilon \in \mathcal{E}_\ell$ such that $P_\ell = \epsilon$ forever.

* Otherwise, $S_\ell = \text{looking}$ and $\text{Token}(\ell)$ holds forever by 1. If $\ell$ eventually satisfies Ready($\ell$), $p$ can execute $Step_2$ by (*) and Remark 4, a contradiction to Corollary 7. So, $\neg \text{Ready}(\ell)$ forever and we have either $P_\ell \in \text{MinEdges}_p$ and $P_\ell$ is fixed to that value forever; or, action $Step_{11}$ is continuously enabled. In this latter case, the daemon being weakly fair, $\ell$ eventually executes $Step_{11}$ (by (*), 2, and Remark 4) and we retrieve the previous case.

Hence case 4a holds in both cases.

Finally, consider Cases 4b and 4c. Let $p$ be process. From $\gamma$, if eventually $L_p = \text{Locked}(p)$ holds, then $L_p$ is fixed forever by 2, 4a, and Corollary 7. In this case, $p$ satisfies Cases 4b and 4c.

Otherwise, eventually actions $\text{Stab}$, $\text{Step}_2$, $\text{Step}_3$, and $\text{Step}_4$ are eventually disabled forever at $p$ by Corollary 5 and Corollary 7. By 2 and 3, action $\text{Token}$ is also eventually disabled forever. From that point, $p$ can execute actions $\text{Step}_{11}$ to $\text{Step}_{14}$ at most once before some neighboring process executes action $\text{Lock}$ to definitely fix the value of its variable $L$. So, as the number of neighbors is finite, action $\text{Lock}$ is eventually the only action that $p$ can execute. Thus, as the daemon is weakly fair, $p$ eventually execute action $\text{Lock}$ and we retrieve the previous case. $\square$

**Lemma 17** If committee meetings never terminate, the system eventually reaches a configuration $\gamma$ where $\text{FreeEdges}_p = \emptyset$ forever for all processes $p$.

*Proof.* Consider a computation $c = \gamma_0 \dots$ where committee meetings never terminate.

Then, the system eventually reaches configuration from which: for every process $p$, the value of $\text{FreeEdges}_p$ is fixed and Correct($p$) = true forever by Lemma 16, Corollaries 5, and 7.

Assume that, from such a configuration, $\text{FreeEdges} \neq \emptyset$ for some processes. Let $q$ be the one among those processes with the highest identity. $\forall \epsilon \in \text{FreeEdges}_q, \forall s \in \epsilon$, $\text{LocalMax}(s) = q$ (in particular $\text{LocalMax}(q) = q$) holds continuously until a meeting involving $q$ convenes, by Lemma 16. Then, by definition of action $\text{Step}_{13}$, Remark 4, and the fact that the daemon is weakly fair, $q$ eventually sticks its pointer on some hyperedge $\epsilon$ of $\text{FreeEdges}_q$ and then eventually satisfies Ready($q$) by definition of action $\text{Step}_{14}$. Then, again by definition of action $\text{Step}_2$, Remark 4, and the fact that the daemon is weakly fair, some process of $\epsilon$ eventually executes action $\text{Step}_2$, a contradiction to Corollary 7.

Hence, eventually every process $r$ satisfies $\text{FreeEdges}_r = \emptyset$ forever. $\square$

**Theorem 4** *Degree of Fair Concurrency of Algorithm CC2 ◦ TC is at least $\min_{MM \cup AMM}$.*

*Proof.* If committee meetings never terminate, the system eventually reaches a configuration $\gamma$ where:
1. Every process $s$ satisfies:

(a) $\text{FreeEdges}_s = \emptyset$ (Lemma 17).

(b) $S_s = \text{looking if and only if } s$ is not in any meeting (Corollary 5 and Lemma 14).

2. By Lemma 16, there is a unique process $\ell$ such that:

(a) $\ell$ is the only token holder forever.

(b) $T_\ell = \text{true}$ forever.

(c) Every process $p \neq \ell$ satisfies $T_\ell = \text{false}$ forever.

(d) There exists $\epsilon \in \mathcal{E}_\ell$ such that:

i. $P_\ell = \epsilon$ forever.

ii. $\forall p \in \epsilon, L_p = \text{true}$ forever.

iii. $\forall p \in V \setminus \epsilon, L_p = \text{false}$ forever.

Consider the following two cases in $\gamma$:

• $\ell$ participates in a meeting $\epsilon$. Let $r$ be a process that does not participate in a meeting in $\gamma$. Then, eventually $\text{FreeEdges}_r = \emptyset$ by case 1a. In this case, for each hyperedge $\epsilon'$ incident to $r$, there a process $t \in \epsilon'$, such that $T_t, L_t$, or $S_t \neq \text{looking}$ holds. In the two first cases, $t$ participates in the meeting $\epsilon$ by case 2. In the latter case, $t$ participates in another meeting by case 1b.

It follows that for all processes $r$ that is not in a meeting in $\gamma$ and for all hyperedges $\epsilon'$ incident to $r$, there exists a process in $\epsilon'$ that participates in a meeting in $\gamma$. Hence, the meetings that hold in $\gamma$ form a maximal matching of the underlying hypergraph $\mathcal{H}$.

• $\ell$ does not participate in any meeting. In $\gamma$, $P_\ell = \epsilon$ such that $\epsilon \in \mathcal{E}_\ell^{\min}$ (see action $\text{Step}_{13}$). Also, there is at least one neighbor of $\ell$ that participates in a meeting in $\gamma$. Let $X$ be the subset of processes in $\epsilon$ that do not participate in a meeting in $\gamma$. Then, $X \subset \epsilon$ and $\ell \in X$. Following a reasoning similar to the previous case, we can deduce that for all processes $s$ that is not in a meeting in $\gamma$ and for all hyperedges $\epsilon'$ incident to $s$, there exists a process in $\epsilon'$ that either participates in a meeting in $\gamma$ or is a process of $X$. Hence, the meetings that hold in $\gamma$ form a maximal matching of $\text{Almost}(\epsilon, X)$.

Hence, the meetings that hold in $\gamma$ form a matching of $\mathcal{MM} \cup \mathcal{AMM}$. $\square$

<figure><img src="image_6.png" /></figure>

In the next theorem, we present a lower bound for $\min_{\mathcal{MM} \cup \mathcal{AMM}}$.

**Theorem 5** $\min_{\mathcal{MM} \cup \mathcal{AMM}} \ge (\min_{\mathcal{MM}} - \text{MaxMin} + 1)$.

*Proof.*

• By definition $\text{MaxMin} > 0$. So, $\min_{\mathcal{MM}} \ge \min_{\mathcal{MM}} - \text{MaxMin} + 1$.

• Let $x$ be the size of the smallest matching in $\mathcal{AMM}$. By definition, there exists a process $p$, a hyperedge $\epsilon \in \mathcal{E}_p^{\min}$, and a set of processes $X$ where $X \subset \epsilon$ and $p \in X$, such that there exists a maximal matching $S$ of $\text{Almost}(\epsilon, X)$ of size $x$. By definition, $S$ is a matching of $\mathcal{H}$. Moreover, there exists a maximal matching $S'$ of $\mathcal{H}$ such that $S \subset S'$. By definition there exists at most one hyperedge of $S'$ incident to some process in $X$. Hence, $|S| \ge |S'| - |X|,$
i.e., $|S| \ge |S'| - |\epsilon| + 1$, which in turn implies that $|S| \ge \min_{MM} -|\epsilon| + 1$. It follows that $|S| \ge \min_{MM} -\text{MaxMin} + 1$. Hence, the size of the smallest matching in $AMM$ is at least $\min_{MM} -\text{MaxMin} + 1$.

□

To evaluate Waiting Time of $CC2 \circ TC$, we need to introduce $\max_{Disc}$ which is the maximum amount of rounds a process discusses in a meeting. We assume that $TC$ is a fair composition of the token circulation algorithm in [27] and the leader election algorithm in [23]. It follows that the following properties hold: (1) starting from any configuration, there is a unique token in the distributed system in $O(n)$ rounds, and (2) once there is a unique token, $O(n)$ processes can receive the token before a process receives the token.

**Theorem 6** *In Algorithm $CC2 \circ TC$, the worst case Waiting Time is $O(\max_{Disc} \times n)$ rounds, where $n$ is the number of processes.*

*Proof.* First, from [27, 23], Corollary 5, and Property 1, we know that starting from any arbitrary configuration, the system reaches a configuration $\gamma$ from where every process satisfies *Correct* and there is one token forever in $O(n)$ rounds. Now, consider a token holder $p$ in any configuration that follows $\gamma$, where $p$ satisfies one of the following three cases:

* $S_p = \text{done}$. In this case, in at most one round, $p$ satisfies $\text{LeaveMeeting}(p)$ and at most $\max_{Disc}$ rounds later, it is enabled to execute $\text{Step}_4$. Hence, $p$ releases the token in $O(\max_{Disc})$ rounds.

* $S_p = \text{waiting}$. In this case, in at most one round, $p$ satisfies $\text{Meeting}(p)$ and after one more round, it satisfies $S_p = \text{done}$. Hence, from the previous case, we can deduce that $p$ releases the token in $O(\max_{Disc})$ rounds.

* $S_p = \text{looking}$. In this case, in one round $p$ sets $T_p$ to true. One another round later, $p$ sets $P_p$ to $\epsilon$ where $\epsilon \in \mathcal{E}_p^{\min}$. After this round and similarly to the previous case, every other process in $\epsilon$ that was in a meeting, leaves its meeting and joins meeting $\epsilon$ in $O(\max_{Disc})$ rounds, which leads to the status $S_p = \text{waiting}$ in the next round. Hence, from the previous cases, we can deduce that $p$ releases the token in $O(\max_{Disc})$ rounds.

It follows that after $O(n)$ rounds, a process can keep the token for $O(\max_{Disc})$ consecutive rounds before releases it. Now, from [27, 23], we know that $O(n)$ processes can hold the token before a given process receives it. Hence, the Waiting Time is $O(\max_{Disc} \times n)$ rounds.

□

## 5.4. Committee Fairness

Algorithm $CC2 \circ TC$ can be easily modified to satisfy the Committee Fairness as follows. Every time a process acquires the token, it sequentially selects a new incident committee. This way, we obtain an algorithm, called Algorithm $CC3 \circ TC$ that satisfies Committee Fairness. Waiting Time of this algorithm remains the same as that of Theorem 6, but Degree of Fair Concurrency will be slightly degraded. Recall that $Y_{\epsilon,p} = \{y \in \mathbb{N}^\epsilon \mid p \in y \wedge |y| < |\epsilon|\}$. Now,
we let $\mathcal{AMM}'(p) = \bigcup_{\epsilon \in \mathcal{E}_p} \bigcup_{y \in Y_{\epsilon,p}} \text{Almost}(\epsilon, y)$ and $\mathcal{AMM}' = \bigcup_{p \in V} \mathcal{AMM}'(p)$. Also, let $\text{MaxHEdge} = \max_{\epsilon \in \mathcal{E}} |\epsilon|$. 1011 1012

Following a proof similar to the one of Theorem 4, we trivially obtain the proof of the following theorem. 1013 1014

**Theorem 7** *The degree of fair concurrency of Algorithm CC3 ◦ TC is at least $\min_{MM \cup AMM'}$.* 1015

In the next theorem, we present a lower bound for $\min_{MM \cup AMM'}$. Its proof is similar to the one used in the proof of Theorem 5. 1016 1017

**Theorem 8** $\min_{MM \cup AMM'} \ge \min_{MM} -\text{MaxHEdge} + 1$. 1018

# 6. Related Work

Solutions to the committee coordination problem mostly focus on the three properties of the original problem described in Subsection 2.3 [2, 3, 4, 5, 6, 7]. In the seminal work by Chandy and Misra [2], the committee coordination problem is reduced to the dining or drinking philosophers problems [14]. Each philosopher represents a committee, neighboring philosophers have a common member, and a meeting is held only when the corresponding philosopher is eating. Bagrodia [3] solves the problem by introducing the notion of *managers*. Each manager handles a set of committees and two managers may have intersecting sets of assigned committees. Each committee member notifies its corresponding committee managers that it desires to participate. Conflicts between two committees (i.e., committees that share a member) managed by the same manager are resolved locally within the manager. Conflicts between two committees managed by different managers are resolved using a circulating token. In a later work [4], Bagrodia combines a message count mechanism (to ensure Synchronization) with a reduction to dining/drinking philosophers (to ensure Exclusion). 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032

Joung [19] extends the original committee coordination problem by considering fairness properties. One such property, called weak fairness in [19] or professor fairness in this paper, requires that if a professor is waiting to participate in some committee meeting, then he must eventually participate in a committee meeting (not necessarily the same). The main result is the impossibility of implementing a fair committee coordination algorithm if one of the following conditions hold: 1033 1034 1035 1036 1037

* One process's readiness to participate in a committee can be known by another only through communication, and the time it takes two processes to communicate is not negligible. 1038 1039

* A process decides autonomously when it will attempt participating in a committee, and at a time that cannot be predicted in advance. 1040 1041

Joung's result holds for fairness on multi-party committees as well. Tsay and Bagrodia [5] reach the same result with respect to the second condition identified by Joung [19]. 1042 1043

In [7], Kumar circumvents the impossibility result of Tsay and Bagrodia by making the following additional assumption: every professor waits for meetings infinitely often. In this model, Kumar proposes an algorithm that solves the committee coordination problem with professor fairness using multiple tokens, each representing one committee. Based on the same assumption, several other committee coordination algorithms that satisfy fairness can be found in [6]. 1044 1045 1046 1047 1048
1049 **7. Conclusion**

1050 In this paper, we proposed two Snap-stabilizing distributed algorithms for the committee co-
1051 ordination problem. The first algorithm satisfies 2-Phase Discussion as well as Maximal Concurrency. The second algorithm satisfies 2-Phase Discussion as well as Professor Fairness assuming
1052 that every professor waits for meetings infinitely often. As we showed, even under this latter
1053 assumption, satisfaction of both Maximal Concurrency and Professor Fairness is impossible.
1054

1055 For the second algorithm, we introduced and analyzed the degree of fair concurrency to show
1056 that it still allows high level of concurrency. We also evaluated an upper bound on waiting time.
1057 Finally, with a slight modification, we obtained another algorithm that respects Committee Fair-
1058 ness.
1059

For future work, several interesting research directions are open. One can consider other com-
1060 combinations of properties. For instance, we conjecture that providing both Maximal Concurrency
1061 and bounded waiting time is impossible. Another problem is to design a fault-tolerant committee
1062 coordination algorithm in the message-passing model. An important issue is to address dynamic
1063 hypergraphs, where professors (processes) can enter or leave the hypergraph, and, new commit-
1064 tees may be created or some committees may be dissolved or merged. Optimality is also an open
1065 question in that one can study the optimal bound on the degree of fair concurrency. Another inter-
1066 esting line of research is enforcing priorities on convening committees. Finally, we are planning
1067 to implement the algorithms presented in this paper in distributed code generation frameworks
1068 such as the one in [8]. Our algorithms will allow generating fully distributed code from high-level
1069 component-based models.
1070

1070 References

[1] B. Bonakdarpour, S. Devismes, F. Petit, Snap-stabilizing committee coordination, in: IPDPS’2011, 25th IEEE International Parallel and Distributed Processing Symposium, 2011, pp. 231–242.

[2] K. M. Chandy, J. Misra, Parallel program design: a foundation, Addison-Wesley Longman
1074 Publishing Co., Inc., Boston, MA, USA, 1988.

[3] R. Bagrodia, A distributed algorithm to implement n-party rendezvous, in: Foundations of Software Technology and Theoretical Computer Science, Seventh Conference (FSTTCS), 1987, pp. 138–152.

[4] R. Bagrodia, Process synchronization: Design and performance evaluation of distributed algorithms, IEEE Transactions on Software Engineering (TSE) 15 (9) (1989) 1053–1065.

[5] Y.-K. Tsay, R. Bagrodia, Some impossibility results in interprocess synchronization, Distributed Computing 6 (4) (1993) 221–231.

[6] C. Wu, G. Bochmann, M. Y. Yao, Fairness of n-party synchronization and its implementation in a distributed environment, in: Workshop on Distributed Algorithms (WDAG), 1993, pp. 279–293.
[7] D. Kumar, An implementation of n-party synchronization using tokens, in: Distributed Com- putung Systems (ICDCS), 1990, pp. 320–327.

[8] B. Bonakdarpour, M. Bozga, M. Jaber, J. Quilbeuf, J. Sifakis, A framework for automated dis- tributed implementation of component-based models, Distributed Computing 25 (5) (2012) 383–409.

[9] A. Bui, A. K. Datta, F. Petit, V. Villain, State-optimal snap-stabilizing pif in tree networks, in: A. Arora (Ed.), WSS, IEEE Computer Society, 1999, pp. 78–85.

[10] A. Bui, A. K. Datta, F. Petit, V. Villain, Snap-stabilization and PIF in tree networks, Dis- tributed Computing 20 (1) (2007) 3–19.

[11] E. W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM 17 (11).

[12] S. Dolev, A. Israeli, S. Moran, Uniform dynamic self-stabilizing leader election, IEEE Trans- actions on Parallel and Distributed Systems 8 (4) (1997) 424–440.

[13] S. Dolev, Self-stabilization, MIT Press, 2000.

[14] K. M. Chandy, J. Misra, The drinking philosophers problem, ACM Transactions on Programming Languages and Systems (TOPLAS) 6 (4) (1984) 632–646.

[15] B. Bonakdarpour, M. Bozga, M. Jaber, J. Quilbeuf, J. Sifakis, Automated conflict-free dis- tributed implementation of component-based models, in: IEEE Symposium on Industrial Embedded Systems (SIES), 2010, pp. 108–117.

[16] B. Bonakdarpour, M. Bozga, M. Jaber, J. Quilbeuf, J. Sifakis, From high-level component- based models to distributed implementations, in: ACM International Conference on Embed- ded Software (EMSOFT), 2010, pp. 209–218.

[17] J. L. Welch, N. A. Lynch, A modular drinking philosophers algorithm, Distributed Computing 6 (4) (1993) 233–244.

[18] A. K. Datta, R. Hadid, V. Villain, A self-stabilizing token-based k-out-of-l exclusion algo- rithm, Concurrency and Computation: Practice and Experience 15 (11-12) (2003) 1069– 1091.

[19] Y.-J. Joung, On fairness notions in distributed systems: I. a characterization of implementabil- ity, Information and Computation 166 (1) (2001) 1–34.

[20] M. Gairing, W. Goddard, S. T. Hedetniemi, P. Kristiansen, A. A. McRae, Distance-two infor- mation in self-stabilizing algorithms, Parallel Processing Letters 14 (3-4) (2004) 387–398.

[21] A. Arora, M. Gouda, Distributed reset, IEEE Transactions on Computers 43 (1994) 316–331.
[22] S. Dolev, T. Herman, Superstabilizing protocols for dynamic distributed systems, Chicago Journal of Theoretical Computer Science 1997.

[23] A. K. Datta, L. L. Larmore, P. Vemula, Self-stabilizing leader election in optimal space, in: Stabilization, Safety, and Security of Distributed Systems (SSS), 2008, pp. 109–123.

[24] S.-T. Huang, N.-S. Chen, Self-stabilizing depth-first token circulation on networks, Distributed Computing 7 (1) (1993) 61–66.

[25] A. K. Datta, C. Johnen, F. Petit, V. Villain, Self-stabilizing depth-first token circulation in arbitrary rooted networks, Distributed Computing 13 (4) (2000) 207–218.

[26] A. Cournier, S. Devismes, V. Villain, A snap-stabilizing DFS with a lower space requirement, in: Self-Stabilizing Systems (SSS), 2005, pp. 33–47.

[27] A. Cournier, S. Devismes, V. Villain, Light enabling snap-stabilization of fundamental protocols, ACM Transactions on Autonomous and Adaptive Systems (TAAS) 4 (1).