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

Sergio Rajsbaum
email: rajsbaum@im.unam.mx

Corentin Travers
email: travers@labri.fr

On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems *

Decentralized runtime monitoring involves a set of monitors observing the behavior of system executions with respect to some correctness property. It is generally assumed that, as soon as a violation of the property is revealed by any of the monitors at runtime, some recovery code can be executed for bringing the system back to a legal state. This implicitly assumes that each monitor produces a binary opinion, true or false, and that the recovery code is launched as soon as one of these opinions is equal to false. In this paper, we formally prove that, in a failure-prone asynchronous computing model, there are correctness properties for which there is no such decentralized monitoring. We show that there exist some properties which, in order to be monitored in a wait-free decentralized manner, inherently require that the monitors produce a number of opinions larger than two. More specifically, our main result is that, for every k, 1 ≤ k ≤ n, there exists a property that requires at least k opinions to be monitored by n monitors. We also present a corresponding distributed monitor using at most k + 1 opinions, showing that our lower bound is nearly tight.

Introduction

Runtime verification is concerned with monitoring software and hardware system executions. It is used after deployment of the system for ensuring reliability, safety, and security, and for providing fault containment and recovery. Its essential objective is to determine, at any point in time, whether the system is in a legal or illegal state, with respect to some specification. Consider a distributed system whose execution is observed by one or several monitors. Passing messages to a central monitor at every event leads to severe communication and computation overhead. Therefore, recent contributions [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] on runtime verification of distributed systems focused on decentralized monitoring, where a set of n monitors observe the behavior of the system. 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. For example, the recovery code can reboot the system, or release its resources. This framework implicitly assumes that each monitor i produces a binary opinion o i ∈ {true, false}, and that the recovery code is launched as soon as one of these opinions is equal to false. In this paper, we formally prove that, in a crash-failure prone asynchronous wait-free computing model [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF], there are correctness properties for which such decentralized monitoring does not exist, even if we let the number of opinions grow to an arbitrary constant k ≥ 2.

Let us consider the following motivating example arising often in practice [START_REF] Bauer | Comparing LTL semantics for runtime verification[END_REF], of a system in which requests are sent by clients, and acknowledged by servers. The system is in a legal state if and only if [START_REF] Afek | Atomic snapshots of shared memory[END_REF] all requests have been acknowledged, and (2) every received acknowledgement corresponds to a previously sent request. Each monitor i is aware of a subset R i of requests that has been received by the servers, and a subset A i of acknowledgements that has been sent by the servers. To verify legality of the system, each monitor i may communicate with other monitors in order to produce some opinion o i . In the traditional setting of decentralized monitoring mentioned in the previous paragraph, it is required that the monitors produce opinions o i ∈ {true, false} such that, whenever the system is not in a legal state, at least one monitor produces the opinion false.

In runtime monitoring, a correctness property is described by a formula in some temporal logic. In this paper, we abstract away the logic, and directly specify the property by the set of legal configurations of the system, that we call a distributed language, denoted by L. For instance, in the request-acknowledgement example above, L is the set of all configurations {(r i , a i ), i ∈ I} such that ∪ i∈I r i = ∪ i∈I a i , where I ⊆ [1, n]. Indeed, this language is specifying that all observed requests have been acknowledged, and every observed acknowledgement corresponds to a previously sent request. The monitors must produce opinions enabling to distinguish the legal configurations, i.e., those in L, from the illegal ones. In order to make up their opinions, the monitors are able to communicate among themselves, so that each monitor can potentially collect system observations of other monitors. Since we are mostly interested in lower bounds, we ask very little from the monitors, and simply require that, for any pair (C, C ′ ) of configurations with C ∈ L and C ′ / ∈ L, the multiset of opinions produced by the monitors given the legal configuration C must be different from the multiset of opinions given the illegal configuration C ′ .

In the centralized setting, more than two logical values may be required to avoid evaluating prematurely the correctness of a property that cannot be decided solely based on a prefix of the execution, like request-acknowledgement. Hence [START_REF] Arafat | Runtime verification revisited[END_REF][START_REF] Bauer | Monitoring of real-time properties[END_REF] extended linear temporal logic (LTL) to logics with three values (e.g., {true, false, inconclusive}). More recently, it was recognised [START_REF] Bauer | Comparing LTL semantics for runtime verification[END_REF] that even three values are not sufficient to monitor some properties, and thus extensions of LTL with four logical values (e.g., {true, false, probably true, probably false}) were introduced. In this paper we argue that, in an asynchronous failure-prone decentralized setting, even four values may not be sufficient.

Our results. We consider decentralized monitoring in the wait-free setting [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF]. (See Section 2 for details about this model, and for the reasons why we chose it). Our main result is a lower bound on the number of opinions to be produced by a runtime decentralized monitor in an asynchronous system where monitors may crash. This lower bound depends solely on the language, i.e., on the correctness property being monitored. More specifically, we prove that, for any positive integer n, and 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. This result holds whatever the system does with the opinions produced by the monitors. That is, our lower bound on the number of opinions is inherent to the language itself -and not to the way the opinions are handled in order to launch the recovery code to be executed in case the system misbehaves.

The number of opinions required to runtime monitor languages in a decentralized manner is actually tightly connected to an intrinsic property of each language: its alternation number. This parameter essentially captures the number of times a sequence of configurations of the system alternates between legal and illegal. Our main result states that, for any k, 1 ≤ k ≤ n, there exists a language with alternation number k which requires at least k opinions to be monitored by n monitors. This bound is essentially tight, as we also design a distributed monitor which, for any k, 1 ≤ k ≤ n, and any distributed language L with alternation number k, monitors L using at most k + 1 opinions in systems with n monitors.

Technically, in this paper, we establish a bridge between, on the one hand, runtime verification, and, on the other hand, distributed computability. Thanks to this bridge, we could prove our lower bound using arguments from (elementary) algebraic topology. More specifically, our impossibility result for 2 opinions is obtained using graph-connectivity techniques sharing similarities with the FLP impossibility result for consensus [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF], while our general impossibility result uses higherdimensional techniques similar to those used in set agreement impossibility results e.g. [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF][START_REF] Herlihy | The topological structure of asynchronous computability[END_REF].

As far as we know, this paper is the first one studying necessary conditions for monitoring distributed systems with failures.

Related work.

The main focus in the literature is on sequential runtime verification. The monitors are event-triggered [START_REF] Kupferman | Model checking of safety properties[END_REF], where every change in the state of the system triggers the monitor for analysis. There is work also in time-triggered monitoring [START_REF] Bonakdarpour | Sampling-based runtime verification[END_REF], where the monitor samples the state of the program at regular time intervals. Parallel monitoring has been addressed in [START_REF] Ha | A concurrent dynamic analysis framework for multicore hardware[END_REF] to some extent by focusing on low-level memory architecture to facilitate communication between application and analysis threads. The concept of separating the monitor from the monitored program is considered in, e.g., [START_REF] Zhu | Predictable runtime monitoring[END_REF]. Later, [START_REF] Berkovich | Gpu-based runtime verification[END_REF] uses a specialized parallel architecture (GPU), to implement runtime formal verification in a parallel fashion. Efficient automatic signaling monitoring in multi-core processors is considered in [START_REF] Chauhan | A distributed abstraction algorithm for online predicate detection[END_REF].

Closer to our setting is decentralized monitoring. In sequential runtime verification one has to monitor the requirement based on a single behavioral trace, assumed to be collected by some global observer. A central observer basically resembles classical LTL monitoring. In contrast, in decentralized monitoring, there are several partial behavioural traces, each one collected at a component of the system. Intuitively, each trace corresponds to the view that the component has of the execution. In decentralized LTL monitoring [START_REF] Bauer | Decentralised LTL monitoring[END_REF] a formula φ is decomposed into local formulas, so monitor i evaluates locally φ i , and emits a boolean-valued opinion. In our terminology, an "and interpretation" is used. That is, it is assumed a global violation can always be detected locally by a process. In addition, it is assumed the set of local monitors communicate over a synchronous bus with a global clock. The goal is to keep the communication among monitors minimal. In [START_REF] Sen | Efficient decentralized monitoring of safety in distributed systems[END_REF] the focus is in monitoring safety properties of a distributed program's execution, also using an "and interpretation". The decentralized monitoring algorithm is based on formulae written in a variant of past time LTL. For the specific case of relaxed memory models, [START_REF] Burnim | Sound and complete monitoring of sequential consistency for relaxed memory models[END_REF] presents a technique for monitoring that a program has no executions violating sequential consistency. There is also work [START_REF] Genon | Monitoring distributed controllers: When an efficient LTL algorithm on sequences is needed to model-check traces[END_REF] that targets physically distributed systems, but does not focus on distributed monitoring.

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]. We extend this previous work in two ways. First, we remove the restriction that the monitors can produce only two opinions. Second, [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF] investigated applications to locality, while here we extend the framework and adapt it to be able to apply it to a more general decentralized monitoring setting.

Related work in the distributed computing literature includes seminal 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 [START_REF] Awerbuch | Distributed Program Checking: A Paradigm for Building Self-stabilizing Distributed Protocols (Extended Abstract)[END_REF] for distributed program checking in the context of self-stabilization.

Organization of this paper. The distributed system model is in Section 2. Distributed languages and wait-free monitoring are presented in Section 3. In Section 4 we present the example of monitoring leader election. Our main result is in Section 5. Its proof is presented in Section 6. We conclude the paper and mention some open problems in Section 7.

Distributed system model

There are many possible computation and communication models for distributed computation.

Here we assume wait-free asynchronous processes that may fail by crashing, communicating by reading and writing a shared memory. This model serves as a good basis to study distributed computability: results in this model can often be extended to other popular models, such as when up to a fixed number of processes can crash (in a dependent or independent way). Also, message-passing, or various networking models that limit direct process-to-process connectivity, are essentially computationally equivalent or less powerful than shared memory. We recall here the main features of the wait-free model, and refer to textbooks such as [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] for a more detailed description, as well as for the relation to other distributed computing models.

