Philipp Del Hougne

From compressed sensing to learned sensing with metasurface imagers

Keywords: Intelligent Imaging, Learned Sensing, Programmable Metasurface Imager, Latency, Compressed Sensing, Machine Learning

Reducing the latency of electromagnetic imaging is a crucial objective for applications such as security screening, autonomous driving, and touchless human-machine interaction. In that respect, a fundamental caveat with conventional compressed sensing techniques is that initially all information is indiscriminately multiplexed across a diverse set of measurement modes, and only during data processing one begins to select the information that is relevant to the task (e.g. concealed weapon detection). In order to only acquire relevant information in the first place, and hence drastically reduce the number of necessary measurements, the "learned sensing" paradigm suggests to interpret reconfigurable measurement hardware (e.g. a dynamic metasurface aperture) as a trainable physical layer. The latter can be directly integrated into the machine-learning pipeline used on the data processing side such that one can jointly optimize physical weights (measurement settings) and digital weights (processing network). We discuss our recent numerical and experimental investigations of this new approach to electromagnetic imaging. Our results show that a considerable reduction of the number of scene illuminations is possible by using learned illumination patterns as opposed to conventional patterns (random, orthogonal or principal scene components). At the same time, we find that there are no intuitive explanations for the learned patterns. We also clarify whether the resolution of sub-wavelength features in the scene is limited by the conventional diffraction limit.

INTRODUCTION

Latency currently limits the most promising applications of electromagnetic imaging and sensing, including security screening, autonomous driving and touchless human-machine interactions. Every imaging pipeline has two main potential latency bottlenecks: (i) the required number of measurements per imaged scene, and (ii) the processing burden. Many efforts to reduce latency revolve around the idea of "compressing" sparse scene information to reduce the number of measurements. [START_REF] Donoho | Compressed sensing[END_REF] An underappreciated point of view regarding latency is that of the flow of information: at what point in the pipeline do we separate relevant and irrelevant information? The vast majority of current electromagnetic imagers indiscrimantely acquires all information, including large amounts of irrelevant information, and then attempts to identify relevant pieces of information during processing. The double disadvantage of this strategy is immediately obvious: more measurements are needed, and it takes more processing effort to select relevant information. Here, we outline a generic strategy for identifying relevant information already during the measurement process, and demonstrate its significant latency gains in various prototypical case studies.

To develop our ideas, without loss of generality we focus in the following on two imaging architectures based on programmable metasurfaces. Both can be thought of as low-cost alternatives to the use of coherently controlled antenna arrays for pattern synthesis. While the latter require countless radiofrequency chains (one per antenna), both metasurface paradigms that we consider operate with a single feed. In one instance, a horn antenna illuminates a programmable metasurface acting as reconfigurable reflect-array that impresses a desired pattern on the reflected wavefront. In another instance, the single feed excites a two-dimensional waveguide which is patterned with metamaterial elements that are programmed to leak energy at desired locations from Correspondance to P.d.H. (philipp.del-hougne@univ-rennes1.fr).

the waveguide to the far field in order to holographically synthesize a desired pattern. While the second instance is more compact, both have in common the use of in situ programmable meta-atoms to shape the waves that illuminate the scene. From an imaging perspective, both constitute programmable coded apertures suitable for multiplexed measurements with configurational diversity.

INFORMATION FLOW

To start our analysis of the information flow in electromagnetic imagers, we note that in the vast majority of cases, creating a visual image of the scene is not the ultimate goal but an intermediate step. The image is then further analyzed (typically with artificial intelligence tools) to detect concealed weapons (security screening), to identify vehicles or pedestrians on the road ahead (autonomous driving), or to recognize hand gestures (touchless human-machine interaction). Often these ultimate processing goals are neglected and studies content themselves with presenting an uninterpreted visual image of a scene; yet it is the specific interpretation task that determines which information is relevant, and which information is acquired but useless for the task at hand. A traditional imager is schematically depicted in Fig. 1(a). It is based on a one-to-one mapping between scene and image, and then the image is interpreted to identify the sought-after information. In other words, the separation of relevant and irrelevant information occurs only at the very last step. A "compressive" imager is illustrated in Fig. 1(b). Instead of the one-to-one mapping between scene and measurements, spatial scene information is multiplexed across a diverse set of measurement modes with a coded aperture. A series of measurements corresponding to different configurations of the coded aperture is taken, and an image of the scene is reconstructed and then interpreted. Assuming that the scene is sparse, this compressive scheme has the potential to reduce latency if the speed-up due to the lower number of measurements outweighs the additional processing burden due to image reconstruction. However, again, relevant information is separated from irrelevant information only at the very last step.

Several ideas have been put forward to lower the latency of the compressive imager from Fig. 1(b). A first set of ideas revolves around reducing the processing burden. One proposal is to limit the image reconstruction to the most significant principal components of the measurement modes. [START_REF] Fromentèze | Lowering latency and processing burden in computational imaging through dimensionality reduction of the sensing matrix[END_REF] Another idea would be to skip the image reconstruction alltogether and directly process the "raw" data. A second set of ideas revolves around the coded aperture configurations. Initially, a series of random configurations was used. [START_REF] Chan | A single-pixel terahertz imaging system based on compressed sensing[END_REF] Subsequent efforts aimed at achieving such randomness by leveraging complex scattering media, using their spatial, 4 spectral 5 or configurational [START_REF] Sleasman | Microwave imaging using a disordered cavity with a dynamically tunable impedance surface[END_REF] diversity, or by fabricating man-made disordered meta-structures to the same effect. [START_REF] Hunt | Metamaterial apertures for computational imaging[END_REF][START_REF] Xie | Single-sensor multispeaker listening with acoustic metamaterials[END_REF][START_REF] Sleasman | Dynamic metamaterial aperture for microwave imaging[END_REF][START_REF] Sleasman | Implementation and characterization of a two-dimensional printed circuit dynamic metasurface aperture for computational microwave imaging[END_REF] Random measurement modes are "quasi-orthogonal" but not truly orthogonal because they always have a finite overlap, resulting in an inevitable acquisition of redundant information in subsequent measurements. Hence, if truly orthogonal measurement modes could be used, no redundant information would be acquired such that fewer measurements would be needed. The implementation of truly orthogonal coded aperture configurations has been achieved by carefully configuring a reflect-array with patterns from the Hadamard basis [START_REF] Watts | Terahertz compressive imaging with metamaterial spatial light modulators[END_REF] or by judiciously tuning the scattering properties of a complex medium. [START_REF] Del Hougne | Optimally diverse communication channels in disordered environments with tuned randomness[END_REF][START_REF] Del Hougne | Optimal multiplexing of spatially encoded information across custom-tailored configurations of a metasurface-tunable chaotic cavity[END_REF] All imagers discussed thus far are completely oblivious to scene, measurement hardware and task. In other words, they ignore available a priori knowledge such that these imagers are slowed down by the flow of irrelevant information through their measurement and processing layers. It is important to note that in a typical imaging scenario, vast amounts of a priori knowledge are available, including the expected scene (e.g. a human in security screening), the measurement hardware (e.g. a specific programmable-metasurface device) and the task (e.g. concealed weapon detection in security screening). The more use of this a priori knowledge is made, the more specific the imaging setup can be, and it is this tailoring that will enable the separation between relevant and irrelevant information earlier on in the pipeline.

A first notable effort in that spirit was the idea to make use of knowledge about the expected scene by using principle scene components as illumination patterns. [START_REF] Liang | Reconfigurable array design to realize principal component analysis (pca)-based microwave compressive sensing imaging system[END_REF][START_REF] Li | Machine-learning reprogrammable metasurface imager[END_REF] These studies indeed achieved a reduction of latency by reducing the number of required measurements. However, they still ignored large portions of the available a priori knowledge, notably about the task. The measurement process did not discriminate between relevant and irrelevant information for the task at hand, implying the acquisition of useless (irrelevant) information.

Here, we describe a class of "intelligent" imagers that select task-relevant information already in the measurement process (see Fig. 2), thereby achieving significant latency improvements. The underlying principle (illustrated in Fig. 3) is to treat the entire pipeline from measurement to answering a specific task in an endto-end fashion. Specifically, inspired by recent work on intelligent microscopes, [START_REF] Horstmeyer | Convolutional neural networks that teach microscopes how to image[END_REF] we interpret reconfigurable measurement settings (in our case in situ programmable meta-atoms) as trainable physical weights that can be optimized in a unique pipeline together with the digital weights of an artificial neural network (ANN) on the processing side. 17 3. An artist's impression of "Learned Sensing". Information flows through a hybrid analog-digital ANN containing both physical and digital weights that are jointly trained. Thereby, the measurement process is aware of the ultimate task and discriminates between relevant and irrelevant information.

LEARNED SENSING

Setting up the hybrid analog-digital end-to-end pipeline

The first step toward implementing a "learned" sensing pipeline is to obtain a forward model of the physical measurement process in order to integrate it into the pipeline. In some scenarios, such a forward model can be of analytical nature. For instance, for the aforementioned planar dynamic metasurface transceivers, an efficient compact description of the radiating sub-wavelength meta-atoms as dipoles is feasible. [START_REF] Del Hougne | Learned integrated sensing pipeline: Reconfigurable metasurface transceivers as trainable physical layer in an artificial neural network[END_REF] In other scenarios, an accurate analytical description of the measurement process may be too cumbersome or impossible. In these cases, an ANN can be trained to approximate the forward model. [START_REF] Li | Intelligent electromagnetic sensing with learnable data acquisition and processing[END_REF] A hybrid approach is also conceivable, in which due to fabrication inaccuracies a few parameters of the analytical model are fine-tuned based on experimental measurements. If an analytical forward model involves mathematical functions that are not easily differentiable, it may be preferable to resort to an ANN-based approximation of the forward model in light of the subsequent training phase.

