Antoine N André

Patrick Sandoz

Maxime Jacquot

Guillaume J Laurent

Pose Measurement at Small Scale by Spectral Analysis of Periodic Patterns

Keywords: Fiducial markers, Fourier analysis, pose measurement

The retrieval of an observed object's pose is an essential computer vision problem.The challenge arises in many different fields, among them robotics control, contactless metrology, or augmented reality. When the observed object shrinks from the macroscopic scale to the microscopic, pose estimation is further complicated by the weaker perspective of imaging macroscale lenses down to the quasi-orthographic projection inherent to microscope objectives. This paper tackles this issue of microscale pose estimation in two complementary steps that rely on the use of planar periodic targets. We first consider the orthographic projection case as a means of presenting the theory of the method and showing how the pose of periodic patterns can be directly retrieved from the Fourier frequency spectrum of a given image. We then address the perspective case with long focal lengths, in which the full six-degrees of freedom (6-DOF) pose can be retrieved without ambiguities by following the same theoretical background. In addition to theoretically justifying pose retrieval via Fourier analysis of acquired images, this paper demonstrates the method's actual performance. Both simulations and experimentation are conducted to validate the method and confirm an experimental resolution lower than 1/1000 th of a pixel for translations. For orientation measurement, resolutions below 1 µrad. for in-plane orientation, and below 100 µrad. for off-axis orientations can be achieved.

I. INTRODUCTION

Pose measurement is a classic computer vision problem whose applications can be found in various fields, including robotics control, contactless metrology or augmented reality. Some methods rely on the use of multiple cameras to reconstruct the object and its pose via well-known feature matching techniques such as SIFT or SURF [START_REF] Bay | Surf: Speeded up robust features[END_REF][START_REF] Moreels | Evaluation of features detectors and descriptors based on 3d objects[END_REF]. Other proposed methods rely on just one camera, using properties of the scene to retrieve the observed object's coordinates in the camera frame referential. This problem of single camera pose estimation has already been widely researched, and many different techniques have been investigated by exploiting various hypotheses or constraints, including the rigidity of observed objects, the coplanarity of studied points, and the use of different kinds of camera projection models. [START_REF] Tamadazte | Cad model-based tracking and 3d visual-based control for mems microassembly[END_REF] and [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF], for example, both tackled the problem in their attempt to retrieve complex objects' poses for visual tracking. [START_REF] Loing | Virtual training for a real application: Accurate object-robot relative localization without calibration[END_REF] also explored the problem in the realm of robotics, proposing a method of retrieving the relative pose between a robot and an object with the aid of neural networks.

One widely spread approach to single-camera pose estimation is to search for features that are physically constrained in the same plane. For example, with checkerboard patterns, this method can be used for both calibration and pose estimation, as described by [START_REF] Liu | Caliber: Camera localization and calibration using rigidity constraints[END_REF]; [START_REF] Bouguet | Camera calibration toolbox for matlab[END_REF]. These features can also be organized more compactly so as to create fiducial markers that are present in the field of pose estimation for a several decades, as described by [START_REF] Kato | Marker tracking and hmd calibration for a video-based augmented reality conferencing system[END_REF], who envisioned applications in the realm of augmented reality. In the decades since [START_REF] Bruckstein | Optimum fiducials under weak perspective projection[END_REF] proposed novel designs for fiducial markers that would lie on a single plane for pose estimation and explored innovative markers [START_REF] Bruckstein | New devices for 3d pose estimation: Mantis eyes, agam paintings, sundials, and other space fiducials[END_REF]. Many more designs have been explored, notably by [START_REF] Fiala | Artag, a fiducial marker system using digital techniques[END_REF], [START_REF] Sattar | Fourier tags: Smoothly degradable fiducial markers for use in human-robot interaction[END_REF], and [START_REF] Naimark | Circular data matrix fiducial system and robust image processing for a wearable vision-inertial self-tracker[END_REF]. Among these, ARTags and ArUco markers [START_REF] Garrido-Jurado | Automatic generation and detection of highly reliable fiducial markers under occlusion[END_REF] are perhaps the most popular, having quickly become the bases of numerous applications. Indeed, such applications are not only numerous, but also quite varied, ranging from macroscopic scale applications with excavators pose estimation as shown by [START_REF] Azar | Feasibility of in-plane articulation monitoring of excavator arm using planar marker tracking[END_REF] to microscopic scale with MEMS pose retrieval as described by [START_REF] Kim | Design of mems vision tracking system based on a micro fiducial marker[END_REF]. As the design of fiducial markers evolved, so too did methods for their pose estimation, and recent works by [START_REF] Didier | Hybrid camera pose estimation combining square fiducials localization technique and orthogonal iteration algorithm[END_REF], [START_REF] Collins | Infinitesimal plane-based pose estimation[END_REF] or [START_REF] Zhong | A robust monocular 3d object tracking method combining statistical and photometric constraints[END_REF] detail higher resolution and more robust measures.

However, as size of the observed object decreases, the focal length of the lens must increase accordingly. This has led a new challenge in pose measurement to emerge as the perspective projection on the camera becomes weaker. As recently observed by [START_REF] Yao | A review of computer microvision-based precision motion measurement: Principles, characteristics, and applications[END_REF] in a survey of different pose measurement techniques in the microscopy field, this change in the scale at which measurement occurs raises newly complicates process of retrieving the pose of an observed object.

A. Contributions

This article proposes a novel method: retrieving a pose from an observed periodic pattern within the Fourier domain by extending the high-resolution in-plane measure provided by periodic patterns to a six-degrees of freedom (6-DOF) pose measure. Assuming that one is working with an orthographic projection, a 5-DOF pose and accompanying scale factor can be measured; considering a perspective projection with a long focal length, an unambiguous 6-DOF pose can be obtained by extending the scale factor measure to the depth measure. This article proposes a formal method of extracting from the Fourier domain all the information needed to retrieve a 6-DOF pose of bi-dimensional periodic patterns.

Alongside with the methodology of pose measurement, this article presents the performances of the measure by simulations with generated images and confronting these results with experimental validations. Finally, this article compares the presented method in simulation with the 6-DOF pose estimation of circular grids for a set of four different projection configurations and its experimental performances with other fiducial markers (AruCo tags, checkerboard).

B. Paper structure

The article is organized into five main sections which together present the method of pose measurement and detail its performance. Section II outlines the phase-based background for in-plane pose measurement; section III tackles the theoretical problem of pose determination with the help of a periodic pattern observed under orthographic projection by presenting the method of retrieving the 5-DOF and scale factor in the Fourier domain. Section IV expands this measure to a sixth degree of freedom by considering a perspective projection with a long focal length that allows the retrieval of the depth measure. Then, in section V the validity of the method and its range of measure are demonstrated with simulated periodic patterns poses. Section VI presents the experimental validation of the results both with a microscope objective and with a macro objective to confirm that the measure is valid across different projections. Finally, section VII ends the papers by defining directions of future work.

II. RELATED AND PREVIOUS WORKS

A. Pose measurement in microscopy

Even when the pose can only be measured along 3-DOF, pose estimation problem at small scale remains relevant for as diverse domains as biology or micro-robotics. For this reason, different methods of in-plane pose sensing have been studied in recent years. These methods can be grouped in three main categories. The first class uses features present in the image to recover the x, y, α pose of the observed object; this category of method is presented in previous research by [START_REF] Chu | Dual-arm micromanipulation and handling of objects through visual images[END_REF], [START_REF] Liu | Locating end-effector tips in automated micromanipulation[END_REF][START_REF] Shang | Vision-based nano robotic system for high-throughput non-embedded cell cutting[END_REF]. The approach has its limits: if only the position of groups of pixels is studied, the best achievable resolution is only one tenth of a pixel. Correlation methods, in contrast, have demonstrated superior resolutions. By studying the faint pixel changes between one image and another to retrieve the in-plane pose, a resolution as fine as one hundredth of a pixel can be attained, as shown by [START_REF] Marturi | Image-guided nanopositioning scheme for sem[END_REF], [START_REF] Bomarito | Increasing accuracy and precision of digital image correlation through pattern optimization[END_REF][START_REF] Li | Realtime in-plane displacements tracking of the precision positioning stage based on computer micro-vision[END_REF]. To achieve even better resolutions, periodic patterns can be printed on the surface of observed objects. The redundancy of this grating in combination with the phase evolution of the pattern, leads to resolutions as high as a thousandth of a pixel. This method has already proven its capabilities in term of resolution performance and large range of measure [START_REF] Kim | Note: An absolute xy-θ position sensor using a two-dimensional phase-encoded binary scale[END_REF][START_REF] Guelpa | Subpixelic measurement of large 1d displacements: Principle, processing algorithms, performances and software[END_REF]. The method of pose measurement presented in this article leans on the previously studied in-plane pose measurement technique [START_REF] Andre | Sensing one nanometer over ten centimeters: A micro-encoded target for visual in-plane position measurement[END_REF] and extends it to a full 6-DOF pose measure that retains high resolution.

B. In-plane pose measurement in Fourier domain

Analysis of the phase tied to a periodic pattern is a known, convenient way of measuring the in-plane position and subsequent displacements of a target observed by a vision system. This method has been largely used with one dimensional periodic gratings in different researches and with different approaches such as classic phase studying, Moiré fringe studying or Vernier phase studying, as described by [START_REF] Yamahata | Subnanometer translation of microelectromechanical systems measured by discrete fourier analysis of ccd images[END_REF]), Ri et al. (2014), [START_REF] Sugiura | On-chip method to measure mechanical characteristics of a single cell by using moiré fringe[END_REF], and [START_REF] Guelpa | Subpixelic measurement of large 1d displacements: Principle, processing algorithms, performances and software[END_REF]. The main advantage of these methods is the high-resolution sub-pixel measure that can be achieved via the phase analysis of the periodic grating along one axis. This periodic pattern designs can be extended into two dimensions, thereby generating a high-resolution in-plane measure along the three coordinates (x, y, α). The 2D Fourier transform of such pattern is presented in Fig. 1. Its periodic arrangement results in four main peaks in the Fourier domain. The link between the frequency domain and the spatial one can be described as follow: where φ 1 and φ 2 are the phase values of peaks F 1 and F 2 , λ is the physical period of the pattern. k 1 and k 2 stand for the unknown orders of the lines and columns of dots with respect to the whole pattern design and allowing to switch from a relative pose measurement to an absolute one. Angle measurement is made by using the peak position F 1 whose coordinates are [m 1 , n 1 ] T in the Fourier domain and k 3 is the quadrant number of the imaged periodic pattern.

               x = φ 1 2π λ + k 1 λ y = φ 2 2π λ + k 2 λ α = atan2(n 1 , m 1 ) + k 3 π 2 (1)