The asynchronous read/write shared memory model assumes a system consisting of n asynchronous processes. Let [n] = {1, . . . , n}. We associate each process to an integer in [n]. Each process runs at its own speed, that may vary along with time, and the processes may fail by crashing (i.e., halt and never recover). We consider wait-free distributed algorithms, in which a process never "waits" for another process to produce some intermediate result. This is because any number of processes may crash (and thus the expected result may never be produced).

The processes communicate through a shared memory composed of atomic registers, organised as an array of n single-writer/multiple-reader (SWMR) registers, one per process. Register i ∈ [n] supports the operation read() that returns the value stored in the register, and can be executed by any process. It also support de operation write(v) that writes the value v in the register, and can be executed only by process i.

In our algorithms we use a snapshot operation by which a process can read all n SWMR registers, in such a way that a snapshot returns a copy of all the values that were simultaneously present in the shared memory at some point during the execution of the snapshot operation (snapshots are linearizable). Snapshots can be implemented by a wait-free algorithm (any number of processes may crash) using only the array of n SWMR registers [START_REF] Afek | Atomic snapshots of shared memory[END_REF] (see also textbooks such as [START_REF]Concurrent Programming -Algorithms, Principles, and Foundations[END_REF]). Thus, we may assume snapshots are available to the processes, without loss of generality. The algorithms are simplified, as well as the proofs of our theorems, without modifying the outcomes of our results.

In a distributed algorithm each process starts with an input value, repeats a loop N times, consisting of writing to its register, taking a snapshot and making local computations1 . At the end each process produces an output value. In a step, a process performs an operation on the registers (i.e., writes or snapshots). A configuration completely describes the state of the system. That is, a configuration specifies the state of each register as well as the local state of each process. An execution is a (finite) sequence of alternating configurations and steps, starting and ending in a configuration. A process participates in an execution if it takes at least one step in the execution. We assume that the first step of a process is a write, and it writes its input.

3 Distributed languages and wait-free monitoring

Distributed languages

Let A be an alphabet of symbols, representing the set of possible values produced by some distributed algorithm to be monitored. Each process i ∈ [n] has a read-only variable, input i , initially equal to a symbol ⊥ (not in A), and where the value to be monitored is deposited. We consider only the simplest scenario, where these variables change only once, from the value ⊥, to a value in A. The goal is for the processes to monitor that, collectively, the values deposited in these variables are correct.

Formally, consider an execution C 0 , s 1 , C 1 , . . ., where each C i is a configuration and each s i is a step (write or snapshot) by some process, and C 0 is the initial configuration where all SWMR registers are empty. We assume the first step by a process i is to write its input, and is taken only once its variable input i is initialized to a value in A. Thus, s 1 is a write step by some process.

The correctness specification to be monitored is usually stated as a global predicate in some logic (e.g. [START_REF] Chauhan | A distributed abstraction algorithm for online predicate detection[END_REF][START_REF] Cooper | Consistent detection of global predicates[END_REF]). We rephrase the predicate in terms of what we call a distributed language. An instance over alphabet A (we may omit A when clear from the context) is a set of pairs s = {(id 1 , a 1 ), . . . , (id k , a k )}, where {id 1 , . . . , id k } ⊆ [n] are distinct process identities, and a 1 , . . . , a k are (not necessarily distinct) elements of A. A distributed language L over the alphabet A is a collection of instances over A. Given a language L, we say that an instance s is legal if s ∈ L and illegal otherwise.

Let s = {(id 1 , a 1 ), . . . , (id k , a k )} be an instance over A. We denote by ID(s) the set of identities in s, ID(s) = {id 1 , . . . , id k }. The multiset of values in s is denoted by val(s) (formally, a function that assigns to each a ∈ A a non-negative integer specifying the number of times a is equal to one of the a i in s).

Note that an instance s can describe an assignment of values from A to the input variables of a subset of processes. More precisely, consider an execution C 0 , s 1 , C 1 , . . . , s k , C k , k ≥ 1. Suppose the processes that have taken steps in this execution are those in P , P ⊆ [n]. This execution defines the instance s = {(id 1 , a 1 ), . . . , (id k , a k )} over A, where ID(s) = P and a i is the first value written by process id i . A configuration C k also defines an instance, given by the input variables of processes that have written at least once (from the local state of a process, one can deduce if it has already executed a write operation).

An execution is correct if and only if its instance s is in L. If the execution is correct, then processes in ID(s) have values as specified by the language (and the other processes have not yet been assigned a value or may be slow in announcing their values).

Consider for example the language req-ack, which captures a simplified version of the requestacknowledgment problem mentioned in the introduction, in which no more than q requests are sent by the clients. Requests and acknowledgments are identified with integers in [q]. A process id i may know of some subset of requests r i ⊆ [q], and some subset of acknowledgments a i ⊆ [q]. The language req-ack over alphabet A = 2 [q] × 2 [q] is defined by instances s as follows

s = (id 1 , (r 1 , a 1 )), . . . , (id k , (r k , a k )) ∈ req-ack ⇐⇒ 1≤i≤k r i = 1≤i≤k a i .
For each process i, the sets r i and a i denote the (possibly empty) sets of requests and acknowledgments, respectively, that process i is aware of. An instance is legal if and only if every request has been acknowledged.

As another example, consider leader election, for which it is required that one unique process be identified as the leader by all the other processes. This requirement is captured by the language leader defined over A = [n] as follows:

s = {(id 1 , ℓ 1 ), . . . , (id k , ℓ k )} ∈ leader ⇐⇒ ∃i ∈ [k] : id i = ℓ 1 = • • • = ℓ k . ( 1
)
An instance is legal if and only if all the processes agree on the identity ℓ of one of them.

Decentralized monitoring

Monitoring the correctness specified by a language L involves two components: an opinion-maker M , and an interpretation µ. The opinion-maker is a distributed algorithm executed by the processes enabling each of them to produce an individual opinion about the validity of the outputs of the system. We call the processes running this algorithm monitors, and the (finite) set of possible individual opinions U , the opinion set.

The interpretation µ specifies the way one should interpret the collection of individual opinions produced by the monitors about the validity of the monitored system. We use the minimal requirement that the opinions of the monitors should be able to distinguish legal instances from illegal ones according to L. Consider the set of all multi-sets over U , each one with at most n elements. Then µ = (Y, N) is a partition of this set. Y is called the "yes" set, and N is called the "no" set.

For instance, when U = {0, 1}, process may produce as an opinion either 0 or 1. Together, the processes produce a multi-set of at most n boolean values. We do not consider which process produce which opinion, but we do consider how many processes produce a given opinion. The partition produced by the and-operator [START_REF] Fraigniaud | Locality and checkability in wait-free computing[END_REF][START_REF] Fraigniaud | Local distributed decision[END_REF] is as follows. For every multi-set of opinions S, we set S ∈ Y if every opinion in S is 1, otherwise, S ∈ N.

Given a language L over an alphabet A, a monitor for L is a pair (µ, M ), as follows.

• The opinion-maker M is a distributed wait-free algorithm that outputs an opinion u i at every process i. The input of process i is any element a i of A (assigned to its read-only variable input i ). Each process i is required to produce an opinion u i such that: (1) every non-faulty process eventually produces an output (termination), and (2) if process i outputs u i , then we must have: u i ∈ U (validity).

• Consider any execution of M where all participating processes have decided an opinion. If the instance s corresponding to the execution is legal, i.e., s ∈ L, the monitors must produce a multiset of opinions S ∈ Y, and if the instance s is illegal, i.e., s ∈ L, then they must produce a multiset of opinions in N.

The paper focusses on the following question: given a distributed language L, how many opinions are needed to monitor L?

Opinion and alternation numbers

As stated above, we are interested in the smallest size |U | of the opinion set enabling the monitors, after the execution of some distributed algorithm, to output opinions that distinguish legal instances from illegal ones. Hence, we focus on the following parameter associated with every distributed language.

Definition 1 (Opinion number) Let L be a distributed language on n processes. The opinion number of L is the smallest integer k for which there exists a monitor (µ, M ) for L using a set of at most k opinions. It is denoted by #opinion(L).

As we shall see, there are monitors using a small number of opinions, independent of the size of the alphabet used to define L, and depending only on the number n of processes. The opinion number is shown to be related to a combinatorial property of languages, captured by the notion of alternation number. Given a language L over the alphabet A, the alternation number of L is the length of a longest increasing sequence of instances s 1 , . . . , s k with alternating legality. More formally:

Definition 2 (Alternation number) Let L be a distributed language. The alternation number of L is the largest integer k for which there exists instances s 1 , . . . , s k such that, for every i, 1 ≤ i < k, s i ⊂ s i+1 , and either

(s i ∈ L) ∧ (s i+1 / ∈ L) or (s i / ∈ L) ∧ (s i+1 ∈ L). It is denoted by #altern(L).
Clearly, the alternation number is at most n since an instance has at most n elements.

Monitoring leader election

As a warm up example, let us show that the language leader of Equation 1 can be monitored using three opinions, namely, that #opinion(leader) ≤ 3. To establish this result, we describe a monitor for leader, called traffic-light. The set of opinions consists of three values, namely {red, orange, green}. Recall that the input of each process i ∈ [n] is a value ℓ i where ℓ i ∈ [n] is supposed to be the identity of the leader. The opinion maker works as follows. Each monitor i writes its identity and it own input ℓ i in shared memory, and then reads the whole memory with a snapshot operation. The snapshot returns a set of pairs, s i = {(id j , ℓ j ), j ∈ I} for some I, that includes the values written so far in the memory. Recall that processes run asynchronously, hence a process may collect values from only a subset of all processes. Process i decides "green" if every process in s i agrees on the same leader, and the ID of the common leader is the ID of one of the processes in s i . Instead, if two or more processes in s i have distinct leaders, then process i decides "red". In the somewhat "middle" case in which every process in s i agrees on the same leader (i.e., same ID), but the ID of the common leader is not an ID of a process in s i , then process i decides "orange".