The hybrid analog-digital end-to-end pipeline is then set-up in a suitable programming environment such as TensorFlow. The first layer is not a standard ANN-layer but a custom layer, namely the forward model of the measurement process. [START_REF] Del Hougne | Learned integrated sensing pipeline: Reconfigurable metasurface transceivers as trainable physical layer in an artificial neural network[END_REF] The programmable parameters therein, in our case the configuration of the programmable meta-atoms, are treated as the trainable variables of this first (physical) layer. [START_REF] Del Hougne | Learned integrated sensing pipeline: Reconfigurable metasurface transceivers as trainable physical layer in an artificial neural network[END_REF] From the first layer, the information seamlessly flows into subsequent layers that are conventional ANN-layers (e.g. fully connected layers), as seen in Fig. 3. Each of these digital layers, of course, also contains numerous trainable (digital) weights.

An interesting aside is the question what type of digital ANN-layers would be most suitable. Currently, convolutional architectures are very popular. [START_REF] Horstmeyer | Convolutional neural networks that teach microscopes how to image[END_REF] Their popularity originates from their use in computer vision, where they are applied to "traditional" images as in Fig. 1(a) and excel at identifying relevant local correlations in the data. However, given that in our case the data is completely scrambled by the multiplexing (and we intend to skip the image reconstruction step), the sought information is very likely encoded in long-range correlations within the data such that fully connected layers appear more suitable. [START_REF] Zheng | Processing global and local features in convolutional neural network (cnn) and primate visual systems[END_REF][START_REF] Del Hougne | Robust position sensing with wave fingerprints in dynamic complex propagation environments[END_REF][START_REF] Zhu | Image reconstruction through a multimode fiber with a simple neural network architecture[END_REF]

Jointly training physical and digital weights

Once the hybrid pipeline is set up, the challenge lies in jointly training both physical and digital weights. Supervised learning requires access to a labelled training data set. Such data can be generated, for instance, based on binarized optical images of the scene. [START_REF] Li | Intelligent electromagnetic sensing with learnable data acquisition and processing[END_REF] The optimization of the trainable weights is then usually accomplished via error backpropagation, [START_REF] Lecun | Deep learning[END_REF] hence the need for differentiable functions in the forward model. In many "learned sensing" problems, the one-bit programmability of the meta-atoms implies binary (thus discontinuous) physical weight variables which are in principle incompatible with error backpropagation. However, various tricks such as the use of a "temperature parameter" can overcome this challenge. [START_REF] Chakrabarti | Learning sensor multiplexing design through back-propagation[END_REF] It is important to note that the outcome of the training process depends to some extent on the random initialization of the variables. This is not surprising but in fact very common in most inverse problems. There is no guarantee of identifying the globally optimal set of configurations, but typically different optimization runs identify distinct sets of locally optimal configurations that perform roughly equally well. An interesting interpretation of this is to draw an analogy with statistical physics: 24 different configurations of the velocity of the air molecules correspond to the same room temperature, pressure, etc. In our problem, there are different realizations of the weights that correspond to roughly similar performance in terms of a specific task.

Performance benchmarking against the state-of-the-art

To evidence the substantial latency improvements with "learned sensing", we benchmark the performance characteristics against the three previously discussed state-of-the-art scene illumination strategies (random patterns, orthogonal patterns, principal scene components) in the same imaging/sensing setup. Specifically, we consider in Fig. 4 the dependence of the achievable accuracy in a prototypical classification task as a function of the number of utilized scene illuminations. The fewer measurements are needed to achieve a targeted accuracy, the faster both the measurement and the processing are, resulting in a double advantage in terms of latency.

In Fig. 4(a) we consider a prototypical object recognition task in simulation. The scene contains a metallic digit that is to be recognized by illuminating the scene with a series of patterns formed by a planar dynamic metasurface transceiver. [START_REF] Del Hougne | Learned integrated sensing pipeline: Reconfigurable metasurface transceivers as trainable physical layer in an artificial neural network[END_REF] If very few measurements are allowed, our approach outperforms all three conventional techniques by up to 15 % in terms of achievable accuracy. Naturally, as more and more measurements are allowed, the gap gets narrower, and if many measurements are taken, no difference between the schemes is expected.

The results in Fig. 4(a) can also be discussed in terms of the amount of useful information obtained per measurement. A random set of illuminations yields the worst performance because it makes no attempt at discriminating between relevant and irrelevant information, and moreover acquires redundant information in subsequent measurements. Orthogonal patterns perform slightly better because they remove the redundancy issue but still fail to discriminate between relevant and irrelevant. A more notable improvement is obtained with principle scene components as illumination patterns because knowledge about the expected scene is used; yet knowledge about the task is still ignored. If knowledge about the task is deployed via the "learned sensing" paradigm, a remarkably better performance is achieved.

In Fig. 4(b) we consider a human gesture recognition task in experiments. This time, the scene is illuminate by waves reflected of a programmable metasurface reflect-array. [START_REF] Li | Intelligent electromagnetic sensing with learnable data acquisition and processing[END_REF] In line with the previous case study, "learned sensing" enables higher classification accuracies with fewer measurements in comparison to the state-of-the art.

Can we understand why the learned patterns are optimal?

Having observed the superior performance of the learned patterns, one question remains: can we gain an intuitive understanding of them? To shed light on this question, we return to our case study from Fig. 4(a). Specifically, we compare the four illumination techniques in terms of the patterns' overlap in Fig. 5(a) and the patterns' resemblance to principle scene components in Fig. 5(b). [START_REF] Del Hougne | Learned integrated sensing pipeline: Reconfigurable metasurface transceivers as trainable physical layer in an artificial neural network[END_REF] First, we note in Fig. 5(a) that the overlap of the orthogonal patterns is close to zero, confirming that they were properly synthesized. The overlap of the learned patterns is similar to that of the random patterns, indicating that redundancy considerations do not play a major role. We further observe that the PCA patterns overlap only slightly less than the random patterns even though ideal PCA patterns are orthogonal by definition -hinting at the difficulty to properly synthesize PCA patterns under the given hardware constraints. This is also evidenced in Fig. 5(b) which reveals that the overlap of the PCA-based patterns with the principal scene components is high but far from unity. The learned patterns have slightly more overlap with the principle scene components than random or orthogonal patterns which are both scene-agnostic. This explains why solely making use of knowledge about the expected scene as in Refs. [START_REF] Liang | Reconfigurable array design to realize principal component analysis (pca)-based microwave compressive sensing imaging system[END_REF][START_REF] Li | Machine-learning reprogrammable metasurface imager[END_REF] only offers limited latency gains well below those achievable with "learned sensing": the optimized learned patterns only mildly take into account the scene [START_REF] Del Hougne | Learned integrated sensing pipeline: Reconfigurable metasurface transceivers as trainable physical layer in an artificial neural network[END_REF] The dependence of the object classification accuracy on the number of utilized scene illuminations is plotted ("LISP") and compared to three state-of-the-art approaches (random, orthogonal, principal scene components). (b) Experiment based on a programmable metasurface reflect-array as hardware for human gesture recognition. [START_REF] Li | Intelligent electromagnetic sensing with learnable data acquisition and processing[END_REF] The dependence of the gesture classification accuracy on the number of utilized scene illuminations is plotted and compared against the use of random scene illuminations.

knowledge. Overall, Fig. 5 demonstrates that the learned patterns are not easily explained in terms of overlap or principal scene components because they take into account the specific task; they are hence not intuitive and can only be obtained through the end-to-end hybrid analog-digital pipeline discussed above.

CONCLUSION AND OUTLOOK

In summary, we have discussed the evolution from "compressed" to "learned" sensing from an information flow perspective. Given the quest to reduce the latency of electromagnetic imagers as much as possible, we showed that discriminating between relevant and irrelevant information already during the measurement process rather than at the very last processing step is crucial. We outlined a general recipe to that effect which consists of a hybrid analog-digital pipeline containing trainable physical and digital weights, encompassing both the programmable measurement process as well as the data processing. Jointly optimizing physical and digital weights allows the measurement process to be task-aware by selecting relevant information. Thereby, more useful information is obtained per measurement such that overall latency is drastically improved. We illustrated this for two prototypical recognition tasks with two distinct examples of single-feed programmable-metasurface hardware. While this paper has focused on latency, it is worthwhile noting that limiting the number of necessary measurements is also favorable with respect to numerous further metrics, including power consumption, radiation exposure, required computational resources and cost. Moreover, although the considered programmable metasurface devices appear advantageous in comparison to traditional antenna arrays in terms of the hardware complexity, the "learned sensing" paradigm is equally applicable to antenna array architectures such as phased arrays. The trainable physical parameters in that case could be the phase and/or amplitude settings of each antenna.

Looking forward, the information flow perspective may offer further opportunities for reducing latency in electromagnetic imaging. Specifically, a dynamic (rather than static) sequence of coded aperture configurations that in addition takes into account information from preceding measurements is an enticing avenue for future investigations, [START_REF] Chaware | Towards an intelligent microscope: adaptively learned illumination for optimal sample classification[END_REF] akin to the recurrent visual attention of humans. [START_REF] Mnih | Recurrent models of visual attention[END_REF] Within the context of metasurface-based hardware, such a step may provide the programmable meta-atoms with a "cognitive" feature.

A second topic for future research is the application of the "learned sensing" paradigm to a special type of coded aperture: the "reverberation coded aperture" (RCA). [START_REF] Del Hougne | Deeply sub-wavelength localization with reverberationcoded-aperture[END_REF] RCAs are coded apertures based on complex media for which the scene is within rather than outside the complex medium. This difference means that waves interact with the scene not once but countless times, hence developing a much stronger sensitivity to sub-wavelength scene details. There is a direct link between the waves' dwell time in the complex medium, their sensitivity to sub-wavelength details and the achievable resolution. [START_REF] Del Hougne | Deeply sub-wavelength localization with reverberationcoded-aperture[END_REF] Without any manipulation of the scene's near field, RCAs enable the recovery of deeply sub-wavelength details -a fact that does not violate the diffraction limit because this limit ignores available a priori knowledge, the signal-to-noise ratio and the fact that coded aperture imagers are not even based on focusing. By optimizing an RCA's scattering properties in a "learned sensing" framework, further resolution improvements appear to be achievable. The practical relevance of RCAs lies in the fact that many electromagnetic imaging scenarios naturally involve a scene enclosed by a scattering enclosure, for instance, imaging and sensing in an indoor environment, a metro station or an airplane.

