Michel Raynal

Julien Stainer

Simultaneous Consensus vs Set Agreement a Message-Passing Sensitive Hierarchy of Agreement Problems

Keywords: Asynchronous system, Distributed computing, Failure detector, Fault tolerance, Message-passing system, Quorum, Reduction, k-Set agreement, Simultaneous consensus, Wait-freedom système asynchrone, calcul réparti, détecteur de fautes, tolérance aux pannes, système à passage de messages, quorum, réduction, accord k-ensembliste, consensus simultanés, sans attente

This paper investigates the relation linking the s-simultaneous consensus problem and the k-set agreement problem. To this end, it first defines the (s, k)-SSA problem which captures jointly both problems: each process proposes a value, executes s simultaneous instances of the k-set agreement problem, and has to decide a value so that no more than sk different values are decided. The paper introduces then a new failure detector class denoted Z s,k , which is made up of two components, one focused on the "shared memory object" that allows the processes to cooperate, and the other focused on the liveness of (s, k)-SSA algorithms. A novelty of this failure detector lies in the fact that the definition of its two components are intimately related. Then, the paper presents a Z s,k -based algorithm that solves the (s, k)-SSA problem, and shows that the "shared memory"-oriented part of Z s,k is necessary to solve the (s, k)-SSA problem (this generalizes and refines a previous result that showed that the failure detector Σ k is necessary to solve k-set agreement). Finally, the paper investigates the structure of the family of (s, k)-SSA problems and introduces generalized (asymmetric) simultaneous set agreement problems in which the parameter k can differ in each underlying k-set agreement instance. Among other points, it shows that, for s, k > 1, (a) the (sk, 1)-SSA problem is strictly stronger that the (s, k)-SSA problem which is itself strictly stronger than the (1, ks)-SSA problem, and (b) there are pairs (s 1 , k 1 ) and (s 2 , k 2 ) such that s 1 k 1 = s 2 k 2 and (s 1 , k 1 )-SSA and (s 2 , k 2 )-SSA are incomparable.

Introduction

The k-set agreement problems The k-set agreement problem is a paradigm of coordination problems. Defined in the setting of systems made up of processes prone to crash failures, it is a simple generalization of the consensus problem (that corresponds to the case k = 1). The aim of this problem, introduced by Chaudhuri [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF], was to investigate how the number of choices (k) allowed to the processes is related to the maximum number of processes t that can crash. The problem is defined as follows. Each process proposes an input value, and any process that does not crash must decide a value (termination), such that a decided value is a proposed value (validity), and no more than k distinct values are decided (agreement).

While it can be solved in synchronous systems prone to any number of process crashes (see [START_REF] Raynal | Fault-Tolerant Agreement in Synchronous Message-Passing Systems[END_REF] for a survey), the main result associated with k-set agreement is the impossibility to solve it in presence of both asynchrony and process crashes when t ≥ k [START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF][START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF][START_REF] Saks | Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge[END_REF].

A way to circumvent this impossibility consists in enriching the underlying pure asynchronous system with a failure detector [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF][START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF]. A failure detector is a device that provides processes with information on failures. According to the type and the quality of this information, several failure detectors have been proposed (see [START_REF] Raynal | Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results[END_REF] for a survey of failure detectors suited to k-set agreement). It has been shown that the failure detector Ω k (anti-omega-k) [START_REF] Raynal | Rump Session at 26th ACM Symposium on Principles of Distributed Computing (PODC'07)[END_REF][START_REF] Zielinski | Anti-Omega: the Weakest Failure Detector for Set Agreement[END_REF] is the weakest failure detector that allow k-set agreement to be solved despite any number of process crashes in asynchronous read/write systems [START_REF] Gafni | On Set Consensus Numbers[END_REF].

The situation is different in asynchronous crash-prone message-passing system. More precisely, (a) while weakest failure detectors are known only for the cases k = 1 and k = n-1 [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF][START_REF] Delporte-Gallet | Tight Failure Detection Bounds on Atomic Object Implementations[END_REF][START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF], (b) it has been shown that the generalized quorum failure detector denoted Σ k is necessary [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF]. k-Set agreement algorithms based on failure detectors stronger than Σ k can found in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF][START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF][START_REF] Mostéfaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF][START_REF] Mostéfaoui | Relations Linking Failure Detectors Associated with k-Set Agreement in Message-Passing Systems[END_REF][START_REF] Mostéfaoui | Chasing the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems[END_REF].

The s-simultaneous consensus problem This problem has been introduced in [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF]. Each of the n processes proposes the same value to s independent instances of the consensus problem, denoted 1, ..., s. Each correct process has to decide a pair (c, v) (termination), where c ∈ {1, ..., s} is a consensus instance and v is a proposed value (validity). Moreover, if (c, v) and (c, v ′ ) are decided we have v = v ′ (agreement). (This is the scalar form of the problem: each process proposes the same value to each consensus instance. In the vector form, a process proposes a vector of s values, one value to each consensus instance. It is shown in [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF] that both forms have the same computational power).

It is shown in [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF] that the x-simultaneous consensus problem and the x-set agreement problem are computationally equivalent in asynchronous read/write systems where up to t = n -1 processes may crash. It follows that in these systems, the failure detector Ω x is both necessary and sufficient to solve x-simultaneous consensus.

As far asynchronous message-passing systems are concerned, it is shown in [START_REF] Bouzid | Simultaneous Consensus is Harder than Set Agreement in Message-Passing[END_REF] that, for x > 1 and t > n+x-2

2

, xsimultaneous consensus is strictly stronger than x-set agreement. This means that, differently from what can be done in asynchronous read/write systems, it is not possible to solve x-simultaneous consensus from a black box solving x-set agreement.

Content of the paper The aim of this paper is to (a) better understand the relations linking s-simultaneous consensus and k-set agreement, and (b) near the weakest failure detector that allows k-set agreement to be solved in crash-prone asynchronous message-passing system.

To this end, the paper introduces first a problem that generalizes both s-simultaneous consensus and k-set agreement. This problem, denoted (s, k)-SSA (for s-Simultaneous k-Set Agreement) consists in s independent instances of the k-set agreement problem (hence, (s, 1)-SSA is x-simultaneous consensus, while

(1, k)-SSA is k-set agreement).
Then, the paper introduces a new failure detector, denoted Z s,k , that allows (s, k)-SSA to be solved in the asynchronous message-passing communication model, despite any number of process crashes. This failure detector is captured by an array of size s whose each entry is made up of two components. The first, which is nothing else than the quorum failure detector Σ k , addresses the data sharing needed to correctly coordinate the processes. The second component states a leader-based property that allows the correct processes to always decide a value. When considering the (1, k)-SSA problem, it appears that Z 1,k is a weaker failure detector than all the failure detectors proposed so far to solve k-set agreement. A noteworthy feature of Z s,k lies in the fact that these two components are not defined independently one from the other (e.g., as done in the pair (Σ, Ω) [START_REF] Delporte-Gallet | Tight Failure Detection Bounds on Atomic Object Implementations[END_REF]), namely, the definition of the leader component of some entry of the array is intimately related to the associated quorum component.

The paper presents then a Z s,k -based algorithm that solves the (s, k)-SSA problem, and shows that the quorum part of Z s,k is necessary to solve the (s, k)-SSA problem (this proof generalizes the proof given in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF] that shows that Σ k captures information on process crashes that is necessary to solve k-set agreement).

Last but not least, the paper considers the family of asymmetric {k 1 , ..., k s }-SSA problems, defined by s simultaneous instances of the k x -set agreement problem where k x = k 1 , ..., k s . It shows that these problems define a strong hierarchy from a computability point of view. It follows from this hierarchy that (as indicated in the abstract) for s, k > 1, (a) the (sk, 1)-SSA problem is strictly stronger that the (s, k)-SSA problem which is itself strictly stronger than the (1, ks)-SSA problem, and (b) there are pairs (s 1 , k 1 ) and (s 2 , k 2 ) such that s 1 k 1 = s 2 k 2 and (s 1 , k 1 )-SSA and (s 2 , k 2 )-SSA are incomparable problems. More generally, given K, the paper shows that the structure of the set of symmetric (s, k)-SSA problems (where sk = K) is a lattice where an arrow from A to B means that B can be solved from a block box solving A, but not vice-versa. The paper associates also with each such pair a failure detector that is necessary to solve A and a failure detector that is sufficient to solve B.

Roadmap

The paper is made up of 6 sections. Section 2 defines the computation model, the (s, k)-SSA problem, and the Failure Detector class Z s,k . Section 3 presents a simple Z s,k -based algorithm that solves the (s, k)-SSA problem. Section 4 proves that the safety part of Z s,k is necessary when one wants to solve the (s, k)-SSA problem (from information on failures). Section 5 investigates the graph structure of the family of asymmetric SSA problems and shows that these problems define a strong hierarchy. Finally Section 6 concludes the paper.

2 Computation Model, (s, k)-SSA Problem, and the Failure Detector Z s,k

Computation model

Process model

The system is made up of n asynchronous sequential processes denoted Π = {p 1 , . . . , p n } (to simplify notations, we sometimes consider that Π is the set {1, . . . , n}). Each process is a Turing machine enriched with two operations, which allows it to send and receive messages. "Asynchronous" means that there is no assumption on the speed of processes: each process proceeds at its own speed, which may arbitrarily vary and is unknown from the other processes.

A process behaves correctly until it possibly crashes (a crash is an unanticipated premature stop). Up to t < n processes may crash. The case t = n -1 defines the wait-free model. A process that crashes in a run is said to be faulty in that run, otherwise, it correct. Given a run, C denotes the set of processes which are correct in that run.

Communication model Each pair of processes is connected by a bidirectional channel. The channels are failurefree (no creation, duplication, alteration, or loss of messages), and asynchronous. "Asynchronous" means that, while each message is received, there is no bound on message transfer delays.

Timing model

The underlying timing model is the set of natural integers N. As the system is asynchronous, this time notion remains unknown to the processes. It is only used, from an external observer point of view, to state or prove properties. Time instants are denoted τ , τ ′ , etc. Notation The previous system is denoted AMP n,t [∅]. Hence, AMP n,n-1 [∅] denotes the wait-free messagepassing model.

The s-Simultaneous k-Set Agreement -(s, k)-SSA-Problem

As indicated in the introduction, the s-simultaneous k-set agreement problem (in short (s, k)-SSA) consists in the simultaneous execution of s instances of the k-set agreement problem. Moreover, each process proposes the same value to each instance of the k-set agreement problem. The (s, k)-SSA problem is defined by the three following properties.

• Termination. Every correct process decides. • Validity. A decided value is a pair (c, v) where 1 ≤ c ≤ s and v is a value proposed by a process.

• Agreement. For any c ∈ {1, ..., s}, there are at most k different values v such that (c, v) is decided.

It is easy to see that at most K = sk different values v are decided, and consequently, any algorithm solving the (s, k)-SSA problem solves the K-set agreement problem. Moreover, (1, k)-SSA is k-set agreement, while (s, 1)-SSA is s-simultaneous consensus.

The Failure Detector Class Z s,k

Definition A failure detector of the class Z s,k provides each process p i with two arrays denoted qr i [1..s] and ℓd i [1..s]. Intuitively, qr i [z] and ℓd i [z], 1 ≤ z ≤ s, denote, with respect to the index z, the current quorum and the current leader of p i , respectively. Z s,k is defined by the following properties, where qr τ i [z] and ℓd τ i [z] denote the value of qr i [z] and ℓd i [z] at time τ .