This method has been notably explored in previous articles such as [START_REF] Sandoz | High-accuracy position and orientation measurement of extended two-dimensional surfaces by a phase-sensitive vision method[END_REF] or [START_REF] Chen | A vision-based method for planar position measurement[END_REF] to perform highly resolute in-plane pose measurement. However the main drawback of this highly resolute method is its range of measure which is limited to one period. To extend this range of measure, a binary sequence can be encrypted within the periodic pattern, thus ensuring absolute in-plane pose sensing through the unambiguous identification of the period orders k 1 , k 2 and the quadrant number k 3 of every imaged area of the pattern.

C. Absolute in-plane pose measurement

Different methods of inserting binary code in periodic patterns for absolute pose registration have been explored, notably by [START_REF] Kim | Note: An absolute xy-θ position sensor using a two-dimensional phase-encoded binary scale[END_REF] or [START_REF] Andre | Sensing one nanometer over ten centimeters: A micro-encoded target for visual in-plane position measurement[END_REF]. This paper relies on the pseudo-periodic pattern design proposed by the latter which is built according to the following steps. First, a bi-dimensional periodic grating of physical period λ is created. Then, a linear feedback shift register binary sequence is added to the pattern such that distortions of the periodic frame phase are avoided and, by padding with neutral lines and columns, a sufficient magnitude is retained for the spatial frequency of interest. Finally, rotation keying is added to allow for an absolute angle determination over 2π by removing specific dots in the pattern (the resulting pattern is depicted in Fig. 1.(a)). This encoding method can easily be scaled, making possible various resolutions and ranges of measure, as shown in previous works [START_REF] André | Robust, precise and scalable: A phase-encoded pattern for visual x, y, θ positioning[END_REF]. This pseudo-periodic pattern embeds two kinds of information: the first relies on the periodicity of the dots, which allows fine pose measurement based on the phase analysis of the pattern, and the second allows absolute position retrieval over a large range as well as absolute angle measurement based on the pattern's binary decoding. This decoding step involves the application of a local threshold to different phase maps of the pattern leading to the retrieval of the fringe counts k 1 , k 2 and quadrant number k 3 . In this fashion, an absolute and unambiguous pose measurement with a high sub-pixel resolution can be achieved for the in-plane case, and the measurement shows great robustness across different image alterations [START_REF] André | Robust phase-based decoding for absolute (x, y, θ) positioning by vision[END_REF]. This article extends this in-plane pose determination method to a full 6-DOF pose measurement through a deeper analysis of the spectral phase in the Fourier domain. Both the orthographic case and the perspective case with long focal lengths are separately examined, and the theory of the method is presented alongside its validation, which is demonstrated by both simulations and experiments.

III. 5-DOF POSE MEASUREMENT METHOD UNDER ORTHOGRAPHIC PROJECTION

A. Referential conventions and notations

As the method detailed in this paper is based on studying periodic patterns in the spectral domain by examining the frequency peaks that embed the pose information, an orthographic projection is considered to conduct the theoretical calculus. This projection allows the conservation of physical periods' proportions in the image and therefore produces punctual peaks (F 1 and F 2 as presented in Fig. 3.(b)) in the Fourier spectrum, which contains all information necessary to measure 6-DOF: the x, y translations, the α, β, γ orientations and the scale factor s of the pattern pose. Indeed, both peaks F 1 and F 2 of the Fourier transform carry their location [m 1 , n 1 ]

T , [m 2 , n 2 ] T and the phase value at the peak φ 1 , φ 2 .

Before considering how the spectrum of the image can be processed to retrieve the 6-DOF, the principal properties of this projection convention must be covered. Let us begin by defining the (scaled) dhorthographic projection:

  u v 1   =   s 0 0 0 0 s 0 0 0 0 0 1   . c T p •     P x P y P z 1     (2) where [u, v]
T is the projected point on the image sensor of the observed point [P x , P y , P z ] T in the object frame and where s is the unknown millimeter-to-pixel factor. c T p is the transformation matrix representing the pose of the frame of the pattern in the image sensor referential. Fig. 2 presents both referentials F c (frame attached to the camera) and F p (frame attached to the observed pattern) with the c T p transformation between them. By considering these successive measurement steps, the transformation matrix between the periodic pattern and the image of the pattern can be defined as follows:

c T p = transl(0, 0, z) • rotz(α) • roty(β) • rotx(γ) • transl(x, y, 0) (3)
α, β and γ are the Tait-Bryan angles describing the object's orientation. This form of transformation has been chosen to ease the calculation of off-axis angles, as it will be demonstrated in the following explanations of the method.

B. In-plane pose measurement

As outlined in section II, the pose measurement relies on the study of the phase of the observed pattern, which is obtained by taking advantage of the shifted 2D Fourier transform of the acquired pattern image. This transformation of an image from spatial domain to frequency domain can be expressed as follows:

Î(m, n) = w u=0 h v=0 I(u, v) • e -2πi[( u w -1 2 )m+( v h -1 2 )n] ( 4
)
where I is the pixel value of the acquired image and w and h are respectively the width and the height of the image. The resulting projection of a periodic pattern and its discrete Fourier transform can also be seen in Fig. 3.(a). The periodicity of the target results in four main peaks in the Fourier spectrum, with symmetrical peaks being complex conjugates of each other. These peaks in the Fourier domain are depicted in Fig. 3. (b). By studying the position [m 1 , n 1 ], [m 2 , n 2 ] and the phase φ 1 , φ 2 of these peaks, the [x, y, α, β, γ] T pose of the pattern can be measured, along with the scale factor s.

To increase the resolution of the phase measurements and the peak locations despite the discrete form of the Fourier transform, two phase maps of the pattern are computed back in the spatial domain using the following process. The coordinates of the two main frequency peaks representative of each direction of the periodic pattern are first retrieved (as depicted in Fig. 1.(b)). This step is made by searching for the pixels of highest modulus. In order to avoid phase distortion due to spectrum discretization, the inverse Fourier transform is computed for each frequency peaks F 1 and F 2 after the application of a Gaussian filter mask on each frequency peak respectively. This step therefore insures the conservation of all the peak information (and by extension the phase information) when doing the inverse Fourier transform. A better phase understanding of the periodic pattern can be done by unwrapping the two phase images resulting from the inverse Fourier transform as shown in Fig. 1.(c 1 ), (c 2 ).

These two phase maps encode the position of the pattern features with respect to the image pixel frame with a high resolution. The two phase maps evolution can be expressed by means of regression plane:

Φ i (u, v) = a i u + b i v + c i ( 5
)
where i is 1 or 2 to denote the main directions of the pattern. The constant c i gives a highly resolute measure of the phase of the peak i:

φ i = c i (6)
The position of the two main frequency peaks can be retrieved from the two phase planes equation:

       m i = w • a i 2π n i = h • b i 2π (7)
Another link between the phase plane equations and the spatial coordinates of the pattern referential can be expressed, based on the fact that each of the points constituting the referential is 2π farther from the center of the pattern image. Thus, the main director vectors of the phase evolution along each direction

h 1 = [u 1 , v 1 ] T and h 2 = [u 2 , v 2 ] T that can be seen in Fig. 1.(c 1 ), (c 2 ), are expressed by:          u 1 = b 1 • c 2 -(c 1 -2π) • b 2 a 1 • b 2 -a 2 • b 1 v 1 = a 2 • (c 1 -2π) -a 1 • c 2 a 1 • b 2 -a 2 • b 1 (8) and          u 2 = b 1 • (c 2 -2π) -c 1 • b 2 a 1 • b 2 -a 2 • b 1 v 2 = a 2 • c 1 -a 1 • (c 2 -2π) a 1 • b 2 -a 2 • b 1 (9)
To measure the pose, the (x, y) position in the pattern referential is processed first. Then, the pattern orientation α is computed accordingly to Eq. ( 1). Finally, the two off-axis angles (β, γ) are measured according to the method explained in the following. The distance between the pattern and the image z is excluded as it cannot be determined with an orthographic projection. The scale factor s of the projection, however, can be measured; it corresponds to a sixth DOF which will be converted into z-information in the perspective case.

F 1 at [m 1 , n 1 ] T and F 2 at [m 2 , n 2 ] T

C. Off-axis angles measurement

To recover the two off-axis angles of the observed pattern pose, along with the scale factor, the peaks' coordinates in the spectral domain are used. Indeed, these two vectors are directly linked with the two unit vectors defining the pattern referential as explained in previous section (with image coordinates By projecting these two points from the pattern frame to the image frame with the projection matrix c T p , a link between the pattern angles and the pattern direction vectors can be established:

h 1 = [u 1 , v 1 ] T and h 2 = [u 2 , v 2 ] T ,
  u 1 v 1 1   =   s 0 0 0 0 s 0 0 0 0 0 1   . c T p •     λ 0 0 1     = sλ cos α cos β sin α cos β (10)
The projection of the second direction vector λy p = [0; λ; 0] gives:

  u 2 v 2 1   =   s 0 0 0 0 s 0 0 0 0 0 1   . c T p •     0 λ 0 1     (11) giving u 2 v 2 = sλ cos α sin β sin γ -sin α cos γ sin α sin β sin γ + cos α cos γ = sλ cos α -sin α sin α cos α sin β sin γ cos γ (12)