Figure 1 .

 1 Figure 1. Comparison of the entire imaging pipeline for "traditional" and "compressive" imagers, from the measurement process all the way to answering a specific task. Both paradigms indiscriminately acquire both relevant (blue) and irrelevant (red) scene information and only separate the two in the very last step. The compressive imager has an additional image reconstruction step because it acquires multiplexed measurements.

Figure 2 .

 2 Figure 2. Conventional imagers (a) are task-agnostic, and drag irrelevant information through the entire pipeline until they discriminate between relevant and irrelevant information at the very last step. An "intelligent" imager (b) is taskaware, and makes this discrimination already during the measurement process. Moreover, the image reconstruction step is skipped and instead the raw data is directly interpreted.

Figure

  Figure3. An artist's impression of "Learned Sensing". Information flows through a hybrid analog-digital ANN containing both physical and digital weights that are jointly trained. Thereby, the measurement process is aware of the ultimate task and discriminates between relevant and irrelevant information.

Figure 4 .

 4 Figure 4. Two implementations of learned sensing with programmable metasurface hardware. (a) Numerical study considering planar dynamic metasurface transceivers as hardware for object (metallic digit) recognition.[START_REF] Del Hougne | Learned integrated sensing pipeline: Reconfigurable metasurface transceivers as trainable physical layer in an artificial neural network[END_REF] The dependence of the object classification accuracy on the number of utilized scene illuminations is plotted ("LISP") and compared to three state-of-the-art approaches (random, orthogonal, principal scene components). (b) Experiment based on a programmable metasurface reflect-array as hardware for human gesture recognition.[START_REF] Li | Intelligent electromagnetic sensing with learnable data acquisition and processing[END_REF] The dependence of the gesture classification accuracy on the number of utilized scene illuminations is plotted and compared against the use of random scene illuminations.

Figure 5 .

 5 Figure 5. Analysis of the learned illumination patterns from Fig. 3(a) in terms of their overlap (a) and their resemblance to principle scene components (b).


The new Norton Critical Edition (NCE) of Leviathan is a boon for students, and its twin, the Norton Library (NL) edition is a boon both for students and teachers alike

are mainly to be found in the presentation, to make it more palatable to undergraduatesyou will find three telling examples of those "slight" changes in "A note on the text" in the NL edition (p. xxxvi-xxxvii). As for the 1670 Bear and the 1668 Latin editions, the main reason why Johnston has "excluded the Latin Leviathan from consideration" (NL, p. xxxv) and has "given only incidental consideration to the Bear edition" (ibid.) is that the historical context had changed, and that the 1650/51 context was more favorable to freedom of thought. In a time of religious and political unrest such as the early years of the Commonwealth of England it was easier for a philosopher to publish what he had on his mind, especially in matters of religion, without "the constraints of censorship" (NL, p. xxxv); after the Restoration, when the Anglican Church had reconquered its predominance in the kingdom, it was no longer possible to publish views on the Trinity such as the ones that could be read in chapter XLII of the Head edition (chap. 42.3, p. 267-269page-numbering of the Head edition is given by NCE and NL editions, which we use in the present review).

Notwithstanding the paradox there is in preferring the version of a text less constrained by censorship when the philosopher defends a doctrine of subjection to the sovereign in matters of doctrines, this choice of the Head edition makes sense. It has a consequence though on the comparison between [203] NCE and NL Leviathan edition and Curley's edition. If the 1651 English and 1668 Latin Leviathans are really, as the editors claim, two different books, it certainly deprives of all relevance a comparison between the two Norton editions and the Hackett publishing edition: "the Latin Leviathan, the text of which differs considerably from that of the Head and Bear editions, should be considered a different work" (NL, p. xxxv). In his pioneering French translation of Leviathan (1971) François Tricaud translated some of the more important Latin variants that he put in footnotes, and it is that French lead which Curley followed in his Hackett edition ("My greatest debt is to François Tricaud…", p. lxxvi). Tricaud's justification wasit must be rememberedthat the Latin Leviathan published in 1668 was based on a Latin proto-Leviathan, never published, that might have been written around 1648-1649(Léviathan, ed. F. Tricaud, 1971, p. XXVI). That hypothesis, that was initially formulated by Zbigniew Lubiénski in 1932, has been abandoned today, even by Martine Pécharman in her introduction to the French translation of the Latin Leviathan which she completed after François Tricaud's death (Léviathan, traduit du latin et annoté par François Tricaud et Martine Pécharman, 2004, p. XXVII-XXX). But Curley was relatively agnostic about the proto-Leviathan hypothesis, stressing only that, "whenever Hobbes may have written a particular passage, the Latin version represents the way he presented his thought in 1668" (p. lxxviv). So the reason why Johnston considers it worthwhile not to have notes with the Latin variants is precisely the reason why Curley did consider it indispensable to include them. The difference in historical context is for the former an excellent reason not to mention the Latin variants to American undergraduates, whereas, for the latter, it is a good reason to mention the most significant of those variants. If there is no doubt that the NCE has now to be preferred because it benefitted for the latest scholarship on Leviathan, it is not so sure that it should also be preferred because it hasn't included the Latin variants. After all, the title of the 1651 and 1668 editions is Leviathan ; if the books were so different, why keep the same title? Moreover, since nobody denies that many chapters of the Latin Leviathan are identical to the early edition in English, and that in both versions the structure is the same, trying to figure out why there are substantial differences, notably but not only in the concluding part, could be considered as an excellent exercise for philosophers in the making. But it is also true that such a pedagogical work may be too demanding for students who are no longer used to working in languages other than English.

Some other arguments could be added in favor of the NCE Leviathan: Johnston's modernization in these editions is more carefully done than Curley's since he had Curley's to work from and think through, and maybe also because it happens to Curley to 'modernize' the punctuation in ways that [204] actually change the sense, a fault not to be found in Johnston's more recent editionsto say it less dogmatically, a fault that the present reviewer has not yet found. Though, as simplifying and modernizing are not exact sciences the two Norton editions will be judged by their respective users. Another argument for using the revised NCE Leviathan is its selection of historical sources: if Leibniz's text on State-Sovereignty has disappeared from the list, there is a text from Aubrey's Brief Lives that adds important biographical elements to the extract from Pierre Bayle's Dictionary Historical and Critical. As for the choice of extracts from scholarly papers, it has been entirely renewed with papers that have been published since 2005. The 1997 choice of "interpretations" included Michael Oakeshott's introduction to Leviathan, an extract from Leo Strauss, Natural Right and History, Johann P. Sommerville's "Hobbes on Political Obligation", Richard Tuck's "Hobbes on Skepticism and Moral Conflict", Jean Hampton's "The Failure of Hobbes's Social Contract Argument", David Johnston's "Theory and Transformation: The Politics of Enlightenment", George Kateb's "Hobbes and the Irrationality of Politics" and Richard E. Flathman's "Of Making and Unmaking". The new selection, presented under the heading "Criticism", includes an extract from Kinch Hoekstra's "Hobbesian Equality", Jane S. Jaquette's "Defending Liberal Feminism: Insights from Hobbes", and extracts from Eleanor Curran's "Blinded by the Light of Hohfeld: Hobbes's Notion of Liberty", Teresa M. Bejan's "Teaching the Leviathan: Thomas Hobbes on Education", Quentin Skinner's "Hobbes on Representation", and Arash Abizadeh's "Hobbes's Conventionalist Theology". Those papers are all outstanding, and reflect recent Anglophone scholarship. This selection will help students situate Hobbes's ideas on equality, liberty, education, feminism, representation and theology.

If we now turn to the NL edition, it might be preferred to the NCE for a variety of reasons, and for sure by teachers, since some addenda to the text makes it a very useful instrument. As for the edited text of Leviathan, it might be said that it is identical in both editions. That affirmation is 99 percent true, but for the purists it must be added that it benefitted from a last complete read by David Johnston, and also from the attention of Kinch Hoekstra, whose contribution to the editorial work was already hailed by David Johnston by special thanks in the NCE -for his "clearness of judgment, largeness of fancy, strength of reason, and graceful elocution" he compares his colleague to Sidney Godolphin who received the same compliments from Hobbes ( "Acknowledgments", p. 649). Among the addenda, one should mention the "Further Reading" section that gives a series of contributions with summaries, so that students and teachers may easily find intellectual resources when dealing with other works by [205] Hobbes, the "composition, title, and frontispiece of Leviathan", "Responses to Leviathan", "Biography", "Introductions and classic interpretations", "Leviathan in its broad and immediate contexts", "Collections of Essays", and various topics. The choice of references is again exclusively Anglophone. The introduction plays of course an important partthere is none in the NCE -, and it is a real compendium of all that a student cannot but know about Hobbes and his work. The summary of "Hobbes's life" is a model (NL, p. xii-xv), what is said on the limitations of philosophy an excellent way to introduce the reader to Hobbes's method, and the part on "The ideological Aims of Leviathan" is a subtle answer to Quentin Skinner's provocative argument that Leviathan might be just another "tract" among the so many that were published in the troubled time of its publication. A quote is the best way to pay homage to the "clearness of judgment" and "graceful elocution" of the authors: "Especially central to his argument is the picture he paints of some aspects of the history of Christianity. Hobbes's rendition of this picture focuses on the immense power of ideas as tools that shape human behavior and as weapons in the struggle for power. The ideological campaign he [Hobbes] launched in this work is at the heart of some of his most impassioned passages, and helped lift Leviathan out of the category of locally significant political tracts and into the category of longremembered works of political philosophy, where it firmly resides today" (NL, p. xxi). The authors are right to recognize the ideological dimension of the book, and its defense of a certain model of sovereignty in a time when it was attacked when threatening the authority of clerics, and right to say that Leviathan is not only an intervention in a particular context, but a view of "the struggle between king and parliament […] within a long historical perspective" (NL, p. xix).