• Safety property. ∀ z ∈ [1.

.s] :

-Quorum intersection property (QI).

∀ i 1 , ..., i k+1 ∈ Π, ∀ τ 1 , ..., τ k+1 : ∃h, ℓ ∈ [1..k + 1] : (h = ℓ) ∧ (qr τ h i h [z] ∩ qr τ ℓ i ℓ [z] = ∅). -Leader validity property(LV). ∀ τ, ∀ i : ℓd τ i [z] ∈ Π. • Liveness property. ∃z ∈ [1..s] :
-Quorum liveness property (QL).

∀ i ∈ C : ∃ τ : ∀ τ ′ ≥ τ : qr τ ′ i [z] ⊆ C. -Eventual leadership property (EL). ∃ℓ ∈ C : ∀i ∈ C : ∀ τ : ∃ τ ′ , τ ′′ ≥ τ : (qr τ ′ i [z] ∩ qr τ ′′ ℓ [z] = ∅) ⇒ ∃ τ : ∀ τ ′ ≥ τ : (ℓd τ ′ i [z] = ℓ) .
The quorum intersection property states that, for any z ∈ {1, ..., s}, there are two quorum values that intersect in any set of k + 1 quorum values, each taken at any time. The leader validity property states that the leader domain is the set of processes. While the safety properties concern all the entries of the arrays qr i [1..s] and ℓd i [1..s], the liveness properties are only on a single of these entries, say z. The quorum liveness property states that there is a finite time after which all quorum values (appearing in qr i [z] for every i ∈ C) contain only correct processes. The eventual leader liveness property involves only the quorum values taken by the entries qr i [z], for every i ∈ C. Hence, it relates these quorum values with the eventual leader values in the local variables ℓd i [z] at each correct process p i . More precisely, it states that there is a correct process p ℓ such that, for any correct process p i whose quorum qr i [z] intersects infinitely often with the quorum qr ℓ [z] of p ℓ (left part of the implication), p ℓ becomes eventually the permanent leader of p i (saved in ℓd i [z], right part of the implication).

Notation Let Z(Q) s,k denote the quorum part of Z s,k (defined by the properties QI and QL). Similarly, let Z(L) s,k denote the leader part of Z s,k (defined by the properties LV and EL where the quorum part brings no information on failures, which means that we have then ∀ i, ∀ z, ∀τ :

qr τ i [z] = Π).
Particular cases This part shows the generality of Z s,k by displaying failure detector classes that have appeared in the literature. As they are not important for the paper, their initial definitions are not recalled here (the reader will find them in the associated referenced papers).

• s = k = 1: Z 1,1 = (Σ, Ω) as defined in [8, 10]. • Z s,k is weaker than the failure detector ΠΣ k,s introduced in [17]. • Z s,1
is the failure detector W s as defined in [START_REF] Bouzid | Simultaneous Consensus is Harder than Set Agreement in Message-Passing[END_REF].

• Z(Q) 1,k is the quorum failure detector Σ k introduced in [3]. • Z(Q) s,1 is the failure detector V Σ s introduced in [6] where it is shown that (a) V Σ s (i.e., Z(Q) s,1
) is necessary to solve the s-simultaneous consensus problem, and (b)

(V Σ s , Ω s ) W s (= Z s,1 ) (V Σ s , Ω). • Z(Q) 1,n-1 is the quorum failure detector L introduced in [11]. This follows from the fact that Z(Q) 1,n-1 is
Σ n-1 and the equivalence between Σ n-1 and L established in [START_REF] Mostéfaoui | Relations Linking Failure Detectors Associated with k-Set Agreement in Message-Passing Systems[END_REF]. • Z(L) s,1 is the failure detector Ω k introduced in [START_REF] Raynal | Rump Session at 26th ACM Symposium on Principles of Distributed Computing (PODC'07)[END_REF][START_REF] Zielinski | Anti-Omega: the Weakest Failure Detector for Set Agreement[END_REF] and used in [START_REF] Gafni | On Set Consensus Numbers[END_REF].

Notation AMP n,n-1 [FD] denotes the wait-free message-passing model enriched with a failure detector of the class FD .

A Z s,k -based Algorithm for the (s, k)-SSA problem

This section presents a simple algorithm that solves the (s, k)-SSA problem in AMP n,n-1 [Z s,k ]. This algorithm consists in the concurrent execution of s algorithms, each solving an instance of the k-set agreement problem (i.e., an instance of the (1, k)-SSA problem). This algorithm is based on an underlying abstraction (object) called alpha k .

The Abstraction alpha k

Historical perspective The abstraction alpha k originates from a similar abstraction (called alpha) introduced in [START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF] (see also [START_REF] Raynal | Concurrent Programming: Algorithms, Principles, and Foundations[END_REF]) to capture the safety property of the consensus problem in message-passing systems. It has then been generalized to capture the safety property of k-set agreement in (a) read/write systems in [START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF], and (b) message-passing systems in [START_REF] Bouzid | Simultaneous Consensus is Harder than Set Agreement in Message-Passing[END_REF][START_REF] Mostéfaoui | Chasing the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems[END_REF].

Definition We consider here the alpha k object that we have introduced in [START_REF] Mostéfaoui | Chasing the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems[END_REF]. Let ⊥ be a default value that cannot be proposed by processes. alpha k is an object, initialized to ⊥, that may store up to k different values proposed by processes. It is an abstraction (object) that provides processes with a single operation denoted alpha_propose k (r, v) (where r is a round number and v a proposed value), which returns a value to the invoking process. The round number plays the role of a logical time that allows identifying the alpha_propose k () invocations. It is assumed that distinct processes use different round numbers and successive invocations by the same process use increasing sequence numbers. alpha k is an abortable object in the sense that alpha_propose k () invocations are allowed to return the default value ⊥ (i.e., abort) in specific concurrency-related circumstances (as defined from the obligation property, see below). More precisely, the alpha k objects used in this paper are defined by the following specification in which the obligation property takes explicitly into account the fact that these objects are used in the system model AMP[Z 1,k ] (which is strictly stronger than AMP[∅]). The properties defining such an alpha k object are the following.

• Termination. Any invocation of alpha_propose k () by a correct process terminates.

• Validity. If alpha_propose k (r, v) returns v ′ = ⊥, then alpha_propose k (r ′ , v ′ ) has been invoked with r ′ ≤ r.

• Quasi-agreement. At most k values different from the default value ⊥ can be returned by the invocations of alpha_propose k ().

• Obligation. (As s = 1, qr i [1] is denoted qr i .) p ℓ being a correct process, let Q(ℓ, τ ) = {i ∈ C | ∀ τ i , τ ℓ ≥ τ : qr τi i ∩ qr τ ℓ ℓ = ∅}.
If, after some finite time τ , (a) only p ℓ and processes in Q(ℓ, τ ) invoke alpha_propose k () and (b) p ℓ invokes alpha_propose k () infinitely often, then at least one invocation issued by p ℓ returns a non-⊥ value.

Differently from the obligation property stated in [START_REF] Bouzid | Anti-Ω k × Σ k )-Based k-Set Agreement Algorithms[END_REF][START_REF] Guerraoui | The Alpha of Indulgent Consensus[END_REF][START_REF] Raynal | In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-free Set Agreement[END_REF] the previous obligation property is Z s,k -aware (or more precisely Z 1,k -aware, i.e., Σ k -aware). This obligation property allows concurrent invocations of alpha_propose k () to return non-⊥ values as soon as the quorums of the invoking processes do not intersect during these invocations. An algorithm implementing the previous alpha k object in AMP[Σ k ] is described in [START_REF] Mostéfaoui | Chasing the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems[END_REF].

A Base Algorithm for the

(1, k)-SSA Problem (k-Set Agreement) Algorithm 1 is a very simple algorithm solving the k-set agreement problem in AMP[Z 1,k ]. A process p i invokes ssa_propose 1,k (v i )
where v i is the value it proposes. It decides a value v when it executes the statement return (v) which terminates its invocation. The local variable r i is the local round number (as it is easy to see, each process uses increasing round numbers and no two different processes use the same round numbers).

A process loops until it decides. If during a loop iteration p i is such that ℓd i = i (where ℓd i denotes ℓd i [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF], the single leader entry locally output at p i by Z 1,k ), p i invokes the underlying alpha k distributed object (denoted

operation ssa_propose 1,k (v i ): (01) dec i ← ⊥; r i ← i; (02) while (dec i = ⊥) do (03) if (ℓd i = i ) then dec i ← ALPHA k .alpha_propose k (r i , v i ); r i ← r i + n end if (04) end while;
(05) for each j ∈ {1, ..., n} do send DECISION(dec i ) to p j end for; return (v).

when DECISION(v) is received: (06) for each j ∈ {1, ..., n} do send DECISION(dec i ) to p j end for; return (v).

Algorithm 1: k-Set agreement in AMP[Z 1,k ] (code for p i )
ALPHA k ) to try to deposit its value v i into it (the success depends on the concurrency and quorums pattern). If a non-⊥ value is returned by this invocation, p i broadcasts it and decides (execution of return()). If it has not yet decided, a process decides when it receives a DECISION() message (lines 5-6 implement a reliable broadcast).

Theorem 1 Algorithm 1 solves the k-set agreement problem in AMP[Z 1,k ].
Proof Validity and agreement properties of k-set agreement. Let us first observe that, due to the test of line 2, the default value ⊥ cannot be decided. The fact that a decided value is a proposed value follows then from the validity of the underlying alpha k object. Similarly, the fact that at most k non-⊥ values are decided follows directly from the quasi-agreement property of the underlying alpha k object.

Termination property of k-set agreement. It follows from lines 5 and 6 that, at soon as a process decides (invokes return()) each correct process eventually delivers the same DECISION(v) message and decides (if not yet done). The proof is by contradiction: assuming that no process decides, we show that at least one correct process executes line 5 (and consequently, all correct processes decide).

Let p ℓ be the correct process that appears in the definition of the eventual leadership property of Z 1,k . It follows from the definition of p ℓ that we eventually have forever ℓd ℓ = ℓ.

Let R ℓ be the (possibly empty) set of identities of the processes p j (with j = ℓ) such that we have ℓd j = j infinitely often. It follows from the contrapositive of the eventual leadership property of Z 1,k that there is a time τ R ℓ such that ∀ j ∈ R ℓ , ∀ τ 1, τ 2 ≥ τ R ℓ : qr τ 1 j ∩ qr τ 2 ℓ = ∅, from which we conclude that R ℓ ⊆ Q(ℓ, τ R ℓ ) (this is the set defined in the obligation property defining an alpha k object).

Let us notice that, due to test of line 3, there is a finite time τ a after which the only processes that invoke alpha_propose k () are the processes in R ℓ ∪ {ℓ}. Moreover (as by the contradiction assumption no process decides) it follows that, after τ a , p ℓ invokes alpha_propose k () infinitely often. Let τ b be a time greater than max(τ R ℓ , τ a ) from which we have

R ℓ ⊆ Q(ℓ, τ R ℓ ) ⊆ Q(ℓ, τ b ).
As after τ b (a) only processes in R ℓ ∪ {ℓ} invoke alpha_propose k (), (b) p ℓ invokes alpha_propose k (), infinitely often, and (c) R ℓ ⊆ Q(ℓ, τ b ), we conclude from the obligation property of the alpha k object that at least one invocation of p ℓ returns a value v = ⊥ and consequently sends the message DECISION(v) to all the processes. This contradicts the fact that no process decides and concludes the proof of the theorem.

