Pierre Fraigniaud
email: pierre.fraigniaud@liafa.univ-paris-diderot.fr

Sergio Rajsbaum
email: rajsbaum@math.unam.mx

Matthieu Roy

Corentin Travers
email: travers@labri.fr

The Opinion Number of Set-Agreement *

This paper carries on the effort to bridging runtime verification with distributed computability, studying necessary conditions for monitoring failure prone asynchronous distributed systems. In a previous paper (to appear in RV 2014), it has been proved that there are correctness properties that require a large number of opinions (e.g., true, false, perhaps, probably true, probably no, etc.) to be monitored. The main outcome of this paper is that the need for this large number of opinions is not an artifact induced by the existence of artificial constructions. Instead, monitoring an important class of properties, requiring processes to produce at most k different values does requires a large number of opinions. Specifically, our main result is a proof that it is impossible to monitor k-set-agreement in an n-process system with fewer than min{2k, n} + 1 opinions. The lower bound is shown to be tight.

Introduction

Monitoring correctness properties at runtime, is a well established research domain. This domain has been recently receiving more attention, with the creation in 2001 of an annual international conference on runtime verification. The essential objective of runtime verification is to determine, at any point in time, whether a system is in a legal or illegal state, with respect to a given specification.

In runtime verification monitors are hardware or software components in charge of surveying the state of the system. In particular, the case of a distributed system whose execution is observed by several monitors has been considered in, e.g., [START_REF] Bauer | Decentralised LTL monitoring[END_REF][START_REF] Berkovich | Gpu-based runtime verification[END_REF][START_REF] Sen | Decentralized runtime analysis of multithreaded applications[END_REF]. As soon as a violation of the legality of the execution is revealed by any of these monitors at runtime, recovery code can be executed for bringing the system back to a legal state. The monitors may communicate with each other, and 1 every monitor i typically produces a binary opinion o i ∈ {true, false} so that a recovery code is launched as soon as one of these opinions is false.

When processes may fail and the distributed system is asynchronous, it is however no longer sufficient for the monitors to produce only two opinions. It has indeed been shown in [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF] that there are correctness properties that cannot be monitored by interpreting the opinions produced by the monitors using the logical conjunction of all the opinions, where the system is in legal state if and only if all opinions are true. Even more problematic is the fact that it was also shown [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF] later on that there are correctness properties for which no decentralized monitoring exists, even if we let the number of opinions grow to an arbitrary large constant k ≥ 2. This holds no matter what the interpretation of the opinions is (logical conjunction or otherwise). The model studied in [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF][START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF] consists of a distributed system composed of n asynchronous processes communicating by reading and writing to a shared memory, and in which any number of processes may fail by crashing. This classical model has been studied in depth in the literature (see textbooks [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF][START_REF] Raynal | Concurrent Programming -Algorithms, Principles, and Foundations[END_REF]). In particular, it is known to be equivalent (with respect to task computability) to a message-passing model where less than half processes may crash, and other more powerful models can be reduced to it.

To be more specific, we consider the same crash-prone asynchronous distributed system, and assume as in [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF][START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF] that each process has a variable that contains the output of a computation that needs to be monitored. The simplest situation is considered, i.e., where the variable at each process is written only once. The correctness property to be monitored describes the set of values that are allowed to appear in these variables simultaneously. Such a set of values is called a instance. The set of correct instances could be expressed by a logic formula, but it turned out to be convenient to describe the correctness property by simply listing the set of all legal instances. This set is called a distributed language. The following illustrative example was detailed in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF], as it is arising often in practice [START_REF] Bauer | Comparing LTL semantics for runtime verification[END_REF]. Let us consider a system where requests are sent by clients, and acknowledged by servers. The execution is correct when (1) all requests have been acknowledged, and (2) every received acknowledgement corresponds to a previously sent request. Each monitor i observes a variable reporting a pair (R i , A i ), namely, the subset R i of requests that has been received by the servers, and the subset A i of acknowledgements that has been sent by the servers. The corresponding distributed language is the set of instances whose variables satisfy conditions (1) and (2).

To monitor the system, processes observe the values in their variables, and communicate with each other as long as needed. Eventually each process must produce its opinion about the legality of the instance with respect to the given language. It is required that the multisets of opinions produced in case the instance is legal differs from those produced for illegal instances. This partition of multisets of opinion is captured by an interpretation. In the most common setting, each opinion is in the set {true, false}, and the (global) interpretation of opinions is the logical conjunction of these opinions. However, as mentioned above, there are languages that require more opinions and more complex interpretations than logical conjunction [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF][START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF].

In [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF], it was shown that, for any k, 1 ≤ k ≤ n, there exists a distributed language requiring monitors to produce at least k distinct opinions in a system with n monitors. To establish this result, an ad hoc language was constructed. The existence of a natural language that would be arbitrarily difficult in terms of the number of opinions needed to monitor it was left open.

In this paper, we study the number of opinions needed to monitor the family of set agreement tasks, widely studied in the distributed computing literature since its introduction in [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF]. Recall that, for n ≥ 1 processes, and 1 ≤ k ≤ n, the (n, k)-set-agreement task is specified as follows. Each processes proposes a value, from some ground set. After communicating with the other processes, each process has to decide on one of the proposed values, such that at most k different proposed values are decided. Hence, if k = 1 then we get the classic consensus task [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF], and, as we increment the value of k, we get easier agreement tasks, until we get the trivial task for k = n.

More precisely, we consider the language L n,k corresponding to (n, k)-set-agreement. The value to be monitored at each process i, 1 ≤ i ≤ n, consists of a pair (s i , t i ). Consider the set of pairs u = {(s i 1 , t i 1 ), (s i 2 , t i 2 ), . . . , (s i ℓ , t i ℓ )} present at some time in the system, where the pair (s i j , t i j ) is the variable of process i j , j = 1, . . . , ℓ. Note that we may have ℓ < n since some processes may crash or be arbitrarily slow. Then u is in the language L n,k (i.e., represents a correct execution of an algorithm A pretending to solve (n, k)-set-agreement) if and only if [START_REF] Afek | Atomic snapshots of shared memory[END_REF] there are at most k different t i j , j = 1, . . . , ℓ (i.e., at most k different values have been decided by A), and (2) for each t i j , there must exist a pair (s i j ′ , t i j ′ ) in u such that s i j ′ = t i j (i.e., t i has been proposed by at least one participating process).