More formally, the traffic-light opinion maker uses two procedures: "agree" and "valid". Given a set s = {(id 1 , ℓ 1 ),. . . , (id k , ℓ k )} of pairs (id i , ℓ i ) ∈ [n] × [n], agree(s) is true if and only if ℓ i = ℓ j for every i, j, 1 ≤ i, j ≤ k. For a same s, valid(s) is true if and only if, for every ℓ i , 1 ≤ i ≤ k, there exists j, 1 ≤ j ≤ k such that id j = ℓ i . Each process performs the pseudo-code below:

Opinion-maker at process p with input ℓ: write (ID(p), ℓ) to p's register ; snapshot memory, to get s = {(id 1 , ℓ 1 ), . . . , (id k , ℓ k )}; if agree(s) and valid(s) then decide "green" else if agree(s) but not valid(s) then decide "orange" else decide "red".

The interpretation of the opinions produced by the monitors is the following. An opinion u i produced by process i is an element of the set U = {green, orange, red}. The opinion-maker produces a multi-set u of opinions. We define the yes-set Y as the set of all multi-sets u with no red elements, and at least one green element. Hence, N is composed of all multi-sets u with at least one red element, or with no green elements. Now, one can easily check (see Appendix A.1) that the traffic-light monitor satisfies the desired property. That is, for every set

s = {(id 1 , ℓ 1 ), . . . , (id k , ℓ k )} of pairs (id i , ℓ i ) ∈ [n] × [n]
, if u denotes the multi-set of opinions produced by the monitors, then we have

s ∈ leader ⇐⇒ u ∈ Y.
Interestingly enough, one can prove that the language leader cannot be monitored using fewer than three opinions. Namely,

Proposition 1 #opinion(leader) = 3.
Crucially, the fact that three opinions are required, and that, in particular, the opinions true and false are not sufficient, is an inherent property of the language leader, independently of the opinionmaker algorithm, and independently of the interpretation of the opinions produced by the monitors. The lower bound argument enabling to establish this result is not hard (see Appendix A.1), but uses a fundamental theorem about two-process read/write wait-free computation: the graph of executions is connected (e.g. see [START_REF] Attiya | The Combinatorial Structure of Wait-Free Solvable Tasks[END_REF]).

As we mentioned before, the number of opinions required to monitor a distributed language is strongly related to its alternation number. The sequence of instances

s 1 = {(1, 2)}, s 2 = {(1, 2), (2, 2)}, and s 3 = {(1, 2), (2, 2), (3, 3)} satisfies s 1 ⊂ s 2 ⊂ s 3 .
Moreover s 1 and s 3 are illegal, while s 2 is legal (as far as leader is concerned). We thus infer that the alternation number of leader is at least 3. In fact, it can be shown that its alternation number is exactly 3. (see Appendix A.2). Namely,

Proposition 2 #altern(leader) = 3.
Intuitively, the alternation between legal and illegal instances forces the processes to use three opinions. Given s 1 , process 1 may say that the instance is "probably illegal" (orange), while, given s 2 , process 2 may say that the instance is "potentially legal" (green). Only process 3, given s 3 , can declare that the instance is "definitively illegal" (red), no matter the number of further processes that may show up.

Main result

In this section, we state our main result, that is, a lower bound on the number of opinions needed to monitor languages with n monitors.

Theorem 1 For any n ≥ 1, and every k, 1 ≤ k < n, there exists a language L on n processes, with alternation number k, that requires at least k opinions to be monitored. For k = n, there exists a language L on n processes, with alternation number n, that requires at least n + 1 opinions to be monitored.

In other words, there are system properties which require a large number of opinions to be monitored. Before dwelling into the details of the proof of Theorem 1, we want to stress the fact that our lower bound is essentially the best that can be achieved in term of alternation number. Indeed, Theorem 1 says that, for every k, there exists a language L with alternation number k such that #opinion(L) ≥ #altern(L). We show that this lower bound is essentially tight. Indeed, we establish the existence of a universal monitor that can monitor all distributed languages using a number of opinions equal roughly to the alternation number. More specifically, we show that, for every k, and for every language L with opinion number k, we have #opinion(L) ≤ #altern(L) + 1.

Theorem 2 There exists a monitor which, for every k ≥ 1, monitors every language with alternation number k using at most k + 1 opinions.

Since the alternation number of a language on n processes is at most n, Theorem 2 yields the following.

Corollary 1 There exists a monitor which, for every n ≥ 1, monitors every language on n processes, using at most n + 1 opinions. Moreover, this monitor uses at most k + 1 opinions for every execution in which at most k processes participate.

A direct proof of Corollary 1 can be found in Appendix B. The interest of this direct proof is that it displays the flavor of some of the technical ingredients used for establishing Theorem 2. The full proof of Theorem 2 can be found in Appendix C.

It is worth noticing that the monitor of Corollary 1 has an interpretation µ which does not depend at all on the language to be monitored, not even on the number of processes involved in the language. (The same holds for Theorem 2). The opinion-maker (as well as the one for Theorem 2), does however depend on the language, but only up to a limited extent. Indeed, the general structure of the opinion-maker is independent of the language. It simply uses a black box that returns whether s ∈ L for any instance s. Apart from this, the opinion-maker is essentially independent of the language. In this sense it is universal.

The rest of the paper is dedicated to describing the main ideas of the proof of our main result.

Tasks and combinatorial topology terminology

When solving a distributed task2 , each process starts with a private input value and has to eventually decide irrevocably on an output value. (In our setting, the input value of a process is a symbol in a given alphabet A, and the output value is an opinion). A process i ∈ [n] is initially not aware of the inputs of other processes. Consider an execution where only a subset of k processes participate, 1 ≤ k ≤ n. These processes have distinct identities {id 1 , . . . , id k }, where for every

i ∈ [k], id i ∈ [n].
A set s = {(id 1 , x 1 ), . . . , (id k , x k )} is used to denote the input values, or output values, in the execution, where x i denotes the value of the process with identity id i -either an input value (e.g., a symbol in a given alphabet A), or a output value (e.g., an opinion).

The monitor task. An opinion-maker M for a language L on n processes with opinion set U , and interpretation µ = (Y, N) is a distributed wait-free algorithm that solves the following monitor task. Any instance over alphabet A is a possible assignment of inputs in A to the processes. If process i has input a i ∈ A, then i is required to produce as output an opinion u i ∈ U such that, in addition to satisfying termination and validity, it also satisfy consistency, defined as follows.

Consider any execution, where I is the set of processes that do not crash, and all others crash without taking any steps. Let s = {(id i , a i ), i ∈ I}, and let u = {u i , i ∈ I} denote the multiset of opinions that are eventually output by the processes in I. We must have:

s ∈ L ⇐⇒ u ∈ Y.
Simplices and complexes. Let s ′ be a subset of a "full" set s = {(1, x 1 ), . . . , (n, x n )}, i.e., a set s such that ID(s) = [n]. Since any number of processes can crash, all such subsets s ′ are of interest for taking into account executions where only processes in ID(s ′ ) participate. Therefore, the set of possible input sets forms a complex because its sets are closed under containment. Similarly, the set of possible output sets also form a complex. Following the standard terminology of combinatorial topology, the sets of a complex are called simplexes. Hence every set s ′ as above is a simplex. More formally, 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. In distributed computing, the simplexes (and complexes) are often chromatic, since each vertex v of a simplex is labeled with a distinct process identity i ∈ [n].

A distributed task T is formally described by a triple (I, O, ∆) where I and O are pure (n -1)dimensional complexes, and ∆ is a map from I to the set of non-empty sub-complexes of O, satisfying ID(t) ⊆ ID(s) for every t ∈ ∆(s). We call I the input complex, and O the output complex. Intuitively, ∆ specifies, for every simplex s ∈ I, the valid outputs ∆(s) for the processes in ID(s) that may participate in the computation. We assume that ∆ is (sequentially) computable.

Given any finite set U and any integer n ≥ 1, we denote by complex(U, n) the (n-1)-dimensional pseudosphere [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF] complex induced by U : for each i ∈ [n] and each x ∈ U , there is a vertex labeled (i, x) in the vertex set of complex(U, n). Moreover, u = {(id 1 , u 1 ), . . . , (id k , u k )} is a simplex of complex(U, n) if and only if u is properly colored with identities, that is id i = id j for every 1 ≤ i < j ≤ k. In particular, complex({0, 1}, n) is (topologically equivalent) to the (n -1)dimensional sphere. For u ∈ complex(U, n), we denote by val(u) the multiset formed of all the values in U corresponding to the processes in u.

Orientation-detection tasks

An oriented complex3 is a complex whose every simplex s is assigned a sign, sign(s) ∈ {-1, +1}. Given an oriented input complex, J , a natural task consists in computing distributively the sign of the actual input simplex. That is, each process is assigned as input a vertex of V (J ), and the set of all the vertices assigned to the processes forms a simplex s ∈ J . Ideally, one would like that processes individually decide "yes" if the simplex is oriented +1 and "no" otherwise. However, this is impossible in general because processes do not have the same view of the execution, and any form of non-trivial agreement cannot be solved in a wait-free manner [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]. Thus, we allow processes to express their knowledge through values in some larger set U . Definition 3 (Orientation detection task) Let J be a (n -1)-dimensional oriented complex. A task T = (J , U , ∆), with U = complex(U, n) for some set U , is an orientation detection task for J if and only if for every two s, s ′ ∈ J , and every t ∈ ∆(s) and t ′ ∈ ∆(s ′ ):