Which can be rearranged in:

cos α sin α -sin α cos α • u 2 v 2 = sλ sin β sin γ cos γ (13)
Peaks coordinates in the Fourier spectrum give:

u 2 1 + v 2 1 = s 2 λ 2 cos 2 α cos 2 β + sin 2 α cos 2 β = s 2 λ 2 cos 2 β (14)
Thus:

cos 2 β = u 2 1 + v 2 1 s 2 λ 2 = b s 2 with b = u 2 1 + v 2 1 λ 2 (15)
Similarly, from equation 13, we have:

cos 2 γ = (-u 2 sin α + v 2 cos α) 2 s 2 λ 2 = g s 2 with g = (-u 2 sin α + v 2 cos α) 2 λ 2 (16)
sin 2 β sin 2 γ = (u 2 cos α + v 2 sin α) 2 s 2 λ 2 = d s 2 with d = (u 2 cos α + v 2 sin α) 2 λ 2 (17)
giving:

1 -cos 2 β 1 -cos 2 γ = d s 2 (18)
By replacing cos 2 β and cos 2 γ in the equation above, a second order equation for determining s is then deduced:

s 4 -(b + g + d)s 2 + bg = 0 (19)
As s is positive, two solutions are found:

s 1 = (b + g + d) + (b + g + d) 2 -4bg 2 (20) s 2 = (b + g + d) -(b + g + d) 2 -4bg 2 (21)
By solving these equations, two groups of 4 symmetric solutions for β and γ can be deduced from eq. 15 and eq. 16:

       β 1 = ± cos -1 √ b s1 γ 1 = ± cos -1 √ g s1 and        β 2 = ± cos -1 √ b s2 γ 2 = ± cos -1 √ g s2 (22)

D. Reduced set of solutions

Among this set of solutions, some of them can be removed, as it is the case for the solutions given by the second scale factor s 2 . Since √ b s2 > 1, solutions given by this set would lead to an evaluation of an arc-cosine larger than one. Setting aside the solutions for β 2 and γ 2 , a more comprehensive understanding of the remaining solutions can be studied. However, owing to the parallel-ray structure inherent in the orthographic projection, it is impossible to remove the ± ambiguity from the remaining solution for β 1 and γ 1 .

Fig. 4 presents a more visual way of understanding this ambiguity in the β and γ solutions with a periodic pattern rotating around the β axis (positively in red and negatively in blue), imaged via an orthographic projection on the camera plane. As the periodic pattern rotates from the same angle, either positively (as denoted by +β) or negatively (denoted by -β), the physical period λ results in the same imaged period p on the camera frame. This same ambiguity similarly affects the γ orientation. With this ambiguity in the angle determination in mind and the solutions derived from the second scale factor s 2 set aside, the final solution for off-axis angles β and γ can be written as follows:

                           β 1 = cos -1 √ b s1 ; γ 1 = cos -1 √ g s1 β 2 = -cos -1 √ b s1 ; γ 2 = cos -1 √ g s1 β 3 = cos -1 √ b s1 ; γ 3 = -cos -1 √ g s1 β 4 = -cos -1 √ b s1 ; γ 4 = -cos -1 √ g s1 (23)
In most of the case, this ambiguity as to whether the angle is positive or negative can be solved simply by hypothesizing that the movement of the periodic pattern remains continuous. However, by switching from a scaled orthographic projection to a perspective one, an unambiguous set of solutions for the 6-DOF pose can be found.

IV. EXTENSION TO 6-DOF POSE MEASUREMENT UNDER PERSPECTIVE PROJECTION WITH LONG FOCAL LENGTHS

As noted in the previous section, orthographic projection conserves the ratio of the imaged scene without regard for the distance from the camera of the points of the scene (as presented in the Fig. 4). Switching to a perspective projection causes the points of the scene to be projected according to the focal distance (pinhole model). This effect can be seen in Fig. 5, where the periods of an inclined periodic pattern yield different imaged periods p 1 and p 2 (in pixels). This projection also allows the measurement of the average distance of the observed periodic pattern from the camera (given its focal distance).

As illustrated in Fig. 5, retrieving the evolution of the pixelic period size inside the image, where larger pixelic periods denote the periodic pattern's closer proximity to the camera, allows a measurement of the absolute pose orientation of the pattern. Indeed, contrary to the case of an orthographic projection, the phase along each direction no longer increases linearly, as shown on Fig. 6. Since the period of the pattern is given by the first derivative of the phase (written Ψ i ), by studying the derivative of the period (written Υ i ), an absolute angle measure can be performed. A more comprehensive way to visualize the evolution of the different derivatives of the phase can be seen in the first supplementary material video, where the evolution Summarizing the different phase image gradients that are considered gives:

         Ψ i = dΦ i dh i Υ 1 = dΨ 1 du = d 2 Φ 1 du 2 (24)
As presented in Fig. 6.(b), in the case of an orthographic projection, the first derivative is a constant that represents the imaged pixelic period of the pattern. However, in the perspective case, this evolution is non linear and depends on the angle of the pattern. If this evolution along each main direction (h 1 , h 2 ) is increasing, the pattern is tilted towards the camera (respectively, if the period is decreasing then the pattern is tilted away from the camera). Thus, the study of the sign of this period evolution (i.e. its gradient) gives an absolute angle retrieval.

   Υ 1 > 0 ⇔ β > 0 Υ 2 > 0 ⇔ γ > 0 (25)
In order to measure the derivatives of the phase evolution along each direction (giving the period evolution along each main direction of the pattern), an implicit change of referential from the camera frame to the pattern is done.

By considering the two phase maps, their gradients in the pattern axis base (h 1 , h 2 ) is given by:

Ψ i = dΦ i dh i = ∂Φ i ∂x c • ∂x c ∂h i + ∂Φ i ∂y c • ∂y c ∂h i ( 26
)
∂Φi dxc and ∂Φi dyc can be calculated with a classic image gradient method consisting of a convolution product between a kernel and the phase map images. Presented method relies on the Sobel operator that gives the following derivatives:

∂Φ i dx c =   1 2 1 0 0 0 -1 -2 -1   ⊗ Φ i (27)
and

∂Φ i dy c =   1 0 -1 2 0 -2 1 0 -1   ⊗ Φ i ( 28
)
where ⊗ is the bi-dimensional convolution product. Since this first Ψ i gradient calculation was made to shift from the camera frame referential to the pattern's one, the next gradient calculation (Υ i ) is more straightforward and can be expressed directly as the gradient of the obtained image along each direction. Finally, to retrieve the sign of pattern orientation, the sign of Ῡi along each direction can be studied as:

               sign(β) = sign( Ῡ1 ) = sign 1 w•h w-1 i=0 h-1 j=0 Υ 1 sign(γ) = sign( Ῡ2 ) = sign 1 w•h w-1 i=0 h-1 j=0 Υ 2 (29)
With this, a direct choice among the set of solutions for β and γ orientations can be made to provide an absolute angle retrieval.

Finally, to ensure a complete pose measurement, the distance of the pattern to the camera z can be calculated with the perspective projection, given the equivalent focal distance f of the camera and the scale factor s:

z = f s (30)
As explained at the beginning of this section, this method of unambiguous pose measurement relies on the non-linearity of the two phase maps. On the other hand, presented method uses the assumption of a linear phase, used to compute the two phase planes equations. Therefore depending on the application, a trade-off between a purely orthographic projection resulting in a highly resolute but ambiguous pose measure and a highly perspective projection resulting in a less resolute pose measurement but unambiguous needs to be found.

With the already discussed method of absolute in-plane pose retrieval shown in section II and the equations for absolute pose measurement presented in the two previous sections, a full pose can be deduced directly from the Fourier analysis of the pattern. The next sections will study the capabilities and limitations of the presented method of pose measurement in order to validate it both with numerical simulation and by experimentation.

V. NUMERICAL PERFORMANCES EVALUATION

The presented method has been programmed in C++ for computation efficiency and can carry the full pose measurement of encoded periodic patterns with a frequency up to 25 Hz (for images sizing 512 × 512 px) with a standard computer (i7 processor at 3.7 GHz with 32 Go of RAM). For larger images (1024 × 1024 px), a frequency of 5 Hz is achieved. Along with the pose measurement implementation, this library can also generate images of periodic patterns along the 6-DOF that can be used for simulation purposes. More insights on the computation time can be found on the library's reference website 1 . With this tool, a closed loop between generated patterns and their pose measure can be done to evaluate numerical accuracy.

A. Orthographic range evaluation

The first evaluation of the method aims to identify the available range of measure for the two off-axis angles in the orthographic case by simulating periodic pattern poses with β and γ rotations. Both angles are set to evolve in the [0, π 2 ] rad. range and by studying the error between the sent pose and the computed one, a refined angle measurement range with an error lower than 1 µrad. can be found. To perform this simulation, perfectly simulated patterns images with a 25 px period are generated at the following poses: [0, 0, 0, 0, β, γ] with β and γ set to evolve in the [0, π 2 ] rad. range. As previously explained in section III-D, under orthographic projection, off-axis angle measurement is the same for positive and negative values of rotation. Thus, simulations can only focus on the case where β and γ evolve on the positive side. This simulation can be treated as a map with the β angle evolving along the x axis and the γ angle along the y axis, as shown in Fig. 7. Fig. 7 summarizes the relative error evolution of each angle measurement as the two maps' results. These error maps provide information about the relative error between the sent pose and the computed one. When both β and γ angles are in the [0, 1.21] rad. range (in the red square), the level of error presents a standard deviation of 1.81 • 10 -7 rad. for both measures.

The first black line represents the limit of the peaks detection of the algorithm when the second one stands for the Shannon limit. Indeed, when the pattern is rotated the apparent period on the image is equal to sλ cos(β) cos(γ). If this value is below 2 px, the frequency of the pattern is not detectable (Nyquist-Shannon sampling theorem). The peak localization in the Fourier transform is no longer efficient when this value is below 3 px that is very close to the theoretical limit.