The new NCE is therefore a huge improvement on the previous edition (not leastbut not onlybecause it includes the whole of the text of the Leviathan), and the NL edition should now be the preferred teaching edition, at least, to put it in American terms, for undergraduates.

Luc Foisneau CNRS -French National Center for Scientific Research, Paris, France luc.foisneau@ehess.fr


Franc ¸ois Bonnet
email: francois.bonnet@irisa.fr

Michel Raynal
email: raynal@irisa.fr

F Bonnet

Looking for the Weakest Failure Detector for k-Set Agreement in Message-passing Systems: Is Π k the End of the Road?

Keywords: Asynchronous systems, Eventual leaders, Failure detectors, Message passing system, Quorums, Reduction, k-Set agreement, Wait-freedom Accord ensembliste, Asynchronisme, Défaillances des processus, Détecteur de fautes

In the k-set agreement problem, each process (in a set of n processes) proposes a value and has to decide a proposed value in such a way that at most k different values are decided. While this problem can easily be solved in asynchronous systems prone to t process crashes when k > t, it cannot be solved when k ≤ t. Since several years, the failure detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the k-set agreement problem in read/write shared-memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases k = 1 (consensus) and k = n -1 (set agreement). This paper introduces a candidate for the general case. It presents a new failure detector class, denoted Π k , and shows Π 1 = Σ × Ω (the weakest class for k = 1), and Π n-1 = L (the weakest class for k = n -1). Then, the paper investigates the structure of Π k and shows it is the combination of two failures detector classes denoted Σ k and Ω k (that generalize the previous "quorums" and "eventual leaders" failure detectors classes). Finally, the paper proves that Σ k is a necessary requirement (as far as information on failure is concerned) to solve the k-set agreement problem in message-passing systems. The paper presents also a Π n-1 -based algorithm that solves the (n -1)-set agreement problem. This algorithm provides us with a new algorithmic insight on the way the (n -1)-set agreeement problem can be solved in asynchronous message-passing systems (insight from the point of view of the non-partitioning constraint defined by Σ n-1 ).

Introduction

The k-set agreement problem This problem is a coordination problem (also called decision task). It involves n processes and is defined as follows [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF]. Each process proposes a value and every non-faulty process has to decide a value (termination), in a such a way that any decided value is a proposed value (validity) and no more than k different values are decided (agreement). The problem parameter k defines the coordination degree; k = 1 corresponds to its most constrained instance (consensus problem) while k = n -1 corresponds to its weakest non-trivial instance (set consensus problem).

Considering the process crash failure model, let t be the maximal number of processes that may crash in a run (1 ≤ t < n). When t < k, the k-set agreement can always be solved, be the system synchronous or asynchronous. When t ≥ k, the situation is different. While the problem can always be solved in synchronous systems, [START_REF] Chaudhuri | Tight Bounds for k-Set Agreement[END_REF] (see [START_REF] Raynal | Synchronous Set Agreement: a concise guided tour (including a new algorithm and a list of open problems)[END_REF] for a survey), it has no solution in asynchronous systems [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].

The failure detector-based approach A failure detector is a distributed oracle that gives alive processes hints on process failures [START_REF] Chandra | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]. Failure detectors have been investigated to solve k-set agreement problem since 2000 [START_REF] Mostéfaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF] 1 . Lower bounds to solve the k-set agreement in asynchronous message-passing systems enriched with limited accuracy failure detectors have been conjectured in [START_REF] Mostéfaoui | k-Set Agreement with Limited Accuracy Failure Detectors[END_REF] and proved in [START_REF] Herlihy | Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors[END_REF]. The question of the weakest failure detector class for the k-set agreement problem (k > 1) has been stated first in [START_REF] Raynal | In search of the holy grail: looking for the weakest failure detector for wait-free set agreement[END_REF].

The case k = 1 and the case k = n -1 When k = 1, as already indicated k-set agreement boils down to consensus, and it is know that the failure detector class Ω is the weakest to solve consensus in asynchronous message-passing systems where t < n/2 [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF]. Ω ensures that there is an unknown but finite time after which all the processes have the same non-faulty leader (before that time, there is an anarchy period during which each process can have an arbitrarily changing leader). This lower bound result is generalized in [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF] where it is shown that Σ × Ω is the weakest failure detector class to solve consensus when t < n. This means that Σ is the minimal additional power (as far as information on failures is concerned) required to overcome the barrier t < n/2 and attain t ≤ n -1. Actually the power provided by Σ is the minimal one required to implement a shared register in a message-passing system [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF][START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF]. Σ provides each process with a quorum (set of process identities) such that the values of any two quorums (each taken at any time) intersect, and there is a finite time after which any quorum includes only correct processes [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF]. Fundamentally, Σ prevents partitioning. A failure detector of the class Σ × Ω outputs a pair of values, one for Σ and one for Ω.

The weakest failure detector classes for the (n -1)-set agreement have been established in 2008, and surprisingly they are not the same in the shared memory model and the message-passing model. More precisely, the weakest class for solving the (n -1)-set agreement problem in the asynchronous read/write shared memory model is Anti-Ω (denoted here Ω n-1 ) [START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF]. Such a failure detector provides each process with a set of (n -1) "leaders" that can change with time but these sets are such that, after some unknown but finite time, they all contain the same non-faulty process 2 .

Differently, the weakest class for solving (n -1)-set agreement in the asynchronous message-passing model, is the Loneliness failure detector class (denoted L) [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF]. Such a failure detector provides each process p with a boolean (that p can only read) such that the boolean of at least one process remains always false and, if all but one process crash, the boolean of that process becomes and remains true forever.

The general case for read/write shared memory The failure detector class Ω k has first been presented at the PODC'07 rump session [START_REF] Raynal | Rump Session at 26th ACM Symposium on Principles of Distributed Computing (PODC'07)[END_REF] where it has been conjectured to be the weakest failure detector class for solving the k-set agreement problem in read/write shared memory systems. This conjecture has been very recently (PODC 2009) proved by three independent groups [START_REF] Delporte-Gallet | The disagreement power of an adversary[END_REF][START_REF] Fernandez Anta | Weakest failure detectors with an edge-laying simulation[END_REF][START_REF] Gafni | The weakest failure detector for solving k-set agreeemnt[END_REF] (using apparently very different techniques). A failure detector of the class Ω k provides each process with a (possibly always changing) set of k processes such that after some unknown but finite time all the sets that are output have in common the same non-faulty process.

The optimality of Ω k to solve k-set agreement in shared memory systems seems to be related to the fact that this problem is equivalent to the k-simultaneous consensus problem [START_REF] Afek | Simultaneous consensus tasks: a tighter characterization of set consensus[END_REF], in which each process executes k independent consensus instances (to which it proposes the same input value), and is required to terminate in one of them. As shown in [START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF], this problem has been instrumental in determining the weakest failure detector for wait-free solving the (n -1)-set agreement problem in asynchronous shared memory systems.

Content of the paper

This paper proposes and investigates a new failure detector class for solving the k-set agreement problem in asynchronous message-passing systems. Its main contributions are the following.

• A new family of failure detector classes, denoted {Π k } 1≤k<n , is introduced. Its first interest lies in the fact that (1) Π 1 Σ × Ω (i.e., it allows expressing the weakest failure detector class for consensus with a one-dimensional output, namely a set of process identities), and (2) Π n-1 = L, from which it results that Π k is optimal for the extreme values of k when one wants to solve the k-set agreement problem in message-passing systems. Expressing the power of both Σ × Ω and L with a single formalism was not a priori evident.

• It is shown that the class Π k is actually equivalent to the class Σ k × Ω k where Σ k is an appropriate generalization of Σ. 3 We have Σ 1 ≡ Σ, and very interestingly Π n-1 Σ n-1 L which sheds a new light on the weakest failure detector class for the (n -1)-set agreement problem.

• It is proved that for any k, Σ k is a necessary requirement (as far as information on failures is concerned) to solve the k-set agreement problem in message-passing systems. It is worth noticing that the proof of this necessity requirement does rely neither on an heavy machinery, nor on a reduction to a previous impossibility result. It is purely constructive and particularly simple.

The paper additionally presents a message-passing (n -1)-set agreement algorithm directly based on Π n-1 (i.e., Σ n-1 ). As already indicated, this provides us with a new algorithmic insight on the way the (n -1)-set agreement can be optimally solved.

Last but not least, an output of this paper is the following intriguing question. As already indicated, the k-set agreement problem and the k-simultaneous consensus problem are equivalent in read/write shared memory systems [START_REF] Afek | Simultaneous consensus tasks: a tighter characterization of set consensus[END_REF], which means that k-set agreement can be solved by executing k independent consensus instances. From a "minimal information on failures" point of view, each such instance relies on the shared memory (i.e., on Σ) to ensure agreement, and on an instance of Ω to ensure termination. For the k-set agreement we only need that one instance does terminate. This is what is captured by Ω k (that eventually provides the processes with sets of k leaders that can arbitrarily change but contain forever the same correct process).

So, the question is: Which is the relation between the k-set agreement problem and the k-simultaneous consensus problem in message-passing systems? Understanding this link and its nature would give us a better understanding of the fundamental difference between shared memory communication and message-passing communication. The intertwining between sharing and agreeing seems to be subtle [START_REF] Delporte-Gallet | Sharing is harder than agreeing[END_REF].

Roadmap This paper is made up of 8 sections. Section 2 describes the computation model and Section 3 defines the failure detector class Π k . Then, Section 4 shows that the classes {Π k } and Σ k × Ω k are equivalent, and Section 5 shows that Π n-1 and L are equivalent. Section 6 presents a Π n-1 -based (n -1)-set agreement algorithm. Section 7 proves that Σ k is a necessary requirement for failure detector-based k-set agreement in message-passing systems. Finally, Section 8 concludes the paper.

System model and k-set agreement 2.1 System model

Process model

The system consists of a set of n > 2 asynchronous processes denoted P = {p 1 , . . . , p n }. Each process executes a sequence of atomic steps (internal action, sending of a message, or reception of a message). A process executes its code until it possibly crashes. After it has crashed a process executes no more step. A process that crashes during a run is faulty in that run, otherwise it is correct. Given a run, C denotes the set of processes that are correct in that run. Up to (n -1) processes can crash in a run. This is called the wait-free environment.