sign(s) = sign(s ′ ) ⇒ val(t) = val(t ′ ).
Hence, to detect the orientation of a simplex s, the processes i, i ∈ I ⊆ [n], occurring in a simplex s have to collectively decide a multiset val(t) = {val(i), i ∈ I} of values in U , where val(i) denotes the value decided by process i. If J is non-trivially oriented, i.e., if there exist s, s ′ ∈ J of the same dimension, with sign(s) = sign(s ′ ), then no orientation-detection tasks for J exists with |U | = 1, because one must be able to discriminate the different orientations of s and s ′ . Instead, for every oriented complex J , there exists an orientation-detection task for J with |U | = 2. To see why, consider the task T = (J , U , ∆), where U is the (n -1)-dimensional sphere, and ∆ maps every k-dimensional simplex s ∈ J with sign(s) = -1 (resp., +1) to the k-dimensional simplex t ∈ U with val(t) = {0, 0, . . . , 0} (resp., val(t) = {1, 1, . . . , 1}). However, this latter task is not necessarily wait-free solvable (i.e., solvable in our context of asynchronous distributed computing where any number of processes can crash). The complexity of detecting the orientation of an oriented complex J is measured by the smallest k for which there exists an orientation-detection task T = (J , U , ∆) that is wait-free solvable, with U = complex(U, n), and |U | = k.

In the next subsection, we show that the problem of finding the minimum-size set U for detecting the orientation of an arbitrary given oriented complex J is essentially equivalent to finding the minimum-size set of opinions U for monitoring a language L J induced by J (and its orientation).

Equivalence lemma

This section shows that the notion of monitoring and the notion of orientation-detection are essentially two sides of the same coin.

Let L be a n-process distributed language defined over an alphabet A. We define J L = complex(n, A). That is, for every collection {a 1 , . . . , a k } of at most k elements of A, 1 ≤ k ≤ n, and every k-subset {id 1 , . . . , id k } ⊆ [n] of distinct identities, {(id 1 , a 1 ), . . . , (id k , a k )} is a simplex in J L . Let us orient J L as follows. For every simplex s ∈ J L , we define:

sign(s) = +1 if s ∈ L; -1 otherwise.
Conversely, let J be a well-formed oriented complex. We say that an oriented complex J on n processes is well-formed if for every I ⊆ [n], there exists s, s ′ ∈ J with ID(s) = ID(s ′ ) = I and sign(s) = -sign(s ′ ). We set L J as the n-process language defined over the alphabet A = {+1, -1} × V (J ). That is, each element of A is a pair (σ, v) where σ is a sign in {+1, -1} and v a vertex of J . The language L J is the set of instances s = {(id 1 , (σ 1 , v 1 )), . . . , (id k , (σ k , v k ))} specified as follows:

s ∈ L J ⇐⇒ t = {(id 1 , v 1 ), . . . , (id k , v k )} is a simplex of J ,
and sign(t) = σ i for every i,

1 ≤ i ≤ k.
That is, in a legal instance, each process is assigned a vertex of some simplex t ∈ J together with the orientation of t.

We have now all ingredients to state formally the first main ingredient toward establishing Theorem 1: the equivalence between language-monitoring and orientation-detection.

Lemma 1 (Equivalence lemma)

• Let L be a n-process language. If there exists k ≥ 1 and a wait-free solvable orientation-detection task for J L using values in some set of size k, then there exists a monitor for L using at most k opinions.

• Let J be a well-formed oriented complex, and let k ≥ 1. If no orientation-detection task for J is wait-free solvable using k values, then the language L J requires at least k + 1 opinions to be monitored.

The proof of Lemma 1 can be found in Appendix D. This lemma establishes an equivalence between wait-free solving orientation-detection tasks and monitoring a language with few opinions. It can be shown that, in addition, this lemma preserves alternation numbers in the following sense. The concept of alternation number (for languages) can be similarly defined for oriented complexes: for an oriented complex J , the alternation number of J is the length of a longest increasing sequence of simplexes of J with alternating orientations. Formally: Definition 4 (Alternation number of oriented complexes) Let J be an oriented complex. The alternation number, #altern(J ), of J is the largest integer k for which there exists s 1 , . . . , s k ∈ J such that, for every i, 1 ≤ i < k, s i ⊂ s i+1 and sign(s i ) = sign(s i+1 ).

The equivalence established in Lemma 1 preserves alternation number as stated by the following result. (see proof in Appendix E):

Lemma 2 For every language L, and every well-formed oriented complex J , we have #altern(J L ) = #altern(L) and #altern(L J ) ≤ #altern(J ) + 1.

Sketch of the proof of Theorem 1

We only sketch the proof of Theorem 1. (see full proof in Appendix F). We use the correspondence between monitors and orientation-detection tasks as stated in Lemma 1, and focus on orientationdetection tasks. Given k, 1 ≤ k < n, we carefully build an oriented complex J with alternation number k -1 and shows that any orientation-detection task with input complex J cannot be solved wait-free with k -1 values or less. Therefore, by the equivalence Lemma (Lemma 1), the language L J induced by J requires at least k values to be monitored. To complete the proof, we establish that the alternation number of L J satisfies #altern(L J ) = #altern(J ) + 1 = k. (The case k = n is similar, except that we construct J with alternation number n, and #altern(L J ) = #altern(J ).).

The main challenge lies in constructing, and orienting the complex J in such a way that no orientation-detection task with input J is wait-free solvable with less than k values. One important ingredient in the proof is an adaptation of Sperner's Lemma to our setting. To get an idea of how the proof proceeds, consider a ℓ-dimensional simplex s ∈ J whose all (ℓ -1)-dimensional simplexes have sign -1, but one which has sign +1. (see Figure 1). Assume moreover that ℓ values only are used to encode the signs of these faces. Recall that any wait-free distributed algorithm induces a mapping from a subdivision of the input complex to the output complex [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF]. By Sperner's Lemma, we prove that, whatever the opinion-maker does, at least one ℓ-dimensional simplex s ′ resulting from the subdivision of s satisfies |val(s ′ )| = ℓ + 1. That is, ℓ + 1 values are used to determine the orientation of s, for every monitor (µ, M ). Appendix F addresses these technical difficulties with care.

Conclusions and future work

We investigated the minimum number of opinions needed for runtime monitoring in an asynchronous distributed system where any number of processes may crash. We considered the simplest case, where each process outputs a single value just once, and the monitors verify that the values collectively satisfy a given correctness condition. A correctness condition is specified by a collection of legal sets of these values, that may occur in an execution. Each monitor expresses its opinion about the correctness of the set of outputs, based on its local perspective of the execution. We proved lower bounds on the number of opinions, and presented distributed monitors with nearly the same number of opinions.

Many avenues remain open for future research. It would be interesting to derive a temporal logic framework that corresponds to ours, and that associates to opinions a formal meaning in the logic. In our setting the processes produce just one output and the monitors must verify that, collectively, the set of outputs produced is correct. It would of course be interesting to extend our results to the case where each process produces a sequence of output values. Also, opinions are anonymous.

The interpretation specifies which multisets of opinions indicate a violation, independently of the identities of the monitors that output them. We do not know whether or not taking into account the identities would help reducing the total number of opinions needed. Finally, it would be interesting to extend our results to other models, such as t-resilient models in which not more than t processes may fail.

A The language leader

A.1 Proof of Proposition 1

We first prove that the traffic-light monitor is correct.

Claim 1

The opinion number of leader is at most three.

Proof. Recall that in every execution, the output of the traffic-light opinion-maker is a multiset O of elements of U = {red, orange, green}. For O the interpretation is as follows:

O ∈ Y ⇐⇒ red / ∈ O ∧ green ∈ O
Consider an execution of the traffic-light opinion-maker on input s. Let O be the multiset of opinions decided by the processes.

-Suppose that red ∈ O. In that case, O ∈ N. A process p i decides red whenever at least two processes disagree on the identity of the leader. Even if the snapshot of p i is a partial view of s, the fact that other processes may show up later will not change the lack of agreement. Hence, s / ∈ L and it is correct for O to be in the "no" set.

-The absence of red in the set of colors returned by the opinion-maker indicates that all participating processes agreed on a unique leader. The absence of green would however indicate that the common leader is invalid, in the sense that its identity is not the identity of a participating process. Hence, s / ∈ L and it is correct for O to be in the "no" set N. -The composition of the presence of green with the absence of red guarantees that all participating processes have the same leader, and that at least one process noticed that the id entity of the common leader is the identity of a participating process. Hence, it is correct for O to be in the "yes" set in the presence of green with the absence of red.

Hence, three opinions suffice to monitor the language leader, independently of the number of processes.

We now prove that two opinions a and b are not sufficient to monitor the language leader, even in the case of a system with only two processes.

Claim 2

The opinion number of leader is at least three.

Proof. Assume, for the purpose of contradiction, that there exists a monitor (µ, M ) using only two opinions, {a, b}. Notice that, in contrast to the traffic-light checker where each process writes and then snapshots once, M is an opinion-maker where processes may communicate with each other by writing and reading an arbitrary (finite) number of times. In particular, executions where a process runs solo will be important below. Namely, M , being wait-free, must specify how many writes and snapshots a process p should execute while not seeing any writes by any other processes, and then what opinion to produce.

Let us then consider the five following instances: s 1 = {(p, q)}, s 2 = {(q, q)}, s 3 = {(p, r)} where r / ∈ {p, q}, s 4 = {(p, q), (q, q)}, and s 5 = {(q, q), (p, r)}, as depicted on Figure 2. Instance s 2 is legal, (the leader of q is itself) while both instances s 1 and s 3 are illegal (in both cases, the identity of the leader of p is not an identity that appears in the instance). W.l.o.g., we i s 3 s 2 s 4 s 1 s 5 l e g a l i l l e g a l legal illegal i l l e g a l (p,q) (q,q) (p,r) can assume that opinion a is output by the opinion-maker when the input is s 2 (i.e., when process q runs solo with input q), while opinion b is output when the input is s 1 or s 3 (p runs solo with either input q or r). Thus, {a} ∈ Y and {b} ∈ N. Let us then focus on the case in which the input is s 4 . This input may be represented by an edge i.e., a 1-dimensional simplex (a set of two elements, one representing process p and its input, and the other representing process q with its input). The collection of all possible inputs actually forms a graph, e.g. a complex I (a collection of simplexes closed under containment -see section 6.1 for more details about topological notions.).