This measurement range can be much appreciated in the second supplementary video where pseudo-periodic pattern images are generated at various off-axis angles in the [0, π 8 ] rad. range. This short video also shows that the level of error between sent angle and computed one doesn't exceed 1 µrad. most of the time even when considering an encoded periodic pattern. The supplementary video 3 presents an other view of the available measurement range. This one presents an encoded periodic pattern rotating along the β angle from 0 to π 2 rad. This video demonstrates the underlying base of the pose measurement method, that lean on the detection of the two main spectrum peaks. As it can be seen in this one, as long as the visible period of the pattern is below the Shannon limit, the pose is measured with a great accuracy.These two videos also provide a more comprehensive way of understanding how the Fourier spectrum and the main peaks used in the pose measurement process move when large off-axis angles are considered.

B. Random 3D pose simulation under orthographic projection

To validate the method's performance along the 6 studied degrees of freedom, a set of 1000 random images has been generated. The considered range is the in-plane (x, y, α) one provided by the encoded target and the range studied in the previous section for off-axis angles (β, γ). To evaluate the last considered degree of freedom s (the scale factor), the apparent period is randomly set between 8 and 12 px. In short, the patterns is generated according to following parameters: [8,12]. The results of this simulation can be visualized as six separate histograms revealing the error of the pose measurement; these are presented in Fig. 8. These results show that the off-axis angles do not impact the in-plane measure with a resolution of less than 1/1000 th of a pixel in translation and 0.2 • 10 -6 rad. in orientation. The two considered off-axis angles β and γ reveal a Fig. 8: Error measure between sent pose and computed one with a data set of 1000 randomly generated poses resolution around 5 • 10 -6 rad. and an error in the scale factor measure of around 6.94 • 10 -4 . Along with the histogram plot of errors, the dataset used for this study can be found in Supp. Mat. 2.

• (x, y) ∈ [0, 10 4 ] px. • α ∈ [0, 2π) rad. • (β, γ) ∈ [0, 3π 8 ] rad. • λ.s ∈

C. Comparison with PnP pose estimation

A last simulation aiming to compare the performance of proposed method with a classic Perspective-n-Point (PnP) pose estimation is put in practice. In order to make a fair comparison, the same set of images of a circle grid has been used for both methods. The pose of the circular grid is estimated via the PnP pose estimation algorithm implemented in OpenCV (with the two commands findCirclesGrid and solvePnP 2 ). Along with the comparison of the presented method with a classical pose estimation method, this simulation aims also to study the impact of the perspective projection on the resolution of the measure. Indeed, as discussed in the last part of section IV, the non-linearity of the phase maps induced by shorter focal lengths may result in less resolute measures. For both methods, the simulations also explore the impact of the pattern period on the achieved resolution on the interval sλ ∈ [6, 70] px.

The parameters to generate the set of grid images can be organized in three parts that are listed below:

• 4 different off-axis angles (0.01, 0.1, π/8 and 1 rad.)

• 4 different focal lengths (orthographic, 300, 50 and 16 mm)

• The pixelic period set to increase in the [6, 70] px range The resulting generated set of images from these parameters are available for download 3 Fig. 9 presents the results of this comparison with a lin-log scale. Concerning the proposed method, Fig. 9.(a) confirms that its resolution varies with the number of periods visible in the image. Indeed, no matter the focal length or the off-axis angle 2 OpenCV PnP solver documentation available here: https://docs.opencv.org/3.4/d9/d0c/group calib3d.html 3 https://sourcesup.renater.fr/www/vernierlibrary/data/ (a) Proposed method error evaluation used, below 25 visible periods (or over a visible pixelic period of 40 px), a significant decrease in the resolution is observed.

When the number of visible periods is over 25, a resolution below 10 -6 rad. can be achieved. This resolution also depends on the focal length used and, as depicted in the sub-figures, the resolution decreases as the focal length also decreases and this impact of the focal length is stronger for larger out-of-plane angles. In comparison, as shown in Fig. 9.(b), the classic PnP method isn't impacted by the focal length used nor by the increase of the off-axis angles. Indeed shown resolution remains below 10 -4 rad. However, since this method uses a perspective projection to estimate the pose, it is normal to see a very low resolution when an orthographic projection is involved. This comparison between the two methods highlights the better sensitivity of the proposed phase-based method, especially for small out-of-plane angles. As one can see, for an off-axis angle of 0.01 rad. a resolution of 10 -7 rad. is achieved to be compared to the 10 -3 rad. achieved by the PnP method. The fact that the proposed method considers the phase of every image pixel rather than only the centers of geometrical features explains partly such a discrepancy.

VI. EXPERIMENTAL VALIDATION

To validate both the high-resolution pose measure and the available range of measure along the two off-axis angles β and γ, and along the optical axis z, two main experiments were designed.

A. Validation under orthographic projection

To demonstrate the proposed method's experimental performance, multiple setups have been put in practice. The first experimental setup uses a camera (IDS UI-3280CP) and a 5x microscope objective (Optem with a numerical aperture of 0.14 and a depth of field of 29 µm) coupled with a 1.5x microscope tube (Optem) to record images of a pseudo-periodic encoded pattern printed on a glass plate with a period of 9 µm. The plate was placed on a single axis rotary stage (Smaract SR2013 with a closed loop resolution of 0.5 µrad. The camera is set to record images at a constant frame-rate of 20 images per second, encoded at a depth of 12 bits. The binary encoded pattern and the rotary stage are placed on a xyz manual axis stage in order to situate the observed target perpendicular to the optical axis of the microscope objective. Fig. 10 and supplementary material 4 summarizes the disposition of the main elements of this experimental setup.

1) Resolution evaluation: A first step in finding the real resolution of the off-axis angular determination is to study the static noise measure. This one is measured with the setup detailled above, with the rotary stage switched off during a 40-second run, resulting in an 800-image analysis. The measure of the noise is collected by computing the standard deviation (std) of each of the computed angles. The results, which are presented in Tab. I indicate a static noise of around one tenth of a milliradian and demonstrate the maximal resolution attainable with this setup. To estimate the angular resolution achievable via the presented method, a square signal consisting of steps of 0.2 mrad. is sent to the rotary stage at a constant rate of 0.25 Hz, thus allowing an acquisition of 40 images per step. Computed angles are presented in Fig. 11.(a). and confirm the resolution capabilities of angle determinations that lie below 0.1 mrad. This figure also presents the computed mean angle and the error bar for each step of the sent square signal. Differences between the resolution evaluated with generated images in the previous section and the resolution presented in Table . I are largely attributable to environmental disturbances such as vibrational noise coming from the experimental setup and from experiment room. A differential analysis of the set of images with the same setup demonstrated that, in the in-plane measurement case, environmental disturbances are responsible for more than 93% of the total variance of errors [START_REF] Andre | Sensing one nanometer over ten centimeters: A micro-encoded target for visual in-plane position measurement[END_REF]. measure, no pertinent quantitative comparison can be done with this setup. However, with the considered displacement range of 10 mm and the measured position shown in Fig. 13.(b), a resolution of at least 0.1 mm can be deduced. In pixelic terms, this sub-millimetric resolution corresponds 0.5 • 10 -3 pixels resolution, which confirms the method's global performance in depth estimation. As explained in the presentation of the experimental setup, the considered objective provides a measurement range of ± 5 mm around the focal plane when closed at f /16, but this range could easily be extended by using an objective with a larger depth of focus.

2) 6-DOF trajectory pose measurement: The final experiment is set up to validate the pose measure under perspective projection along the 6 degrees of freedom simultaneously. For this purpose, this setup also make use of the 6-DOF serial robot described above. To generate a trajectory that would evolve in the whole studied range, each degree of freedom is assigned to a sinusoidal input with slightly different frequencies and phase shifts resulting in the global 6-DOF trajectory presented in Fig. 14. Using this trajectory generation method ensures that the majority of the range is studied during the experiment and that computed results are homogeneous within the entire range.

As presented in the introduction of this paper, there are other viable methods of single-camera pose measurement using the coplanar constraint of fiducial markers, such as chessboards and ArUco markers. This experiment is therefore also designed to compare these alternatives' capabilities with those of the presented method. To that end, a chessboard with squares sizing 1.8 mm and an ArUco marker sizing 9.8 mm are printed and placed on the end effector of the robot. The results of the acquired images,as well as the sizes of the different markers can be seen in Fig. 12.(b 1 ), (b 2 ).

To keep the ArUco fiducial marker and the chessboard in the camera frame, translations along the x and y axis are set in the [-5; 5] mm range. The range of displacement along the z axis is also set to stay within [-5; 5] mm around the focal plane (the same range used in the prior experiment). As this experiment's goals include the validation of the method in cases where larger off-axis angles are implied, sent angles are set in the [-10, 10] degree range ([-0.17, 0.17] rad.).

The results of the pose measurement are presented in Fig. 14, along with different views that help elucidate the global 6-DOF trajectory evolution of the robot. The validation of the method therefore stems from the global evolution of the trajectory, which remains unchanged across the three tested methods. However, while ArUco markers and chessboards tend to work better with wider perspective projection and lower distances, as discussed in section V-C, and as shown by [START_REF] Abawi | Accuracy in optical tracking with fiducial markers: an accuracy function for artoolkit[END_REF][START_REF] Pentenrieder | Accurate full-field optical displacement measurement technique using a digital camera and repeated patterns[END_REF], their measured poses present much more noise than the presented method, especially for off-axis orientations β and γ and for z depth measure. In fact, relying on the highly redundant periodic information of the pattern processed in the Fourier domain reduces the noise of the resulting computed poses and, as shown on Fig. 14, greatly increases their resolution.

VII. CONCLUSION AND PROSPECTS