Our results

We first prove that the language L n,k can be monitored using min{2k, n} + 1 opinions. Then, our main result is a proof that it is impossible to monitor L n,k with fewer opinions. Thus, in particular, consensus can be monitored with 3 opinions, and cannot be monitored with less than 3 opinions, even using interpretations different from the logical conjunction of boolean opinions.

The upper bound is a simple adaptation of the universal algorithm presented in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF]. Our proof technique for the lower bound is also inspired from the lower bound in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF], and, as such, is also based on combinatorial topology arguments using Sperner's lemma. However, a careful analysis of the alternation number of the set agreement language had to be achieved in this paper. This parameter captures the number of times a sequence of instances can alternate between legal and illegal over an execution of the system.

Hence, the main outcome of this paper is the perhaps surprising result, that the difficulty of monitoring set agreement (in terms of number of opinions) is captured by the formula min{2k, n}+1. The difficulty grows linearly as k is increased, at double the rate, and only until 2k = n. For larger values of k, the number of opinions stays at its maximum, equal to n + 1 (no task requires more opinions). Indeed, monitoring the most important case in distributed computing, which is k = n -1, does not require more opinions than when 2k = n. We conjecture that the number of opinions has a direct relation with the number of logic values needed to design a temporal logic framework, and it is well known that more logic values dramatically increase the difficulty of reasoning in the logic. Hence this paper continues motivating further research at the border between runtime verification and distributed computability, in the context of studying necessary conditions for monitoring asynchronous distributed systems susceptible to failures.

Related work.

Most work on decentralized monitoring, is based on logical frameworks, using LTL or variants of it, see e.g. [START_REF] Bauer | Decentralised LTL monitoring[END_REF], where a formula φ is decomposed into local formulas, so monitor i evaluates locally φ i , and emits a boolean-valued opinion. In our terminology, a logical conjunction interpratation is used. That is, it is assumed a global violation can always be detected locally by a process. See [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF] for a more detailed discussion logic-based runtime verification. To the best of our knowledge, the effects of asynchrony and failures in a decentralized monitoring setting were considered for the first time in [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF], and subsequently in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF]. Related work in the distributed computing literature includes papers such as [START_REF] Chandy | Distributed Snapshots: Determining Global States of Distributed Systems[END_REF] for stable property detection in a failure-free message-passing environment, and e.g. [START_REF] Awerbuch | Self-stabilization by Local Checking and Correction[END_REF] for distributed program checking in the context of self-stabilization.

Organization of this paper.

The distributed system model and the notion of distributed languages are defined is in Section 2. Wait-free monitoring is presented in Section 3. A monitor for the language L n,k appears in Section 4. The lower bound on the number of opinions to monitor L n,k is shown in Section 5. We conclude the paper and mention some open problems in Section 6.

Preliminaries

We consider the standard wait-free shared memory model [START_REF] Raynal | Concurrent Programming -Algorithms, Principles, and Foundations[END_REF]. The system consists of n processes denoted {p 1 , . . . , p n } that communicate via a shared memory. Processes are asynchronous and any number of them may fail by crashing (i.e., halt and never recover.). The shared memory is made of n shared registers, one per process, that support atomic read and write operations. To simplify the design of protocol, we assume that atomic snapshots [START_REF] Afek | Atomic snapshots of shared memory[END_REF] are available. An atomic snapshot consists in an n-components array R and supports two operations update(v) and snapshot(). update(v) by process p i sets the value of R[i] to v and snapshot() reads atomically all the components [START_REF] Afek | Atomic snapshots of shared memory[END_REF].

A task specifies for each process possible inputs and for each possible assignment of inputs to the processes, which are the valid outputs. More precisely, an input or output set is a non-empty set s = {(id 1 , v 1 ), . . . , (id ℓ , v ℓ )} where id 1 , . . . , id k are distinct processes identities1 and v 1 , . . . , v k are values from some set V. s specifies an assignment of input or output values to each processes in ID(s) = {id 1 , . . . , id k }. The set of values in s is denoted by val(s). Sometimes, the values in s are seen as a multiset, in which case we use the notation mval(s). Two input or output sets s, t match if ID(s) = ID(t). A task is specified by a triplet (I, O, ∆) where I and O are inclusion-closed sets of input and output sets respectively, and ∆ maps each input set s ∈ I to a non-empty set of matching output sets.

In the (n, k)-set agreement task [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF], each process input is a value taken from some set V of cardinality larger than k. Each process is required to output a value which is the input value of a participating process such that no more than k distinct values are output. More precisely, I is the set of the input sets s with val(s) ⊆ V and t

= {(id 1 , v 1 ), . . . , (id ℓ , v ℓ )} ∈ O if and only if |val(t)| ≤ k. For any input set s ∈ I, ∆(s) = {t ∈ O : ID(s) = ID(t) and val(t) ⊆ val(s)}.

Distributed Languages

Distributed languages have been introduced in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF] as a simple way to represent correctness properties of distributed systems. Given an alphabet of symbols A, a distributed language over A is a set of non-empty input sets with, for each s ∈ L, val(s) ⊆ A. In the context of distributed languages, input sets s with val(s) ⊆ A are called instances. An instance s is legal if s ∈ L and illegal otherwise. A distributed language might specify a global property that a distributed system should satisfy. In this case, each element of A encodes a local state and the sets in L represent the global states of the system that satisfy the property.

We focus on checking that the result of a distributed computation satisfies the specification of a given task. More precisely, given a task T = (I, O, ∆), we define the language L T induced by T as follows. Let V I and V O be respectively the sets of possible input and output values of T . Language L T is defined over the alphabet

V I × V O . That is, each process input is a pair (s i , t i ) ∈ V I × V O .
Given an input set u = {(id 1 , (s 1 , t 1 )), . . . , (id ℓ , (s ℓ , t ℓ ))}, let s u = {(id 1 , s 1 ), . . . , (id ℓ , s ℓ )} and t u = {(id 1 , t 1 ), . . . , (id ℓ , t ℓ )}. Then, u ∈ L ⇐⇒ t u ∈ ∆(s u ). In other words, an input set u belongs to L T if and only if each process i starting with input value s i is allowed to decide t i , according to the specification of T .