✷ T heorem 1

An Algorithm for the (s, k)-SSA Problem

A simple algorithm solving the (s, k)-SSA problem can be easily obtained by launching s concurrent instances of algorithm 1, the zth instance (1 ≤ z ≤ s) relying, at each process p i , on the components

qr i [z] and ℓd i [z] of AMP[Z s,k ].
A process decides the value returned by the first of the s instances that locally terminates. Hence, it decides the pair (c, v) where c is its first deciding instance and v the value it decides in that instance. As there are s instances of algorithm 1 and at most k values can be decided in each of them, it follows that at most K = sk different values can be decided. Moreover, as there is at least one instance z such that the failure detector outputs ℓd i [z] at each correct process p i converge to the same correct process, it follows that the correct processes decide (if not done before) in at least one of the s instances of algorithm 1.

4 Z(Q) s,k is Necessary to Solve the (s, k)-SSA problem

This section shows that Z(Q) s,k is necessary to solve the (s, k)-SSA problem as soon as we are looking for a failure detector-based solution. To that end, given an algorithm A that solves the (s, k)-SSA problem in AMP n,n-1 [FD ], this section presents an algorithm that emulates the output of Z(Q) s,k , namely an array qr i [1.

.s] at each process p i , which satisfies the properties QI and QL. This means that it is possible to build Z(Q) s,k from any failure detector FD that can solve the (s, k)-SSA problem.

According to the usual terminology, Z(Q) s,k is extracted from the FD -based algorithm A. This extraction is a generalization of the algorithm introduced in [START_REF] Bonnet | On the Road to the Weakest Failure Detector for k-Set Agreement in Message-passing Systems[END_REF], which extracts Σ k from any failure detector-based algorithm that solves the k-set agreement problem.

The Extraction Algorithm Each process p i participates in several executions of the algorithm A. S being a set of processes, A S denotes the execution of A in which exactly the processes of S participate. In this execution, each process of S either decides, blocks forever, or crashes. So the execution of the extraction algorithm is composed of 2 n -1 executions of A.

Init: Q i [1, . . . , s] ← [Π, . . . , Π]; queue i ← 1, . . . , n ;
for each S ⊆ Π such that(i ∈ S) do A S .ssa_propose s,k (i) end for; activate the tasks T 1 to T 5.

Task T 1: repeat periodically send ALIVE(i) to each p j such that j ∈ Π \ {i} end repeat.

Task T 2: when ALIVE(j) is received: move j at the head of queue i .

Task T 3: when (c, -) is decided by p i in the cth k-set agreement instance of A S :

Q i [c] ← Q i [c] ∪ {S}; send DECISION(c, S) to each p j such that j ∈ Π \ {i}.
Task T 4: when DECISION(c, S) is received:

Q i [c] ← Q i [c] ∪ {S}.
Task T 5: repeat forever for each c ∈ {1, ..., s} do Initially, each process p i proposes its identity i to all the instances of A in which it participates. To that end it invokes A S .ssa_propose s,k (i) for each set S such that i ∈ S (ssa_propose s,k () is the operation associated with each instance of the (s, k)-SSA problem). When it decides in the cth k-set agreement of A S (task T 3), p i adds the set S to Q i [c] and informs each other process p j , which includes S in Q j [c] when it learns it (task T 4).

min_rank i ← min{max{rank(queue i , j), j ∈ S}, S ∈ Q i [c]}; qr i [c] ← any S min ∈ Q i [c] such that max{rank(queue i , j), j ∈ S min } = min_rank i end for; end repeat.
Each alive process p i sends periodically messages ALIVE(i) (task T 1) to inform the other processes that it is alive. When it receives a message ALIVE(j) (task T 2), a process p i moves j at the head of its local queue (denoted queue i ) which always contains all process identities. It follows that the identities of all the correct processes eventually precede in this queue the identities of all the faulty processes. (Initially, each queue queue i contains all process identities, in any order.)

T 5 is a task whose aim is to repeatedly compute the current value of qr i [1..s]. It uses the function rank(queue i , j) which returns the current rank of p j in the queue queue i . The value of qr i [c] is computed as follows. It is the "first set of Q i [c] with respect to queue i " (i.e., with respect to the processes which are currently seen as being alive). This is captured with the help of the local variable minrank i . As an example Let Q i [c] = {{3, 4, 9}, {2, 3, 8}, {4, 7}, {1, 2, 3, 4, 5, 6, 7, 8, 9}}, and queue i = 4, 8, 3, 2, 7, 5, 9, 1, 6 . We have then minrank = 4, and S min = {2, 3, 8}. This set of identities is the first set of Q i [c] with respect to queue i because each of the other sets {3, 4, 9}, {4, 7}, or {1, 2, 3, 4, 5, 6, 7, 8, 9}, includes an element (9, 7, and 6, respectively) that appears in queue i after all the elements of {2, 3, 8} (in case several sets are "first", any of them can be selected).

Theorem 2 Given any algorithm A that solves the (s, k)-SSA problem in AMP n,n-1 [FD ], the extraction algorithm described in Figure 2 is a wait-free construction of a failure detector Z(Q) s,k .

Proof Proof of the quorum liveness property. We have to show that there is an entry z such that, after some finite time and for each i ∈ C, qr i [z] contains only correct processes. Let us consider the execution of A C . As all the processes in C are correct (definition), A C terminates. It then follows from the tasks T 3 and T 4 that there is an entry z such the set Q i [z] of each correct process eventually contains the set C.

Moreover, as each correct process sends forever messages ALIVE() (task T 1), it follows that the identities of the correct processes appear in queue queue i before the identities of the faulty processes (task T 2). It then follows from task T 5 (which computes the "first set of Q i [z] with respect to queue i ") that, after some finite time, qr i [z] contains only correct processes.

Proof of the quorum safety property. We have to show that, for each entry z ∈ {1, ..., s}, we have

∀ i 1 , ..., i k+1 ∈ Π, ∀ τ 1 , ..., τ k+1 : ∃h, ℓ ∈ [1..k + 1] : (h = ℓ) ∧ (qr τ h i h [z] ∩ qr τ ℓ i ℓ [z] = ∅).
The proof is by contradiction. Let us assume that it exists a family (i m ) 1≤m≤k+1 of k + 1 (not necessarily distinct) process identities, a family (τ m ) 1≤m≤k+1 of time instants and an integer z ∈ {1, . . . , s} such that for all m 1 , m 2 ∈ {1, . . . , k + 1} qr

τm 1 im 1 [z] ∩ qr τm 2 im 2 [z] = ∅. Let S m denote the set qr τm im [z].
Let us remark that the previous non-intersection assumption and the fact that no set S m is empty imply that, for each m ∈ {1, . . . , k + 1}, a process p jm ∈ S m decided a value v m in the zth k-set agreement of A Sm (no set S m can have the initial value Π since it would intersect any other one). As the sets S m , 1 ≤ m ≤ k + 1 are pairwise disjoint, there is an execution of A in which the set of participants is m∈{1,...,k+1} S m that is indistinguishable from the considered execution of A Sm from the point of view of each p jm (just consider that the messages between processes of S m1 and S m2 are delayed and received only after all processes decide). It follows that in this execution each process p jm also decides v m in the zth instance of the k-set agreement. It then follows from the agreement property of the k-set agreement problem that |{v m , 1 ≤ m ≤ k + 1}| ≤ k. Hence, it exists m 1 , m 2 ∈ {1, . . . , k + 1} such that v m1 = v m2 . But, since the values decided in the zth instance of the k-set agreement problems involved in both A Sm 1 and A Sm 2 are identities of participating processes (this follows from the validity property of the k-set agreement problem), it follows that v m1 = v m2 ∈ S m1 ∩ S m2 . This contradicts the initial assumption, which concludes the proof of the quorum intersection property of Z(Q) s,k .

✷ T heorem 2

5 The Structure of Generalized (s, k)-SSA problems

This section studies the mathematical structure of the family of (s, k)-SSA problems for sk = K. To that end, it first introduces a straightforward generalization of this family and then shows that this generalized family can be represented by a directed graph where an arrow from A to B means that the problem B can be solved from a black box solving the problem A, while the opposite is impossible. Given such a pair of problems (A, B), this section also associates with this pair a failure detector that is necessary to solve A and a failure detector that is sufficient to solve B. For each z ∈ {1, . . . , ss ′ }, it follows from the definition of G(K) that there is a pair (x z , y z ) of distinct integers in {1, . . . , s-z+1} such that a z xz ≥ a z yz , x z < y z (w.l.o.g.), and {a z+1 1 , . . . , a z+1 s-z } = {a z 1 , . . . , a z s-z+1 }\{a z xz , a z yz }∪ {a z xz + a z yz }. Let f z be the function that associates with each x ∈ {1, . . . , s

The Generalized

-z + 1} (i) x if a z x > a z xz + a z yz , (ii) x + 1 if a z xz + a z yz ≥ a z x and x < x z , (iii) x if a z xz + a z yz ≥ a z x and x z < x < y z , (iv) x -1 if a z xz + a z yz ≥ a z
x and y z < x, and (v) the index w 0 of the first occurrence of a z xz + a z yz in {a z+1 1 , . . . , a z+1 s-z } if x ∈ {x z , y z }. (The aim of these cases is to place the element a z xz + a z yz at its right place in the multiset {a z+1 1 , . . . , a z+1 s-z }.) By construction, for all y ∈ {1, . . . , s -z} \ {w 0 }, f -1 (y) contains a single value and