This article proposed a novel method of measuring the pose of periodic patterns by analyzing the Fourier spectrum of the acquired images. The presented method can be applied in orthographic projection with a 5-DOF pose measures with ambiguities to determine the off-axis angles and the scale factor. This can be solved by using a perspective projection with long focal lengths that leads to a full and unambiguous pose measure, including a measure of depth. By validating the method through simulations, this research demonstrated a range of measure of ±3π/8 rad. (1.21 rad.). These simulations also permitted the demonstration of high-resolution capabilities of the measure with an error level of less than 1/1000 th of a pixel in translation, 0.2 µrad for in-plane orientation, and 1 µrad for off-axis orientations.

Presented method was numerically compared to the widely used PnP method for a set of four focal lengths, four out-ofplane angles and on a pixelic period interval of [40,70] px. The proposed spectral method outperforms the OpenCV PnP implementation, especially in the orthographic projection case and at low out-of-plane angles. The fact that the proposed method considers the phase of every image pixels rather than only the centers of geometrical features explains partly such a discrepancy.

The method was investigated experimentally within the range allowed by the lenses used and revealed a resolution of 0.1 mrad. and a linearity of 0.035% for the off-axis orientation measure. Finally, the proposed method was applied to a perspective projection experiment, revealing a resolution of the pattern pose measure along the z axis lower than 0.1 mm. To conclude, the method was tested through a comparison experiment implying other well known fiducial markers and proved the measure to be more resolute than other methods.

As shown in the different experiments, the encoded pattern can be scaled and applied to various camera projection models, leading to either a 5-DOF or a 6-DOF pose measure, and can therefore be addressed to different fields of application. In microrobotics, for instance, the pattern might be used to control the precise localization of microrobots, viewed under microscopes for micro assembly issues. On a larger scale, the method could also be applied to control the pose of robots along the 6-DOF and offer an interesting alternative with better resolution to pre-existing markers. With the large covering of the pattern in the image and with the knowledge of its physical period, it is possible to carry high resolution calibration both for robots and for camera used. Finally, this method offers a good compromise between interferometry and visual pose estimation by requiring fewer material than interferometers while presenting better resolutions than fiducial-marker-based methods.

A major prospect for the presented work is its enlargement under a wider perspective by considering different forms of Fourier analysis that could function with non-linear projection of periodic pattern evolution. This non-linear analysis in the Fourier domain could also lead to new applications which would be less focused on the micro-scale such as camera calibration following the work of [START_REF] Chen | Fourier-transform-based two-stage camera calibration method with simple periodical pattern[END_REF], who used the phase planes to robustly detect the points of a grid before solving the PnP problem.

Fig. 1 :

 1 Fig. 1: In-plane pose measurement process with (a) an image of a pseudo-periodic encoded pattern, (b) the corresponding spectrum of the pattern image resulting from the Fourier transform, (c 1 ) the inverse Fourier transform phase evolution along the first direction and (c 2 ) along the second direction once 2π unwrapped. Vectors h 1 and h 2 denote the main direction vectors associated with each phase plane

Fig. 2 :

 2 Fig. 2: 3D view of the orthographic projection of the pattern on the image with referential convention annotated

Fig

  Fig. 3: (a) Front view of the orthographic projection of the pattern on the image sensor and (b) Main lobes of the Fourier transform of the periodic pattern with main periodic peaks F 1 at [m 1 , n 1 ] T and F 2 at [m 2 , n 2 ] T

  as shown in Fig. 3.(a)) sizing one period long λx p = [λ, 0, 0] T and λy p = [0, λ, 0] T .

Fig. 4 :

 4 Fig.4: Same periodic pattern of period λ rotated of +β (in red) and -β (in blue) and imaged via an orthographic projection on a camera frame, resulting in the same perceived pixelic period p

Fig. 5 :

 5 Fig. 5: Perspective projection of a rotated periodic pattern presenting different imaged pixelic period, depending of the distance of the pattern to the camera frame

Fig. 6 :

 6 Fig.6: Line projection of a tilted pattern through perspective projection with its phase evolution and its derivatives. (a) phase evolution along direction h in the image and highlights the impact of the perspective projection on the phase evolution compared to an orthographic projection. (b) first derivative of the phase along h and by extension the observed period evolution of the periodic pattern. (c) second derivative of the phase that allows to find the angle sign with the sign of its mean

  Fig. 7: Off-axis angles error maps when the pattern (period 25 px)is tilted along β and γ orientations in the [0, π/2] range. (a) presents the error of evaluation of the β angle and (b) presents the γ error map. The area where both angles are measured with an error lower than 1 µrad. is denoted in red in both sub-figures. The black lines show the angles for which the apparent period is respectively 3 and 2 pixels long.

Fig. 9 :

 9 Fig. 9: Off-axis angle measurement error in function of the pixelic period of the periodic pattern for a set of four focal lengths and of four off-axis angles. (a) proposed method; (b) OpenCV PnP method.

Fig. 10 :

 10 Fig. 10: Experimental setup put in practice to validate the resolution performances of the off-axis angle measurement

  Fig. 11: (a) β resolution evaluation, steps of 2 seconds (containing 40 images per step ) run over 40 seconds. (b) Linearity evaluation experiment along β orientation

  Fig. 14: 6-DOF trajectory evaluation with different sinusoidal inputs made with a pseudo-periodic pattern, a chessboard and an ArUco marker distributed in two sub-figures for (a) the translations and (b) the orientations measures

ACKNOWLEDGMENT

  This work was supported by Région Bourgogne Franche-Comté, by the ANR project Holo-Control (ANR-21-CE42-0009), by the I-SITE BFC project HoloNet (ANR-15-IDEX-03), by Cross-disciplinary Research (EIPHI) Graduate School (ANR-17-EURE-0002). The encoded target was realized thanks to the RENATECH technological network and its FEMTO-ST facility MIMENTO. The experiments was conducted within the ROBOTEX robotics network (ANR-10-EQPX-44-01) and its FEMTO-ST micro-nano-robotics center. Authors acknowledge G. Jutzi, L. Robert, M. Suarez and L. Gauthier-Manuel for technological and experimental assistance.

TABLE I :

 I Standard deviation levels observed on each measured degree of freedom during a static test of 40 seconds (800 images)

	DOF std	unit
	x	8.07	nm
	y	16.02	nm
	s	0.42 • 10 -6	px/mm
	α	3.25	µrad.
	β	0.1205	mrad.
	γ	0.1181	mrad.

https://projects.femto-st.fr/vernier/en

2) Linearity and range of measure evaluation: To complete the evaluation of the method's performance, a test of linearity is conducted. Since this article's primary contribution is to present a novel means of retrieving a 6-DOF pose at the micro-scale, the range of measure presented in the simulation section of 3π/8 can't be achieved with experiments involving a microscope. Indeed this range of measure is inherently shortened by the depth of field of used microscope objectives. The one used for the experiment has a depth of field of 28 µm, with this, any angle higher than 0.03 rad. will result in a blurred image on each side of the pattern. The problem raised by this blur appearing at the borders of acquired images is a weaker spectrum peak energy that leads to a less resolute measure. The experimental validation of the linearity will therefore be made by sweeping the target in the range of [0; 0.03] rad. The results, presented in Fig. 11.(b), highlights the high linearity of the orientation measurement, with an error factor of approximately 0.35% in the evaluated range with regards to the inherent limitations of he experimental setup and its envionmen,

B. Validation under perspective projection with long focal length

In order to validate the 6-DOF pose measurement method presented in section IV, another experiment involving a macroscopic setup is put in practice.

This setup, presented in Fig. 12, comprises a 6-DOF serial robot (with 3 prismatic and 3 rotational Smaract actuators), a macro objective (Kowa 50 mm) and the same camera that was used in the experiments previously described. As this set of experiments is meant to validate the pose measure at a larger scale, an encoded periodic pattern with a 140 µm period is placed on the end effector of the robot (the resulting acquired images of the pattern can be seen in Fig. 12.(b 3 )). To maximize the depth of field (and therefore the available range of measure) along the optical axis z, the objective is stopped at f /16. The capabilities of the lens include an available range of focusing around 10 mm; the closing of the aperture results in sharper acquired images, in addition to the increased depth of field. The objective and the camera are placed at a distance of 30 cm from the robot, allowing a perspective projection weak enough to carry the localization of the peaks in the Fourier transform with sufficient accuracy. However, the robot's accuracy is unknown and experiments are carried out to broaden the measure by considering larger rotations and displacements under perspective projection.

1) Evaluation along the z axis: The first experiment involving this setup is to insure the validity of the pose measurement along the optical axis z. To do this, a trajectory composed by a translation along the x and y axis (resulting in the logo pattern presented in Fig. 13.(c)) and by a sinusoidal translation along the z axis (as shown in Fig. 13.(b)) is sent to the robot. The chosen objective and aperture allow a range of ± 5 mm around the focal plane in which the pattern would stay sharply in focus, and therefore, the sinusoidal trajectory sent along the z axis is set to evolve in the [-5; 5] mm range.

The resulting curves show that the measure is qualitatively smooth all along its path in the z direction and is unaffected by the x, y position of the pattern. Unfortunately, since the measure of the robot is of a lower resolution that the tested pose

CONFLICT OF INTEREST

The authors declare that they have no conflict of interest.


Carole Delporte-Gallet

Hugues Fauconnier

Andreas Tielmann
email: tielmann@liafa.jussieu.fr

Fault-Tolerant Consensus in Unknown and Anonymous Networks

This paper investigates under which conditions information can be reliably shared and consensus can be solved in unknown and anonymous message-passing networks that suffer from crash-failures. We provide algorithms to emulate registers and solve consensus under different synchrony assumptions. For this, we introduce a novel pseudo leaderelection approach which allows a leader-based consensus implementation without breaking symmetry.

Introduction

Most of the algorithms for distributed systems consider that the number of processes in the system is known and every process has a distinct ID. However, in some networks such as in wireless sensors networks, this is not necessarily true. Additionally, such networks are typically not totally synchronous and processes may suffer from failures such as crashes.