The fundamental theorem of wait-free read/write computability states that the final views of the processes, on all executions of a wait-free opinion-maker can be represented by a subdivision of the input complex I [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF]. In the special case of two processes, in the case of the input s 4 , I is simply a graph consisting of one edge, and all executions of processes p and q both with input q, the final views of the opinion-maker can be represented as a path [START_REF] Attiya | The Combinatorial Structure of Wait-Free Solvable Tasks[END_REF] (its length depend on the number of operations of the opinion-maker). A final view of a process in this path is represented by a vertex, which can be coloured with the opinion decided by the corresponding process. Two vertices belong to the same edge, when the views of the processes correspond to the same execution of the opinion-maker. The endpoints of the path correspond to views in which one process runs solo, and decides an opinion without seeing the input of the other process. Thus, these two extremities of the subdivided edge s 4 are mapped to the two different values, a and b. Since the path is connected, at least one of its edges (representing one execution of the opinion-maker where p and q run) must also have its two vertices coloured with a and b. For more details about the structure of executions of two-process wait-free algorithms see [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF] Chapter 2.

A bit more formally, the colors induce a mapping from a subdivision of the input complex I to the 1-dimensional sphere complex({a, b}, 2) [START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF]. Since the two extremities of the edge s 4 are mapped to the two different values a and b, every opinion-maker returns the multiset {a, b} for at least one run of p and q on simplex s 4 . As a consequence, one must have {a, b} ∈ Y, for s 4 is legal. By the same reasoning, every opinion-maker returns the multiset {a, b} for at least one run of p and q on input simplex s 5 , which implies {a, b} ∈ N, for s 5 is not legal. This contradiction completes the proof.

A.2 Proof of Proposition 2

We show that the alternation number of leader is 3, in a system with at least three processes, p, q, r. Although the proof is not difficult, this serves as an illustration for the definition.

ii Recall that, given an instance s = {(id 1 , ℓ 1 ), . . . , (id k , ℓ k )}, we denote ID(s) = {id 1 , . . . , id k } and val(s) = {ℓ 1 , . . . , ℓ k }. Consider the following sequences of instances s 1 = {(p, q)}, s 2 = {(p, q), (q, q)}, s 3 = {(p, q), (q, q), (r, p)}, where p, q, r ∈ [n] are three distinct identities. Instance s 2 is a legal instance in which the leader of both processes p and q is q. Clearly, s 1 ⊂ s 2 ⊂ s 3 . Moreover, the sequence s 1 , s 2 , s 3 alternates between legal and illegal instances. Indeed, in s 1 , the leader of p is not in ID(s 1 ) (validity is violated), and, in s 3 , two processes do not have the same leader (agreement is violated). Therefore, according to the definition of the alternation number (Definition 2), we have: #altern(leader) ≥ 3 Conversely, let s 1 ⊂ . . . ⊂ s k be a sequence of increasing instances such that, for every i,

1 ≤ i ≤ k -1, s i ∈ leader ∧ s i+1 / ∈ leader or s i / ∈ leader ∧ s i+1 ∈ leader
Notice that val(s i ) ⊆ val(s i+1 ) and ID(s i ) ⊂ ID(s i+1 ), for every i,

1 ≤ i ≤ k -1. Assume that k ≥ 3.
Then consider the smallest i, 1 ≤ i ≤ k -1 for which we have s i ∈ leader ∧ s i+1 / ∈ leader. By definition of the sequence, i ∈ {1, 2}. Then, either at least two distinct leaders appear in s i+1 , or validity is violated in s i+1 , i.e., val(s i+1 ) ⊆ ID(s i+1 ). Instead, by construction, the instance s i is legal: every process has the same leader whose identity is in ID(s i ). Therefore, since s i ⊂ s i+1 , a leader ℓ that does not appear in

s i (ℓ / ∈ val(s i )) is elected in s i+1 (ℓ ∈ val(s i+1 )). Thus |val(s i+1 )| > |val(s i )| = 1.
It thus follow that one cannot find an instance s i+2 that contains s i+1 and such that s i+2 ∈ leader. Hence, i + 1 = k, and, as i ∈ {1, 2}, the length of the sequence is at most 3. Hence, #altern(leader) ≤ 3 which completes the proof.

B Proof of Corollary 1

We present a simple universal monitor (µ, M ) that uses at most n + 1 opinions for monitoring n-processes languages. This monitor is not adaptive to the alternation number, but to the number of participating processes (the adaptiveness to the alternation number requires significantly more work). More precisely, every opinion output in any execution of the opinion-maker M in which at most k processes participate belongs to the same set of size k + 1. The interpretation µ is dealing with multisets of opinions taken from the set

U = {(green, ℓ) : 0 ≤ ℓ ≤ ⌊n/2⌋} ∪ {(red, ℓ) : 1 ≤ ℓ ≤ ⌊(n + 1)/2⌋}. Note that |U | = n + 1.
The partition (Y, N) of N U is as follows: for any multiset u ∈ N U we define g = max{ℓ : (green, ℓ) ∈ u} and r = max{ℓ : (red, ℓ) ∈ u}. We then set: u ∈ Y ⇐⇒ g ≥ r . Then the opinion-maker works as follows:

Opinion-maker M at process p with input a: write (p, a) in memory; snapshot memory, to get s ′ = {(id 1 , a 1 ), . . . , (id k , a k )}; if s ′ ∈ L then decide (green,

⌊ |s ′ | 2 ⌋) else decide (red, ⌊ |s ′ |+1 2 ⌋).
iii Let us fix an arbitrary language L defined over the alphabet A. Consider an execution of the opinion-maker on s = {(id 1 , a 1 ), . . . , (id ℓ , a ℓ )}. That is, only processes with identities in ID(s) participate, and the input of process i ∈ ID(s) is the pair (i, a i ), where a i is an element of the alphabet A. Let us assume that every participating process outputs, and let u ∈ N U be the multiset of the opinions decided by the processes. The proof is divided in two cases according to whether s ∈ L or s / ∈ L. Denote by p the last process that takes a snapshot of the memory. Notice that p observes the full input s.

Assume first that s ∈ L. In this case, p decides (green, ⌊|s|/2⌋), and therefore (green, ⌊|s|/2⌋) ∈ u. If the color red does not appear in u, then u ∈ Y. Suppose that some process p ′ decides (red, ℓ ′ ). Then, the instance s ′ that p ′ observes in the memory is such that s ′ / ∈ L. Since the memory is read in snapshots, and since the input of the execution is s, we get that s ′ s. In particular, |s ′ | < |s| and thus ℓ ′ = ⌊(|s ′ | + 1)/2⌋ ≤ ⌊|s|/2⌋. Therefore, for each pair (red, ℓ) ∈ u, we have ℓ ≤ ⌊|s|/2⌋. Since (green, ⌊|s|/2⌋) ∈ u, we conclude that g ≥ r, and thus u ∈ Y.

Now, let us assume that s / ∈ L. As s is the instance that p observes in the memory, it decides (red, ⌊(|s| + 1)/2⌋). Therefore (red, ⌊(|s| + 1)/2⌋) ∈ u. If u does not include any pair containing the color green, then u ∈ N. Otherwise, suppose that some process p ′ decides (green, ℓ ′ ). In that case, the instance s ′ that p ′ observes is such that s ′ ∈ L. Again, since the memory is read in snapshots, and since the input of the execution is s with s / ∈ L, we get that s ′ s. In particular, |s ′ | < |s| and thus ℓ ′ = ⌊|s ′ |/2⌋ ≤ ⌊(|s| -1)/2⌋ < ⌊(|s| + 1)/2⌋. Therefore, for each pair (green, ℓ) ∈ u, we have ℓ < ⌊|s|/2⌋. Since (red, ⌊|s|/2⌋) ∈ u, we conclude that g < r, and thus u ∈ N.

C Proof of Theorem 2

We use again the equivalence between monitoring a language and solving orientation detection tasks as stated in the first bullet of the Equivalence Lemma (Lemma 1). Given a language L with #altern(L) = k, we are aiming at solving wait-free an orientation-detection task with input complex J L using at most k + 1 values. To describe this universal distributed algorithm, one needs to introduce the notion of negalternation number for the oriented complex J , which is essentially the alternation number, restricted to counting only alternations from positive simplexes to negative simplexes. More precisely, the negalternation number of an ascending chain s 1 ⊂ s 2 ⊂ . . . ⊂ s k of oriented simplexes is 1 plus the number of occurrences of an index i, 1 ≤ i ≤ k -1, such that sign(s i ) = +1 and sign(s i+1 ) = -1. The negalternation number, negalt(s), of an oriented simplex s is the maximum, taken over all ascending chains ending at s, of the negalternation numbers of these chains. The negalternation number of an oriented complex J is then defined as

negalt(J ) = max s∈J negalt(s). It follows from the definition that 2 • negalt(J ) -2 ≤ #altern(J ) ≤ 2 • negalt(J ).
For every oriented complex J with #altern(J ) = k, we define an orientation-detection task T od whose output complex uses at most k + 1 values. If #altern(J ) is even, then let us set U = {(green, 1), . . . , (green, negalt(J ) -1), (red, 1), . . . , (red, negalt(J ))} ; iv otherwise, U = {(green, 1), . . . , (green, negalt(J )), (red, 1), . . . , (red, negalt(J ))} .

The above set U does not contain more than 2 negalt(J ) values, at most two values red or green per level of negalternation, from 1 to negalt(J ). By the definition, we have 2 negalt(J ) ≤ #altern(J )+ 1 except if #altern(J ) is even, in which case we may have 2 negalt(J ) = #altern(J ) + 2. Nevertheless, in that case, U contains 2 negalt(J ) -1 values. It thus follows from the definition of U that |U | ≤ #altern(J ) + 1.