The language L n,k induced by (n, k)-set agreement is defined as follows. The alphabet over which L n,k is defined is V × V where V is the set from which values are proposed in the (n, k)-set agreement task. Then, for any instance s = {(id 1 , (s 1 , t 1 )), . . . , (id ℓ , (s ℓ ))}, s ∈ L n,k if and only if |{t 1 , . . . , t ℓ }| ≤ k and {t 1 , . . . , t ℓ } ⊆ {s 1 , . . . , s ℓ }.

Wait-free languages monitoring

As defined in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF], monitoring the correctness specified by a distributed language L over an alphabet A involves two components: an opinion-maker M , and an interpretation µ. The opinion-maker is a distributed protocol. For each process p i , its input is a pair (id i , a i ) where a i ∈ A and its output is an opinion about the legality of the input set. The processes running this algorithm are called monitors, and the (finite) set of possible individual opinions U , the opinion set.

The interpretation µ specifies how the collection of individual opinions produced by the monitors should be interpreted. It is required that the opinions of the monitors should be able to distinguish legal input sets from illegal ones according to L. Thus, µ = (Y, N) is a partition of all multi-sets of at most n elements over U . Y is called the "yes" set, and N is called the "no" set.

A pair (M, µ) is a monitor for language L over alphabet A if the following holds:

• For the opinion-maker protocol M , input of of each process i is any element a i of A and the output an opinion u i . M is required to be wait-free: each participating process is required to decide an opinion in a finite number of its own steps, regardless of the behavior of the other processes.

• For any input set s, in any execution of M with input s where all participating processes decide, the multiset S of opinions that are decided satisfies:

s ∈ L ⇐⇒ S ∈ Y.
Thus, if the input set s is illegal, i.e., s ∈ L, then the processes must produce a multiset of opinions in N.

By extension, a pair (M, µ) is a monitor for a task T if (M, µ) is a monitor for the induced language L T .

Example: AND-interpretation

When the set of opinions consists only in two values, i.e., U = {0, 1}, a natural interpretation µ is induced by the and-operator [START_REF] Fraigniaud | Local Distributed Decision[END_REF][START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF] as follows. For every multi-set of opinions S, S ∈ Y if every opinion in S is 1, otherwise, S ∈ N. Intuitively, a process outputs 1 if according to its view the instance is legal and 0 otherwise. Note that the interpretation is id-oblivious: for each opinion, the identities of the processes that produce that opinion is not taken into account by the interpretation.

Not every language has a wait-free monitor with an and-interpretation. Indeed, the languages that can be monitored with the and-interpretation are exactly those that are projection-closed2 [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF]. In particular, the language induced by the consensus task is not projection-closed and therefore does not have a wait-free monitor with the and-interpretation. In fact, our main result implies that three opinions are necessary and sufficient to wait-free monitor consensus.

Opinion number and alternation number

The opinion number #opinion(L) of a language L, is the smallest size of the opinion set U for which there exists a monitor with opinion U for L. The alternation number #altern(L) of a language L is the longest sequence of increasing instances that alternates between legal and illegal instances. More precisely, #altern(L) is the largest integer ℓ for which there exists instances s 1 ⊂ s 2 ⊂ . . . ⊂ s ℓ such that for every i, 1 ≤ i < ℓ, s i ⊂ s i+1 , and either

s i ∈ L ∧ s i+1 / ∈ L or s i / ∈ L ∧ s i+1 ∈ L.
A strong relationship between opinion and alternation numbers of languages is exposed in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF]. First, it is established that the alternation number gives an upper bound on the opinion number: For every language L, #opinion(L) ≤ #altern(L)+1. Second, it is shown that for any k, 1 ≤ k ≤ n, there exists a n-processes language L with #altern(L) = k that requires at least k opinions to be monitored, i.e., #opinion(L) ≥ k.

For (n, k)-set agreement, the alternation number of the induced language L n,k is:

Lemma 3.1. #altern(L n,k ) = min{2k + 1, n}.
Proof. Consider the following sequence of instances:

s 1 = {(1, (0, 1))}, s 2 = {(1, (0, 1)), (2, (1, 1))}, . . ., s 2i = {(1, (0, 1)), (2, (1, 1)
), . . . , (2i, (i, i))}, s 2i+1 = {(1, (0, 1)), . . . , (2i, (i, i)), (2i + 1, (i, i + 1))},. . . for i : 2i, 2i + 1 ≤ n. Note that s 2i+1 / ∈ L n,k as this instance corresponds to the case in which a value, namely i + 1 is decided whereas it has not been proposed. In s 2i , however, i values are decided and each of them is also a proposed value. Thus, if the number of decided values is less than or equal to k, that is, i ≤ k, s 2i ∈ L n,k . Hence, the increasing sequence s 1 , s 2 , . . . , s min{2k+1,n} alternates between legal and illegal instances. Thus, #altern(L n,k ) ≥ min{2k + 1, n}.

Let s 1 ⊂ . . . ⊂ s x be a sequence of increasing instances such that for every i,

1 ≤ i < x, s i ∈ L n,k ∧ s i+1 / ∈ L n,k or s i / ∈ L n,k ∧ s i+1 ∈ L n,k . Let D(i) denote the size of the set of values decided in s i . That is, if s i = {(id 1 , (a 1 , b 1 )), . . . , (id ℓ , (a ℓ , b ℓ ))}, D(i) = |{b 1 , . . . , b ℓ }|. Note that D(1) ≥ 1.
Consider instances s i , s i+1 with i such that with s i ∈ L n,k . As s i ⊂ s i+1 , and since in s i no more that k values are decided and every decided value is valid, it follows that a value not decided in s i is decided in s i+1 , i.e., D(i) < D(i + 1).