Designing protocols for such networks is especially intricate, since a process can never know if its messages have been received by all processes in the system. In this paper, we investigate under which conditions information can be reliably shared and consensus can be solved in such environments.

Typically, in systems where no hardware registers are available, one makes additional assumptions to be able to reliably share information, e.g. by assuming a correct majority of processes. However, these techniques assume also some knowledge about the total number of processes. With processes with distinct identities, the requirements to emulate a register have been precisely determined by showing that the quorum failure detector Σ is the weakest failure detector to simulate registers in asynchronous message passing systems [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF]. But again, this approach fails due to the lack of identities in our anonymous environment.

To circumvent these problems, we assume that the system is not totally asynchronous, but assume the existence of some partial synchrony. We specify our environments by using the general round-based algorithm framework (GIRAF) of [START_REF] Keidar | How to choose a timing model[END_REF]. This has two advantages: (i) it is easy to precisely Carole Delporte-Gallet and Hugues Fauconnier were supported by grant ANR-08-VERSO-SHAMAN. Andreas Tielmann was supported by grants from Région Ile-de-France.

specify an environment and (ii) it makes it easy to emulate environments to show minimality results.

We first define the moving source environment (MS) in which at every time at least one process (called the source) sends timely messages to all other processes, but this source may change over time and infinitely often. Although this environment is considerably weaker than a total synchronous environment, we show that it is still sufficient to implement registers, although it is not possible to implement the consensus abstraction. In fact, it can be emulated by hardware registers in totally asynchronous "known" networks for any number of process crashes. Therefore, if we would be able to implement consensus in this environment, we could contradict the famous FLP impossibility result [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF]. This result states, that consensus cannot be implemented in asynchronous message passing networks, even if only one process may crash. Since we can emulate registers if only one process may crash [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF], we can also emulate the MS environment and therefore cannot be more powerful.

To implement consensus, we consider some additional stronger synchrony assumptions. Our first consensus algorithm assumes that additionally to the assumptions of the MS environment, eventually all processes communicate timely. We call this environment the eventual synchronous (ES) environment. It resembles Dwork et al. [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]. In our second consensus algorithm, we consider a weaker environment and only assume that eventually always the same process is able to send timely to all other processes. We call it the eventual stable source environment (ESS). It resembles the model of [START_REF] Aguilera | On implementing omega with weak reliability and synchrony assumptions[END_REF] in which it is used to elect a leader, a classical approach to implement in turn consensus.

Due to the indistinguishability of several processes that behave identical, a true leader election is not possible in our anonymous environment. Therefore, in our second algorithm, we take benefit of the fact that it suffices for the implementation of consensus if all processes that consider itself as a leader behave the same way. We show how to eventually guarantee this using the history of the processes proposal values.

Furthermore, we consider the weak-set data-structure [START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF]. This data-structure comes along some problems that arise with registers in unknown and anonymous networks. Every process can add values to a weak-set and read the values written before. Contrary to a register, it allows for sharing information without knowing identities of other processes and without the risk of an overwritten value due to a concurrent write. Furthermore, we show that it precisely captures the power of the MS environment, i.e. we can show that it can be implemented in the MS environment and a weak-set can be used to emulate the MS ennvironment. Interestingly, in known networks, a weak-set is equivalent to the register abstraction and can thus be seen as a generalization for unknown and anonymous networks.

Furthermore, we show that although it is possible to emulate registers in our MS environment, it is not possible to emulate Σ [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF], the weakest failure detector for registers. And this result is not only due to the anonymity of the processes, it holds even if the number of processes and their identities are known. Note that this is not a contradiction, since the result in [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF] means only that Σ is the weakest of all failure detectors with which a register can be implemented and we have exhibited synchrony assumptions where the existence of a failure detector is not necessary at all.

Related work

There have been several approaches to solve fault-tolerant consensus in anonymous networks deterministically. In [START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF], fault-tolerant consensus is solved under the assumption that failure detector Ω [3] exists, i.e. exactly one correct process eventually knows forever that it is the leader. In [START_REF] Guerraoui | Anonymous and faulttolerant shared-memory computing[END_REF], faulttolerant and obstruction-free1 consensus is solved if registers are available.

There has also been some research on systems where IDs are known but the number of processes is not. In [START_REF] Greve | Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks[END_REF], it is assumed that processes may crash, but furthermore that it is possible to detect the participants initially. In [START_REF] Tucci | Brief announcement: Eventual leader election in the infinite arrival message-passing system model[END_REF], a leader election algorithm for a system where infinitely many processes may join the system is presented if the number of processes simultaneously up is bounded.

To the best of our knowledge, this paper presents completely new approaches to emulate registers and solve the consensus problem in unknown and anonymous environments with partial synchrony.

Model and Definitions

We assume a network with an unknown (but finite) number of processes where the processes have no IDs (i.e. they are totally anonymous) and communicate using a broadcast primitive. The set of processes is denoted Π. We assume that the broadcast primitive is reliable, although it may not always deliver messages on time. Furthermore, any number of processes may crash and the processes do not recover. Processes that do not crash are called correct.

We model an algorithm A as a set of deterministic automata, one for every process in the system. We assume only fair runs, i.e. every correct process executes infinitely many steps.

Consensus

In the consensus problem, the processes try to decide on one of some proposed values. Three properties have to be satisfied:

Validity:

Every decided value has to be a proposed value. Termination: Eventually, every correct process decides. Agreement: No two processes decide different values.

An extension to GIRAF

Algorithm 1 presents an extension to the generic roundbased algorithm framework of [START_REF] Keidar | How to choose a timing model[END_REF] (GIRAF). It is extended to deal with the particularities of our model, namely the anonymity and unknown number of the processes. The framework is modeled as an I/O automaton. To implement a specific algorithm, the framework is instantiated with two functions: initialize() and compute(). The compute() function takes the round number and the messages received so far as parameters. We omit to specify a failure detector output as parameter (as in [START_REF] Keidar | How to choose a timing model[END_REF]), because we are not interested in failure detectors here. Both functions are non-blocking, i.e. they are not allowed to wait for any other event.

Our extension lies in the way we model the received messages. Since the processes have no IDs, we represent the messages that are received during one round as a set instead of an array.

The communication between the processes proceeds in rounds and the advancement of the rounds is controlled by the environment via the receive i and end-of-round i input actions. These actions may occur separately at each process p i and therefore rounds are not necessarily synchronized among processes. The framework can capture any asynchronous message passing algorithm (see [START_REF] Keidar | How to choose a timing model[END_REF]).

Environments are specified using round-based properties, restricting the message arrivals in each round.

Environments

We say that a process p i is in round k, if there have been k invocations of end-of-round i . A process p i has a timely link in round k, if end-of-round i occurs in round k and every correct process p j receives the round k message of p i in round k.

In this paper, we consider three different environments:

Algorithm 1: Extended GIRAF generic algorithm for process p i .

States:

ki ∈ N, initially 0;

Mi[N] ⊆ Messages, initially ∀k ∈ N : Mi[k] = ∅;
Actions and Transitions:

input end-of-round i if (ki = 0) then m := initialize(); else m := compute(ki, Mi); Mi[ki + 1] := Mi[ki + 1] ∪ {m}; 10 ki := ki + 1; 11 output send( Mi[ki], ki )i; 12 input receive( M, k )i 13 Mi[k] := Mi[k] ∪ M ;
14 exists a process p s (a source) that has a timely link in round k. • In the second environment, which we call the eventual synchronous (ES) environment, we demand the same as in the MS environment, but additionally require that there is some round k such that in every round k ′ ≥ k, all correct processes have timely links in round k ′ . • In the third environment, which we call the eventually stable source (ESS) environment, we demand the same as in the MS environment, but additionally require that eventually the source process p s is always the same in every round. This means, that there is some round k such that in every round k ′ ≥ k, the same process p s has a timely link in round k ′ . on compute(ki, Mi) do Algorithm 2 implements consensus in the ES environment. The idea of the algorithm is to ensure safety by waiting until a value is contained in every message received in a round. In this way, one can ensure that a value has also been relayed by the current source and is therefore known by everybody (we say that the value is written). If a process evaluates Line 9 to true, then VAL is known by everybody (because it was written in the last round) and no other process will consider another value as written, because only a value which has also been relayed by a source can be in WRITTEN. But the relayed value of a source would also be in PROPOSED at every process.

Implementing consensus in ES

WRITTEN := T m∈M i [k i ] m; PROPOSED := ( S m∈M i [k i ] m) ∪ PROPOSED; if (ki mod 2 = 0) then if (PROPOSED = WRITTENOLD = {VAL})
To guarantee the liveness of the consensus algorithm, we use the fact that eventually, all proposal values in the system are received in every even round by everybody and everybody will select the same maximum in Line 12. Therefore, everybody will propose the same value in the next round and the algorithm will terminate.

Analysis

For all local variables VAR, we denote by VAR i the local variable of process p i (e.g., PROPOSED i ). For every variable VAR i , VAR k i is the value of this variable after process p i has executed Line 7 when compute has been invoked with parameter k (i.e. in round k).

Lemma 1.

If no process has decided yet and for some p i , v ∈ WRITTEN k i , then every process p j that enters round k has v ∈ PROPOSED k j . Proof: If a process p i has a value v in WRITTEN k i , then v has been contained in every message, which p i has received in round k (Line 6). This includes the message of the source, since by assumption the source has not yet terminated. But by definition, every other process p j that enters round k also has received the message of this source in this round and added it to its set PROPOSED k j (Line 7). Therefore, v is in PROPOSED k j . Lemma 2. If no process has decided yet and p i has v ∈ WRITTENOLD k i in an even round k, then every other process

p j that enters round k has v ∈ WRITTEN k j . Proof: If a process p i has a value v in WRITTENOLD k i , then it has had v in WRITTEN k-1 i
. Therefore, every other process p j that enters round k -1 has v in PROPOSED k-1 j in the same odd round k -1 (Lemma 1). Since no value is removed from a set PROPOSED in odd rounds, v will be contained in every set PROPOSED broadcast at the end of round k -1 and therefore get into WRITTEN k j at every process p j that enters round k.