Communication model

The processes communicate by sending and receiving messages through channels. Every pair of processes is connected by a bidirectional channel. The channels are failure-free (there is no creation, alteration, duplication or loss of messages) and asynchronous (albeit the time taken by a message to travel from its sender to its destination process is finite, there is no bound on transfer delays). The notation "broadcast MSG TYPE(m)" is used to send a message m (the type of which is MSG TYPE) to all the processes. It is a (non-atomic) shortcut for "for each j ∈ {1, . . . , n}do send MSG TYPE(m) to p j end for". Notation The previous asynchronous message-passing model is denoted AS n [∅]. When enriched with any failure detector of a given class X, it will be denoted AS n [X].

The k-set agreement problem

As already indicated, the k-set agreement problem has been introduced by S. Chaudhuri [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF]. It generalizes the consensus problem (that corresponds to k = 1). It is defined as follows. Each process proposes a value and has to decide a value in such a way that the following properties are satisfied:

• Termination. Every correct process decides a value.

• Validity. A decided value is a proposed value.

• Agreement. At most k different values are decided.

Failure detector classes definition

If xx i is the local variable that contains the output of the failure detector at process p i , xx τ i denotes its value at at time τ .

The eventual leaders families (the Omega families)

Each process p i is endowed with a local variable leaders i that satisfies the following properties.

The eventual leaders family Ω k (1 ≤ k ≤ n -1) This family has been introduced by Neiger [START_REF] Neiger | Failure Detectors and the Wait-free Hierarchy[END_REF]. The local variables leaders i satisfy the following properties.

• Validity. ∀i : ∀τ : leaders τ i is a set of k process identities.

• Eventual leadership. ∃τ : ∃LD = { 1 , . . . , k } : (LD ∩ C = ∅) ∧ (∀τ ≥ τ : ∀i : leaders τ i = LD).
Let us notice that τ is finite but unknown. Before τ , there is an anarchy period during which the local sets leaders i can contain unrelated values. After τ , these sets are equal to the same set LD that contains at least one correct process.

Ω = Ω 1 is the weakest failure detector class to solve consensus [START_REF] Chandra | The Weakest Failure Detector for Solving Consensus[END_REF] in message-passing systems with a majority of correct processes, and in shared memory systems [START_REF] Guerraoui | Failure detectors as types boosters[END_REF][START_REF] Lo | Using failure detectors to solve consensus in asynchronous shared-memory systems[END_REF]. An Ω k -based algorithm that solves the k-set agreement in message-passing systems where t < n/2 is described in [START_REF] Mostéfaoui | On the Computability Power and the Robustness of Set Agreement-oriented Failure Detector Classes[END_REF]. This algorithm can easily be modified to replace the t < n/2 assumption by a failure detector of the class Σ 1 (as defined below [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF]).

The eventual leaders family