We are thus now focusing on the task T od = (J , U , ∆ od ) where U = complex(U, n), and, for every s ∈ J and every t = {(id 1 , (c 1 , ℓ 1 )), . . . , (id r , (c r , ℓ r ))} ∈ U such that ID(s) = ID(t), we have t ∈ ∆(s) if and only if max 1≤j≤r ℓ j ≤ negalt(s) and

   ∃j, 1 ≤ j ≤ r : (c j , ℓ j ) = (green, negalt(s)) if sign(s) = +1; ∃j, 1 ≤ j ≤ r : (c j , ℓ j ) = (red, negalt(s)) and ∀i, 1 ≤ i ≤ r, (c i , ℓ i ) = (green, negalt(s)) if sign(s) = -1.
Let us verify that T od is indeed an orientation-detection task. To that end, let s, s ′ ∈ J , t, t ′ ∈ U be simplexes such that t ∈ ∆(s), t ′ ∈ ∆(s ′ ), ID(s) = ID(t), ID(s ′ ) = ID(t ′ ) and sign(s) = sign(s ′ ). If negalt(s) = negalt(s ′ ), then val(t) = val(t ′ ) since, for some color c ∈ {green, red}, the pair

(c, max{negalt(s), negalt(s ′ )})
is included in one of the multisets but not in the other. Otherwise, negalt(s) = negalt(s ′ ) = ℓ, and, since sign(s) = -sign(s ′ ), it follows from the definition of ∆ od that only one of the two multisets val(t) and val(t ′ ) contains (green, ℓ).

A wait-free distributed algorithm M for T od then performs as follows:

Orientation-detector M : write (i, s i ) in memory; snapshot memory, to get s ′ ∈ J ; if sign(s ′ ) = +1 then decide (green, negalt(s ′ )) else decide (red, negalt(s ′ )).

We prove that distributed algorithm M is correct. Let s ∈ J be an oriented simplex. Assume that the processes participating in the distributed algorithm are all processes with identities in ID(s) and that they all decide. For every process p i , i ∈ ID(s), denote by (c i , ℓ i ) the value decided by p i and denote by t the simplex representing the decisions. At least one process i 0 reads s in memory. Every other process reads some simplex s ′ ⊆ s, and thus decides some pair (c, ℓ) where c ∈ {green,red} and ℓ = negalt(s ′ ) ≤ negalt(s). If sign(s) = +1, then process i 0 decides (green, negalt(s)). Hence, (green, negalt(s), i 0 ) ∈ t and thus t ∈ ∆(s). Instead, if sign(s) = -1, then process i 0 decides (red, negalt(s)). Now, every s ′ i ⊆ s with negalt(s ′ i ) = negalt(s) have sign(s ′ i ) = -1. Hence, every process p i that decides (c i , ℓ i ) with ℓ i = negalt(s) satisfies c i = red. Hence (green, negalt(s)) / ∈ t, and therefore, t ∈ ∆(s).

Let L be a language. We showed above that a wait-free solvable orientation-detection task T od = (J L , U , ∆ od ), where J L is the complex induced by L, and U = complex(U, n) for a set U of size at most #altern(J L ) + 1, can be defined. Therefore, since #altern(J L ) = #altern(L) by v Lemma 2, we get that the first bullet of the Equivalence Lemma (Lemma 1) implies that L can be monitored with at most #altern(T ) + 1 opinions.

The opinion-maker for monitoring L is the distributed algorithm M described above. A generic interpretation is described in the proof of the first bullet of Lemma 1. A more specialized interpretation µ is as follows. Given S = {(c j , ℓ j ) : c j ∈ {green,red}, ℓ j ∈ N, j = 1, . . . , r}, let maxlevel = max j=1,...,r ℓ j .

Then, S ∈ Y ⇐⇒ (green,maxlevel) ∈ S

To see that the pair (µ, M ) is indeed a monitor for L, consider an instance s. By definition of J T , s is a simplex of J L oriented +1 if and only if s is a legal instance. Assuming that every process with IDs in ID(s) decides, let t be the simplex representing the decisions in some execution of M with input s, and let S be the multiset S = val(t). By definition of ∆ od , for every (c, ℓ) ∈ S, ℓ ≤ negalt(σ) and (c, negalt(s)) ∈ S. Moreover, (green, negalt(s)) ∈ S if and only if sign(s) = +1. Therefore (green, max (c,ℓ)∈S ℓ) ∈ S, i.e., S ∈ Y, if and only if sign(s) = +1 or, equivalently, s ∈ L.

D Proof of the equivalence lemma (Lemma 1)

To establish the first statement, let L be a language defined over some alphabet A, and assume that there exists a wait-free distributed algorithm M solving the orientation-detection task T = (J L , U , ∆) using values in some set U of size k. We claim that (µ, M ) is a monitor for L where the interpretation µ is defined as follows:

Y = {val(u) | u ∈ ∆(r), r ∈ J L and sign(r) = +1} . and N = {val(u) | u ∈ ∆(r), r ∈ J L and sign(r) = -1}
If L is on n processes, then N and Y are composed of multisets with size at most n. For every instance s, we have

s ∈ L ⇐⇒ sign(s) = +1 ⇐⇒ ∀u ∈ ∆(s), val(u) ∈ Y . Similarly: s / ∈ L ⇐⇒ ∀u ∈ ∆(s), val(u) ∈ N . Therefore, if s ∈ L, then val(M (s)) ∈ Y. Similarly, if s / ∈ L, then val(M (s)) ∈ N.
As a consequence, (µ, M ) is indeed a monitor for L.

To establish the second statement of the lemma, let J be a well-formed oriented complex, let k ≥ 1, and assume that no orientation-detection task for J is wait-free solvable with k values. Then, let us consider the language L J , and assume, for the purpose of contradiction, that there exists a monitor (µ, M ) for L J using opinions in U , with |U | = k. Let A = {-1, +1} × V (J ) vi denote the alphabet over which L J is defined. Recall that the interpretation µ specifies a partition (Y, N).

In an execution of the opinion-maker M , processes receive as input element of A and decides values in U . The multiset of the decided values is in Y if the elements of A assigned to the processes form a legal instance of L J and in N otherwise. M thus solves the task T = (I, O, ∆) where

I = complex(A, n), O = complex(U, n)
and ∆ is defined as follows. For J ⊆ [n], let us set:

Y [J] = {u ∈ complex(U, n) : ID(u) = J ∧ val(u) ∈ Y} and N [J] = {u ∈ complex(U, n) : ID(u) = J ∧ val(u) ∈ N} .
For every s ∈ complex(A, n) with ID(s) = J, we then have:

∆(s) = Y [J] if s ∈ L J N [J] otherwise.
By definition of complex(A, n), for each simplex s ∈ J , there are two simplexes s + and s -in complex(A, n) except that every vertex of s + is additionally labeled +1 and every vertex of s -is additionally labeled -1. Let J + denote the complex identical to J except that vertex of J + is additionally labeled +1. Note that J + is a subcomplex of complex(A, n).

Let r, r ′ ∈ J + with sign(r) = sign(r ′ ), that is the simplexes corresponding to r and r ′ have opposite orientation in J , say sign(r) = +1 = -sign(r ′ ). Hence, r ∈ L J while r ′ / ∈ L J . Therefore, the output of the opinion-maker is in Y for r and N for r ′ . Thus, the opinion-maker M maps r and r ′ to two simplexes u and u ′ of complex(U, n) satisfying val(u) = val(u ′ ). Therefore, M also solves an orientation-detection task with input complex J and output complex complex(U, n). The fact that M is a wait-free distributed algorithm solving T is thus a contradiction with the fact that no orientation-detection tasks for J are wait-free solvable with k values. Hence, the language L J requires at least k + 1 opinions to be monitored.

E Proof of Lemma 2

Let L be a distributed language defined over the alphabet A. The fact that the oriented complex J L associated with it has the same alternation number as L directly follows from the definition of J L . To see why, recall that J L = complex(A, n) and, for every simplex s ∈ J L , we have sign(s) = +1 if and only if s ∈ L.

Let now J be a well-formed oriented complex. We show that the language L J associated with it has alternation number at most #altern(J ) + 1. Recall that language L J is defined over the alphabet A = {+1, -1} × V (J ), and an instance s = {(i 1 , (σ 1 , v 1 )), . . . , (i k , (σ k , v k ))} is legal if and only if for some σ ∈ {-1, +1}, σ i = σ for every i, 1 ≤ i ≤ k and {(i 1 , v 1 ), . . . , (i k , v k )} is a simplex of J with orientation σ. Given such an instance s, we will denote by s the simplex s = {(i 1 , v 1 )), . . . , (i k , v k )}. Let S = s 1 ⊂ . . . ⊂ s ℓ+1 be a sequence of instances with alternating legality. Let k be the index of the largest legal instance in the sequence. Note that k ∈ {ℓ, ℓ + 1}. vii As s k ∈ L J , for any pair of elements (i, (σ, v)), (i ′ , (σ ′ , v ′ )) in s k , σ = σ ′ = sign( s k ). Therefore, for any j, 1 ≤ j ≤ k and any element (i ′′ , (σ ′′ , v ′′ )) in s j , σ ′′ = sign( s k ) as s j ⊆ s k . Similarly, s j ⊆ s k and it thus follows that s j ∈ J . Consequently, if instance s j is illegal, this is because the common sign (i.e., sign( s k )) associated with each element of s j is different from the orientation of the simplex s j in J . This implies that the sequence S = s 1 ⊂ . . . ⊂ s k of increasing simplexes of J alternates between simplexes of opposite orientations. The length of S is upper-bounded by the alternation number of J , i.e., k ≤ #altern(J ). Since k ∈ {ℓ, ℓ + 1}, we conclude that #altern(L J ) ≤ #altern(J ) + 1.

F Proof of Theorem 1