Theorem 1. Algorithm 2 implements consensus in the ES environment.

Proof: We have to prove the 3 properties of consensus. Validity is immediately clear, because VAL is always an initial value.

To prove termination, assume that the system has stabilized, i.e. all faulty processes have crashed and all messages are received in the round after which they have been sent. Then, all processes receive the same set of messages in every round. Therefore, the set PROPOSED and thus WRITTEN is the same at all correct processes and everybody will always select the same maximum in Line 12. In the next round all processes start with the same proposal value and this value will be written in every future round. Thus, everybody will evaluate Line 9 to true in the next round.

To prove agreement, assume p i is the first process that decides a value v in a round k. This means, that p i has evaluated Line 9 to true. If some other value than v would have been written anywhere in the system, this would contradict PROPOSED = {v} (Lemma 1), since p i is the first process that decides. Furthermore, v is in WRITTEN at every process in the system in round k, since it is also in WRITTENOLD (Lemma 2). Therefore, every other process decides v in the same round, or it will evaluate Line 11 to true and select v as new VAL. Thus, no other value will ever get into PROPOSED anywhere in the system, no other value will ever be written and no other value will ever be selected as VAL.

Implementing consensus in ESS

Algorithm 3 implements consensus in the ESS environment. For the safety part, the algorithm is very close to algorithm 2 (see Section 3).

To guarantee liveness, we use the fact that we have at least one process which is eventually a source forever. We use the idea of the construction of the leader failure detector Ω [START_REF] Deepak | The weakest failure detector for solving consensus[END_REF]. It elects a leader among the processes which is eventually stable. In "known" networks, with some eventual synchrony, Ω can be implemented by counting heartbeats of processes (e.g. in [START_REF] Aguilera | On implementing omega with weak reliability and synchrony assumptions[END_REF]). But we are not able to count heartbeats of different processes here, because in our model the processes have no IDs. To circumvent this problem, we identify processes with the history of their proposal values. If several processes have the same history, they either propose the same value, or their histories diverge and will never become identical again. Eventually, all processes will select the same history as maximal history and the processes with this history will propose in every round the same values.

Implementation

Every process maintains a list of the values it broadcasts in every round (specifically, its proposal values). This list is denoted by the variable HISTORY. In this way, two processes that propose in the same round different values will eventually have different HISTORY variables. Note that, although the space required by the variables may be unbounded, in every round they require only finite space. Thus, if we could ensure that eventually all processes that propose have in every round the same history (and at least one process proposes infinitely often), then the proposal values sent are indistinguishable from the proposal values of a single "classical" leader.

However, the history of a process permanently grows. Therefore, every process includes its current history in every message it broadcasts. Furthermore, it maintains a counter C for every history it has yet heard of (in such a way that no memory is allocated for histories it has not yet heard of). Then, it compares the histories it receives with the ones it has received in previous rounds. If some old history is a prefix of a new history, it assigns the counter of the new history the value of the counter of the old one, increased by one. Thus, the counter of a history that corresponds to an eventual source is eventually increased in every round.

In this way, it is possible to ensure that eventually only eventual sources that converge to the same infinite history consider itself as leader. In a classical approach, eventually only these leaders would propose values. But to meet our safety requirements, it is crucial to ensure that all processes propose in every round at least something to make sure that the value of the current source is received by everybody. Therefore, we let processes that do not consider itself as a leader propose the special value ⊥.

Analysis

Similarly to Section 3, for every variable VAR i , VAR k i is the value of this variable after process p i has executed Line 9 in round k. Definition 1. We say, that p i has heard of p j 's round k message (m k j ), if p i has received m k j in round k, or if there exists another process p l such that p i has heard of p l 's round k ′ message for some k ′ > k and p l has heard of p j 's round k message. Let process p s be an eventual source. We then identify three groups of processes:

out-connected: The processes, the eventual source p s has infinitely often heard of.

⋄-silent:

The processes that are not out-connected.

⋄-proposer:

The out-connected processes that have eventually in every round timely links towards all other out-connected processes.2 leader:

We say that a process p i is a leader in some round k

(p i ∈ leader(k)), iff ∀H, C k i [HISTORY k i ] ≥ C k i [H].
If process p i is eventually a leader forever, i.e. there exists a k, such that for all k ′ ≥ k, p i ∈ leader(k ′ ), then we simply write that p i ∈ leader. Note that it may be possible that there are several processes in leader. The sets relate to each other in the following way:

{p s } ⊆ ⋄-proposer ⊆ out-connected ⊆ correct and ⋄-silent ∩ out-connected = ∅
We will later show that leader ⊆ ⋄-proposer (Lemma 6). Lemma 3. Eventually, in every odd round k, for every ⋄-proposer p i , the set PROPOSED in m k i is a subset of the set WRITTEN at all out-connected processes in round k + 1. More formally:

∃k, ∀k ′ ≥ k with k ′ mod 2 = 1, ∀p i ∈ ⋄-proposer, ∀p j ∈ out-connected : m k ′ i = PROPOSED, -, - → PROPOSED ⊆ WRITTEN k ′ +1 j
Proof: Follows directly from the definition of ⋄proposers and the fact that out-connected processes eventually do not receive any timely messages from ⋄-silent processes. Lemma 4. Eventually, at all out-connected processes, the counters that correspond to histories of ⋄-proposers increase in every round by one. More formally:

∃k, ∀k ′ ≥ k, ∀p i ∈ ⋄-proposer, ∀p j ∈ out-connected, C k ′ +1 j [HISTORY k ′ +1 i ] = C k ′ j [HISTORY k ′ i ] + 1
Proof: Assume a time when the system has stabilized. This means, that all ⋄-proposers send timely messages to all out-connected processes in every round and no out-connected process receives timely messages from ⋄-silent processes. Then, let k be the number of the current round and for every ⋄-proposer p i let p j be an out-connected process, such that the counter C k j [HISTORY k i ] is minimal among all out-connected processes in round k. Then, the counter for p i 's history at p j will never decrease, because p j will never receive a message with a lower counter from any other process.