Ω k (1 ≤ k ≤ n -1)
The class Ω n-1 (called anti-Omega) has been introduced in [START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF] where it has been shown to be weakest failure detector class to solve (n -1)-set agreement in shared memory systems. It has been generalized in [START_REF] Raynal | Rump Session at 26th ACM Symposium on Principles of Distributed Computing (PODC'07)[END_REF] (as cited in [START_REF] Zielinski | Anti-Omega: the weakest failure detector for set agreement[END_REF]). The local variables leaders i satisfy the following properties.

• Validity. ∀i : ∀τ :

leaders τ i is a set of k process identities. • Weak Eventual leadership. ∃τ : ∃ ∈ C : ∀τ ≥ τ : ∀i : ∈ leaders τ i . Ω 1 is the same as Ω 1 . For k > 1, Ω k is weaker than Ω k : it
requires only that after some (finite but unknown) time the sets leaders i contain the same correct process. Very recently, it has been shown that Ω k is the weakest failure detector class to solve k-set agreement in shared memory systems [START_REF] Delporte-Gallet | The disagreement power of an adversary[END_REF][START_REF] Fernandez Anta | Weakest failure detectors with an edge-laying simulation[END_REF][START_REF] Gafni | The weakest failure detector for solving k-set agreeemnt[END_REF]. As noticed in the Introduction, this family of failure detectors is related to the k-set consensus problem [START_REF] Afek | Simultaneous consensus tasks: a tighter characterization of set consensus[END_REF].

The quorum family

Σ k (1 ≤ k ≤ n -1)
Each process p i is endowed with a local variable qr i that satisfies the following properties.

• Intersection. Let {id 1 , . . . , id k+1 } denote a subset of k + 1 process identities, and τ 1 , . . . , τ k+1 be any multiset of k + 1 arbitrary time instants. ∀{id 1 , . . . , id k+1 } : ∀{τ 1 , . . . , τ k+1 } : ∃i, j :

1 ≤ i = j ≤ k + 1 : (qr τi idi ∩ qr τj idj = ∅). • Liveness. ∃τ : ∀τ ≥ τ : ∀i ∈ C : qr τ i ⊆ C.
After a process p i has crashed (if it ever does), we have (by definition) qr i = {1, . . . , n} forever. Σ k is a generalization of the quorum failure detector class Σ introduced in [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF] (that does correspond to Σ 1 ), where it is shown to be the weakest failure detector class to implement an atomic register in a message-passing system whatever the number of process failures ("wait-free" environment). It is interesting to notice that the intersection property of Σ k is the same as the one used to define k-coteries [START_REF] Manabe | K-arbiter: a safe and general scheme for h-out of-k mutual exclusion[END_REF].

The agreement quorum family

Π k (1 ≤ k ≤ n -1)
Each process p i is endowed with a local variable qr i that satisfies the Intersection and Liveness properties of the quorum family Σ k plus the following property:

• Eventual leadership. ∃τ : ∃LD = { 1 , . . . , k } : ∀τ ≥ τ : ∀i : qr τ i ∩ LD = ∅.
After a process p i has crashed (if it ever does), we have (by definition) qr i = {1, . . . , n} forever. Moreover, let us observe that the Eventual leadership property of Π k is weaker than the Eventual leadership property of Ω k or Ω k : it is not required that, after τ , qr i must always contain the same correct process. It follows from the Intersection property that a quorum can never be empty. Moreover, it follows from the Liveness property that the set LD = { 1 , . . . , k } defined in the Eventual leadership property is such that LD ∩ C = ∅ (which means that this set contains at least one correct process). Let us also observe that the intersection requirement in the Eventual leadership property is similar to but weaker than the intersection property used in the definition of a k-arbiter [START_REF] Manabe | K-arbiter: a safe and general scheme for h-out of-k mutual exclusion[END_REF].

Collection des Publications Internes de l'Irisa c IRISA

Relations between failure detector classes Definition 1 The failure detector class A is stronger than the failure detector class B (denoted A B or B A) if it is possible to build a failure detector of the class B in AS

n [A].
It follows from their definitions that (1) for any k: Ω k Ω k , and (2) F D standing for any of Σ, Ω, Ω, and Π:

F D 1 • • • F D k F D k+1 • • • F D n-1 .

Definition 2

The class A is strictly stronger than the class B (denoted A B) if A B and ¬(B A).

Definition 3

The classes A and B are equivalent

(denoted A B) if A B and B A. 4 Π k vs Σ k × Ω k (1 ≤ k ≤ n -1) 4.1 From Σ k × Ω k to Π k
An algorithm that builds a failure detector of the class Π k from a failure detector of the class Σ k × Ω k is described in Figure 1.

Init: queue i ←< 1, . . . , n >.
Task T 1: repeat periodically broadcast ALIVE(i) end repeat. Task T 2: when ALIVE (j) is received: suppress j from queue i ; enqueue j at the head of queue i . when p i reads qr i : let be the first id of queue i that belongs to the output of

Ω k ; return (output of Σ k ∪ { }). Figure 1: From Σ k × Ω k to Π k (code for p i )
Theorem 1 The algorithm described in Figure 1 is a wait-free construction of a failure detector of the class

Π k in AS n [Σ k × Ω k ].
Proof The Intersection property of Π k follows directly from the corresponding property of Σ k and the fact that qr i includes the current output of Σ k . For Liveness property of Π k let us recall that after some finite time τ , Ω k outputs forever the same set { 1 , . . . , k } of k process identities and this set contains at least one correct process. Let us consider any time instant after τ , and a correct process p i . Due to the ALIVE (j) messages periodically sent by the correct processes, it follows that the ids of correct processes move at the head of queue i (see task T 2). It follows that the process p that is currently selected by the task T 2 is always a correct process locally output by Ω k . This, combined with the fact that there is a time after which Σ k always outputs correct processes, proves the Liveness property of Π k .

The Eventual leadership property of Π k follows directly from the fact that, after some finite time, Ω k always outputs the same set { 1 , . . . , k } of k process identities, and the fact that one of these identities appears in the definition of the current value of qr i .

2 T heorem 1 4.2 From Π k to Σ k and Ω k It is trivial to build Σ k in AS n [Π k ]: the output of Σ k is the output of Π k . The rest of this section focuses on the construction of Ω k in AS n [Π k ].

Description of the algorithm

Principle of the algorithm Each process p i manages a local variable quorum set i that contains a set of quorums. (Its initial value is the current value of qr i , the local output supplied by Π k ). The principle of the algorithm is to maintain invariant the following property where 1 , . . . , k are different process identities:

(∃{ 1 , . . . , k } : ∀qr ∈ quorum set i : qr ∩ { 1 , . . . , k } = ∅),
and "extract" Ω k from it.

As we are about to see, this property guarantees that, if the process p i was alone, it could consider { 1 , . . . , k } as its local output of Ω k . So, in addition of maintaining the previous property invariant, the processes additional use a reset mechanism and a gossip mechanism in order to ensure that all the local outputs ({ 1 , . . . , k }) eventually satisfy the leadership property of Ω k .

Description of the algorithm

The algorithm is described in Figure 2 in which each when statement is assumed to be executed atomically. Each process p i executes a sequence of phases, locally identified by ph nb i . The behavior of p i is as follows.

• Initially, p i broadcasts NEW(quorum set i , ph nb i ) to inform the other processes of its value qr i locally supplied by Π k . It does the same broadcast each time the value of quorum set i changes (line 15 whose execution is entailed by the invocation of pres inv&gossip() at lines 02 or 07). • When p i receives a NEW(qset, ph nb) message, its behavior depends on ph nb.

-If ph nb > ph nb i , p i jumps to the phase ph nb, adopts the quorum set qset it receives (line 03), and broadcasts its new state (line 04).

-If ph nb < ph nb i , p i discards the message.

-If ph nb = ph nb i , p i and the message are at same phase. In that case, p i adds qset to its quorum set quorum set i . Moreover, if this addition has changed its value, p i gossips it (line 07).

• The procedure pres inv&gossip() is invoked in a when statement when quorum set i has been modified (line 02 or line 07). It has a reset role and a gossip role.

-Reset. The first is to preserve the invariant property stated before. To that end, p i resets quorum set i if the property was about to be violated (lines [START_REF] Fernandez Anta | Weakest failure detectors with an edge-laying simulation[END_REF][START_REF] Gafni | The weakest failure detector for solving k-set agreeemnt[END_REF]. In that case, p i starts a new phase. -Gossip. Then, in all cases, p i broadcasts the new value of quorum set i .

• Finally, the algorithm defines as follows the value returned as the current local output of Ω k (lines 09-12). The process p i first considers all the increasing sequences of k process identities the intersection of which with each quorum currently in quorum set i are not empty (lines 09-10). Let us notice that each of these sequences satisfies the invariant property. Then, p i deterministically selects and returns one of them (e.g., the first in lexicographical order, lines 11-12).

Init:

ph nb i ← 0; quorum set i ← {qr i }; broadcast NEW(quorum set i , ph nb i ).
when the value of qr i changes: (09) let k seqs the set of length k increasing sequences of process ids [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF] 1 < • • • < k such that ∀qr ∈ quorum set i : qr ∩ { 1 , . . . , k } = ∅; (11) let 1 , . . . , k be the first sequence of k seqs (according to lexicographical order); [START_REF] Delporte-Gallet | The disagreement power of an adversary[END_REF]

(01) quorum set i ← quorum set i ∪ {qr i }; (02
return({ 1 , . . . , k }). % local output of Ω k % procedure pres inv&gossip(): (13) if ( ∃{ 1 , . . . , k } : ∀qr ∈ quorum set i : qr ∩ { 1 , . . . , k } = ∅) (14) then ph nb i ← ph nb i + 1; quorum set i ← {qr i } end if; (15) broadcast NEW(quorum set i , ph nb i ).

Proof of the algorithm

As Ω k is defined by an eventual property, let us consider the time instant definition with respect to a run of the algorithm described in Figure 2.

Definition 4

Let τ be the time instant max(τ α , τ β , τ γ , τ δ ) where 1. From τ α : all the faulty processes have crashed, 2. From τ β : for each alive process p i : qr i contains only correct processes, 3. From τ γ : ∃{ 1 , . . . , k } such that, for any alive process p i , we have { 1 , . . . , k } ∩ qr i = ∅, 4. From τ δ : all the messages NEW() sent before max(τ α , τ β , τ γ ) are received and processed.

Collection des Publications Internes de l'Irisa c IRISA Let us notice that τ is well-defined. This follows from the observation that τ α is well-defined for any run, τ β and τ γ are well-defined due to the liveness property and the eventual leadership property of Π k respectively, and τ δ is well-defined due to the reliability of the underlying communication network.

Lemma 1 Let X be the value of the the greatest local variable ph nb i at time τ . X is finite and no ph nb i variable becomes greater than X + 1.

Proof Let us first observe that, as τ is finite and only a finite number of messages can be exchanged in a finite duration, X is finite. The rest of the proof is by contradiction. Let us assume that a process sets its phase number to X + 2. Let p i be the first process that does it. As it is the first to proceed to the phase X + 2, p i has necessarily increased ph nb i to X + 2 at line 14 (p i cannot receive a message NEW(qset, X + 2) while it is in phase X + 1 and proceeds to the phase X + 2 at line 03). As no process was in the phase X + 1 at time τ (very definition of X), it follows that all the sets quorum set j sent during the phase X + 1 contain only quorums qr x whose value was the local output of Π k after τ (line 13). Consequently, all the messages NEW(qset, X + 1) received by p i are such that qset contains only quorums qr x whose value has been obtained after τ . It then follows from τ ≥ τ γ , that there is a set { 1 , . . . , k } such that ∀qr ∈ qset : qr ∩ { 1 , . . . , k } = ∅. We then conclude that, if the reception of NEW(qset, X + 1) entails the invocation of pres inv&gossip(), the test of line 13 is false. Hence, ph nb i is not increased, which proves the lemma.

2 Lemma 1

Lemma 2 There is a finite time after which no message are exchanged.

Proof The proof follows from the following three observations.

• As the number of processes n is bounded, there is a bounded number of distinct quorums.

• During a phase, no process p i sends twice the same set of quorums quorum set i (line 02 and 07).

• The number of phases executed by a process is finite.

2 Lemma 2

Lemma 3

The set k seqs defined at line 09 is never empty, and each of its elements is a non-empty set.

Proof The proof is by induction. Initially, quorum set i = {qr i }, and consequently k seqs is not empty. Moreover, it follows from the the Intersection property of Π k qr i is not empty. Let us assume that, before modifying quorum set i is modified, k seqs is not empty and each of its element is a non-empty set. We show the modification of quorum set i keeps these properties. The variable quorum set i can be modified at line 02, line 03, line 07, or line 14.

• quorum set i is modified at line 03. In that case, quorum set i takes the value of qset that, due to the induction assumption, satisfies the property. • quorum set i is modified at line 14. This case is a reset of quorum set i : it is exactly the same as the initialization case. Hence, quorum set i then contains only the non-empty set. • quorum set i is modified at line 02 or 07. In both cases, the procedure pres inv&gossip() is invoked. The case where line 14 is executed has been dealt with in the previous item. If the line 14 is not executed, the predicate ∃{ 1 , . . . , k } : ∀qr ∈ quorum set i : qr ∩ { 1 , . . . , k } = ∅ is satisfied. But this predicate is exactly the predicate that states that k seqs is not empty and none of its elements is the empty set (line 12).

2 Lemma 3 Lemma 4 ∃LD = { 1 , . . . , k } : LD ∩ C = ∅ : ∃τ ≥ τ : ∀τ ≥ τ : ∀i ∈ C: leaders τ i = LD.
Proof Let M be the greatest phase number ever attained by a correct process. Due to Lemma 1 this phase number does exist. Moreover, due to the lines 15 and 03, all the correct processes enter the phase M .

During the phase M , each correct process p i exchanges its quorum set quorum set i each time this set is modified (lines 02 and 07). It follows from the network reliability and the fact that, during a phase, quorum set i can take a bounded number of distinct values, that there is a finite time after which all the correct processes have the same set of quorums in their local variables quorum set i (line 03). Let QS be this set of quorums.

Let τ be a time after which all the processes p i are such that quorum set i = QS. The first part of the lemma follows from the fact that, after τ , the processes compute deterministically the same set LD of k leaders from the (never changing) same input QS (lines 09-12).

The fact that LD contains a correct process follows from the the liveness property of Π k (there is a finite time after which each qr i contains only correct processes), from which we conclude that the quorum set QS contains only quorums made up of correct processes. Due to its very definition, it follows that LD contains at least one correct process.

2 Lemma 4

Init: qr i ← {i, j} where j = i.

Task T 1: repeat periodically broadcast ALIVE(i) end repeat.

Task T 2: when alone i becomes true: qr i ← {i}. when ALIVE(j) is received: if (i = j) ∧ (|qr i | = 1) then qr i ← {i, j} end if.

Figure 4: From L to Π n-1 (code for p i )

Proof The proof considers each property of Π n-1 separately. Proof of the Intersection property. As k = n -1, we have to prove that ∀{τ 1 , . . . , τ n } : ∃i, j : 1 ≤ i = j ≤ n : (qr τi i ∩ qr τj j = ∅). Due to the Stability property of L, there is at least one process (say p i ) such that alone i never becomes true. So, until p i crashes (if it ever crashes), we have |qr i | = 2. Consequently, there is always a process p j such that qr i = {i, j}, from which it follows that there is always a process p j (not necessarily always the same) such that at any time qr i ∩ qr j = ∅, which proves the property until p i crashes. After p i has crashed (if it does), the Intersection property is trivially satisfied.

Proof of the Liveness property. Let p i be a correct process. We consider two cases.

• The boolean alone i takes (at least once) the value true. In that case, we will have qr i = {i}. Then, qr i remains forever equal to {i}, and the Liveness property is satisfied. • The boolean alone i never takes the value true, and consequently we will never have qr i = {i}. In that case, there are other correct processes (at least one). As, after some finite time, there are only correct processes, p i will receive infinitely often messages ALIVE(j) from each of these correct processes p j (and it will receive messages only from them). It follows that, after some time, qr i contains only ids of correct processes.

Proof of the Eventual leadership property. We have to prove that ∃τ : ∃LD = { 1 , . . . , n-1 } : ∀τ ≥ τ : ∀i : qr τ i ∩ LD = ∅. Let us recall that any boolean (but one) can flip infinitely often between false and true. Let τ be the time after which no more boolean moves from false to true for the first time. Let Z = {i|∃τ : alone τ i = true}. It follows from the definition of L that 0 ≤ |Z| ≤ n -1. We consider two cases.

• |Z| = n -1. Let Z = { 1 , . . . , n-1 } and take LD = Z. We show that, in that case, after τ , we always have ∀i : LD ∩ qr i = ∅. This is trivial for any process p x , 1 ≤ x ≤ n -1, as we always have x ∈ qr x . Let us now consider the process p n such that alone n remains always equal to false (due to definition of L, p n does exist). Due to the algorithm of Figure 4, the process p n is such that we always have |qr n | = 2. Consequently, the predicate qr n ∩ LD = ∅ is always satisfied, which completes the proof of the case.

• |Z| < n -1. Let |Z| = z.
Let us recall that each process p i in Z is such that after some finite time we always have qr i = {i}.

In that case, let us add (n -1) -z processes to Z in order to obtain a set LD of (n -1) processes. Due to the definition of Z and the algorithm of Figure 4, it follows that the process (say p n ) that is not in LD is such that |qr n | = 2. Consequently (as in the previous item) the predicate qr n ∩ LD = ∅ is always satisfied. Hence, the set LD satisfies the Eventual leadership property, which completes the proof of the theorem.

2 T heorem 5 5.4 Σ n-1 , L and Ω n-1 Theorem 6 Σ n-1 L Π n-1 Σ n-1 × Ω n-1 .
Proof The proof follows from Theorem 4 (that builds L from Σ n-1 ), Theorem 5 (that builds Π n-1 from L), and Theorem 3 (that builds Σ n-1 × Ω n-1 from Π n-1 ), and the fact that Σ n-1 is trivially obtained from Σ n-1 × Ω n-1 .

T heorem 6

This theorem generalizes a result of [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF] where it is shown that Σ 1 Σ 1 × Ω 1 in systems made up n = 2 processes. The following corollaries are an immediate consequence of the previous theorem and the definition of Σ k . The second one generalizes a result of [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF] that (expressed with our notations) states

Σ 1 L Ω n-1 . Corollary 2 Σ n-1 is stronger than Ω n-1 . Corollary 3 Σ 1 Σ 2 . . . Σ n-2 Σ n-1 L.

A Σ n-1 -based (n -1)-set agreement algorithm

An L-based (n-1)-set agreement algorithm is presented in [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF]. Hence, the stacking of this algorithm on top of the algorithm described in Figure 4 (that builds Π n-1 , i.e., Σ n-1 , in AS n [L]), supplies a Σ n-1 -based (n -1)-set agreement algorithm. This Section describes a (n -1)-set agreement algorithm that is directly built on top of Σ n-1 and consequently saves the construction of L when one is provided with a failure detector of the class Π n-1 .

The algorithm

The code of the algorithm for a process p i is described in Figure 5. The local variable est i contains p i 's current estimate of the decision value, while qsize i contains a quorum size, namely, the size of smallest quorum that allowed computing the current value of est i .

The processes proceed in n asynchronous rounds. At the end of the last round, p i returns (decides) the current value of est i (line 09). During a round r, a process p i first broadcasts it current state (the pair (qsize i , est i )) and waits for the current states of the processes in its current quorum qr i (lines 03-04). Then, considering these states (qsize, est) plus its local state, p i selects the smallest one according to their lexicographical ordering 4 (line 06). Finally, p i updates qsize i and est i (line 07). The local estimate est i is updated to the estimate value est x of the processes p x of q = qr i ∪ {i} such that qsize x is the smallest; qsize i is set to min(qsize x , |q|) to take into account the size of the quorum that allowed computing est i (line 07).

Function set agreement n-1 (v i ): (01) est i ← v i ; qsize i ← n; (02) for r i from 1 to n do (03) broadcast PROPOSE(r i , qsize i , est i );
(04) wait until PROPOSE(r i , -, -) received from all the processes in qr i ; (05) let q be {i}∪ the quorum qr i that allowed the wait statement to terminate; (06) let (qsize, est) be the smallest pair (lex. order) rec. from the processes ∈ q; (07) qsize i ← min(qsize, |q|); est i ← est (08) end for; (09) return(est i ). i denote the value of est i at the end of the round r (that is the value of est i at the beginning of the round (r + 1) if p i starts that round). Let EST [r] = i {est r i }.

Lemma 5 Let r be a round, 1 ≤ r ≤ n. At the end of r, (i) |EST [r]| ≤ (n -1), or (ii) the process p i that has the greatest pair (qsize i , est i ) at the beginning of the round r, is such that qsize i = 1 at the end of the round r.

Proof Let us consider a round r, and assume that Item (i) is not satisfied, i.e., we have |EST [r]| = n. The proof shows that Item (ii) is then satisfied. Let p i be a process with the highest (qsize, est) pair (according to lexicographical order). As |EST [r]| = n, all the estimate values are different at the end of r, from which follows that the process p i is unique. Let us first observe that no other process p j can adopt the value est i of p i . This is because when p j executes line 05 we have j ∈ q and the pair (qsize i , est i ) is the highest according to lexicographical order, from which we conclude that p j cannot select it at line 06.

Let us now consider p i . If it receives at line 04 messages from other processes (i.e., qr i = {i}), it adopts one of these pairs to define its new value of qsize i and est i . We then have |EST [r]| < n which contradicts the assumption stating that Item (i) is not satisfied. Consequently, this case cannot occur. If, at line 04, p i receives a message only from itself, we then have qr i = {i}, i.e., |q| = 1 at line 05. In that case, qsize i is set to 1 at line 07 which concludes the proof of the lemma.

2 Lemma 5

Lemma 6 If, during a round r, 2 ≤ r ≤ n, a process p i sets qsize i to 1 due to another process (i.e., while |q| = 1 at line 07), then two processes have the same estimate value at the end of that round.

Proof Let ONE [ρ] be the set of processes p x such that qsize x = 1 at the end of the round ρ, and EST ONE [ρ] be the set of their estimates at the end of ρ. The definition ONE [ρ] is extended as follows for the processes that crash. If a process p x crashes after it has been added to ONE [ρ], it is also added to ONE [ρ ] for all ρ such that ρ ≤ ρ ≤ n. We consequently have

ONE [ρ] ⊆ ONE [ρ + 1].
Let r > 1 be a round. Let us consider the processes p y that are in ONE [r -1] and execute the round r. As all these processes p x are such that qsize x = 1, some of them can adopt the estimate value of other processes but those processes belong to ONE [r -1]. The important point is that the set of their estimate values remains the same or decreases during the round r.

Let us now consider the process p i defined in the lemma assumption. It is such that i / ∈ ONE [r -1] and i ∈ ONE [r] (it is during r that p i set qsize i to 1 while |q| = 1). Consequently, p i has adopted an estimate est associated with an integer qsize = 1. It follows that est 2 Lemma 6

Theorem 7 The Σ n-1 -based algorithm described in Figure 5 solves the (n -1)-set agreement in a wait-free environment.

Proof The validity property of the k-set agreement problem follows from the initialization of the local variables est i and the fact that, when it is updated to a new value, such a variable can only take the value of one of the estimates values (lines 03, 06 and 07).

The termination property consists in showing that no correct process can block forever at line 04. The proof is by contradiction. Let r be the first round during which a correct process blocks forever at line 04. As no correct process blocks forever during a round r < r, it follows that every correct process broadcasts a message PROPOSE(r i , -, -) when it starts the round r. Moreover, due to the liveness property of Σ n-1 , there is a finite time after which qr i contains only correct processes. If follows from these observations that there is a finite time after which p i has received a round r message from all the processes in qr i , and consequently no correct process can block forever at round r which contradicts the definition of the round r. Hence, all the correct processes decide.

The proof of the agreement property (at most (n -1) distinct values are decided) is by contradiction. Let us assume that n distinct values are decided. Hence, each process executes the n rounds and decides at the end of the round n, which means that |EST [n]| = n. The proof is a consequence of the following items.

It follows from EST

[r + 1] ⊆ EST [r] and |EST [n]| = n, that ∀ r : 1 ≤ r < n : [EST [r]| = n. 2.
Initially, all the variables qsize i are equal to n. 3. Due to the lines 06-07, once a process p x has updated qsize x to 1, qsize x keeps that value forever. 4. Let us consider the case where there is at least one process p j such that qsize j > 1 at the beginning of a round r. As |[EST [r]| = n (Item 1), Item (i) of Lemma 5 does not apply. So, it follows from Item (ii) of this lemma that, the process p j , the (qsize j > 1, est j ) of which is the greatest at the beginning of r, is such that qsize j = 1 at the end of that round. 5. It follows from the previous items 2,3 and 4 that all the processes p i are such that qsize i = 1 at the end of the round r = n.

Let us notice that, as there are n distinct values at the end of the round n (|[EST [r]| = n), it follows from Lemma 6 that the update of qsize i to 1 by p i is due to the fact that q = qr i ∪ {i} with |q| = 1 when p i has executed the lines 04-07 during some round r (otherwise, due to Lemma 6, we would have |[EST [r]| < n). Consequently, for each process p i , there is a time τ i such that qr τi i = {i}, which contradicts the intersection property of Σ 1 (in any set of n quorums, two of them have to intersect), and concludes the proof of the k-set agreement property.

2 T heorem 7

7 Necessity of Σ k to solve k-set agreement

This section shows that Σ k is necessary to solve the k-set agreement problem as soon as we are looking for a failure detector-based solution. To that end, given any algorithm A that solves the k-set agreement problem with the help of a failure detector D, we provide an algorithm that emulates the output of Σ k . This means that it is possible to build a failure detector of the class Σ k from any failure detector D that can solve the k-set agreement problem (according to the usual terminology, Σ k can be extracted from the D-based algorithm A). The output of Σ k at p i is kept in qr i . Interestingly enough, and in addition of being more general, the proposed construction (Figure 6) provides us with a proof of the necessity of Σ 1 to solve the consensus problem that is simpler that the one described in [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF].

Underlying principle

As in [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF], the proposed extraction algorithm does not rely on the asynchronous impossibility of a problem. Its design principle is the following. Each process p i participates in several runs of A. Let R {i} denote a run of A in which only the process p i participates, R {i,j} (i = j) a run of A in which only the processes p i and p j participate, etc., and R {1,2,...,n} a run of A in which all the processes participate. This means that in a run denoted R Q only the processes of Q take steps, and each process of Q either decides, blocks forever or crashes 5 . So, the extraction algorithm uses 2 n -1 runs of A. Let us observe that, due to asynchrony and the fact that any number of processes can crash ("wait-free" environment), any prefix of any of these runs can occur in a given execution.

The algorithm

The algorithm executed by each process p i is described in Figure 6. Each process manages two local variables: a set of sets denoted S i and a queue denoted queue i . The aim of S i is to contain all the sets Q such that p i decides in the run R Q (Task T 1), while queue i is managed as the queue with the same name in Figure 1 (task T 2 and first when statement of T 3). The important point point is here that the correct processes eventually appear before the faulty processes in queue i .

The idea is to select a set of S i as the current output of Σ k . As we will see in the proof, any (k + 1) sets of S i are such that two of them do intersect which will supply the intersection property. The main issue is to ensure the liveness property of Σ k (namely, eventually the set qr i associated with p i contains only correct processes), while preserving the intersection property. This is done as follows with the help of queue i . The current output of Σ k is the set (quorum) of S i that appears as being the "first" in queue i . The formal definition of "first set of S i wrt queue i " is stated in the task T 3. To make it easy to understand let us consider the following example. Let S i = {{3, 4, 9}, {2, 3, 8}, {4, 7}}, and queue i =< 4, 8, 3, 2, 7, 5, 9, • • • >. The set F = {2, 3, 8} is the first set of S i with respect to queue i because each of the other sets {3, 4, 9} and {4, 7} includes an element (9 and 7, respectively) that appears in queue i after the elements of F . (In case several sets are "first", any of them can be selected). Remark Initially S i contains the set {1, . . . , n}. As only sets of processes can be added to S i (task T 1), S i is never empty. Moreover, it is not necessary to launch a run in which all the processes participate. This is because, as the D-based k-set agreement algorithm A is correct, it follows that all the correct processes decide in that run R {1,...,n} . This case is directly taken into account in the initialization of S i (thereby saving the run R {1,...,n} ).

Theorem 8 Given any algorithm

A that solves the k-set agreement problem with the help of a failure detector D, The algorithm described in Figure 6 is a wait-free construction of a failure detector of the class Σ k .

Proof The Intersection property of Σ k is proved by contradiction. Let us first notice that a set qr i returned to a process p i is a set Q of S i . Let us assume that there are k + 1 subsets of processes Q 1 , . . . , Q k+1 that (1) ∀x : 1 ≤ x ≤ k + 1 : Q x ∈ 1≤i≤n S i , and (2) ∀x, y : 1 ≤ x = y ≤ k + 1 : Q x ∩ Q y = ∅. (pairwise independence). The item (1) means that Q x can be returned as the value of qr i by a process p i . Let Q = Q 1 ∪ . . . ∪ Q k+1 . Let R be the run of A in which (1) only the processes of Q participate, and (2) for each x, 1 ≤ x ≤ k + 1, the processes of Q x behave exactly as in R Qx (as defined in the Init part of Figure 6). Due to the second item, in R, the processes in Q x , 1 ≤ j ≤ k + 1, that decide do decide as in R Qx . It follows that, even if the processes in each Q x would decide the same value, up to k + 1 different values could be decided. This contradicts the fact that A solves the k-set agreement in the run R, from which we conclude that ∃x, y : 1 ≤ x = y ≤ k + 1 : Q x ∩ Q y = ∅ which proves the Intersection property of Σ k .

As far as the Liveness property, let us consider the run of A in which the set of participating processes is exactly C (the set of correct processes). Due to the termination property of A, every correct process does terminate in that instance. Consequently, in the extraction algorithm, the variable S i of each correct process p i eventually contains the set C. Moreover, after some finite time, each correct process p i receives ALIVE(j) messages only from correct processes. This means that, for each correct process p i , all the correct processes eventually precede the faulty processes in queue i . Due to the definition of "first set of S i wrt queue i " stated in the task T 3, and the fact that C ∈ S i , it follows that the quorum Q selected by the task T 3 is such that Q ⊆ C, which proves the liveness property of Σ k . a necessary requirement for any k. Although it seems a posteriori simple, finding a single parameterized formulation for Σ 1 × Ω 1 and L was not a priori evident. The remaining question is now: is Π k the end of the road or has it to be made stronger in order to be the weakest class when 1 < k < n?

Figure 2 :

 2 Figure 2: From Π k to Ω k (code for p i )

Figure 5 : 6 . 2 Notation 1

 5621 Figure 5: Σ n-1 -based (n -1)-set algorithm (code for p i )

  r i ∈ EST ONE [r -1]. It follows from the previous observations that |ONE [r -1]| < |ONE [r]| and EST ONE [r -1] = EST ONE [r], from which we conclude that two processes of ONE [r] have the same estimate value.

Figure 6 :

 6 Figure 6: Extracting Σ k from a k-set agreement failure detector-based algorithm A

2 T heorem 8 8

 28 Concluding remarkThis paper has addressed the question of the weakest failure detector class to solve the k-set agreement problem in asynchronous message-passing systems prone to any number of process crashes. It has proposed Π k as a candidate for the corresponding failure detector class, and has shown that (1) Π 1 and Π n-1 are indeed the weakest classes for k = 1 and k = n -1, respectively, and (2) Σ k is Collection des Publications Internes de l'Irisa c IRISA

end case. when p i reads leaders

) if (quorum set i has changed) then pres inv&gossip() end if. when NEW(qset, ph nb) is received: (03) case ph nb > ph nb i then ph nb i ← ph nb; quorum set i ← qset; (04) broadcast NEW(quorum set i , ph nb i ) (05) ph nb < ph nb i then discard the message (06) ph nb = ph nb i then quorum set i ← quorum set i ∪ qset; (07) if (quorum set i has changed) then pres inv&gossip() end if (08) i :

  Init: S i ← {{1 . . . , n}}; queue i ←< 1, . . . , n >;for each Q ∈ 2 Π \ {∅, {1, . . . , n}} such that (i ∈ Q) do let A Q denote the D-based instance of A inwhich participate only the processes of Q; p i proposes i to A Q end for. Task T 1: when p i decides in the instance of A in which participate only the processes of Q: S i ← S i ∪ {Q}. suppress j from queue i ; enqueue j at the head of queue i . when p i reads qr i : let m = min Q∈S i (max x∈Q (rank[x])) where rank[x] denotes the rank of x in queue i ; return (a set Q such that max x∈Q (rank[x]) = m).

Task T 2: repeat periodically broadcast ALIVE(i) end repeat. Task T 3: when ALIVE (j) is received:

Interestingly, a failure detector class weaker than Σ × Ω k is proposed in[START_REF] Zhang | Weakening failure detectors for k-set agreement via the partition approach[END_REF] to solve k-set agreement in message-passing systems. It is easy to show that Σ × Ω n-1 is stronger than L.Collection des Publications Internes de l'Irisa c IRISA

Collection des Publications Internes de l'Irisa c IRISA

Recall that this order is defined as follows:(q1, est1) < (q2, est2) def = (q1 < q2) ∨ (q1 = q2 ∧ est1 < est2) .Collection des Publications Internes de l'Irisa c IRISA

As the processes that are not in Q do not participate, the messages sent by the processes of Q to these processes are never received. Alternatively, as in[START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF], we could say that the processes of Q "omit" sending messages to the processes that are not in Q.Collection des Publications Internes de l'Irisa c IRISA

Theorem 2

The algorithm described in Figure 2 is a wait-free quiescent construction of a failure detector of the class

Proof The fact that the algorithm constructs a failure detector of the class Ω k follows from Lemma 3 (validity), and Lemma 4 (eventual leadership). The fact that the algorithm is quiescent follows from Lemma 2. Finally, it is trivially wait-free as there is no wait statement.

2 T heorem 2

Finally, (as already noticed), taking taking the output of Π k as the output of

The failure detector class L

The failure detector class L (for loneliness) has been introduced in [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF] where it is shown to be the weakest failure detector class that solves the (n -1)-set agreement problem in message-passing systems. ( [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF] also shows that L is strictly stronger than Ω n-1 and strictly weaker than Σ.) It is defined as follows. Each process p i is provided with a boolean variable alone i that it can only read. These variables are such that:

• Stability. There is at least one process whose boolean remains always false.

• Loneliness. If only one process is correct, eventually its boolean outputs true forever.

By definition, after a process p i has crashed (if it ever crashes) its boolean alone i is set to false and keeps that value forever. Let us notice that nothing prevents the value of a boolean alone i to change infinitely often (as long as the corresponding process p i is neither the one whose boolean remains always false, nor the only correct process in the the case where all the other process crash).

From Π n-1 to L

The algorithm that constructs a failure detector of the class L from any failure detector of the class Π n-1 is described in Figure 3. It is pretty simple: the boolean of a process p i becomes true (and remains true forever) only if the quorum of that process contains only its own identity. (A similar construction is described in [START_REF] Delporte-Gallet | The Weakest Failure Detector for Message Passing Set-Agreement[END_REF] to show that Σ is stronger than L.)

Init: alone i ← false. when qr i = {i}: alone i ← true. Proof The Loneliness property of L follows from a simple observation. If a single process p i is correct, it follows from the Liveness property of Π n-1 that eventually qr i = {i}. When this occurs alone i is set to true and remains true forever.

The proof of the Stability property of L is by contradiction. Let us assume that all the boolean variables alone i are set to true. Due to the initialization, this means that, for each p i , we had at some time qr i = {i}. But this violates the Intersection property of Σ n-1 . Consequently, there is at least one process whose boolean variable remains always false.

2 T heorem 4

The following corollary is an immediate consequence of the fact that Π n-1 = Σ n-1 × Ωn -1.

Corollary 1

The algorithm described in Figure 3 builds a failure detector of the class L in AS n [Π n-1 ].

From L to Π n-1

The algorithm that constructs a failure detector of the class Π n-1 from any failure detector of the class L is described in Figure 4. It is very simple. Each process p i periodically sends ALIVE(i) messages, processes the messages it receives, and set qr i to {i} when alone i becomes true (then, qr i is no longer modified).

Theorem 5 The algorithm described in Figure 4 is a wait-free construction of a failure detector of the class Π n-1 in AS n [L].

Collection des Publications Internes de l'Irisa c IRISA