Let s x ′ be the largest legal instance in the sequence. Note that x ′ = x or x ′ = x -1. On one hand, we have D(x ′ ) ≤ k. On the other hand, 1 + ⌊ x ′ -1 2 ⌋ ≤ D(x ′ ), since the number of alternations from a legal instance to an illegal one in the sequence s 1 , . . . , s x ′ is at least ⌊ x ′ -1 2 ⌋ and D(1) ≥ 1. Hence, x ′ ≤ 2k, and as x ≤ x ′ + 1, we obtain x ≤ 2k + 1. Therefore, any sequence of increasing and alternating instances is of length at most 2k + 1. Hence, #altern(L n,k ) ≤ min{2k + 1, n}.

The two next sections focus on determining how many opinions are needed to monitor (n, k)-set agreement. We show that #opinion

(L n,k ) = #altern(L n,k ) if #altern(L n,k ) < n and #opinion(L n,k ) = n + 1 otherwise, that is, #opinion(L n,k ) = min{2k, n} + 1.

Monitoring k-set agreement

We prove in this section that (n, k)-set-agreement can be wait-free monitored using min{2k, n} + 1 opinions.

In [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF], an universal monitor is presented that uses at most n + 1 opinions for any n-processes language. The opinion-maker of this monitor depends on the language being checked whereas the interpretation depends solely on the opinions output by the processes. Independently of the language, the opinions produced by each process belongs to a set of size n + 1. If k > n 2 , min{2k, n} + 1 = n + 1 and thus in this case the language L n,k induced by (n, k)-set-agreement can be checked by the universal monitor described in [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF].

For the case k ≤ n 2 , we present a monitor (M, µ) for (n, k)-set agreement that uses 2k + 1 opinions. The set of opinions is:

U = {red} ∪ {(green, ℓ) : 1 ≤ ℓ ≤ k)} ∪ {(orange, ℓ) : 1 ≤ ℓ ≤ k)}.
Note that |U | = 2k + 1. The partition (Y, N) is defined as follows. For any multiset S with values in U , let maxlevel(S) = max{ℓ : (green, ℓ) ∈ S ∨ (orange, ℓ) ∈ S}.

Then, S ∈ Y ⇐⇒ (green, maxlevel(S)) ∈ S ∧ red / ∈ S (1)
Equivalently, any multiset S that contains the value red or a pair (orange, ℓ) and no pair (green, ℓ ′ ) with ℓ ≤ ℓ ′ is in the "no" set N. Recall that each process p i starts with an input-output pair (s i , t i ), runs the opinion-maker protocol and produces an opinion based on what it sees during the execution of the protocol. Since we consider wait-free protocol and processes run asynchronously, it may be the case that a process p i does not see the input-output pair of some participating processes.

Intuitively, a process outputs red if in the collection (s ′ , t ′ ) of input-output pairs it sees does not fit the specification of (n, k)-set-agreement, and furthermore, this cannot be fixed by completing (s ′ , t ′ ) with other input-output pairs. This occurs if agreement is broken, i.e., more than k values are decided in t ′ . In the case where agreement is satisfied (t ′ contains at most k distinct values) as well as validity (every decided values is proposed, that is, appears in s ′ ), the process outputs (green, d) where d ≤ k is the number of decided values. In the last case, namely agreement is satisfied but validity is not (a decided value in t ′ does not appear in s ′ ), (orange, d) is output. Note that in this case, the global input (s, t) consisting in the collection of input-output pairs of each participating process may still fit the specification of (n, k)-set agreement. The pseudo-code of the opinion-maker appears in Fig. 1.

Opinion-maker M at process i with input (i, (si, ti)): R.update i, (si, ti) ; r ← R.snapshot(); The following Lemma summarizes the result of this section:

(s ′ , t ′ ) ← ({(j, sj) : r[j] = ⊥}, {(j,
Lemma 4.1. (n, k)-set-agreement has a monitor that uses min{2k, n}+1 opinions, i.e., #opinion(L n,k ) ≤ min{2k, n} + 1.

Proof. We prove that, for k ≤ n 2 , the opinion-maker M of Fig. 1 together with the interpretation µ described in Equation 1 are a wait-free monitor for (n, k)-set agreement task (I, O, ∆). Note that the opinion set of M is of size 2k + 1, as desired.

Let V denote the set of possible input values for the (n, k)-set agreement task. Let us consider an execution e of the opinion-maker with input set {(id 1 , (s 1 , t 1 )), . . . , (id ℓ , (s ℓ , t ℓ ))} where (s i , t i ) ∈ V × V for each i, 1 ≤ i ≤ ℓ. Assume that every participating process decides, and let S denote the multiset of opinions that are decided in this execution. In addition, let s = {(id 1 , s 1 ), . . . , (id ℓ , s ℓ )} and t = {(id 1 , t 1 ), . . . , (id ℓ , t ℓ )}.

A process p i decides red if more than k values are decided in the output set t ′ it sees. Even if i has only a partial view of the input, i.e., (s ′ , t ′ ) (s, t), the lack of agreement cannot be fixed in (s, t) since every value decided in t ′ is also decided in t. Therefore, t / ∈ ∆(s), and consequently, it is correct that S ∈ N.

Suppose that no processes decides red. Let p i be the last process that writes its input (s i , t i ) into shared memory. The invocation of R.snapshot() by p i thus starts after every participating process p j has updated the shared object with its input (s j , t j ). It thus follows that p i observes the full input (s, t). Denote by d the number of decided values in t. Since no process decides red, d ≤ k. We consider two cases, depending on whether t ∈ ∆(s) or not.

• Assume first that t ∈ ∆(s). Since p i sees the full output, it decides (green, d). As in every partial input (s ′ , t ′ ) ⊆ (s, t), the number of decided values is at most d, each process that sees a partial input decides either (green, d ′ ) or (orange, d ′ ) with d ′ ≤ d. Therefore, maxlevel(S) = d, and thus S ∈ Y.

• Assume now that t / ∈ ∆(s). Since no processes decide red, the number of decided values in t is at most k. Because t / ∈ ∆(s), it must be the case that a decided value is not valid, i.e., there exists a value u ∈ val(t) that is not contained in val(s). Therefore p i decides (orange, d). Assume for contradiction that a process p j decides (green, ℓ) with ℓ ≥ d. Observe that, at process j, the collection of input-output pairs (s ′ , t ′ ) seen by j is such that (s ′ , t ′ ) ⊆ (s, t). Hence, every value decided in t ′ is also decided in t. Thus ℓ = |val (t ′ )|, the number of decided values seen by p j , is smaller than of equal to d.

Therefore ℓ = d and processes p i and p j see the same output set W = val (t) = val (t ′ ) of decided values. Moreover, as p j decides (green, ℓ), validity holds for the pair (s ′ , t ′ ), that is W = val (t ′ ) ⊆ val (s ′ ). Consequently, as s ′ ⊆ s, each value v ∈ W is also proposed in s. Therefore, agreement and validity are verified in (s, t) and p i should decide (green, d): a contradiction. Hence, for every (green, ℓ) ∈ S, ℓ < d from which we conclude that S ∈ N.

Opinion Number of (n, k)-set agreement

We now establish a lower bound on the number of opinions required to monitor L n,k . The proof is by contradiction.

Assume for contradiction that L n,k has a wait-free monitor (M, µ) with opinion set U , |U | < min{2k, n} + 1. The existence of this monitor implies that a specific task T U,µ has a wait-free protocol. When solving a task, each participating process starts with a private input value and has to eventually decide irrevocably on an output value. Let V, V ⊇ {0, . . . , k}, the alphabet of the language L n,k . In task T U,µ , process p i 's input is any pair (s i , t i ) ∈ V × V and it is required to output a value u i ∈ U . When the input set s is a legal instance, i.e., s ∈ L n,k , the multiset of output value must belong to the "yes" set Y and in the "no" set N otherwise. We show that as long as the set of opinion U is of cardinality less than min{2k, n} + 1, whatever the interpretation µ, task T U,µ is not wait-free solvable. To that end, we rely on the representation of wait-free computations by topological objects, as in, e.g., [START_REF] Attiya | The Combinatorial Structure of Wait-free Solvable Tasks[END_REF][START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF][START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF]. Our main tool is a variant of Sperner's Lemma.

Preliminaries

Basic notions of topology

We first review some basic definitions. A complex K is a set of vertices V (K), and a family of finite, nonempty subsets of V (K), called simplexes, satisfying: (1) if v ∈ V (K) then {v} is a simplex, and (2) if s is a simplex, so is every nonempty subset of s. The dimension of a simplex s is |s| -1, the dimension of K is the largest dimension of its simplexes, and K is pure of dimension k if every simplex belongs to a k-dimensional simplex. A simplex τ is a face of a simplex σ if τ is a subset of σ. If τ is not equal to σ then τ is a proper face of σ. The complex induced by a simplex σ consists in σ and all its faces.

In distributed computing, a vertex represents a local state, a simplex a global state and a complex a collection of global states. Hence, one of the labels of each vertex is an identity in [n]. We denote by ID(σ) the identities of the vertexes of σ. A simplex is chromatic if it is properly colored with ids in [n]. A complex is chromatic if each of its simplex is chromatic.

A simplicial map f from complex K to complex L is a function from V (K) to V (K) that preserves simplexes. That is, if τ = {v 1 , . . . , v ℓ } is a simplex of K, then {f (v 1 ), . . . , f (v ℓ )} is a simplex of L. In addition, if K and L are chromatic complexes, f is said to be id-preserving if for any simplex τ = {v 1 , . . . , v ℓ } ∈ K, ID(τ ) = ID({f (v 1 ), . . . , f (v ℓ )}).

Pseudomanifold and divided images

A complex K of dimension n is a pseudomanifold with boundary if it is strongly connected, and each (n -1)-simplex in K is a face of precisely one or two n-simplexes. For simplicity, a pseudomanifold with boundary will simply be called a pseudomanifold. We sometimes write n-pseudomanifold as a shorthand for a n-dimensional pseudomanifold. Let K be a n-pseudomanifold. A (n -1)-simplex σ is said to be internal if it is a face of exactly two n-simplexes of K and external otherwise. The boundary of K, denoted ∂K, is the sub-complex of K induced by its external simplexes. More precisely, ∂K consists in each (n -1)-simplex of K that is a face of exactly one n-simplex together with all its faces.

Divided images of complexes have been introduced in [START_REF] Attiya | The Combinatorial Structure of Wait-free Solvable Tasks[END_REF] as a combinatorial tool to represent certain classes of executions of read/write wait-free protocols. A subdivision of a complex is a divided image, but subdivided images are not always subdivisions. Divided images capture the essential properties to study wait-free computability. Definition 5.1 ([2], Definition 4.1). Let K and L be finite n-dimensional complexes and ψ a function that maps every simplex of K to a subcomplex of L. The complex K is a divided image of L under ψ if and only if

1. ψ(∅) = ∅, 2. for every 0-simplex σ ∈ L, ψ(σ) is a single vertex, 3. for every σ, σ ′ ∈ L, ψ(σ ∩ σ ′ ) = ψ(σ) ∩ ψ(σ ′ ), and 4. for every σ ∈ L, ψ(σ) is a dim(σ)-pseudomanifold with ∂ψ(σ) = ψ(∂σ).
When ψ is clear from the context or not relevant, we simply say that K is a subdivided image of L . Next Lemma state some properties of divided:

Lemma 5.1 ([2], Lemma 4.2). Let K, L be n-dimensional complexes such that K is a divided image of L under ψ. 1. For every σ, σ ′ ∈ L, if σ ⊆ σ ′ , then ψ(σ) ⊆ ψ(σ).

For every pair of

j simplexes σ, σ ′ ∈ K, if σ = σ ′ and σ ∩ σ ′ = ∅, then ψ(σ ∩ σ ′ ) is a
pseudomanifold of dimension strictly smaller than j.

3. A (n -1)-dimensional simplex τ ∈ K is external if and only if for some external (n -1)- dimensionnal simplex σ ∈ L, τ ∈ ψ(σ).
The carrier of simplex τ ∈ K, denoted carrier(τ ) is the simplex σ ∈ L of smallest dimension such that τ ∈ ψ(σ). Note that, by Definition 5.1(3), carrier(τ ) is well defined and by Lemma 5.

1(2), it is unique. If L is a chromatic complex, K is a chromatic divided image [2] of L if K is a divided image of L, K is a chromatic complex,
and for any τ ∈ K, ID(τ ) ⊆ ID(carrier(τ )). Note in particular that if dim(τ ) = dim(carrier(τ )), τ is properly colored with the ids in ID(τ ).

Combinatorial implication of wait-free computability

Simplexes and complexes are a convenient way to represent tasks and distributed protocol. A tasks T = (I, O, ∆) can be equivalently described by an input complex I, an output complex O and a function ∆ that maps each simplex of I to a sub-complex of O. Vertexes of I and O are labeled with an identity and a value and there is a simplex s = {(id 1 , v 1 ), . . . , (v ℓ , id ℓ )} in I (respectively, O) if and only if s is an input set in I (respectively, an output set in O). Similarly, t ∈ ∆(s) if and only if the corresponding output set t is in ∆(s). In the following, we consider the topological representation for tasks and drop the notation.

Without loss of generality, a read/write wait-free protocol consists in a certain number B of (asynchronous) rounds. In each round, process p i writes its state in its cell R[i], takes a snapshot of the memory and updates its state. The process initial state is its input. At the end of the B rounds, a final state is reached on which depends the process decision. A protocol complex P represents all possible final states for some execution. Each vertex is labeled with an id and a possible final state. σ = {(id 1 , v 1 ), . . . , (id ℓ , v ℓ )} is a simplex in P if there is an execution at the end of which process p i with identity id i is in state v i , for 1 ≤ i ≤ ℓ.

An immediate snapshot execution can be divided into blocks. In each block, a subset of the participating processes are active. They first simultaneously write before taking a snapshot. One important result of the topological approach is a characterization of the structural properties of the protocol complex of immediate snapshot executions, namely the immediate snapshot protocol complex is a chromatic divided image of the input complex [START_REF] Attiya | The Combinatorial Structure of Wait-free Solvable Tasks[END_REF]. If a protocol solves a task T = if the set of input-output pairs (s i , t i ) in s satisfy the agreement property and validity property, respectively, of (n, k)-set agreement. That is, agree k (s) ⇐⇒ |{t j : (id j , (s j , t j )) ∈ s}| ≤ k valid(s) ⇐⇒ {t j : (id j , (s j , t j )) ∈ s} ⊆ {s j : (id j , (s j , t j )) ∈ s} A vertex of a simplex t ∈ U has two labels: and identity id and an opinion u ∈ U . Recall that ID(t) and mval(t) then denote the set of ids and the multiset of opinions, respectively, of the vertexes of t. ∆ µ is then defined as follows. For any s ∈ I, t ∈ U, t ∈ ∆ µ (s) ⇐⇒ ID(t) = ID(s) and mval(t) ∈ Y if agree k (s) and valid(s) mval(t) ∈ N otherwise.

We associate with each simplex s ∈ I a value in {+1, -1} depending on whether agreement and validity hold in s: ∀s ∈ I : sign(s) = +1 if agree k (s) and valid(s) -1 otherwise.

We focus on the following simplexes of I (See also Figure 2):

σ 2i = {(1, (0, 1)), (2, (1, 1)), (3, (1, 2)), (4, (2, 2)
), . . . , (2i -1, (i -1, i)), (2i, (i, i))}, for i ≥ 1,

σ 2i+1 = {(1, (0, 1)), (2, (1, 1)), (3, (1, 2)), (4, (2, 2)
), . . . , (2i, (i, i)), (2i + 1, (i, i + 1))}, for i ≥ 0.

Note that σ 1 ⊂ σ 2 ⊂ . . . ⊂ σ n and that for each simplex σ i , the complex induced is a (i -1)pseudomanifold. Furthermore, we have    valid(σ i ) and agree k (σ i ) if 1 ≤ i ≤ 2k and i is even ¬valid(σ i ) and agree k (σ i ) if 1 ≤ i ≤ 2k and i is odd

¬agree k (σ i ) if 2k < i
Hence, sign(σ i ) = (-1) i if 1 ≤ i ≤ 2k + 1 and sign(σ i ) = -1 for 2k + 1 ≤ i. Another noteworthy property is the fact that every (dim(σ i ) -1)-dimensional face of σ i except σ i-1 has the same sign as

σ i : ∀i ∈ [2, 2k + 1], ∀σ ⊂ σ i , dim(σ) = dim(σ i ) -1 ∧ σ = σ i-1 =⇒ sign(σ) = sign(σ i ) (2)
Since there is a wait-free protocol for the task T = (I, U , ∆ µ ), namely the opinion-maker M , it follows from Theorem 5.1 that there is a chromatic divided image I * of I under a function ψ and a id-preserving simplicial map δ : I * → U that agrees with ∆ µ . Since δ is a simplicial map, it maps each vertex v ∈ V (I * ) to a vertex δ(v) in U . Recall that each vertex of U has two labels: a process id ∈ [n] and an opinion u ∈ U . δ thus implies a (not necessarily proper) coloring c : V (I * ) → U on the vertexes of I * : For each vertex v of I * , c(v) = val(δ(v)). Given a simplex s = {v 1 , . . . , v ℓ } ∈ I * we denote by slight abuse of notation c(s) = {c(v 1 ), . . . , c(v ℓ )} ⊆ U the multiset of colors induced by δ of the vertex of s. Figure 3 represents a chromatic divided image of the input simplex σ 3 .

Claim 5.1. Let σ, σ ′ be j-simplexes in I with sign(σ) = -sign(σ ′ ) and let s, s ′ be j-simplexes in I * . If s ∈ ψ(σ) and s ′ ∈ ψ(σ ′ ), c(s) = c(s ′ ). Proof of Claim 5.1. c(s) is the multiset of opinions output by the participating processes (those processes with ids ID(s) = ID(σ)) in some execution e of the opinion-maker M in which the initial configuration is σ. Similarly, in some execution e ′ of M with initial configuration σ ′ , the opinions collectively output by the participating processes is c(s ′ ). As sign(σ) = -sign(σ ′ ), the validity and agreement properties of (n, k)-set agreement in one initial configuration are satisfied but this is not the case in the other execution. Therefore the same multiset of opinion cannot be output in both executions. For example, in Figure 3, for any 1-dimensional simplex s in the subdivided left edge {(p 1 , (0, 1)), (p 2 , (1, 1))} and any s ′ in the subdivided top right edge {(p 1 , (0, 1)), (p 3 , (1, 2))}, c(s) = c(s ′ ).

Next, we show that for each j, 1 ≤ j ≤ min{2k + 1, n}, there exists at least one execution of the opinion-maker where the input configuration is σ j in which the j participating processes output j distinct opinions. More precisely, we establish by induction on j the following claim. The proof strategy is illustrated in Figure 3.

Claim 5.2. For each j, 1 ≤ j ≤ min{2k + 1, n}, there exists a set C j ⊆ U of size j such that {s ∈ ψ(σ j ) : c(s) = C j } is odd Proof of Claim 5.2.
• Base case j = 1. By definition, σ 1 is a vertex. By Definition 5.1(2), ψ(σ 1 ) is also a vertex v of I * . Since δ is a simplicial map, δ(ψ(σ 1 )) is a vertex in U . Let C 0 = val(δ(ψ(σ 1 ))), i.e., C 0 = {c(v)}. That is, C 0 is the singleton consisting in the opinion output by process 1 when it runs alone with input/output pair (0, 1).

• Induction step. Let j ≥ 2 and assume that the claim is true for j -1.

By Definition 5.1(4), ψ(σ j ) is a (j -1)-pseudomanifold. In order to apply our variant of Sperner's Lemma, we establish that the number of (j -2)-simplexes in the boundary of ψ(σ j ) that are colored with C j-1 is odd. To that end, let s ∈ ∂ψ(σ j ) be an (dim(σ j )-1) dimensional simplex and assume that c(s) = C j-1 . We prove that s ∈ ψ(σ j-1 ).

Note that dim(s) = j -2. By Lemma 5.1(3), there exist a (j -2) dimensional face σ of σ j such that s ∈ ψ(σ). Suppose for contradiction that σ = σ j . It then follows that sign(σ) = sign(σ j ) (Equation ( 2) from which we have sign(σ) = -sign(σ j-1 ). By the induction hypothesis, there is a least one (j -2)-simplex s ′ ∈ ψ(σ j-1 ) with c(s ′ ) = C j-1 . Since sign(σ) = -sign(σ j-1 ), it follows from Claim 5.1 that no (j -2)-simplex in ψ(σ) is C j-1 -colored. In particular, c(s) = C j-1 : a contradiction.

Therefore, the only simplexes s ∈ ∂ψ(σ j ) that are C j-1 -colored are the simplexes s in ψ(σ j-1 ) such that c(s) = C j-1 . By the induction hypothesis, the number of such simplex is odd. It thus follows from Lemma 5.2 that there exists a set C = C j ⊃ C j-1 ⊇ U of j elements such that the number of (j -1)-simplexes s ∈ ψ(σ j ) colored with C j is odd.

If min{2k + 1, n} = 2k + 1, we can stop here: we have just proved that ψ(σ j ) ⊆ I * contains at least one 2k-dimensional simplex colored with 2k + 1 distinct colors. Hence |U | ≥ 2k + 1 = min{2k, n} + 1, as desired.

Suppose that n < 2k + 1. A similar reasoning can be carried over the collection of simplexes σ 1 ⊂ . . . ⊂ σ n defined as follows (See also Figure 2): 2 , n-1 2 + 1), . . . , (1, n-1 2 + 1, n-1 2 + 1)} if n is odd Note that sign( σ i ) = (-1) i+1 and if σ is a (dim( σ i ) -1) face of σ i different from σ i-1 , then sign( σ) = sign( σ i ).

We have established above (Claim 5.2) that ψ(σ n ) contains at least one (n -1)-dimensional simplex s with c(s) = C n , where C n is the a set of n opinions. By applying the same reasoning as in Claim 5.2, considering simplexes σ 1 , . . . , σ n instead, one can show that ψ( σ n ) contains a (n -1)dimensional simplex s colored with a set C n ⊆ U of size n. Since sign( σ n ) = (-1) n+1 = -sign(σ n ), C n = C n (Claim 5.1), from which we conclude that |U | ≥ n + 1.

Conclusion

We have investigated the minimum number of opinions needed to monitor (n, k)-set agreement, or equivalently, to monitor language L n,k . We have shown that this number is related to the alternation number as follows: #opinion(L n,k ) = #altern(L n,k ) = 2k + 1 if #altern(L n,k ) < n and n + 1 otherwise.

Several problems remain open for future research including:

1. Non-id-oblivious interpretation. In our settings, the interpretation is id-oblivious in the sense that it does not take into account for each opinion the ids of the processes that output this opinion. We do not know if taking into account the identities could help reducing the number of opinions.

2.

A general lower bound. In the case of (n, k)-set agreement, the alternation number is a lower bound on the minimum number of opinions. On the other hand, [START_REF] Fraigniaud | On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems[END_REF] shows that any language with opinion number α can be monitored with O(α) opinions. It would be interesting to generalize the lower bound to other languages or to find a language that can be monitored with strictly fewer opinions than its alternation number.

3. Generalization to long-lived computation. In our setting, one output per process is produced the distributed monitor must check that the set of outputs produced is correct. It would of course be interesting to extend our results to the case where a sequence of outputs is produced.

Summarizing, we have shown that Since v∈V deg(v) is even, and deg(u) is odd, there must exist an odd number of n-simplexes whose set of labels strictly contains B. Therefore, for some x ∈ U \ B, the number of n-simplexes σ ∈ K such that f (σ) = B ∪ {x} is odd.

Figure 1 :

 1 Figure 1: Opinion-maker for (n, k)-set-agreement, k ≤ n 2 .

3 σ3Figure 2 :

 32 Figure 2: The simplexes σ 1 ⊂ σ 2 ⊂ σ 3 , and σ 1 ⊂ σ 2 ⊂ σ 3 and their sign.

Figure 3 :

 3 Figure 3: Proof strategy.

σ 2i- 1 =

 1 {(2, (1, 1)),(3, (1, 2)),[START_REF] Bauer | Decentralised LTL monitoring[END_REF], (2, 2)), . . . , (2i -1, ((i -1), i)), (2i, (i, i))}, for 1 ≤ i ≤ n 2 , σ 2i = {(2, (1, 1)), (3, (1, 2)), (4, (2, 2)), . . . , (2i, (i, i)), (2i + 1, (i, i + 1))}, for 1 ≤ i ≤ n -1 2 , σ n = {(2, 1, 1), (3, 1, 2), (4, 2, 2), (n, n 2 , n 2 ), . . . , (1, n 2 , n 2 + 1)} if n is even {(2, 1, 1), (3, 1, 2), (4, 2, 2), (n, n-1

  v∈V deg(v) = deg(u) + {σ ∈ K, dim(σ) = n and B f (σ)} + 2 {σ ∈ K, dim(σ) = n and B = f (σ)} .

Identities are equal to processes indexes. That is, the identity of process pi is i.

Language L is projection-closed if and only if for each s ∈ L and each s ′ ⊂ s, s ′ ∈ L.

* This work was supported in part by ECOS-nord project M12M01. † Additional supports from the ANR project DISPLEXITY, and from the INRIA project GANG. ‡ Additional support from UNAM-PAPIIT project and CONACYT LAISLA. § Additional support from ANR project DISPLEXITY.

(I, O, ∆), in any execution, the final states can be mapped to decision values in such a way that the output set is allowed for the input set of the execution according to ∆. As considering only a subset of all possible executions might be sufficient to derive an impossibility result, we obtain the following necessary condition for read/write wait-free solvability of tasks: Theorem 5.1 ([2], Theorem 5.10). Let T = (I, O, ∆) a task. If there is a read/write waitfree protocol which solves T , then there is a chromatic divided image I * of I and a id-preserving simplicial map δ from I * to O that agrees with ∆.

A variant of Sperner's Lemma

Given a function f : V (K) -→ U , for each σ = {v 0 , . . . , v ℓ } simplex of K, f (σ) denote the set of labels of the vertexes of σ by f , i.e., f (σ) = {f (v 0 ), . . . , f (v ℓ )}. The proof can be found in appendix A.

Lemma 5.2. Let K be a n-pseudomanifold, let U be a set of at least n + 1 elements and let f : V (K) → U . If for some subset B ⊂ U of size n, there is an odd number of B-labeled (n -1)simplexes in the boundary of K, then there is an odd number of C-labeled n-simplexes in K, for some set Proof. Recall that in the (n, k)-set agreement task, each process starts with a value from some set V and is required to decide an initial value of some process such that no more than k distinct values are decided. For the proof, we assume without loss of generality that V = {0, . . . , k}.

The lower bound

The proof is by contradiction. We assume that there exists a monitor (M, µ) with opinion set U, |U | < min{n, 2k}+1. The opinion-maker M is a wait-free protocol. In any of its executions, each participating process i starts with a pair (s i , t i ) ∈ V × V and is directed to decided a value u i ∈ U . The interpretation µ defines a partition (Y, N) of all the multisets with values in U ; the multiset of decided values belongs to Y if and only if the set of initial pairs (s i , t i ) verify the specification of (n, k)-set agreement.

M is therefore a wait-free protocol for the task T = (I, U , ∆ µ ) where I = complex(V × V, n), U = complex(U, n). Given any finite set X, complex(X, n) is the (n -1)-dimensional pseudosphere [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF] complex induced by X: for each i ∈ [n] and each x ∈ X, there is a vertex labeled (i, x) in the vertex set of complex(X, n) and s = {(id 1 , x 1 ), . . . , (id ℓ , x ℓ )} is a simplex of complex(X, n) if and only if {x 1 , . . . , x ℓ } ⊆ X and s is properly colored with identities. The relation ∆ µ is defined next.

Each simplex s = {v 1 , . . . , v ℓ } of I represents the initial and decided values of the participating processes in some execution of a (n, k)-set agreement protocol. In more details, each vertex v j has two labels: an id id j , a pair (s i , t i ) ∈ V × V representing the process input and output value for the (n, k)-set agreement tasks. Let us define two predicates, agree k (s) and valid(s), that are verified A A variant of Sperner's Lemma Lemma 5.2. Let K be a n-pseudomanifold, let U be a set of at least n + 1 elements and let f : V (K) → U be a function that labels each vertex of K with an elements of U .

Suppose that, for some subset B ⊂ U of size n, the number of B-labeled (n -1)-simplexes in the boundary of K is odd. Then exists a set

Proof. The proof follows the proof of Sperner's Lemma [START_REF] Henle | A Combinatorial Introduction to Topology[END_REF], we construct a graph G = (V, E). We associate a vertex denoted v σ to each n-simplex σ ∈ K. In addition V contains an "external" vertex u which is not associated with any simplex of K. That is,

For every pair σ, σ ′ of n-simplexes of K, there is an edge between v σ and v σ ′ if and only if σ and σ ′ share a (n -1)-dimensional face and this face is labeled B, i.e.,

Similarly, for every n-dimensional simplex σ ∈ K, there is an edge between the external vertex u and v σ if and only if an σ has an (n -1)-dimensional face in the boundary of K labeled B:

Let σ be a n-simplex of K. It follows from the definition of the graph G and the fact that K is an n-pseudomanifold that:

Indeed, in the first case σ has exactly one (n -1)-dimensional face τ labeled B. This face is either in the boundary of K, and thus v σ share and edge with the external vertex u, or is in the interior of K. In the former case, since K is a pseudomanifold, τ is a face of exactly one n-simplex σ ′ = σ, and hence {v σ , v σ ′ } is an edge of G. If f (σ) = B, exactly two (n -1)-dimensional faces of σ are labeled B. By the same reasoning, it follows that deg(v σ ) = 2.

The edges of G with endpoint u are induced by the (n -1)-dimensional simplexes of ∂K that are labeled B. Indeed, as K is a n-pseudomanifold, a (n -1) simplex τ ∈ ∂K is a face of exactly one n-simplex σ of K. Thus, if f (τ ) = B, there is an edge between u and v σ . Therefore, the degree of u is the number of B-labeled (n -1)-simplexes of ∂K. By assumption there is a odd number of such simplexes: deg(u) is odd .