Since p i is a ⋄-proposer, the counter for p i 's history will increase by one at p j in every round. For every other out-connected process, since it receives also a message from p i in every round and it can only finitely often receive a lower counter corresponding to p i 's history (the lowest one is p j 's), the counter of p i 's history eventually increases in every round by one. Lemma 5. If a history of a process p j infinitely often corresponds to a maximal counter at a ⋄-proposer p i , then p j is a leader forever. More formally:

∀p i ∈ ⋄-proposer, ∀p j ∈ Π : (∀k, ∃k ′ > k, ∀h, (C k ′ i [HISTORY k ′ j ] ≥ C k ′ i [h])) → p j ∈ leader
Proof: We first show that p j ∈ ⋄-proposer. Assume that it is not. Since p i ∈ ⋄-proposer, eventually the counter that corresponds to p i 's history is increased by one at every out-connected process (Lemma 4). Since p j ∈ ⋄-proposer, some out-connected process p l does not receive m k j in round k for infinitely many rounds k. Therefore, the counter at p l that corresponds to p j 's history is not increased by one in these rounds and is eventually strictly lower than the one that corresponds to p i 's history. Since every time some out-connected process has a lower counter than the others, eventually this counter propagates to all other out-connected processes, p i 's history will eventually be higher than p j 's at all out-connected processes. A contradiction.

If p i and p j are both ⋄-proposers, then eventually they receive their messages timely in every round k. Since p j 's history increases at all out-connected processes by one (Lemma 4), eventually

C k j [HISTORY k j ] = C k i [HISTORY k j ]
. Since by our assumption, in some future round k ′ , p j 's history is maximal at p i and a counter can increase by at most one and the counters that correspond to p j 's history increase always by one (Lemma 4), C k j [HISTORY k j ] is maximal forever and therefore p j is a leader forever. Lemma 6. Eventually, there exists a process p i ∈ leader and every leader is a ⋄-proposer. More formally:

∃k, ∃p i ∈ Π, ∀k ′ ≥ k : p i ∈ leader(k ′ ) (1) and ∀p i ∈ Π : (∀k, ∃k ′ , k ′ > k, p i ∈ leader(k ′ )) → p i ∈ ⋄-proposer (2)
Proof: The eventual source p s is a ⋄-proposer. Therefore, there exists at least one ⋄-proposer. Either p s is also a leader forever, or there is another process whose history infinitely often corresponds to a higher counter at p s than p s 's history. Then, with Lemma 5 this process is a leader forever. This implies [START_REF] Aguilera | On implementing omega with weak reliability and synchrony assumptions[END_REF].

Assume a process p i is not a ⋄-proposer. Then, p i 's counter is increased by less than one in infinitely many rounds at some processes. Because eventually these counters propagate to all out-connected processes and the values of ⋄-proposers are increased in every round by at least one (Lemma 4), eventually the history of some ⋄-proposer is higher than that of p i . Therefore, p i cannot be a leader forever. This implies (2).

Lemma 7.

If no process has decided yet, then eventually only values of leaders and ⊥ get into a set WRITTEN anywhere. More formally: ∃k, ∀k ′ ≥ k, ∀p i ∈ Π :

WRITTEN k ′ i ⊆ ∪ pj ∈leader(k ′ ) VAL k ′ j ∪ {⊥}
Proof: There is a time after which there exists at least one leader and all leaders are ⋄-proposers (Lemma 6) and since leaders propose their values always, all their values get into every set WRITTEN at all out-connected processes in every even round (Lemma 3).

Therefore, every set PROPOSED contains a value of a leader (compare Lemma 1) and no process that considers itself not as leader and has a value different from a leader will evaluate line 15 to true and add a different value to its set PROPOSED.

Theorem 2. Algorithm 3 implements consensus in ESS.

Proof: We have to prove the 3 properties of consensus. Validity is clear, since VAL is always an initial value.

To prove termination, assume there exists a run where no process ever decides. Then, eventually only non-⊥ values of leaders will get into a set WRITTEN anywhere (Lemma 7) and they will get into WRITTEN always in every even round (Lemma 3) and all out-connected processes select the same value (the maximum in Line 14). Therefore, only this value and ⊥ will be written in subsequent rounds and every out-connected process will select this value as value for PROPOSED in Line 16 (i.e., no out-connected process will select ⊥) and everybody will evaluate Line 11 to true in the next round. Therefore, eventually, every correct process will decide.

To prove agreement, assume p i is the first process that decides a value v in a round k. This means, that p i has evaluated Line 11 to true. Then, as PROPOSED ⊆ {v, ⊥}, no other value different from ⊥ is in a set WRITTEN anywhere in the system (compare Lemma 1) and v is in WRITTEN at every process in the system in round k, since it is also in WRITTENOLD (compare Lemma 2). Therefore, every other process decides v in the same round, or it will evaluate Line 13 to true and select v as new VAL and no other value different from ⊥ will ever get into PROPOSED anywhere in the system and therefore, no other value will ever be selected as VAL.

Weak-Sets

The weak-set data structure has been introduced by Delporte-Gallet and Fauconnier in [START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF].

A weak-set S is a shared data structure that contains a set of values. It is defined by two operations: the add S (v) operation to add a value v to the set and the get S operation which returns a subset of the values contained in the weakset. Note that we do not consider operations to remove values from the set. Every get S operation returns all values v where the corresponding add S (v) operation has completed before the beginning of the get S operation. Furthermore, no value v ′ where no add S (v ′ ) has started before the termination of the get S operation is returned. For add S operations concurrent with the get S operation, it may or may not return the values. Therefore, weak-sets are not necessarily linearizable3 .

Weak-Sets and registers

A weak-set is clearly stronger than a (regular) register: Proposition 1. A weak-set implements a (regular) multiplewriter multiple-reader register.

Proof: To write a value, every process reads the weakset and stores the content in a variable HISTORY. Then, every process adds the value to be written together with HISTORY to the weak-set.

To read a value, a process reads the weak-set and returns the highest value among all values accompanied by a HISTORY with maximal length.

This transformation satisfies the two properties of regular registers, namely termination and validity. Termination follows directly from the termination property of weak-sets.

If several processes write at the same time, two reads at two different processes may return different values, but after

Algorithm 2 :

 2 A consensus algorithm in ES for process p i . on initialization do VAL := initial value; WRITTEN := WRITTENOLD := PROPOSED := ∅; return PROPOSED;

then decide VAL; halt 10 else

 10 if (WRITTEN = ∅) then 11 VAL := max(WRITTEN); 12 PROPOSED := {VAL}; 13 WRITTENOLD := WRITTEN; 14 return PROPOSED; 15

Algorithm 3 : 2 WRITTEN 6 PROPOSED 8 ∀m∈

 3268 The consensus algorithm in ESS for process p i . on initialization do 1 VAL := initial value; ∀H, C[H] := 0; HISTORY := VAL; := WRITTENOLD := PROPOSED := ∅; 3 return m = PROPOSED, HISTORY, C ; 4 on compute(ki, Mi) do 5 WRITTEN := T m∈M i [k i ] m.PROPOSED; := ( S m∈M i [k i ] m.PROPOSED) ∪ PROPOSED; 7 ∀H, C[H] := min m∈M i [k i ] (m.C[H]); Mi[ki], C[m.HISTORY] := 1 + 9 max{ C[H] | H is a prefix of m.HISTORY}; if (ki mod 2 = 0) then if (WRITTENOLD = {VAL}) ∧ (PROPOSED ⊆ {VAL, ⊥}) then decide VAL; halt; else if (WRITTEN \ {⊥} = ∅) then VAL := max(WRITTEN \ {⊥}); if (∀H, C[HISTORY] ≥ C[H])∨(PROPOSED ⊆ {VAL, ⊥}) then PROPOSED := {VAL}; else PROPOSED := {⊥}; WRITTENOLD := WRITTEN; WRITTEN := PROPOSED; append VAL to HISTORY; return m = PROPOSED, HISTORY, C ;

For obstruction-free consensus, termination is only guaranteed if a process can take enough steps without beeing interrupted by other processes.

• In the first one, which we call the moving-source (MS) environment, we assume that in every round k, there

Note that it is possible that the message an out-connected process actually has received is not the message that a ⋄-proposer has sent. It is sufficient if it receives an identical message from another process.

A weak object is linearizable (also called atomic) if all of its operations appear to take effect instantaneously[START_REF] Herlihy | Linearizable concurrent objects[END_REF].

all writes have completed, the return value will be the same at all processes. To see that also validity holds, consider the value returned by a read. If there is no concurrent write, then the value returned is the last value written (i.e. the maximal value of all values concurrently written).

In [START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF], a weak-set is implemented using (atomic) registers in the following two cases: Proposition 2. If the set of processes using the weak set is known (i.e. the IDs and the quantity), then weak-sets can be implemented with single-writer multiple-reader registers. Proposition 3. If the set of possible values for the weak set is finite, then weak-sets can be implemented with multiplewriter multiple-reader registers.

Weak-Sets and the MS environment

Algorithm 4 shows how to implement a weak-set in the MS environment. Similarly to Section 3, for every variable VAR i , VAR k i is the value of this variable after process p i has executed Line 15 in round k (i.e. after compute is called with parameter k).

if (VAL ∈ WRITTEN) then BLOCK := false; return PROPOSED; Lemma 8. If for some p i , v ∈ WRITTEN k i , then every process p j that enters round k has v ∈ PROPOSED k j . Proof: The proof is analogous to Lemma 1.

Lemma 9.

If some value is in WRITTEN at some process, then this value will be forever in PROPOSED at all processes.

Proof: Since it is never a value removed from any set PROPOSED, this follows immediately from Lemma 8.

Theorem 3. Algorithm 4 implements a weak-set. Proof: We have to show that all operations terminate at all correct processes and that every get operation returns all values which have been added before.

The only position where an operation may be blocked is in Line 11. But since eventually all messages will be received by all correct processes, every value will eventually be in every set PROPOSED and therefore eventually be in every set WRITTEN. Thus, no correct process will block in Line 11 forever.

To show that every get operation returns all values which have been added before, see that an add(v) operation only terminates if v is in WRITTEN at some process. Together with Lemma 9, this means that this value will be returned by every process in Line 6.

Emulation of the MS environment with weaksets

Algorithm 5 emulates the MS environment using a weakset S and the corresponding add S and get S methods.

As a weak-set is implementable by only using registers (see Proposition 2) and the FLP impossibility result [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF] states that consensus is not implementable using only registers, this implies, that it is not possible to implement consensus in the MS environment (without any additional assumptions like in ES). Proof: Clearly, eventually all messages get delivered and all correct processes execute an infinite number of rounds.

It remains to show, that in every round k, there exists a process s k such that for every process p i at which end-of-round i occurs in round k, p i receives the round k message of s k in round k.

Let p i be the first process that finishes to add the value of a round k. If several processes finish to add their values at exactly the same time, choose one.

Claim: Every process at which end-of-round is triggered in round k has received p i 's round k value.

The proof is by contradiction. Assume that a process p j triggers end-of-round in round k without having received p i 's round k value. By the definition of a weak-set, this means that p j 's get S begun before p i 's add S was completed. But a process will only start a get S after it has finished to add its own value. A contradiction to the fact that p i was the first process that has completed its add S .

The MS-environment and the Σ failure detector

The quorum failure detector Σ [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF] outputs lists of IDs of trusted processes (i.e. it is not well-defined in our anonymous model) and it satisfies the following properties: Intersection: Given any two lists of trusted processes, possibly at different times and by different processes, at least one process belongs to both lists. Completeness: Eventually at all correct processes, every trusted process is correct.

Σ has been shown to be the weakest failure detector to emulate registers in totally asynchronous message-passing systems [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF] (with known IDs). This means, that Σ is sufficient to emulate registers in such systems and with any failure detector which is also sufficient to implement registers in such a system, it is possible to emulate Σ. Interestingly, although it is possible to implement a register in the MS environment (via weak-sets), we show that even if we assume that the number of processes and their IDs are known, it is not possible to emulate Σ. Note that this is no contradiction, since in our model no failure detector is necessary for the emulation. Proposition 4. It is not possible to emulate Σ in the MSenvironment, even if the number of processes and their IDs are known.

Proof: Assume there exists such an algorithm and consider a run r 1 where process p 1 is the only correct process, p 1 is always the source, and p 1 receives no messages from other processes. Then, by the completeness property of Σ, there exists some time t after which the output of Σ is {p 1 }.

Similarly, consider a run r 2 where process p 2 is the only correct process and p 1 crashes after time t. Again, p 1 is the source until time t and receives no messages from other processes (this is possible, since the messages from p 2 may be arbitrary delayed). For p 1 , run r 1 and r 2 are indistinguishable up to time t and consequently the Σ at p 1 will output {p 1 } at p 1 at time t. But since eventually, the output at p 2 has to be {p 2 } forever, this contradicts to the intersection property of Σ.

Conclusions

This paper has provided algorithms to emulate registers and solve consensus under different synchrony assumptions in unknown and anonymous message-passing networks that suffer from crash-failures. One of these algorithms uses a novel pseudo leader election primitive.

Furthermore, we have shown that the MS environment (i.e. a system with a moving timely source) is equivalent to weak-sets, a generalization of registers for unknown and anonymous systems. In some sense, this indicates that the synchrony assumptions in this environment are necessary to implement basic safety primitives.

Additionally, we have shown that in the MS environment, it is not possible to emulate Σ, the weakest failure detector to emulate registers [START_REF] Delporte-Gallet | Shared Memory vs Message Passing[END_REF], even if we assume the existence of IDs and a bound on the number of processes. To the best of our knowledge, we found for the first time a partially synchronous environment in which registers are implementable and Σ is not.