a z f -1 (y) = a z+1 y , while f -1 (w 0 ) = {x z , y z }. Since a z xz + a z yz = a z+1 w0 , P ({a z 1 , . . . , a z s-z+1 }, {a z+1 1 , . . . , a z+1 s-z }) is satisfied. Let f be f z •f z-1 •• • ••f 1 , since the property verified by f is stable by composition, the path from ({k 1 , ..., k s } to {k ′ 1 , ..., k ′ s ′ }) ensures that P ({k 1 , . . . , k s }, {k ′ 1 , ..., k ′ s ′ } is satisfied. Direction ⇐. Let ({k 1 , ..., k s }, {k ′ 1 , ..., k ′ s ′ }
) be a pair of vertices of G(K) that satisfies the predicate P . Two cases are possible: (i) s = s ′ and then f is the identity function (or just a reordering of the values appearing multiple times) and {k 1 , ..., k s } = {k ′ 1 , . . . k ′ s ′ } or (ii) s > s ′ . In the case (i), there is a path (of length zero) from any node to itself. In the case (ii), consider the function f defined in the predicate P . Since s > s ′ , f is not injective (one-to-one), and there are two distinct integers x 1 , y 1 such that f (x 1 ) = f (y 1 ). Let then {a 2 1 , . . . , a 2 s-1 } be {k 1 , ..., k s }\{k x1 , k y1 }∪{k x1+y1 }. If f is injective from {1, . . . , s}\{y 1 } to {1, . . . , s ′ }, since according to P it is surjective (onto), it follows that s ′ = s -1 and that {a 2 1 , . . . ,

a 2 s-1 } = {k ′ 1 , ..., k ′ s ′ } and there is a path in G(K) from {k 1 , ..., k s } to {k ′ 1 , ..., k ′ s ′ }. If f is not injective from {1, . . . , s} \ {y 1 } to {1, . . . , s ′ }, then it exists two distinct integers x 2 , y 2 in {1, . . . , s} \ {y 1 } such that f (x 2 ) = f (y 2 ) (consider that y 2 = x 1 , w.l.o.g.). Let then build {a 3 1 , . . . , a 3 s-2 } be (i) {k 1 , ..., k s } \ {k x1 , k y1 , k x2 , k y2 } ∪ {k x1 + k y1 , k x2 + k y2 } if x 1 = x 2 , or (ii) {k 1 , ..., k s }\{k x1 , k y1 , k y2 }∪{k x1 +k y1 +k y2 } if x 2 = x 1 . If f is injective from {1, . . . , s}\{y 1 , y 2 } to {1, . . . , s ′ } then, as it is also surjective, s ′ = s -2, {a 3 1 , . . . , a 3 s-2 } = {k ′ 1 , ..., k ′ s ′ } and there is a path of length 2 in G(K) from {k 1 , ..., k s } to {k ′ 1 , ..., k ′ s ′ }. If f is not injective from {1, . . . , s} \ {y 1 , y 2 } to {1, . . . , s ′ } then let choose x 3 , y 3 in {1, . . . , s} \ {y 1 , y 2 } such that f (x 3 ) = f (y 3 ) and y 3 /
∈ {x 1 , x 2 } and continue the construction. After ss ′ iteration steps, we have |{1, . . . , s} \ {y 1 , . . . , y s-s ′ }| = s ′ , and the vertices which have been traversed belong to a path of G(K) starting at {k 1 , ..., k s } and ending at {k

′ 1 , ..., k ′ s ′ }. ✷ Lemma 2
Theorem 3 The transitive closure of G(K) is a partial order.

Proof The theorem follows from the fact that the relation captured by the predicate P is anti-symmetric (Lemma 1) and transitive (Lemma 2).

✷ T heorem 3 5.3 Associated Generalized Failure Detector GZ k 1 ,...,ks
The failure detector Z s,k is implicitly tailored for the symmetric (s, k)-SSA problem. A simple generalization allows to extend it to obtain an "equivalent" failure detector suited to asymmetric problems. As Z s,k , this generalized failure detector, denoted GZ k1,...,ks , provides each process p i with an array qr i [1.

.s] and an array ℓd i [1..s]. It differs from Z s,k in the constraint imposed by the quorum intersection property that is now specific to each entry z ∈ {1, ..., s}. More explicitly, QI is replaced by the property GQI defined as follows

• Quorum intersection property (GQI). ∀ z ∈ [1..s]: ∀ i 1 , ..., i kz+1 ∈ Π, ∀ τ 1 , ..., τ kz +1 : ∃h, ℓ ∈ [1..k z + 1] : (h = ℓ) ∧ (qr τ h i h [z] ∩ qr τ ℓ i ℓ [z] = ∅).
The other properties -leader validity (LV), quorum liveness (QL), and eventual leader liveness (EL)-remain unchanged. It is easy to see, that GZ k1,...,ks boils down to Z s,k when

k 1 = • • • = k s = k.
Let GZ(Q) k1,...,ks denotes the quorum part of GZ k1,...,ks (properties GQI and QL). The proof of the following theorem is a simple extension of the proof of Theorem 2. It is left to the reader.

Theorem 4 Given any algorithm A that solves the {k 1 , ..., k s }-SSA problem in AMP n,n-1 [FD ], the extraction algorithm described in Figure 2 is a wait-free construction of a failure detector GZ(Q) k1,...,ks .

A Hierarchy of Agreement Problems

Problem hierarchy Let AMP n,n-1 [X] denote the asynchronous message-passing model in which any number of processes may crash (AMP n,n-1 [∅]) enriched with an algorithm that solves the problem X.

Given the the message-passing model AMP n,n-1 [∅], a problem A is stronger than a problem B (denoted A B) if B can be solved in AMP n,n-1 [A] (we also say that B is weaker than A, denoted B A). Moreover, A is strictly stronger than B (denoted A ≻ B) if A B and ¬(B A) (A cannot be solved in AMP n,n-1 [B]).

Lemma 3 P {k 1 , ..., k s }, {k ′ 1 , ..., k ′ s ′ } ⇒ {k 1 , . . . , k s }-SSA {k ′ 1 , . . . , k ′ s ′ }-SSA .
Proof Let us consider an algorithm A that solves the {k 1 , . . . , k s }-SSA problem. To solve the {k ′ 1 , . . . , k ′ s ′ }-SSA problem it is sufficient that each process p i executes A until it decides a pair (x, v) and then outputs the pair (f (x), v) as the decided value for the {k ′ 1 , . . . , k ′ s ′ }-SSA problem (where f is the function appearing in P ). The validity and termination properties of the obtained algorithm follow directly from those of A. Moreover, according to the agreement property satisfied by A, at most k x different pairs (x, -) can be decided by the underlying algorithm. It then follows from the definition of f that for any y ∈ {1, . . . , s ′ }, at most x∈f -1 (y) k x = k y distinct pairs (y, -) are decided in the simulated solution of the {k ′ 1 , . . . , k ′ s ′ }-SSA problem, and the agreement property of the {k ′ 1 , . . . , k ′ s ′ }-SSA is satisfied.

✷ Lemma 3 Lemma 4 Let n > K ≥ 2. {k 1 , . . . , k s }-SSA {k ′ 1 , . . . , k ′ s ′ }-SSA ⇒ P {k 1 , . . . , k s }, {k ′ 1 , . . . , k ′ s ′ } .
Proof The principle and structure of the proof are as follows.

• The proof considers first the failure detector GZ k1,...,ks , which is sufficient to solve the {k 1 , ..., k s }-SSA problem (the (s, k)-SSA algorithm described in Section 3 can be easily adapted to solve the {k 1 , ..., k s }-SSA problem in AMP n,n-1 [GZ k1,...,ks ]).

• As {k 1 , . . . , k s }-SSA {k ′ 1 , . . . , k ′ s }-SSA, it is possible to solve the {k ′ 1 , . . . , k ′ s ′ }-SSA problem in AMP n,n-1 [GZ k1,...,ks ]. Moreover, as GZ(Q) k ′ 1 ,...,k ′ s ′ is necessary to solve the {k ′ 1 , . . . , k ′ s ′ }-SSA problem (Theorem 4), it is possible to simulate GZ(Q) k ′ 1 ,...,k ′ s ′ in AMP n,n-1 [GZ k1,...,ks ].
• The proof constructs such a simulation and shows that this simulation allows to define a function f such that the predicate P {k 1 , . . . , k s }, {k ′ 1 , . . . , k ′ s ′ } is satisfied, from which the lemma follows.

Assuming n > K ≥ 2, and A being an algorithm that simulates GZ(Q) k ′ 1 ,...,k ′ s ′ in AMP n,n-1 [GZ k1,...,ks ], let QR i [1, . . . , s ′ ] denote the outputs of the simulated quorum at process p i . Moreover, for each process p i , 1 ≤ i ≤ K + 1 and for each x ∈ {1, . . . , s}, let α x i be an execution of A in which the only process to take steps is p i and the underlying failure detector GZ k1,...,ks always outputs (locally at each p i ) qr i [x] = {i}, ld i [x] = i, and ∀x ′ = x, qr i [x ′ ] = {1, . . . , K + 1} and ld i [x ′ ] = i (let us notice that these outputs comply with the definition of the underlying failure detector GZ k1,...,ks ]). According to the quorum liveness property of the constructed failure detector GZ(Q) k ′ 1 ,...,k ′ s ′ , it exists in α x i an instant τ x i and an index c x i such that ∀τ ≥ τ x i : QR i [c x i ] = {i}. Considering the solo executions {α x i } 1≤i≤K+1 , one can build, for any subset of K distinct processes such that {i 1 , . . . , i K } ⊂ {1, . . . , K + 1}, an execution of A denoted

α i1•••iK = α 1 i1 • α 1 i2 • • • α 1 i k 1 , α 2 i k 1 +1 • • • α 2 i k 1 +k 2 , . . . , α s i K-ks +1 • • • α , iK s
as follows where W (x) denotes the integer interval

[1 + k 1 + • • • + k x-1 ..k 1 + • • • + k x ]:
• All processes p i , i > K + 1, crash before taking any step,

• All message receptions are delayed after time τ _max = max{τ x i such that i ∈ {1, ..., K + 1}, x ∈ {1, ..., s}},2

• Let us observe that α i1•••iK contains the prefix of the solo execution α x iw of the process p iw if and only if w ∈ W (x).

For each x ∈ {1, . . . , s} and for each w ∈ W (x), the outputs at p iw of the underlying failure detector GZ k1,...,ks are the same as in α x iw until τ _max. After this instant, for each i ∈ {i 1 , . . . , i K } and for x ∈ {1, . . . , s}, qr i [x] = {i 1 , . . . , i K } and ld i [x] = i 1 .

Let us remark that the outputs of the underlying failure detector GZ k1,...,ks are valid in this execution, and that, for each x ∈ {1, . . . , s} and each p iw , w ∈ W (x), the execution α i1•••iK is indistinguishable from α x iw until τ _max from the point of view of p iw . It follows that for each x ∈ {1, . . . , s} and each p iw , w ∈ W (x), we have QR iw [c x iw ] = {i w } at time τ _max in α i1•••iK . It follows from this observation and the quorum intersection property of the failure detector GZ(Q) k ′ 1 ,...,k ′ s ′ built by A (this property has to be preserved on each quorum index y ∈ {1, . . . , s ′ }) that {c 1 i1 , . . . , c , . . . , c s i K-ks +1 , . . . , c s iK } contains k x times f (x) for each x ∈ {1, . . . , s} (and only these values), it follows from the multiset equality above that ∀y ∈ {1, . . . , s ′ } : Σ x∈f -1 (y) k x = k y , which ends the proof of the lemma.

✷ Lemma 4 Theorem 5 Let n > K ≥ 2. {k 1 , . . . , k s }-SSA {k ′ 1 , . . . , k ′ s ′ }-SSA ⇔ P {k 1 , . . . , k s }, {k ′ 1 , . . . , k ′ s ′ } .
Proof The proof follows directly from Lemma 3 and Lemma 4. ✷ T heorem 5

Theorem 6 The relation ≻ on generalized-SSA problems is a partial order.