Let 0 ≤ k < n. We exhibit a language for n processes with alternation number k + 1 that cannot be monitored with k + 1 or less opinions. We do not construct such a language directly but rather rely on the correspondence between monitoring languages and solving orientation-detection tasks, as stated in the second bullet of the Equivalence Lemma (cf. Lemma 1). We define and orient a complex J of dimension n -1 with alternation number k. We next show that any orientationdetection task with input complex J cannot be solved wait-free with less than k value. Then, by the Equivalence Lemma, the language L J induced by J requires at least k + 1 opinions to be monitored. To complete the proof, we show that #altern(L J ) = k + 1. That is, language L J has alternation number k + 1 and requires at least k + 1 opinions to be monitored.

We start with the definition of an oriented complex J k for k processes with #altern(J k ) = k. We establish that solving wait-free any orientation-detection task with input complex J k requires at least k + 1 values. We then extend the complex J k to form an oriented complex J for n processes without changing the alternation number, i.e., #altern(J ) = #altern(J k ). Since J k is a sub-complex of J , solving an orientation-detection task with input J also requires at least k + 1 values.

Let s k-1 and s ′ k-1 be two simplexes of dimension k-1 properly colored with identities {1, . . . , k}. Moreover, s k-1 and s ′ k-1 share a face of dimension (k -2) that we denote s k-2 . The input complex J k is the complex induced by s k-1 ∪ s ′ k-1 . That is, J k consists of the simplexes s k-1 , s ′ k-1 and each of their faces. Fix a sequence (s i ) 0≤i≤k-2 of simplexes of increasing dimension included in the common face s k-2 :

s 0 ⊂ s 1 ⊂ . . . ⊂ s k-2
Note that each simplex s i has dimension i. We assign an orientation to each simplex s of J k inductively:

∀s ∈ J k , sign(s) =        +1 if s = s 0 ; -sign(s i ) if s ⊆ s i+1 and s ⊆ s i for 0 ≤ i < n -1; -sign(s k-2 ) if s s ′ k-1 and s ⊆ s k-2 ; sign(s k-2 ) if s = s ′ k-1 .
The construction is illustrated in Figure 3 for the case k = 3. Each simplex is labeled with its orientation. To avoid cluttering the figure, identities are represented by the color of each vertex.

Note that the two simplexes of dimension (k -1), s k-1 and s ′ k-1 , have opposite orientations. Also, notice that the sequence of simplexes s 0 , . . . , s k-1 is such that s i ⊂ s i+1 and sign(s i ) = viii

s 0 +1 -1 +1 +1 s 2 +1 s ′ 2 -1 +1 +1 -1 s 1 +1 +1
Figure 3: Oriented input complex for the orientation-detection task T 3 .

-sign(s i+1 ) for each i, 0 ≤ i < k -1. Hence, the alternation number of J k is #altern(J k ) = k.

There are orientation-detection tasks with input J k that are wait-free solvable, e.g., the task (J k , J k , Id) where Id is the identity map. Next, we consider a set U and a wait-free solvable orientation-detection task T k = (J k , U , ∆) with input complex J k , where U = complex(U, n). We establish that |U | ≥ k + 1.

Claim 3 If the orientation-detection task T k = (J k , U , ∆), where U = complex(U, n), is wait-free solvable, then |U | ≥ k + 1.

To establish the claim, let A be a wait-free distributed algorithm for T k . Without loss of generality, we assume that A is a full-information distributed algorithm in normal form [START_REF] Attiya | The Combinatorial Structure of Wait-Free Solvable Tasks[END_REF][START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF]. Fullinformation means that every process writes all it knows each time it performs a write operation. A distributed algorithm is in normal form if each process p i proceeds in a sequence of rounds. In each round, p i writes to the register M [i] and reads the whole memory M . We restrict our attention to a subset of the possible executions of A, namely, immediate snapshot (IS) executions. An IS execution proceeds in rounds. Each round is specified by a non-empty set of processes, which are active in the round. A round consists of concurrent writes performed by each active process followed by concurrent snapshots of the shared memory by each active processes. IS executions capture the computing power of the wait-free read-write shared memory model [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF].

We recall some facts on representing distributed computations by combinatorial objects. Our exposition follows the framework developed in previous works, e.g., [START_REF] Attiya | The Combinatorial Structure of Wait-Free Solvable Tasks[END_REF].The distributed algorithm complex P of A gives a representation of the set of all IS executions of A. Each vertex v ∈ V (P) represents the final state of some process at the end of some IS execution of A with input some simplex s ∈ J k . Each vertex v is thus colored with an identity ID(v) ∈ [k], a state state(v), and a value µ(v) ∈ U such that is µ(v) the value decided by the process with identity ID(v) in some IS execution in which its final state is state(v). A set σ = {v 1 , . . . , v ℓ } ⊆ V (P) is a simplex of P if it is properly colored with ID and there is an IS execution of A in which the final state of ix the process with identity ID(v i ) is state(v i ), for each i, 1 ≤ i ≤ ℓ. Given a simplex s ∈ J k , the IS-complex for s, denoted P(s) is the sub-complex of P containing each simplex that corresponds to an IS execution with input s. For every s ∈ J k , P(s) is a subdivision of s, and in particular P(s) is a dim(s)-pseudomanifold [START_REF] Attiya | The Combinatorial Structure of Wait-Free Solvable Tasks[END_REF][START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF]. A ℓ-dimensional (sub-)complex C is a ℓ-pseudomanifold if it is pure for dimension ℓ and every (ℓ -1)-dimensional simplex of C is contained in one or two ℓ-dimensional simplexes of C. For every simplex σ ∈ P, the carrier of σ carrier(σ) is the simplex s ∈ J k of smallest dimension such that σ ∈ P(s).

For each simplex σ = {v 1 , . . . , v ℓ } ∈ P, denote by val(σ) = {µ(v 1 ), . . . , µ(v ℓ )} the multiset of values output in the IS execution of A corresponding to σ. As A solves an orientation-detection task with input complex J k , we have:

{µ(σ) | σ ∈ P and sign(carrier(σ)) = +1} ∩ {µ(σ) | σ ∈ P and sign(carrier(σ)) = -1} = ∅
The proof relies on the following property which is satisfied by the subdivision P and the coloring µ for every i, 0 ≤ i ≤ k -1: P i : There exists a set of i + 1 distinct colors {c 0 , . . . , c i } such that |{σ | carrier(σ) = s i and µ(σ) = {c 0 , . . . , c i }}| is odd.

Property P i means that there exists an odd number of simplexes of dimension i in the subdivided complex P(s i ) colored with the same i + 1 distinct colors by µ. The property also holds if we replace the last element of the sequence s 0 ⊂ . . . ⊂ s k-1 by s ′ k-1 , i.e.,

P ′ k-1 : There exists a set of k distinct colors {c ′ 0 , . . . , c ′ k-1 } such that |{σ | carrier(σ) = s ′ n-1 and µ(σ) = {c ′ 0 , . . . , c ′ k-1 }}| is odd.
Assume that both properties P k-1 and P ′ k-1 are true. By construction of the orientation of J k , sign(s k-1 ) = -sign(s ′ k-1 ). Hence, for every σ, σ ′ ∈ P such that carrier(σ) = s k-1 and carrier(σ

′ ) = s ′ k-1 , µ(σ) = µ(σ ′ ). Therefore, {c ′ 0 , . . . , c ′ k-1 } = {c 0 , . . . , c k-1 }, from which we conclude that |U | ≥ k + 1, as desired.
We next show by induction that P i is true for every i, 0 ≤ i ≤ k -1 and that P ′ k-1 is also satisfied. For i = 0, let c 0 be the color assigned to a vertex with carrier s 0 by µ. Since there is a unique vertex with carrier s 0 in P, P 0 is true. Fix i, 0 ≤ i ≤ k -2. Assume that P i is satisfied for some set of i + 1 distinct colors {c 0 , . . . , c i }. We consider the sub-complex P(s i+1 ) and its coloring induced by µ. The proof is similar to the proof of Sperner's Lemma. However, since the coloring of P(s i+1 ) may not be a Sperner coloring as the vertexes on the boundaries of P(s i+1 ) may be colored arbitrarily, we cannot directly apply this Lemma.

Following 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(s) to each simplex s ∈ P(s i+1 ). Then, V = {v(s) | s ∈ P(s i+1 ) and dim(s) = i + 1} ∪ {u} x where u is an external vertex, which is not associated with any simplex of P(s i+1 ).

For every pair s, s ′ of (i+1)-dimensional simplexes in P(s i+1 ), there is an edge between v(s) and v(s ′ ) if and only if s and s ′ share an i-dimensional face colored with {c 0 , . . . , c i } : ∀v

(s) = v(s ′ ) ∈ V , {v(s), v(s ′ )} ∈ E ⇐⇒ val(s ∩ s ′ ) = {c 0 , . . . , c i }
Similarly, for every (i + 1)-dimensional simplex s in P(s i+1 ), there is an edge between u and v(s) if and only if an i-dimensional face s ′ of s is colored with {c 0 , . . . , c i } and the dimension of carrier(s ′ ) is i. In other words, s has an i-dimensional face s ′ in the boundary of P(s i+1 ) and µ(s ′ ) = {c 0 , . . . , c i } : ∀v(s) ∈ V , {v(s), u} ∈ E ⇐⇒ ∃s ′ ⊂ s | dim(carrier(s ′ )) = i and val(s ′ ) = {c 0 , . . . , c i } Let s ∈ P(s i+1 ) be a simplex of dimension (i + 1). It follows from the definition of G and the fact that P(s i+1 ) is an (i + 1)-pseudomanifold that:

deg(v(s)) =    1 if {c 0 , . . . , c i } set(val(s)); 2 if {c 0 , . . . , c i } = set(val(s)); 0 otherwise.
where set(m) denotes the set formed by the elements in the multiset m. Suppose now that s has an i-dimensional face s ′ in the boundary of P(s i+1 ) , i.e., dim(carrier(s ′ )) = i. Assume in addition that val(s) = {c 0 , . . . , c i }. By construction of the orientation of J k , for each i-dimensional face t = s i of s i+1 , sign(t) = -sign(s i ). Hence, two simplexes with carrier s i and t, respectively, cannot be colored the same way by µ. Moreover, by the induction hypothesis, there exists a simplex of dimension i in P(s i ) colored {c 0 , . . . , c i } by µ. Therefore, carrier(s) = s i , and since the number of i-dimensional simplexes that belong to P(s i ) and that are colored {c 0 , . . . , c i } by µ is odd (Property P i ), it follows that: deg(u) is odd.

Note that this also holds in the case s i+1 = s ′ k-1 , since by construction, for every (k-2)-dimensional face t = s k-2 of s ′ k-1 , sign(t) = -sign(s k-2 ). Since v∈V deg(v) is even, there must exist an odd number of (i + 1)-dimensional simplexes s in P(s i+1 ) such that {c 0 , . . . , c i } set(val(s)). Therefore, for some color c i+1 ∈ U \ {c 0 , . . . , c i }, the number of simplexes s ∈ P(s i+1 ) such that val(s) = {c 0 , . . . , c i+1 } is odd, which completes the proof of P i+1 and P ′ n-1 (if i = n -2). This completes the proof of Claim 3.

Essentially, to complete the proof of Theorem 1, we extend task T k to obtain an orientationdetection task T for n processes whose input complex J contains the input complex J k of T k . Our construction does not change the alternation number and preserves the orientation of J k . So #altern(J ) = #altern(J k ), and any wait-free distributed algorithm A for T can also be used by k processes for T k , and therefore requires at least k + 1 values by Claim 3.

Claim 4 There exists an (n-1)-dimensional oriented complex J with alternation number #altern(J ) = k such that for any orientation-detection task T = (J , U , ∆), where U = complex(U, n), if T is wait-free solvable, then |U | ≥ k + 1.

xi

We define the (n -1)-dimensional oriented input complex J as follows. Let {v k+1 , . . . , v n } and {v ′ k+1 , . . . , v ′ n } be two sets of vertexes properly colored with identities {k + 1, . . . , n}, i.e., ∀i, j, k + 1 ≤ i, j ≤ n, v i = v ′ j and ID(v i ) = ID(v ′ i ) = i. Denote by s n-1 and s ′ n-1 , respectively, the simplexes s n-1 = s k-1 ∪ {v k+1 , . . . , v n } and s ′ n-1 = s ′ k-1 ∪ {v ′ k+1 , . . . , v ′ n }. J is the complex induced by s n-1 ∪ s ′ n-1 . That is, simplex s is included in J if and only if s ⊆ s n-1 ∨ s ⊆ s ′ n-1 . J is thus a complex of dimension n -1; every simplex in J is properly colored with identities ⊆ {1, . . . , n}. Moreover, J k is a sub-complex of J . For each simplex s ∈ J k , denote by sign J k (s) the orientation assigned to s in the definition of J k .

By construction, for every v i , k + 1 ≤ i ≤ n and v ′ j , k + 1 ≤ j ≤ n, no simplex s of J includes both v i and v ′ j . Notice also that each simplex s ∈ J that does not contain any vertex v i or v ′ i for any i, k + 1 ≤ i ≤ n is a simplex included in the sub-complex J k . The complex J is oriented as follows:

∀s ∈ J , sign(s) =    sign J k (s) if s ∈ J k ; sign(s k-1 ) if ∃v i , k + 1 ≤ i ≤ n | v i ∈ s; sign(s ′ k-1 ) if ∃v ′ i , k + 1 ≤ i ≤ n | v ′ i ∈ s.
The input complex for 4 processes obtained by extending of the input complex of T 3 is depicted in Figure 4. Similarly, every simplex that includes vertex v ′ 4 is oriented -1 as s ′ 2 . Other simplexes keep their original orientation, as described in Figure 3.

Let U be an arbitrary set and let U denote the complex complex(U, n). Consider an orientationdetection task T = (J , U , ∆) with input complex J . Since J k is a sub-complex of J , and each simplex s ∈ J k has the same orientation in J k and J , every wait-free distributed algorithm A for T is also a wait-free solution for the orientation-detection task T k = (J k , U , ∆). It thus follows from Claim 3 that A requires at least k + 1 colors, i.e., |U | ≥ k + 1.

xii

We next show that the alternation number of J is #altern(J ) = k. To that end, consider an arbitrary sequence t = t 0 ⊂ t 1 ⊂ . . . ⊂ t m of simplexes in J . For any sequence τ = τ 0 . . . τ j of simplexes, denote by β(τ ) the number of changes of orientation in the sequence, i.e., β(τ ) = |{i | 0 ≤ i < j and sign(τ i ) = -sign(τ i+1 )}| Let t ℓ denote the simplex in t of largest dimension that is included in J k . By construction of J , t ℓ+1 must contain either a vertex v i or a vertex v ′ i , for some i, k + 1 ≤ i ≤ n. Assume without loss of generality that v i ∈ t ℓ+1 . Since t ℓ+1 ⊂ . . . ⊂ t m , v i ∈ t j for every j, ℓ + 1 ≤ j ≤ m from which it follows that sign(t ℓ+1 ) = . . . = sign(t m ). Hence, β(t) = β(t 0 , . . . , t ℓ+1 ) ≤ ℓ + 1.

Since the dimension of J k is k -1, ℓ ≤ k -1. If ℓ < k -1, β(t) = β(t 0 , . . . , t ℓ+1 ) ≤ k -1. Otherwise, ℓ = k-1 and thus the dimension of t ℓ is k-1. The complex J k contains two simplexes of dimension k -1: s k-1 and s ′ k-1 . As t ℓ ⊂ t ℓ+1 and a vertex v i , for some i, k +1 ≤ i ≤ n, is included in t ℓ+1 , it follows from the construction of J that t ℓ = s k-1 . Thus, sign(s k-1 ) = sign(t ℓ ) = sign(t ℓ+1 ), from which we conclude that β(t) = β(t 0 , . . . , t ℓ+1 ) = β(t 0 , . . . , t ℓ ) ≤ ℓ = k -1. This complete the proof that for every sequence t 0 ⊂ . . . ⊂ t m of simplexes in J , the number of times two consecutive simplexes have opposite orientation is at most k -1. Therefore, #altern(J ) ≤ k. As J k is a subcomplex of J , and each simplex s ∈ J k has the same orientation in J k and J , #altern(J ) ≥ k. Hence #altern(J ) = k.

This completes the proof of Claim 4.

We use the Equivalence Lemma (Lemma 1) to complete the proof of the theorem. By Claim 4, there exists an (n -1)-dimensional oriented complex J with alternation number k such that any orientation-detection task with input J requires at least k + 1 values to be wait-free solvable. Therefore, it follows from the second bullet of the Equivalence Lemma (Lemma 1) that language L J requires k + 1 opinions to be monitored.

We next show that #altern(J L ) = k + 1. Recall that L J is defined over the alphabet A = {-1, +1} × V (J ). For an instance t = {(i 1 , (σ 1 , v 1 )), . . . , (i ℓ , (σ ℓ , v ℓ ))}, let t denote the simplex t = {(i 1 , v 1 ), . . . , (i ℓ , v ℓ )}. Let T = t 0 ⊂ . . . ⊂ t k a sequence of instances defined as follows. For each i, 0 ≤ i ≤ k -1, t i = s i ∈ J and for each element (id, (σ, v)) of t i , σ = sign(s i ) if i and k -1 have the same parity and σ = -sign(s i ) otherwise. t k is such that t k is a k-dimensional simplex of J containing s k-1 and there are two elements (id, (σ, v)), (id ′ , (σ ′ , v ′ )) in t k , σ = σ ′ . Note that instance t k is illegal and, for i : 0 ≤ i ≤ k -1, instance t i is legal if and only if i and k -1 have the same parity. Hence, the sequence T alternates between legal and illegal instances from which we have #altern(L J ) ≥ k + 1. As #altern(J ) = k, it follows from Lemma 2 that #altern(L J ) = k + 1, which completes the proof of the theorem for k < n.

For k = n, Claim 4 immediately follows from Claim 3 and the language L J has alternation number n = k. It requires at least n + 1 opinions to be monitored by the Equivalence Lemma. xiii

Figure 1 :

 1 Figure 1: Using Sperner's Lemma

Figure 2 :

 2 Figure 2: A partial representation of the possible inputs for monitoring leader.

Figure 4 :

 4 Figure4: Extending T 3 for 4 processes. Every simplex that includes vertex v 4 is oriented +1, the same orientation as s 2 . Similarly, every simplex that includes vertex v ′ 4 is oriented -1 as s ′ 2 . Other simplexes keep their original orientation, as described in Figure3.

If the set of possible input values is finite, all processes may execute the loop the same number of times, N (e.g. see[START_REF] Attiya | The Combinatorial Structure of Wait-Free Solvable Tasks[END_REF]).

Orientation-detection tasks, and proof of Theorem 1To establish our lower bound, we show that the design of distributed runtime monitors using few opinions is essentially equivalent to solving a specific type of tasks, that we call orientation-detection tasks. This equivalence is made explicit thanks to an equivalence lemma (Lemma 1). Introducing orientation-detection tasks requires elementary notions of combinatorial topology.

A task is the basic distributed computing problem, defined by a set of inputs to the processes and for each input to the processes, a set of legal outputs of the processes -see, e.g.,[START_REF] Herlihy | Distributed Computing Through Combinatorial Topology[END_REF].

In the case of chromatic manifolds, our definition is equivalent to usual definition of orientation in topology textbooks.

supported in part by the CONACYT-CNRS ECOS Nord M12M01 research grant. † Additional support from the ANR project DISPLEXITY, and from the INRIA project GANG. ‡ Additional support from UNAM-PAPIIT and LAISLA. § Additional support from ANR project DISPLEXITY.