Proof The proof follows from Theorem 3 (G(K) is a partial order), Lemma 2 (all paths in (G(K) are characterized by P ), and Theorem 5 (which relates P and ≻). ✷ T heorem 6

The next corollary follows from the observation that, for any K > 1, the K-set agreement problem is a sink vertex in the directed graph G(K).

Corollary 1 The weakest failure detector for the K-set agreement problem does not allow to solve any {k 1 , . . . , k s }-SSA problem such that s > 1 and k 1 + • • • + k s = K.

The Lattice of Symmetric SSA Problems

As seen before, a symmetric vertex is a vertex {k 1 , ..., k s } such that k 1 = . . . = k s = k. Let SG(K) denote the graph whose vertices are the symmetric vertices of G(K), and there is an edge from (s x , k x ) to (s y , k y ) iff there is a path in G(K) from the vertex {k x , ..., k x } (k x appearing s x times) to the vertex {k y , ..., k y } (k y appearing s y times) and no path connecting these vertices passes through a symmetric vertex. As an example, SG( 6) is given in Section 5.2.

Theorem 7 For any K, SG(K) is a lattice.

Proof Let (s x , k x ) and (s y , k y ) be two pairs of integers such that k x < k y and s x k x = s y k y = K. It follows from the definition of SG(K) that there is an edge from (s x , k x ) to (s y , k y ) iff k y = k x p where p is prime (if p is not prime there is a symmetric vertex on a path from (s x , k x ) to (s y , k y ), and if k y /k x is not an integer, there is no path from (s x , k x ) to (s y , k y )). It follows that we can associate with any pair of pairs (s x , k x ) and (s y , k y ) such that s x k x = s y k y = K,

• among its ancestors, the vertex (s z , k z ) in SG(K) where s z k z = K and k z = gcd(k x , k y ), and • among its successors, the vertex (s ′ z , k ′ z ) in SG(K) where s ′ z k ′ z = K and k ′ z = lcm(k x , k y ).

As the greatest common denominator and the least common multiple of any pair of integers are unique, it follows that SG(K) is a lattice. ✷ T heorem 7

The next corollary follows from the previous theorem. As far as agreement problems are concerned, this shows a strong difference between the message-passing model and the read/write model. In the read/write model, (s 1 , k 1 )-SSA and (s 2 , k 2 )-SSA are the same problem (they are both equivalent to the K-simultaneous problem which is itself equivalent to the K-set agreement problem, where

K = s 1 k 1 = s 2 k 2 ).

Conclusion

This paper has investigated the comparative power of simultaneous agreement and set agreement in asynchronous message-passing systems prone to any number of process crashes. This study was initially motivated by the lasting (and difficult) quest for the weakest failure detector for the k-set agreement problem in message-passing systems.

While k-simultaneous consensus and k-set agreement are equivalent problems in asynchronous read/write systems prone to any number of process crashes [START_REF] Afek | The k-Simultaneous Consensus Problem[END_REF], the paper has introduced a general formulation of agreement problems, namely the family of (s, k)-SSA (s-simultaneous k-set agreement) problems, and has shown that these agreement problems define a strong hierarchy, thereby showing that their shared memory equivalence is no longer true in messagepassing systems. Hence, this study contributes to a better understanding of the relation (equivalence/difference) between the send/receive model and the read/write model (equivalence when a majority of processes are correct [START_REF] Attiya | Sharing Memory Robustly in Message Passing Systems[END_REF], and difference -from a problem ranking point of view-in the other cases).

Algorithm 2 :

 2 Extracting Z(Q) s,k from a failure detector-based algorithm A solving the (s, k)-SSA problem The behavior of each process p i is described in algorithm 2. The internal statements of the tasks T 1 and T 5, and the tasks T 2-T 4 are locally executed in mutual exclusion. The local array Q i [1..s] is initialized to [Π, . . . , Π]. The aim of Q i [c] is to contain all the sets S such that a value has been decided in the cth instance of the k-set agreement of the execution of A S .

  Asymmetric {k 1 , ..., k s }-SSA Problem While the (s, k)-SSA problem is a symmetric problem which consists in s simultaneous instances of the k-set agreement problem, a simple generalization consists in considering an asymmetric version made up of s simultaneous instances of possibly different set agreement problems, namely the k 1 -set agreement problem, the k 2 -set agreement problem, etc., and the k s -set agreement problem. Hence, among the proposed values, at most K = Σ s x=1 k x different values are decided.

Corollary 2

 2 Let (s 1 , k 1 ) and (s 2 , k 2 ) be two different pairs of integers such that s 1 k 1 = s 2 k 2 , and none of k 1 and k 2 divides the other one. The symmetric (s 1 , k 1 )-SSA and (s 2 , k 2 )-SSA problems are incomparable in AMP n,n-1 [∅].

  K-ks +1 , . . . , c s iK } is a multiset of K elements where for each y ∈ {1, . . . , s ′ }, the value y appears k ′ y times (and those are the only values of the elements of this multiset).Let us now consider the execution α σ(1)•••σ(K) where σ is any permutation of {1, . . . , K}. According to the previous discussion, any process p i σ(w) , w ∈ {1, . . . , K} can be replaced by p K+1 in the execution without changing the multiset {c 1 iσ (1) , . . . , c 1 i σ(k 1 ) , . . . , c s i σ(K-ks +1) , . . . , c s i σ(K) }. It then follows that ∀x ∈ {1, . . . , s}, ∀w ∈ {1, . . . , K} :(σ(w) ∈ W (x) ⇒ c x i σ(w) = c x K+1). As σ can be any permutation, it follows that ∀x ∈ {1, . . . , s}, ∀w ∈ {1, . . . , K} : c x w = c x K+1 . Moreover this implies that ∀x ∈ {1, . . . , s}, ∀i, j ∈ {1, . . . , K + 1} : c x i = c x j . Let us finally consider the function f which, with each x ∈ {1, . . . , s} associates c x 1 (which, as just shown, is equal to c x i for all i ∈ {1, . . . , K}). Since, {c 1 i1 , . . . , c 1

	1 i k 1	, . . . , c s i i k 1

The set notation is used to represent a multiset. A multiset is a set in which several elements can have the same value. As an example, {1,

2, 1, 1, 3} is a multiset of 5 elements. Hence, the multisets {1, 2, 1, 1, 3} and {2, 1, 3} are different (while {1, 2, 1, 1, 3} = {2, 1, 3} from a set point of view).

This is the only place where the "asynchronous message-passing" assumption is used. If communication was through atomic read/write registers, this message asynchrony would not exist and the lemma would not hold.

Acknowledgments

This work has been partially supported by the French ANR project DISPLEXITY devoted to computability and complexity in distributed computing.

This asymmetric version is denoted {k 1 , ..., k s }-SSA where {k 1 , ..., k s } is a multiset 1 . The particular instance where k 1 = • • • = k s = k is the symmetric (s, k)-SSA problem. As permuting the integers k x does not change the problem, we consider the canonical notation where k 1 ≥ k 2 ≥ . . . ≥ k s ≥ 1.

Associating a

Graph with a Family of Generalized {k 1 , ..., k s }-SSA Problems Graph definition Given an integer K and starting from the source vertex labeled with the multiset {1, ..., 1} (K times the integer 1), let us define a graph denoted G(K) as follows. Given a vertex labeled {k 1 , ..., k s } (initially, s = K and k 1 = • • • = k K = 1), we add all possible vertices of s -1 elements labeled {k ′ 1 , ..., k ′ s-1 } and directed edges from {k 1 , ..., k s } to each vertex {k ′ 1 , ..., k ′ s-1 } defined as follows. Any pair of elements k x , k y of the multiset {k 1 , ..., k s } gives rise to a vertex labeled by the multiset {k

Then, the construction process is recursively repeated until we arrive at a node composed of a single element labeled {K}.

An example of graph for K = 6 is given on the right. The labels corresponding to symmetric instances ((s, k)-SSA problems) are underlined. The graph (lattice) on the right side of the figure considers only the symmetric problem instances.

Meaning of the graph As we will see in Section 5.4, given an integer K, this graph describes the computability hierarchy linking all the {k 1 , k 2 , ...}-SSA

Let the label A of a vertex denotes both the vertex itself and the associated agreement problem. An edge from a vertex A to a vertex B means that (a) given an algorithm that solves the problem A it is possible to solve the problem B, while (b) the opposite is impossible.

Proof The proof is an immediate consequence of the fact that the successors of any vertex labeled by a multiset of size s are multisets of size s -1.

✷ T heorem 1

As we will see in Lemma 2, the following predicate P characterizes (with the existence of a function f ) the pairs of vertices connected by a path in G(K).


Antoine Le Riche
email: antoine.le-riche@univ-amu.fr

Carine Nourry
email: carine.nourry@univ-amu.fr

Alain Venditti
email: alain.venditti@univ-amu.fr

Greqam

Efficient Endogenous Fluctuations in Two-Sector OLG Model *

Keywords: Two-sector OLG model, multiple consumption goods, dynamic efficiency, endogenous fluctuations. Journal of Economic Literature Classification Numbers: C62, E32, O41

We consider a two-sector two-good two-periods overlapping generations model with inelastic labor, consumption in both period of life and homothetic CES preferences. There are two consumption goods, one pure (non-durable) consumption and one consumable (durable) capital good which can be either consumed or invested. Assuming gross substitutability and a capital intensive pure consumption good, we prove the existence of efficient endogenous fluctuations through a Hopf bifurcation if the share of the consumption of young in the composite good is low enough. We also show that some fiscal policy rules can improve welfare and prevent the existence of business-cycle fluctuations in the economy by driving it to the optimal steady state as soon as it is announced.

Introduction

The existence of endogenous fluctuations under gross substitutability is a well established fact in overlapping generations (OLG) models. In particular, a large proportion of the literature considers that endogenous fluctuations occur through sunspot equilibria and are driven by changes in expectations about fundamentals. As shown by Woodford [START_REF] Woodford | Stationary Sunspot Equilibria. The Case of Small Fluctuations Around a Deterministic Steady State[END_REF], the existence of sunspot equilibria is a consequence of local indeterminacy of the equilibrium under perfect foresight, i.e. the existence of a continuum of equilibrium paths converging towards one steady state from the same initial value of the state variable.

In a seminal contribution, Reichlin [START_REF] Reichlin | Equilibrium Cycles in Overlapping Generations Economy with Production[END_REF] shows how the co-existence of dynamic efficiency, i.e., Pareto-optimal equilibrium paths, and local indeterminacy in OLG models is an important question in terms of stabilization policies. If sunspot fluctuations occur under dynamic efficiency, a public policy can simultaneously stabilize the economy and reach the Pareto optimal steady state. On the contrary, when local indeterminacy occurs under dynamic inefficiency, stabilization policies targeting the steady state leave room for welfare losses. As shown by Reichlin [START_REF] Reichlin | Equilibrium Cycles in Overlapping Generations Economy with Production[END_REF], locally indeterminate dynamically efficient equilibria occurs in aggregate OLG models, but only throughout flip bifurcations and period-two cycles. This feature generates fluctuations that are far to what is generally observed. Indeed, in presence of period-two cycles, the main variables are characterized by unrealistic negative auto-correlations. Dufourt et al. [START_REF] Dufourt | Sunspot Equilibria and the Expectation-Driven Phillips Curve[END_REF] show on the contrary that when a Hopf bifurcation instead occurs, persistent and non-monotonous convergence to the steady-state with positive auto-correlations provide empirically plausible endogenous fluctuations.

In Galor [START_REF] Galor | A Two-Sector Overlapping-Generations Model: A Global Characterization of the Dynamical System[END_REF] type two-sector OLG models, 1 with one pure consumption good and one pure investment good, the occurrence of endogenous fluctuations and local indeterminacy is based upon a capital intensive consumption good. The factor allocation across sectors generates oscillations of the capital accumulation path which can propagate in the economy through the savings behavior of the agents. Nourry and Venditti [START_REF] Nourry | Local Indeterminacy Under Dynamic Efficiency in a Two-Sector Overlapping Generations Economy[END_REF] have proved that local indeterminacy is likely to occur under dynamic efficiency, but again throughout a flip bifurcation. 2 1 See also Venditti [START_REF] Venditti | The Two Sector Overlapping Generations Model: A Simple Formulation[END_REF]. 2 The sectoral technologies need to be close enough to Leontief functions. See also Drugeon et 1 However, when heterogeneous sectors are introduced, the assumption of a unique consumption good is a strong simplification likely to generate singular properties. In a multisector framework is introduced, it is quite common to consider many consumption goods as Benhabib and Nishimura [START_REF] Benhabib | Stability of Equilibrium in Dynamic Models of Capital Theory[END_REF] for an optimal growth infinite-horizon model. In such a case, the existence of additional substitution mechanisms between the different consumption goods suggests that new rooms for the occurrence of endogenous business cycles could be obtained. Kalra [START_REF] Kalra | Cyclical Equilibria in Multi-Sector Productive Economies: the Role of Substitution and Factor Intensity[END_REF] and Nourry and Venditti [START_REF] Nourry | Endogenous Business Cycles in OLG Economies with Multiple Consumption Goods[END_REF] consider a two-sector model in which the first sector produces a pure consumption good (non-durable), and the second sector produces a mixed good which can be either consumed or used as capital (durable). They show that local indeterminacy can now occur through the occurrence of a Hopf bifurcation.

Nevertheless this last approach has two major flaws. First it considers a structure of the life cycle consumption which is symmetric, meaning that agents' tastes concerning their consumption bundle are invariant. As a result they basically consume the same amount of durable goods throughout their life. This is in contradiction with the recent study of Fernandez-Villaverde and Krueger [START_REF] Fernandez-Villaverde | Consumption over the Life Cycle: Facts from Consumer Expenditure Survey Data[END_REF]. Using a Consumer Expenditure Survey data to estimate life cycle profile, they show that consumption expenditures differ qualitatively among age, retired agents consuming relatively less durable goods. Such patterns highlight that consumption expenditures evolve over time and thus should have an impact on the model dynamics through saving behaviors. Secondly, Nourry and Venditti [START_REF] Nourry | Endogenous Business Cycles in OLG Economies with Multiple Consumption Goods[END_REF] consider that the bifurcation parameter is also the parameter allowing the normalization of the steady state. As a consequence, it is almost impossible to show the existence of a non-empty set of parameters leading to an indeterminate efficient steady state characterized by a Hopf bifurcation.

In this paper, we extend the formulation of Nourry and Venditti [START_REF] Nourry | Endogenous Business Cycles in OLG Economies with Multiple Consumption Goods[END_REF] by considering heterogenous intratemporal preferences among the period of life. This gives us an additional degree of freedom which allows to show the existence of efficient endogenous fluctuations through a Hopf bifurcation if the share of the pure consumption (non-durable) good in the utility of young agents is low enough, or equivalently if the share of the mixed (durable) good in the utility of young is large enough. Since this condition is now compatible with a large share of the al. [START_REF] Drugeon | On Efficiency and Local Uniqueness in Two-Sector OLG Economies[END_REF].

durable good in the utility of old agents, our results are in line with the empirical evidence provided by Fernandez-Villaverde and Krueger [START_REF] Fernandez-Villaverde | Consumption over the Life Cycle: Facts from Consumer Expenditure Survey Data[END_REF]. We also prove that a fiscal policy based on transfers and taxes could simultaneously stabilize the economy, and reach the efficient steady state. Finally, a numerical illustration is provided and shows that there exists a non empty set of parameters for which local indeterminacy under dynamic efficiency occurs through a Hopf bifurcation.

The paper is organized as follows: Section 2 presents the model and proves the existence of an efficient steady state. Section 3 contains our main results on the occurrence of efficient endogenous fluctuations through Hopf bifurcation. Section 4 depicts a stabilization policy. Section 5 illustrates the theoretical result of the previous section by a numerical example. Concluding remarks are in Section 6 and the proofs are gathered in a final Appendix.

The model 2.1 Technology

Consider a competitive economy in which there are two sectors, one representative firm for each sector and each firm producing one final good. In this economy there exist two goods: one consumption good Y 0,t and one consumable capital good Y t which can be either consumed or invested. The consumption good is taken as a numeraire. Each sector uses two factors, capital K t and labor L t , both factors are mobile between sectors. Depreciation of capital is complete within one period 3 : K t+1 = Y t -Z t where K t+1 is the total amount of capital in period t + 1 and Z t is the consumption share of the consumable capital good in period t. A constant returns to scale technology is used for each sector:

Y 0,t = F 0 K 0 t , L 0 t , Y t = F 1 (K 1 t , L 1 t with K 0 t + K 1 t ≤ K t ,
any χ > 0, F j 1 (0, χ) = F j 2 (χ, 0) = ∞, F j 1 (∞, χ) = F j 2 (χ, ∞) = 0, where j ∈ {0, 1}.
The optimal allocation of factors between sectors is defined by the social production function T (K t , Y t , L t ):

T (K t , Y t , L t ) = max K j t ,L j t Y 0,t | Y t ≤ F 1 K 1 t , L 1 t , K 0 t + K 1 t ≤ K t , L 0 t + L 1 t ≤ L t (1)
Under Assumption 1, the function T (K t , Y t , L t ) is homogeneous of degree one, concave and twice continuously differentiable 4 . Denoting r t the rental rate of capital, p t the price of the consumable capital good and w t the wage rate, all in terms of the price of the consumption good, using the envelope theorem the following relationships hold:

r (K t , Y t , L t ) = T 1 (K t , Y t , L t ) p (K t , Y t , L t ) = -T 2 (K t , Y t , L t ) w (K t , Y t , L t ) = T 3 (K t , Y t , L t ) (2)
The relative capital intensity difference is derived from the factor-price frontier

b = L 1 Y K 1 L 1 -K 0 L 0 (3)
The sign of b is positive (resp. negative) if and only if the consumption good is labor (resp. capital) intensive. The Stolper-Samuelson effect dr d p and the Rybczynski effect dY dK are determined respectively by the factor-price frontier and the full employment condition.

dr d p = dY dK = b -1 (4)
Under a consumption good labor intensive, i.e. b > 0, the Stolper-Samuelson effect states that an increase of the relative price decreases the rental rate of capital and raises the wage rate whereas the Rybczynski effect specifies that an increase of the capital-labor ratio decreases the production of the consumption good and increases the production of the consumable capital good. Furthermore, from the GDP function

T (K t , Y t , L t ) + p t Y t = w t L t + r t K t ,
we get the share of capital in the economy:

s (K t , Y t , L t ) = r t K t T (K t ,Y t ,L t )+p t Y t (5)

Preferences

Consider an infinite-horizon discrete time economy that is populated by overlapping generations who live for two periods: young and old. At each period, a new generation N t is born. The population is constant over time and normalized to one. In the first period, young agents inelastically supply one unit of labor and receive an income. They assign this income between saving φ t and the consumption of the composite good C t . The composite good C t is defined by a Cobb-Douglas composition of a consumption good 0, c 0,t , and a consumption good 1, c 1,t :

C t = c θ c 0,t c 1-θ c 1,t (6)
where 0 < θ c ≤ 1 is the share of the consumption good 0 in the composite good C t . In the second period, old agents are retired. The return on saving, R t+1 φ t , give their income which they spend entirely in the consumption of the composite good D t+1 . D t+1 is determined by a Cobb-Douglas composition of a consumption good 0, d 0,t+1 , and a consumption good 1, d 1,t+1 :

D t+1 = d θ d 0,t+1 d 1-θ d 1,t+1 (7)
where 0 < θ d ≤ 1 is the share of the consumption good 0 in the composite good D t+1 . An agent born in period t has preferences defined over consumption of the composite good C t and D t+1 . Intertemporal preferences of agents are described by the following CES utility function 5

U C t , D t+1 Γ =        C γ-1 γ t + δ D t+1 Γ γ-1 γ        γ γ-1 (8)
where δ is the discount factor, γ is the elasticity of intertemporal substitution in consumption and Γ is a scaling constant parameter. Let us define π c,t (resp. π d,t+1 ) the price of the composite good C t (resp. D t+1 ). An agent born in period t has to solve the optimal composition of the composite goods C t and D t+1 which are derived from the following static optimizations:

max max d 0,t+1 ,d 1,t+1 d θ d 0,t+1 d 1-θ d 1,t+1 | π d,t+1 D t+1 = d 0,t+1 + p t+1 d 1,t+1 (10)
The first order conditions gives:

c 0,t = θ c π c,t C t , c 1,t = (1-θ c )π c,t C t p t , π c,t = p t 1-θ c 1-θ c θ -θ c c . ( 11
)
d 0,t+1 = θ d π d,t+1 D t+1 , d 1,t+1 = (1-θ d )π d,t+1 D t+1 p t+1 , π d,t+1 = p t+1 1-θ d 1-θ d θ -θ d d . (12)
Contrary to Nourry and Venditti [START_REF] Nourry | Endogenous Business Cycles in OLG Economies with Multiple Consumption Goods[END_REF], we assume that young and old agents allocate their consumption differently between the non-durable and durable consumption goods, i.e. θ c θ d . As shown by Fernandez-Villaverde and Krueger [START_REF] Fernandez-Villaverde | Consumption over the Life Cycle: Facts from Consumer Expenditure Survey Data[END_REF], the consumption of durable goods fall when agent are retired. In order to satisfy this empirical evidence, and since θ c and θ d are the shares of the non-durable good in the consumption of young and old agents, we assume in the rest of the paper that θ c < θ d . Under perfect foresight w t and R t+1 are considered as given. A young agent born at period t solves the following dynamic program:

max C t ,D t+1 U C t , D t+1 Γ | w t = π c,t C t + φ t , π d,t+1 D t+1 = R t+1 φ t ( 13
)
Solving the first order condition gives:

π c,t C t = α R t+1 π c,t Γπ d,t+1 w t ≡ w t 1+δ γ R t+1 π c,t Γπ d,t+1 γ-1 ∈ (0, 1) (14)
where α

R t+1 π c,t
Γπ d,t+1 is the propensity to consume of young agent. Similarly using (13), the saving function is

φ t = 1 -α R t+1 π c,t
Γπ d,t+1 . In the following, we assume that the saving function is increasing with respect to the gross rate of return R t+1 .

Assumption 2. γ > 1.

This assumption states that the substitution effect following an increase in the gross rate of return R t+1 is greater than the income effect.

Dynamic equilibrium

Let us introduce k t = K t /L t the capital-labor ratio at time t and y t = Y t /L t the output-labor ratio at time t. The dynamics of the economy is described by the evolution of the capital stock and the market clearing condition for the consumable capital good:

k t+1 -w(k t ,y t ) p(k t ,y t ) 1 -α Θr(k t+1 ,y t+1 ) Γp(k t ,y t ) θc p(k t+1 ,y t+1 ) 1-θ d = 0 ( 15
)
θ c k t+1 -y t + (1 -θ d ) k t r(k t ,y t ) p(k t ,y t ) + (1 -θ c ) w(k t ,y t ) p(k t ,y t ) = 0 ( 16
)
with a constant term Θ =

(1-θ d ) 1-θ d θ θ d d (1-θ c ) 1-θc θ θc c
. The set of admissible paths is defined as follows:

ω = (k t , y t ) ∈ R 2 + | k t ≤ k, y t ≤ F 1 (k t , 1) (17)
where the maximum admissible value of capital k is solution of k -F 1 (k, 1) = 0. A perfect-foresight competitive equilibrium, defined as a sequence of allocations {k t , y t } ∞ t=0 , satisfies the two differences equations ( 15)-( 16) for every period t, with the pair (k 0 , y 0 ) given.

An efficient normalized steady state

A steady state (k t , y t ) = (k * , y * ) is defined by: k * -w(k * ,y * ) p(k * ,y * ) 1 -α Θr(k * ,y * ) Γp(k * ,y * ) 1+θc-θ d = 0 ( 18
)
θ c k * -y * + (1 -θ d ) k * r(k * ,y * ) p(k * ,y * ) + (1 -θ c ) w(k * ,y * ) p(k * ,y * ) = 0 (19)
In two-sector OLG model, any steady state depends on both consumption and production characteristics. Any variation of the elasticity of intertemporal substitution in consumption γ induces a change in the stationary capital-labor ratio and thus involves a modification of all the previously defined shares and elasticities evaluated at the steady state. In the following, we consider a set of economies parametrized by γ. In order to guarantee that the steady state remains unaltered when γ varies, the steady state (k * , y * ) is normalized by using two scaling parameters (Γ, θ d ).

Remark 1. Nourry and Venditti [START_REF] Nourry | Local Indeterminacy Under Dynamic Efficiency in a Two-Sector Overlapping Generations Economy[END_REF] assume that θ c = θ d = θ in [START_REF] Woodford | Stationary Sunspot Equilibria. The Case of Small Fluctuations Around a Deterministic Steady State[END_REF]. As a result the existence of a normalized steady state (NSS) is guaranted by two scaling parameters (Γ, θ). However, θ is also used as a bifurcation parameter. Such a dual role significantly complicates the analysis of the occurrence of endogenous fluctuations. In our model, we introduce a heterogeneity in the intratemporal preferences (θ c θ d ) which allows to disentangle the dual role of θ: θ d is taken as a scaling parameter while θ c is a bifurcation parameter.

Let us define ν = y k , the output-capital ratio, the inverse of ν represents the share of the consumable capital good which is invested. From [START_REF] Woodford | Stationary Sunspot Equilibria. The Case of Small Fluctuations Around a Deterministic Steady State[END_REF], the scaling parameter θ d lies between 0 and 1 if ν lies between ν and ν, with ν < ν:

ν = 1-αθ c 1-α , ν = 1-(1-s)αθ c (1-α)(1-s) (20)
Then, the following Proposition holds:

Proposition 1. Under Assumptions 1-2, (k * , y * ) is a normalized steady state if and only if Γ = Γ (k * , y * , γ) > 0 and θ d = θ d (k * , y * ) ∈ (0, 1).
Proof : See Appendix 7.1.

In the rest of the paper we made the following Assumption in order to guarantee the existence of NSS.

R = s (1-α)(1-s) (21)
If R > 1, the steady state (k * , y * ) is lower than the Golden-Rule level, i.e. the equilibrium is dynamically efficient. From Drugeon et al. [START_REF] Drugeon | On Efficiency and Local Uniqueness in Two-Sector OLG Economies[END_REF], the following Lemma holds:

Lemma 1. Under Assumptions 1-3, let α = 1-2s
1-s . An intertemporal competitive equilibrium converging towards a normalized steady state is dynamically efficient if α ∈ α, 1 and dynamically inefficient if α ∈ 0, α .

Lemma 1 asserts that under-accumulation of capital occurs when labor income of agents is less than capital income, i.e. s 1 2 . A young agent does not have enough labor income to save a sufficient amount. On the contrary, over-accumulation of capital occurs if the labor income of agents is higher than the capital income, i.e. s < 1 2 . A young agent have enough labor income to save a sufficient amount. However, over-accumulation of capital can be avoided provided the share of consumption of young agents is high enough, i.e. α > α. In the rest of the paper, the following Assumption is made:

Assumption 4. α ∈ α, 1 , s ∈ 1 3 , 1 2 and b < 0.
Assumption 4 states that we consider dynamically efficient paths, that we restrain the share of capital in the economy s in order to get positive value for α and that we concentrate on a capital intensive consumption good case. Cecchi and Garcia-Peñalosa [START_REF] Cecchi | Labour Market Institutions and the Personal Distribution of Income in the OECD[END_REF] show that over the period 1960-2003, OECD countries were characterized by a share of capital between 0.35 and 0.5 with an average level of 0.36. Using national accounting data on the main developed countries, Takahashi et al. [START_REF] Takahasi | Does the Capital Intensity Matter? Evidence from the Postwar Japanese Economy and Other OECD Countries[END_REF] show that over the last three decades the aggregate consumption good sector is more capital intensive than the capital good sector 6 .

Efficient endogenous fluctuations

This section discusses the existence of efficient endogenous fluctuations derived from changes in expectations about fundamentals. In our setting, the existence of local indeterminacy occurs if the two characteristic roots associated with the linearization of the dynamical system (15)-( 16) around the normalized steady state have a modulus less than one. Moreover, a Hopf bifurcation occurs if there exists some value of γ for which these roots are complex conjugate and cross the unit circle in the complex plane. To pursue the analysis, the elasticity of the rental rate of capital is introduced

ε rk = -T 11 (k * ,y * )k * T 1 (k * ,y * ) ( 22
)
6 See also Baxter [START_REF] Baxter | Are Consumer Durables Important for Business Cycles?[END_REF].

Drugeon [START_REF] Drugeon | On Consumptions, Inputs and Outputs Substituabilities and the Evanescence of Optimal Cycles[END_REF] points out that the elasticity of the rental rate of capital is negatively linked to the elasticities of capital-labor substitution.

Σ =

(y 0 +py)(pyk 0 l 0 σ 0 +y 0 k 1 l 1 σ 1) pyky 0

, ε rk = l 0 y 0 2 w(y 0 +py) Σ

with σ 0 , σ 1 the sectoral elasticities of input substitution. Let us denote two critical bounds on ν which appears to be important for the stability properties of the normalized steady state (k * , y * ):

ν 0 = 1 1-α , ν 1 = 1-αθ c (1-α)(1-s) . (24)
Then the following Lemma applies:

Lemma 2. Under Assumptions 1-3, the characteristic polynomial is defined by

P(λ) = λ 2 -λT + D where: T = 1+α(γ-1)ε rk [1-b(ν-ν)] 2 + sθ 2 c b 2 (1-α)(1-s) +ε rk b ν 1 -ν+ sbαθcν (1-α)(1-s) [1-b(ν-ν)]α (γ-1)bθ c ε rk (25) D = s 1-b ν-ν 0 -θcα(γ-1) 1-α (1-s)bθ c α(γ-1) (26)
Proof : See Appendix 7.2. Nourry and Venditti [START_REF] Nourry | Endogenous Business Cycles in OLG Economies with Multiple Consumption Goods[END_REF] assume symmetric preferences over the life cycle with θ c = θ d = θ. They show the possibility of efficient endogenous fluctuations through Hopf bifurcation when θ is low enough. 7 But the structure of their model appears in contradiction with the empirical evidence of Fernandez-Villaverde and Krueger [START_REF] Fernandez-Villaverde | Consumption over the Life Cycle: Facts from Consumer Expenditure Survey Data[END_REF]. Although these authors show that old agents consume less durable goods than young agents, the assumption θ c = θ d = θ implies a symmetric consumption behavior across the two periods of life. In our extended framework, we then focus on the case where the share of the pure consumption (non-durable) good is larger for old agents than for young agents, i.e. θ c < θ d . Put differently, we consider that young agents consume more durable goods than old agents. We then obtain the following Proposition: b) and ε rk ∈ (ε rk , ε rk ), the efficient steady state is locally indeterminate when γ ∈ (γ T , γ H ), undergoes a transcritical bifurcation when γ = γ T8 , and undergoes a Hopf bifurcation when γ = γ H . Moreover, there generically exist locally indeterminate (resp. saddle-point stable) period-2 cycles

Proposition 2. Under Assumptions 1-4, there exists θ c < θ d (k * , y * ) < 1, ν 0 > ν > 1, b < b < 0, ε rk > ε rk > 0 and γ F > γ H > γ T > 1 such that if α ∈ ( 1 2 , s 1-s ), θ c < θ c , ν ∈ (ν, ν 0 ), b ∈ (b,
when γ ∈ (γ F -ǫ, γ F ) (resp. γ ∈ (γ F , γ F +ǫ)) with ǫ > 0, i.e.

, when the bifurcation is super-(resp. sub-) critical, and locally indeterminate (resp. locally unstable) quasi-periodic cycles when

γ ∈ (γ H , γ H + ε) (resp. γ ∈ (γ H -ε, γ H )) with ε > 0, i.e.

, when the bifurcation is super-(resp. sub-) critical.

Proof : See Appendix 7.3.

Remark 2. Whether the bifurcation is super-or sub-critical is driven by the sign

of some coefficient computed from the second-and third-order approximations to two difference equations ( 15)-( 16). This property determines whether the bifurcation leads to the occurrence of locally indeterminate or unstable (resp. saddle point stable) quasi-periodic (resp. period-2) cycles near the bifurcation value.

Contrary to the formulation of Nourry and Venditti [START_REF] Nourry | Endogenous Business Cycles in OLG Economies with Multiple Consumption Goods[END_REF] with symmetric preferences over the life cycle, under dynamic efficiency a large share of the consumption of young agent, does not ruled out self-fulfilling fluctuations. The intuition of this result is quite simple. Starting from an arbitrary equilibrium, consider another one in which the agents expect a higher rate of investment at time t leading to some higher capital stock at time t + 1. This expectation will be self-fulfilling provided the amount of saving at date t is large enough to support the increase of the investment good output which directly provides the capital stock of the next period. When the equilibrium is dynamically efficient, the share of first period consumption is large enough to generate a stationary capital stock lower than the Golden Rule and thus prevents the agent from saving enough. At the same time, when the share of the pure consumption good in the composite good θ c is low enough, the production of the mixed good is consequently increased. This increase may then compensate the lack of savings and lead to an increase of capital compatible with the expectations. As a result, the initial expectation can be realized as an equilibrium, and, under dynamic efficiency, local indeterminacy together with fluctuations based on local sunspots are possible. Such sunspot fluctuations arise through a Hopf bifurcation. That generates quasi-periodic cycles which coincide to various period of expansion followed by various periods of boom. Therefore, the associated macroeconomic volatility corresponds to empirically plausible endogenous fluctuations.

Stabilization policy

The result of the previous section emphasizes that the economy may exhibits efficient endogenous fluctuations. It raises the question of a stabilization policy which may simultaneously stabilize the economy and move the equilibrium to the optimal steady state which provide an equal level of utility to all generations 9 . In the present section, it is proven that a fiscal policy exists under the assumption that agents and policy-maker do not make forecasting mistakes. Consider that the policy-maker buys goods, levies taxes and makes transfers under balanced budget rule. Let G t be the flows of consumption goods which is bought, β g,t > 0(< 0) the taxes (transfers) on the income of period of life g ∈ {c, d}, for generation t. The intertemporal maximization problem (13) turns to:

max C t ,D t+1 U C t , D t+1 Γ | w t + β c,t = π c,t C t + φ t , π d,t+1 D t+1 = R t+1 φ t + β d,t+1 (27)
The optimal saving function becomes:

φ t = Γ(w t +β c,t ) δR t+1 Π c,d Γ γ -β d,t+1 Π c,d R t+1 Π c,d +Γ δR t+1 Π c,d Γ γ ( 28
)
where

Π c,d = π c,t π d,t+1
Consider Proposition 1, the scaling parameter Γ is written as:

Γ (k, y) = R (k, y) Π c,d kp(k,y) δ γ [w (k,y)-k(k,y)p(k,y) ] 1 1-γ (29) where r (k, y) = T 1 (k, y) , p (k, y) = -T 2 (k, y) , w (k, y) = T 3 (k, y). Let, β o t+1 = kp (k, y) R (k, y) Π c,d + Γ (k, y) δR(k,y)Π c,d Γ γ R t+1 Π c,d R(k,y) γ -k t+1 p t R t+1 Π c,d + Γ (k, y) δR t+1 Π c,d Γ γ (30)
β c,t = w (k, y) -w t (31)
where R (k, y) = r(k,y) p(k,y) Plugging β c,t = β c,t , β d,t+1 = β d,t+1 , β c,t+1 = β d,t+2 = 0 into (28) gives

φ t = Γw(k,y) δR(k,y)Π c,d Γ γ R(k,y)Π c,d +Γ δR(k,y)Π c,d Γ γ (32)
It follows that if agents believe the announced policy rule, they will expect the optimal steady state to hold in the future. This expectation in turn drives the system to the steady state and keeps it there forever.

Numerical illustration

In order to show that when dynamic efficiency holds, local indeterminacy and endogenous fluctuations through Hopf bifurcation also holds, we provide a numerical illustration. Our aim is to prove the non-emptiness of the set of parameters' values for which the conditions of Proposition 2 holds.

A CES-Leontief Economy

Let us consider the following sectoral technologies:

F 0 K 0 , L 0 = µ K 0 -ρ 0 + (1 -µ) L 0 -ρ 0 -1 ρ 0 F 1 K 1 , L 1 = min K 1 η , L 1 (33)
with η > 0, µ ∈ (0, 1) and ρ 0 > -1. The sectoral elasticity of capital-labor substitution in the consumption good sector is σ 0 = 1 1+ρ 0 while the sectoral elasticity of capital-labor substitution in the consumable capital good sector is σ 1 = 0. Then the social production function is defined as:

T (K, Y, L) = µ (K -ηY) -ρ 0 + (1 -µ) (L -Y) -ρ 0 -1 ρ 0 (34)
Let L = 1 so that K = k * and Y = y * . We derive the stationary propensity to consume of young agents α, the share of capital in the economy s, the relative capital intensity difference b and the output-capital ratio ν * :

b = η-k * 1-y * , ν * = y * k * (35) α = (1-µ)(1-k * )k * ρ 0 (1-ην * ) ρ 0 +1 -ηµ(1-y) ρ 0 +1 (1-µ)k * ρ 0 (1-ην * ) ρ 0 +1 s = µ(1-y * ) ρ 0 +1 (1-µ)k * ρ 0 (1-ην * ) ρ 0 +1 +µ(1-y * ) ρ 0 +1 (36)
The numerical example is computed in line with the following approach: we choose θ c , η, µ, ρ 0 , γ and ν * in their admissible ranges. Substituting these parameters' values into (35)-(36), we then compute the values of α, b, s, ε rk and θ d (k * , y * ) and the critical bounds on b, ε rk , ν * and γ.

Efficient endogenous fluctuations

Let us consider the following set of parameters: µ = 0.99865, η = 0.022, θ c = 0.125, ρ 0 = 3, k * = 0.45, y * = 0.9, ν * = 2, γ = 2. We get an efficient steady state with α ≃ 0.53 and α ≃ 0.03. The corresponding share of capital is s ≈ 0.49. We find the share of the consumption good 0 in the composite good D t+1 , θ d (k * , y * ) ≃ 0.99, and the relative capital intensity difference b ≃ -4.28. We obtain the elasticity of the rental rate of capital ε rk ≃ 1.68. Then the efficient normalized steady state is locally indeterminate for any γ ∈ γ T , γ H , where γ T = 1.69 is a Transcritical bifurcation value inducing the existence of a second steady state and γ H = 2.55 corresponds to a Hopf bifurcation value leading to quasi-periodic cycle. The associated macroeconomic volatility is compatible with empirically relevant properties of fluctuations, in the sense that the Hopf bifurcation causes quasi-periodic cycles where several periods of expansion are followed by several periods of recession. Proposition 2 is satisfied for any b ∈ (-6.99, -4.18), ν * ∈ (1.98, 2.12), ε rk ∈ (0.38, 1.68), θ c < 0.98 and γ ∈ (1.69, 2.55).

Our findings (c 0 , c 1 , d 0 , d 1 ) = (0.02, 0.3, 0.41, 0.01) are qualitatively in line with the empirical evidence provided in Fernandez-Villaverde and Krueger [START_REF] Fernandez-Villaverde | Consumption over the Life Cycle: Facts from Consumer Expenditure Survey Data[END_REF] along which young agents consume more durable goods than old agents while old agents consume more non durable goods.

Concluding Remarks

The main objective of this paper is to study the influence of heterogeneous consumption goods on the occurrence of efficient endogenous fluctuations in twosector OLG model. We show that efficient endogenous fluctuations occur through Hopf bifurcation if the share of the pure consumption in the composite good is low enough for young agent. This condition is in line with the empirical evidence provided in Fernandez-Villaverde and Krueger [START_REF] Fernandez-Villaverde | Consumption over the Life Cycle: Facts from Consumer Expenditure Survey Data[END_REF] along which old agents consume less durable goods than young agents. We also prove that a fiscal policy based on transfers and taxes could simultaneously stabilize the economy and give an equal level of utility to each generation. Finally, we provide a numerical illustration showing that there exists a non-empty set of parameters' values for which efficient endogenous fluctuations arise through Hopf bifurcation. The associated macroeconomic volatility generates several periods of expansion, followed by several periods of recession.

Appendix

Proof of Proposition 1

Let (k * , y * ) ∈ 0, k × 0, k and Π c,d = Θp (k * , y * ) θ d -θ c . Solving equation [START_REF] Venditti | The Two Sector Overlapping Generations Model: A Simple Formulation[END_REF] with respect to Γ yields to:

Γ (k * , y * , γ) = Π c,d (k * , y * ) R (k * , y * ) δ γ [w (k * ,y * )-k * p(k * ,y * ) ] k * p(k * ,y * ) 1 γ-1 > 0 (37)
Solving equation ( 19) with respect to θ d yields to:

θ d (k * , y * ) = 1 + ν(k * ,y * )-ν(k * ,y * ) R(k * ,y * ) (38)

Proof of Lemma 2

From ( 14), one gets:

α ′ = -α(γ-1)(1-α)Γ RΠ c,d (39)
Under Assumption 1, the first order conditions of firm's profit maxmization problem 10 (1) yield to T 12 = -T 11 b, T 22 = T 11 b 2 , T 31 = -T 11 a and T 32 = T 11 ab with a ≡ K 0 L 0 > 0, b as defined by (3) and T 11 < 0. Consider ε rk as given by ( 22) and the fact that the homogeneity of T (K, Y, L) implies a = (1b) k * . T and D are obtained from the linearization of the two difference equations ( 15)-( 16) in the neighborhood of the normalized steady state.

Proof of Proposition 2

Following Grandmont et al. [START_REF] Grandmont | Capital-Labor Substitution and Competitive Nonlinear Endogenous Business Cycles[END_REF], we study the local dynamic properties by analysing the trace T and the determinant D. This methodology allows to analyse the variation of the trace T and the determinant D by choosing a bifurcation parameter. In this setting, the bifurcation parameter chosen is the elasticity of intertemporal substitution in consumption γ. Then the variation of the trace T and the determinant D in the (T , D) plane will be studied as γ evolves continuously within (1, +∞). The relationship between T and D is given by a half-line ∆ (T ) which is characterized from the consideration of its extremities (Figure 1). The starting point is the pair (lim γ→+∞ T ≡ T ∞ , lim γ→+∞ D ≡ D ∞ ), while the end point is the pair (lim γ→1 T ≡ T 1 , lim γ→1 D ≡ D 1 ). ∆ (T ) is obtained from the two difference equations ( 15)-( 16), by solving T and D with respect to α (γ -1):

∆(T ) = D ∞ + S (T -T ∞ ) ( 40
)
where the slope S , D ∞ and T ∞ are: Consider that b < 0 and α ∈ 1 2 , s 1-s so that D ∞ > 1, T ∞ < 0 and P ∞ (1) > 0. Let assume that θ c < θ c implying that ν 0 < ν 1 , defined in (24), and b 0 < b, where:

S = sε rk [1-b(ν-ν 0 )]
θ c =
Assume that ν = ν 0dν with dν > 0 small, it follows that Ξ in (45) is negative.

As a result T ≥ -2 if and only if:

ε rk > ε rk = -

Assumption 3 .

 3 Γ = Γ (k * , y * , γ) and θ d = θ d (k * , y * ).In our model, the Golden-Rule level of capital, denoted k, is characterized from the total stationary consumption C + D = T (k, y) + p yk . Denoting R (k, y) = -T 1 (k, y) /T 2 (k, y), k satisfies as usual R( k, ŷ) ≡ R = 1. Let us derive R the stationary gross rate of return at the NSS:

2 c b 2 RFigure 1 :

 221 Figure 1: Stability triangle and ∆ (T ) segment.

s 1 νFinally, T 1 =P - 2 - 1 )

 1121 α+(1-2α)(1-s) , b = -ν 1 -ν Rανθ c , b 0 = that θ c < θ d (k * , y * ) if ν ∈ ν, ν 0 and α > 0. Under ν ∈ ν, ν 0 and b ∈ b 0 , b we get D 1 = -∞ and P ∞ (-1) = 1 + T ∞ + D ∞ < 0, where b = -+∞ if and only if ν < ν 1 , b > b and ε rk1 > ε rk1 with ε rk1 = -1 Rbαθ c ν(b-b 1 ) (44)Using the expression of T and D allows to show that when D = 1, T > -2 if and only if:1 + ε rk α (γ -1) | D=1 P -2 (b) + b (ν 1ν + Rbαθ c ν) (b) = θ 2 c Rb 2 + 2θ c b 1b νν + 1b νν | D=1 = s(ν-ν 0 )(b 0 -b)bθ c( α-α)

1 [Figure 2 :

 12 Figure 2: Hopf and transcritical bifurcation.

In a two-periods OLG model, full depreciation of capital is justified by the fact that one period is about thirty years.

See Benhabib and Nishimura[START_REF] Benhabib | Stability of Equilibrium in Dynamic Models of Capital Theory[END_REF].

c 0,t ,c 1,t c θ c 0,t c 1-θ c 1,t | π c,t C t = c 0,t + p t c 1,t(9)5 All the conclusion of this paper can be obtained with a general concave and homothetic utility function U C t , D t+1 Γ .

Indeed, when θ is close to 1, only efficient endogenous fluctuations through a flip bifurcation can occur. The Hopf bifurcation is ruled out. See also Nourry and Venditti[START_REF] Nourry | Local Indeterminacy Under Dynamic Efficiency in a Two-Sector Overlapping Generations Economy[END_REF].

When the bifurcation parameter γ crosses a γ T , one characteristic roots crosses 1. We cannot a priori differentiate between the transcritical, the pitchfork or the saddle-node bifurcation from the linearized dynamic system (15)-(16). Under Assumption 3, the existence of the NSS is always ensured and a saddle-node bifurcation cannot occur. Moreover, the pitchfork bifurcation requires non-generic conditions, see Ruelle[START_REF] Ruelle | Elements of Differentiable Dynamics and Bifurcation Theory[END_REF]. In order to simplify the exposition we focus on the generic case and we relate the existence of one characteristic root going through 1 to a transcritical bifurcation.

For an example of stabilization policy in aggregate OLG model see Reichlin[START_REF] Reichlin | Equilibrium Cycles in Overlapping Generations Economy with Production[END_REF], and in Galor[START_REF] Galor | A Two-Sector Overlapping-Generations Model: A Global Characterization of the Dynamical System[END_REF] type two-sector OLG model see Nourry and Venditti[START_REF] Nourry | Local Indeterminacy Under Dynamic Efficiency in a Two-Sector Overlapping Generations Economy[END_REF].

See Benhabib and Nishimura[START_REF] Benhabib | Competitive Equilibrium Cycles[END_REF] and Bosi et al.[START_REF] Bosi | Competitive Equilibrium Cycles with Endogenous Labor[END_REF]