O Bonnefoy
email: olivier.bonnefoy@emse.fr

F Gruy

J.-M Herri

A-priori calculation of the refractive index of some simple gas hydrates of structures I and II

Keywords: Clathrate gas hydrate, Index of refraction, Optical properties, Dielectric properties, Lorenz-Lorentz model, Light scattering

This work aims at providing theoretical values of the refractive index of some gas hydrates using up-to-date physical data. Indices of refraction have been computed with a modified Lorenz-Lorentz model for a pressure between 2 and 15 MPa, a temperature between 0 and 12 °C and wavelengths in the extended visible domain. Given the prohibitive time required to perform the calculations with the standard procedure (up to 20 min for one P -T -λ set), we considered separately the crystalline structure and the molecules that occupy its sites. Thus, we obtain a series of tensors, characterising the sole structure, that we can easily use to get the refractive indices within less than 1 s. In this paper, all data are given to calculate the absolute or relative refractive index of any gas hydrate, provided the host gas polarisability is known. The numerical results are in agreement with experimental data.

Introduction

Literature is abundant on gas hydrates, which give rise to a growing attention. The novice can safely refer to Sloan's book [START_REF] Sloan | Clathrate Hydrates of Natural Gases[END_REF] for a detailed presentation of these crystals. Among the industrial contexts where they appear, we shall cite : hydrate plugs obstructing oilor gas-pipelines, energy resources in form of methane hydrates trapped in permafrost or sub-marine sediments, natural gas transport in form of a slurry or gas separation by fractionnated crystallisation. The intelligent exploitation of hydrates in these contexts require a considerable amount of scientific data and the research efforts of many nations (United States, Russia, France, Germany, Great Britain, Japan and China, to cite the most active ones) greatly contribute to this goal. From this perspective, it seems to us that the knowledge of hydrates dielectric properties is a valuable tool, in particular for those who wish to measure the particle size distribution of hydrates in suspension via diffusion methods. Here, we need to cite the works of Melnikov et al. [START_REF] Melnikov | Proc. 4th Int. Conf. on Gas Hydrates[END_REF] and, previously, of Bylov and Rasmussen [START_REF] Bylov | [END_REF]. The structure of this document is following. We first develop the calculation method. The index of refraction is the convergence point of a macroscopic approach in terms of field and of a microscopic approach in terms of crystalline structure. We then present the experimental data we used to perform the calculations and, eventually the numerical results (absolute and relative refractive indices). Finally, we study the sensibility of the results and compare with experimental data available in the literature.

Calculation method

We will successively use two approaches to express the polarisation P as a function of the field E. The first approach is macroscopic and utilizes the dielectric permittivity [ǫ] whereas the second one is microscopic. She utilizes the crystal molecular structure and superposition principle. This method is presented in numerous reference books (see, for instance, Durand [START_REF] Durand | Electrostatique et Magnétostatique[END_REF] or Ashcroft and Mermin [START_REF] Ashcroft | Solid State Physics[END_REF]) and was first applied to hydrates by Herri and Gruy [START_REF] Herri | [END_REF]. The comparison of the two relationships that we will get provides a mean to express the dielectric permittivity as a function of the crystal structure.

Macroscopic approach

When we apply an electric field EA to a dielectric medium, this field creates a polarisation P which, in turn, produces a depolarising field E dep opposed to the applied field EA. The total field E in the dielectric medium is the sum of the two fields :

E = EA + E dep (1)
The dielectric permittivity (or dielectric constant) may be defined by the following relationship between polarisation and electric field :

P = [ǫ] -I 4π E (2)
2.2. Microscopic approach 2.2.1. Expression of the local field At a given time, the macroscopic field E at position r is the spatial average of E micro r on a sphere of radius r0, centered around r, and such that r0 is small compared to the macroscopic length scale and big compared to characteristic atomic dimensions (intermolecular distances). The local field E loc r at r is the existing field at r if we remove the atome at this place. To calculate it, we decompose the space into two zones : one sphere B of radius r1 centered at r and the rest of the space B. We could have taken a cube but the subsequent calculations would have been more complicated. The radius r1 is small compared to the crystal size and big compared to r0. With this decomposition, we get :

E loc = E loc B + E loc B ( 3
)
Since r1 is big compared to r0, E loc B may be approximated by the average of the microscopic electric field existing out of the sphere B, i.e., by the macroscopic field E macro B . Moreover, the macroscopic field E may be decomposed in :

E = E macro B + E macro B
where E macro B is the macroscopic field that would exist if there were only the charges in B (included the atom at r). Thus, Eq. (3) becomes :

E loc = (E -E macro B ) + E loc B
Given the previous decomposition of the macroscopic field E, we finally get :

E loc = EA + E dep -E macro B + E loc B 2.2.

Geometrical simplifications

The hydrate particle is spherical, as well as the cavity that we have diged around the point. This is for sure an advantage since the field in a uniformly polarised sphere does not depend on its diameter and equals the Lorentz field. We can deduce that :

E macro B = E dep = -4π 3 P (4)
Thanks to this relationship, the equation of the local field can be simplifed in :

E loc = EA + E loc B (5)

Calculation of the field E loc

B

The methane hydrate structure is such that water molecules are located on three types of cristallographic sites and gas molecules on two types of cristallographic sites. We now study the case where the center of the sphere B is a site of type k. For clear understanding, we replace the notation E loc B by E loc B k . The field E loc B k is the electric field created by the presence of water and gas molecules in the sphere B. We group together the contributions of molecules placed on a same type of site i.

E loc B k = 5 i=1 Zi = 5 i=1 j∈B E k,j(i)
where Zi is the sum of the fields E k,j(i) created by the molecules j(i) located on a site of type i. The electric field created on a site k by a dipole-molecule j located on a site i is2 :

E k,j(i) = 3 (p i r kj ) r kj -r kj 2 p i r kj 5 with r kj = --→ KJ = -→ OJ - --→ OK.
To go further, we express the dipole moment of a molecule j located on a site of type i with its total polarisability αi and the local field

E loc i that acts on it : p i = αi.E loc i . Consequently, we get E loc Bk = 5 i=1 j∈B αi 3 E loc i r kj r kj -r kj 2 E loc i r kj 5
Coming back to Eq. ( 5), we have

E loc k = EA + E loc Bk .
In form of matrices, we have :

E loc k = EA + 5 i=1 αi [W ki ] E loc i ( 6
)
where

W k,i,q,qq = j∈B 3KJqq KJq - --→ KJ 2 δq,qq --→ KJ 5
Through Eq. ( 6), we see that the local field E loc k depends on the four other local fields E loc i and on EA. We solve numerically this system of five equations and five unknowns and we obtain the five following equalities, for k ∈ {1, ..., 5} :

E loc k = [γ k ] EA (7)
With the assumption of linearity with respect to polarisabilities, we decompose the tensors [γ k ] in a sum of terms where the crystalline structure and the polarisability of its constituting molecules are dissociated :

[γ k ] = I + 5 i=1 αi [T ki ] (8)

Calculation of the matrices [T ]

To calculate each of the matrices [T ki ], we will study the five particular cases where all polarisabilities are equal to zero excepted the polarisability of the component located on sites i : αi = 1. Then, we will proceed in two steps. We will first calculate the tensor [Tii] and second, use it to deduce the four other tensors [T ki ] (k ∈ {1 . . . 5}-{i}). Henceforth, we omit the exponent "loc" in the writing of the field E loc k . Calculation of [Tii]. Equation [START_REF] Herri | [END_REF] written for k = i leads to 3 :

Ei = EA + [Wii] Ei
In our case, Eq. ( 8) becomes [γ k ] = I + [Tii], so Eq. ( 7) turns into Ei = (I + Tii) EA 3 In the particular case of hydrate of structure I, the sites k =4, occupied by the gas molecules in the small cavities, form a cubic lattice. For this reason, in such site, the contribution to the local field of the molecules located on same sites is equal to zero and consequently the tensor also :

T 44 = [0].
If we compare this equation with the previous one, we have : 7) and ( 8) give

[Tii] = [I -Wii] -1 -I Calculation of [T ki ] for k = i. Equation (6) written for k = i leads to E k = EA + [W ki ] Ei = EA + [W ki ] (I + Tii) EA Equations (
E k = (I + T ki ) EA So, finally [T ki ] = [W ki ] [I -Wii] -1

Polarisation

The polarisation P of the dielectric material can be calculated as a function of the dipole moments p k of the molecules located on sites k and their respective volume concentration N k :

P = 5 k=1 N k p k 5 k=1 N k α k E loc k = 5 k=1 N k α k [γ k ] EA = [S] EA
where the agregate [S] is a tensor defined by

[S] = 5 k=1 N k α k [γ k ]
Moreover, the combination of Eqs. ( 1) and ( 4) leads to

EA = E + 4π 3 P
From this, we extract P and express it as a function of E :

P = I - 4π 3 [S]
-1

[S] E (9)

2.2.6. Link between the two approaches Comparing Eqs. ( 2) and ( 9), we find the equality

[ǫ] -I 4π = I - 4π 3 [S] -1 [S]
which leads to the final expression of the relative dielectric permittivity :

[ǫr] = I + 4π I - 4 π 3 [S ] -1 [S ]
To sum up, we need first to calculate the matrices [W ki ] and deduce from that the matrices [T ki ]. Then, we build the tensors [γ k ] and the agregate [S]. Then it is easy to compute the dielectric permittivity tensor [ǫr] and extract from it the absolute refractive index of the hydrate. 3

Calculation of the index of refraction

The tensor [ǫr] has three eigenvalues : ǫ1, ǫ2 and ǫ3. The main indices of refraction are then n1, n2 and n3 so that : n 2 i = ǫi for i ∈ {1, 2, 3}. Let us consider an electric displacment in the direction of the unit vector

u =      u1 u2 u3      . We have the equality u 2 1 + u 2 2 + u 2 3 = 1.
Given the random crystal orientation, we have

u 2 1 = u 2 2 = u 2 3 .
The ellipsoïd of polarisability is :

u 2 1 n 2 1 + u 2 2 n 2 2 + u 2 3 n 2 3 = 1 n 2
Consequently, the index of refraction n can be written

n = 3 n -2 1 + n -2 2 + n -2 3
So, the relative index of refraction m is equal to :

m = n nwater = 3n -2 water n -2 1 + n -2 2 + n -2 3

Numerical data

As will show the sensitivity study, special emphasis must be given to the precision of experimental data involved in the calculation of the relative index of refraction of the crystal.

Description of the crystal

The nature and, above all, the volume of the gas molecules trapped in the hydrate determine its crystalline structure. In the pressure and temperature conditions of our good old earth, there are two cubic crystalline forms, both composed of a juxtaposition of two kinds of cavities. These rigid cages are made out of water molecules and can contain a gas molecule in a state similar to gaseous state. The description of the crystalline structure that we have used was established by Stackelberg and Müller [7]. The unit cell 4 of the crystal of structure sI (group Pm3n) consists of 2 small cages 5 12 and 6 big cages 5 12 6 2 , whereas the unit cell for structure sII (group Fd3m) consists of 16 small cages 5 12 and 8 big cages 5 12 6 4 . In this article, we study hydrates of CH4, C2H6, CO2, H2S, C3H8 and N2. The four first gases form hydrates of structure sI and the two latter hydrates of structure sII. 4 A cage a b is a cage composed of b faces with a sides each.

Non-stoechiometry of hydrates

If all cages were filled with a gas molecule, the structure sI hydrate formula would be (H2O)46 • (gas)8 and the structure sII hydrate formula would be (H2O)136 • (gas)24. In fact, the occupancy rate θ k of a cage of type k depends on pressure and temperature and is inferior to 100 %. Adsorption theory, developped by Langmuir, leads to

θ k = C k f 1 + C k f
where C k is a constant and f is the fugacity of the fluid phase in equilibrium with the hydrate. The two Langmuir constants C1 and C2 are linked to the intermolecular forces in the crystalline lattice and can be calculated theoretically using Van der Waals and Platteeuw [8] model with the Kihara potential. However, given the low sensibility of the final result towards this parameter, we will use the empirical correlation proposed by Parrish and Prausnitz [9]

C k = A k T . exp B k T
Table 1 gives the constants A k and B k for the different gases studied. Numerically, in the range 270-300 K, the constants C1 and C2 take values between 0.05 and 70. If the fugacity varies between 2 and 20 MPa, it means that the cages occupancy rates will be between 50 and 100 %. It is a very broad range that we could tighten considering the thermodynamical stability of partially filled cages, but that represents a safe basis for the sensibility analysis. The fugacity f of the fluid phase, described by a Soave-Redlich-Kwong-type equation of state, is computed with the compressibility Z of the considered gas :

ln f P = Z -1 -ln(Z -B) + A B ln Z Z + B
The compressibility Z is solution of the cubic equation

Z 3 -Z 2 + (A -B 2 -B)Z -AB = 0
where T is the absolute temperature and R = 8.314 J.K -1 .mol -1 is the universal gas constant. The constants A and B are defined by A = aP /R 2 T 2 and B = bP /RT where a and b are functions of the critical temperature Tc and the critical pressure Pc of the considered gas : a = 0.42748

R 2 T 2 c Pc 1 + K 1 - T Tc 2 and b = 0.08664 RTc
Pc with K function of the acentric factor ω : K = 0.480 + 1.875ω -0.176ω 2 . The numerical data for the gases studied in this article are given in Table 2.

Polarisabilities

The most relevant experimental situation is represented by hydrates particles in liquid water. Consequently, we are dealing with three types of molecules : -The host gas trapped in the cavities. Given that all movements are authorised (with the only exception of the translation), its polarisability is taken equal to that of the free gas under atmospheric pressure and at 0 °C. -The liquid water were the hydrate particles are immersed. -The H2O molecules that consitute the cavities.

Given that the hydrogen bonds that rigidify them, we consider that their volume polarisability is equal to that of the ice at hydrate pressure and temperature. In what follows, we will study the polarisabilities for these three cases. The polarisability depends on the wavelength but also on the pressure and temperature.

Gas polarisability

The gas polarisability α depends on the wavelength in a complex manner. However, the range of interest is quite narrow (250-750 nm) and a polynomial interpolation is sufficient. So we take the relationship

α = β0 + β1 λ + β2 λ 2 + β3 λ 3
where the constants βi depend on the considered gas, as indicated in Table 3. The unit of the constants βi is such that, if the wavelength is expressed in nm, then the polarisability α is expressed in Å3 . Numerically, between 200 and 800 nm, the polarisability decreases with the wavelength and ranges between 1 and 10 Å3 for the considered gases. These data come from Landolt-Börnstein's data tables [START_REF] Landolt-Börnstein | Zahlenwerte und Funktionen aus Physik[END_REF], where we find, as a function of the wavelength λ, the index of refraction n of the pure gas. The polarisability α is then deduced with the Lorenz-Lorentz formula :

n 2 -1 n 2 + 2 = 4παN 3
where N , the number of molecules per unit of volume, is

N = NA n V = NA P RT
where P is the pressure and NA = 6.023 × 10 23 mol -1 the constant of Avogadro. This formula is valid if we consider that the perfect gas law correctly describes the gas behaviour in the (P, T ) conditions, where indices are experimentally measured. We consider it is true since the pressure is 1 atm and the temperature is 0 °C. In this case, the numerical value of N does not depend on the gas and we have N = 2.687 × 10 25 . The relative deviation between the polarisability value interpolated by the polynom and the value deduced from the experimental values of the index of refraction is below 0.3 %, with the exception of H2S where it is 2.4 %.

Solid water polarisability

The polarisability of the water molecules that consitute the hydrate cages is approximated by the polarisability of water molecules in ice. To justify this assumption, we use the fact that the hydrate crystalline structure is very close from the ice structure and that water is the main component of those two crystals. We use data given by Herri and Gruy [START_REF] Herri | [END_REF] :

α = a + b λ 2 + c λ 3
where λ is expressed in nm and α in 10 -30 m 3 . Here, we use data from the International Association for the Properties of Water and Steam [START_REF]International Association for the Properties of Water and Steam, Release on the Refractive index of Ordinary Water Substance as a Function of Wavelength, Temperature and Pressure[END_REF] which very precisely evaluate the density and refractive index as a function of pressure, temperature and wavelength

n 2 -1 n 2 + 2 . 1 ρ = a0 + a1 ρ + a2 T + a3 λ2 T + a4 λ2 + a5 λ2 -λ2 UV + a6 λ2 -λ2 IR + a7 ρ2
where T = T /T * , ρ = ρ/ρ * and λ = λ/λ * . Numerical values for the coefficients are given in Table 5. Besides, we have T * =273.15 K, ρ * =1000 kg•m -3 and λ * =0.589 µm.

Results

The calculation method explained above has been encoded in Matlab5 and provides the structure matrices T ki . Then we apply these results to methane hydrate and a value of 1.346 is found for a pressure of 11 MPa, a temperature of 1 °C and a wavelength of 750 nm. This result is in full agreement with experimental results of Bylov and Rasmussen [START_REF] Bylov | [END_REF]. The appendix contains the coefficients of the T ki matrices for hydrates of structures sI and sII. Table 6 shows the quantity m -1 for methane hydrate (of structure sI) and a wavelength of 350 nm. It is a function of the pressure and the temperature and it is a key data for light scattering measurements. In Table 7, we can read the quantity m -1 for methane hydrate for different pressures and wavelengths. The temperature is set to 1°C. Table 8 shows the influence of the gas. We can see that for N2, the hydrate index of refraction is lower than the liquid water refractive index. In comparison, H2S hydrates are easier to detect via light scattering than CH4 hydrates.

Sensitivity analysis

A study of sensitivity makes it possible to better appreciate the result precision. The relative index of refraction h = m -1 and the absolute index of refraction n depend on the parameters G, which are affected by an imprecision ∆G and each contribute to the imprecision ∆h and ∆n of the final results. Table 9 shows the relative influence of the differents parameters through the sensitivity coefficient σ defined by the relationships Comments. Concerning the absolute index of refraction, the most important parameters are the polarisabilities of the water consituting the hydrate cages and of the gas as well as the occupancy rate of the cavities. Concerning the relative index of refraction (with liquid water as reference), the most important parameter is by far the liquid water index of refraction. An error of 1 % in its estimation leads to an error of 95 % on m -1 ! This is a justification a posteriori of the special emphasis that we have brought to use precise experimental data. Then, the four same parameters come in order.

  Numerical values are calculated with methane as host gas and for variations around the point (P =11 MPa, T =1 °C, λ=750 nm).

Table 2

 2

	Parameters to calculate the gas fugacity
	Gas Pc (MPa) Tc (K) ω (-)
	CH 4	4.54	190.6 0.008
	C 2 H 6	4.82	305.4 0.098
	CO 2	7.28	304.2 0.225
	H 2 S	8.82	373.2 0.100
	C 3 H 8	4.19	369.8 0.152
	N 2	3.35	126.2 0.040

Table 3

 3 Parameters to calculate the gas polarisability

	Gas	β 0	β 1	β 2	β 3
	CH 4 2.511837 6.289468E1 -8.709333E3 4.768704E6
	C 2 H 6 4.354728 1.197474E2 -1.992029E4 9.112365E6
	CO 2 2.578497 4.457932E1 -3.189352E3 3.173479E6
	H 2 S 2.610619 1.473791E3 -6.055990E5 9.286059E7
	C 3 H 8 6.234656 1.648687E2 -2.759611E4 1.354185E7
	N 2 1.673443 7.525817E1 -1.750347E4 3.387202E6

  Polarisability of liquid waterA great precision is required in the calculation of the liquid water refractive index since the relative hydrate index of refraction is very sensitive to this latter.

	3.3.3.
	Table 4
	Parameters to calculate the solid water polarisability
	a	b	c
	1.4447 17953 -1609200

Table 5

 5 Parameters to calculate the liquid water index of refraction

	a 0 =0.244257733	a 4 =1.58920570E-3
	a 1 =9.74634476E-3 a 5 =2.45934259E-3
	a 2 =-3.73234996E-3 a 6 =0.900704920
	a 3 =2.68678472E-4 a 7 =-1.66626219E-2
	λUV =0.2292020	λIR =5.432937

Table 6 100

 6 * (m -1) values for CH 4 hydrate at λ = 350 nm. Pressure is in bar and temperature in °C

	P/T 0	3	6	9	12	15
	30 1.0034 0.9680 0.9330 0.8979 0.8625 0.8264
	50 1.0876 1.0659 1.0455 1.0260 1.0071 0.9882
	70 1.1104 1.0955 1.0823 1.0705 1.0597 1.0495
	90 1.1121 1.1013 1.0925 1.0854 1.0795 1.0747
	110 1.1041 1.0961 1.0904 1.0865 1.0841 1.0829
	130 1.0910 1.0852 1.0818 1.0803 1.0804 1.0819
	Table 7
	100 * (m -1) values for CH 4 hydrate at 1°C. Pressure is in
	bar and wavelength in nm
	P/λ 350	450	550	650	750
	30 0.9915 0.9881 0.9539 0.9358 0.9380
	50 1.0802 1.0745 1.0393 1.0205 1.0223
	70 1.1052 1.0990 1.0635 1.0446 1.0463
	90 1.1082 1.1020 1.0665 1.0476 1.0493
	110 1.1012 1.0952 1.0598 1.0410 1.0428
	130 1.0888 1.0832 1.0480 1.0293 1.0312
	Table 8
	100 * (m -1) values for different gas hydrates (at 1°C and
	350 nm)
	P/gas CH 4 CO 2 H 2 S	N 2
	30 0.9915 1.0533 4.6008 -0.8941
	50 1.0802 1.0673 4.5803 -0.6796
	70 1.1052 1.0527 4.5598 -0.5924
	90 1.1082 1.0377 4.5391 -0.5522
	110 1.1012 1.0221 4.5184 -0.5343
	130 1.0888 1.0062 4.4976 -0.5289

Table 9

 9 Influence of parameters' imprecision to the final result's imprecision

	Parameter	σn	σ h
	Pressure	0.0007 0.0575
	Temperature	0.0116 0.6233
	Wavelength	0.0100 0.0863
	Water polarisability in hydrate 0.2204 21.36
	Gas polarisability	0.0656 6.358
	Cage 1 occupancy rate	0.0160 1.554
	Cage 2 occupancy rate	0.0496 4.795
	Liquid water index of refraction 0	95.93
	Gas fugacity	0.0010 0.0959
	Langmuir constant A 1	0.0006 0.0575
	Langmuir constant B 1	0.0066 0.6425
	Langmuir constant A 2	0.0004 0.0384
	Langmuir constant B 2	0.0038 0.3740

Rigorously, we should utilize the index j(i) instead of i when we write p i and α i , because the dipole moment and the polarisability do not depend on the site i but on the molecule j that occupies it. However, in hydrate, each site is occupied by only one type of molecule and, to keep it easy to read, we will use the compact writing.

Available on simple request to olivier.bonnefoy@emse.fr

Appendix A : T ki matrices for structure sI hydrates


George Giakkoupis
email: george.giakkoupis@inria.fr

Maryam Helmi
email: mhelmikh@ucalgary.ca

Lisa Higham
email: higham@ucalgary.ca

Philipp Woelfel
email: woelfel@ucalgary.ca

Test-and-Set in Optimal Space

Keywords: E.1 [Data Structures]: Distributed data structures, D.1.3 [Concurrent Programming]: [Distributed Programming], F.1.2 [Modes of Computation]: [Parallelism and Concurrency], F.2 [Analysis of Algorithms and Problem Complexity]: General Shared Memory Model, Test-and-Set Algorithm, Space Complexity, Obstruction-free

, we also obtain a randomized wait-free testand-set algorithm from Θ(log n) registers, with expected step-complexity Θ(log * n) against the oblivious adversary. The core tool in our algorithm is the implementation of a deterministic obstruction-free sifter object, using only 6 registers. If k processes access a sifter, then when they have terminated, at least one and at most (2k + 1)/3 processes return "win" and all others return "lose".

INTRODUCTION

A test-and-set (TAS ) object is perhaps the simplest standard shared memory primitive that has no wait-free deterministic implementation from registers. A one-shot testand-set is a one-bit register, which is initially 0, and supports one operation, namely test&set(). A test&set() sets the bit's value to 1 and returns its previous value. The TAS problem is related to weak leader election, where participating processes elect a leader among themselves. The leader returns win, and all other participating processes return lose. (The term leader election is ambiguous. It is also used to denote the name consensus problem, where the losing processes need to output the ID of the winner. We add the qualifier "weak" in order to distinguish the two variants.)

Leader election and TAS are equally hard problems: A single test&set() call solves leader election (by replacing the return values 0 and 1 with win and lose, respectively). On the other hand, there is a wait-free linearizable test&set() implementation, where in addition to participating in a leader election, a process needs to perform only two steps on a single register [START_REF] Golab | An O(1) RMRs leader election algorithm[END_REF].

TAS objects have consensus number two. That is, they can be used together with registers to solve deterministic wait-free consensus only in systems with two processes. Despite that, TAS is a standard building block for shared memory algorithms that solve many classical problems, such as mutual exclusion and renaming [4-7, 9, 19, 20]. Since TAS objects are among the simplest synchronization primitives, they are well suited to investigate the difficulties arising in synchronization problems. Algorithms or impossibility results for TAS can provide insights into the complexity of other shared memory problems, and can contribute to solutions for them.

We consider a standard shared memory system in which n processes communicate through atomic read and write operations on shared registers. A common assumption is that each register can store Θ(log n) bits, although in some settings registers of unbounded size are assumed. The strongest reasonable progress condition is wait-freedom, which guarantees that every operation finishes in a finite number of the calling process's steps, independent of other processes. Since TAS has consensus number two, no deterministic wait-free TAS implementation from registers exists, even for 2 processes. A weaker progress condition, and the one most frequently used for analyzing space complexity, is obstructionfreedom [START_REF] Herlihy | Obstruction-free synchronization: Double-ended queues as an example[END_REF]. It guarantees that any process will finish its operation, provided the process takes sufficiently many steps on its own, without interference from other processes (i.e., if it runs solo). Any shared memory object has an obstructionfree implementation from n registers [START_REF] Herlihy | Wait-free synchronization[END_REF].

The randomized step complexity of TAS has been thoroughly investigated, with significant progress being made in recent years [START_REF] Afek | Wait-free test-and-set[END_REF][START_REF] Alistarh | Sub-logarithmic test-and-set against a weak adversary[END_REF][START_REF] Alistarh | Fast randomized test-and-set and renaming[END_REF][START_REF] Giakkoupis | A tight RMR lower bound for randomized mutual exclusion[END_REF][START_REF] Tromp | Randomized two-process wait-free test-and-set[END_REF]. In contrast, little was known about the space complexity of obstruction-free or randomized wait-free TAS. In 1989, Styer and Peterson [START_REF] Styer | Tight bounds for shared memory symmetric mutual exclusion problems[END_REF] studied the space complexity of the related mutual exclusion problem, under the deadlock-free progress requirement. As a special case they also considered a variant of deadlock-free weak leader election, where only the leader has to terminate. It suffices to add a single one-bit register to transform any such deadlock-free leader election protocol into a linearizable deadlock-free TAS. Styer and Peterson proved a space lower bound of log n + 1 registers, and provided an algorithm that established that this bound is tight. Hence, in the case of deadlock-freedom, Styer and Peterson's results answer the question of the space complexity of one-shot TAS precisely up to a single register.

Deadlock-freedom is a natural progress property for mutual exclusion related problems, where waiting for other processes is inherent in the problem specification. But for other problems, it is inappropriate because it does not preclude a single slow or failing process preventing all other processes from making progress. Alternative progress properties, such as obstruction-freedom, lock-freedom, or randomized wait-freedom, are more desirable for such problems. Research on the space complexity of shared memory problems has focused on the obstruction-free progress property [START_REF] Faith | Obstruction-free algorithms can be practically wait-free[END_REF][START_REF] Guerraoui | Toward a theory of transactional contention managers[END_REF][START_REF] Herlihy | Obstruction-free synchronization: Double-ended queues as an example[END_REF][START_REF] Jayanti | Time and space lower bounds for nonblocking implementations[END_REF]. However, despite significant research on TAS, until recently the space complexity of obstruction-free TAS implementations remained an unanswered question.

In 2012, Giakkoupis and Woelfel [START_REF] Giakkoupis | A tight RMR lower bound for randomized mutual exclusion[END_REF] used the same lower bound technique as that of Styer and Peterson to conclude that obstruction-free one-shot TAS requires log n -1 registers. In 2013 we devised a deterministic obstruction-free TAS algorithm using just Θ( √ n) registers, where the longest solo-run for any process to finish a test&set() method call comprises Θ( √ n) steps [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF]. We now present an asymptotically tight result.

Theorem 1. There is a deterministic obstruction-free implementation of a TAS object from Θ(log n) registers of size Θ(log n) bits, where any process finishes its test&set() method call in Θ(log n) solo steps.

In general, there are performance benefits if the solo run that is required for termination is short, because processes have a better chance of completing their TAS before they get interrupted. Our algorithm satisfies an even stronger property: A process needs to execute only a constant number of solo steps Θ(log n) times, to finish its test&set() method call.

Giakkoupis and Woelfel [START_REF] Giakkoupis | A tight RMR lower bound for randomized mutual exclusion[END_REF] presented a randomized TAS algorithm that has O(log * k) expected step complexity against the oblivious adversary, where k is the contention. The algorithm requires Θ(n) registers, but with high probability (w.h.p.) processes access only the first logarithmic number of them. In [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF] we also showed that any obstruction-free algorithm can be made randomized waitfree against the oblivious adversary, with a polynomial expected step complexity. A combination of two previous al-gorithms [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF][START_REF] Giakkoupis | A tight RMR lower bound for randomized mutual exclusion[END_REF] led to a randomized-wait free TAS implementation from Θ( √ n) registers, which has expected step complexity O(log * n). This approach, with some additional work, can be applied to our Θ(log n) space algorithm.

Theorem 2. There is a randomized TAS implementation from Θ(log n) registers of size Θ(log n) bits, such that for any fixed schedule (determined by an oblivious adversary), the maximum number of steps executed by any process is O(log * n) in expectation and O(log n) with high probability.

Recently, Aghazadeh and Woelfel [START_REF] Aghazadeh | Space-and time-efficient long-lived test-and-set[END_REF] gave a general transformation of any (one-shot) TAS object implemented from m b-bit registers into a long-lived one using O(m • n) registers of size max{b, log(n + m)} + O(1) bits. A reset() operation takes only constant time in the worst-case, and the step complexity of a test&set() operation of the longlived object is the same (up to a constant additive term) as the one of the one-shot TAS. Applying this to the construction described in the proof of Theorem 2, yields a long-lived TAS object implemented from O(n log n) registers, where the expected step complexity of the test&set() operation is O(log * n) and worst-case step complexity of the reset() operation is O(1). Previously, the best space bound for achieving similar step complexities for test&set() and reset() was O(n 3/2 ) registers, achieved by, again, combining previous results [START_REF] Aghazadeh | Space-and time-efficient long-lived test-and-set[END_REF][START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF]. The space lower bound for mutual exclusion [START_REF] Burns | Bounds on shared memory for mutual exclusion[END_REF] implies that any long-lived TAS implementation requires at least n registers.

MODEL AND TOOLS

Our model of computation is the standard asynchronous shared memory model where a set P of n processes with distinct identifiers communicate through a set of shared multireader multi-writer registers. Each register supports two atomic operations, read and write. To simplify our algorithm and proofs, we use a modified model that uses writes and scans where each scan returns the content of all registers instantaneously. This is not a loss of generality because, as proved in [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF], with one additional register, any system that supports scans and writes can be replaced with atomic multi-reader multi-writer registers. Theorem 3. [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF] An obstruction-free implementation of a scan() operation can be obtained by using one reserved register in addition to those that can be scanned.

Each process runs a program that can access the process's local registers as well as shared registers. A schedule is a sequence of process identifiers. A schedule, σ, gives rise to a sequence of operations, called an execution as follows. The i th operation in the execution is the next operation in the program of the i th process in σ. In our proofs, it suffices to consider just the shared memory operations in an execution. In an execution, process p is poised to write to register r, if it writes to register r in its next step. Equivalently, we say that p covers register r.

An algorithm is deterministic if each process's program is deterministic. A deterministic implementation of a method is wait-free if, from any point of an execution and for any process, the process completes its method call in a finite number of its own steps, regardless of the intervening steps taken by other processes. A deterministic implementation of a method is obstruction-free if, from any point of an execution and for any process p, p completes its method call in a finite number of its own steps, provided there are no intervening steps taken by other processes. In such an execution, we say that p runs solo during these uninterrupted steps by p.

The algorithm is randomized if some process's program is randomized. An implementation of a method is randomized wait-free if, from any point of an execution and for any process p, the number of steps by p required for p to complete its method call is finite in expectation, regardless of the intervening steps taken by other processes [START_REF] Herlihy | Wait-free synchronization[END_REF].

A test-and-set (TAS ) object stores one bit, which is initially 0, and supports a test&set() operation that sets the bit's value to 1 and returns its previous value. A TAS object trivially provides a solution to weak leader election, where each participating process has to decide on one value, win or lose. Among all processes that finish their leader election protocol, at most one process is allowed to win, and not all processes may lose. Hence, if all processes finish, then exactly one process, the leader, wins. Weak leader election and test-and-set are equally hard problems: Replacing the return values 0 and 1 of a test&set() operation with win and lose, respectively, yields a weak leader election protocol. On the other hand, Golab, Hendler and Woelfel gave an implementation of a TAS object using weak leader election and one additional register [START_REF] Golab | An O(1) RMRs leader election algorithm[END_REF]. Theorem 4. [START_REF] Golab | An O(1) RMRs leader election algorithm[END_REF] A linearizable TAS object can be implemented using a weak leader election protocol and one additional multi-reader/multi-writer binary register, such that a test&set() operation requires only a constant number of read and write operations in addition to the leader election protocol.

EFFICIENT SIFTERS

An f (k)-sifter, where f is a function satisfying 1 ≤ f (k) ≤ max{k -1, 1}, supports only one method call, compete(). Each compete() method call returns either win or lose. In any execution, where k processes call compete(), at most f (k) of them return win, and at most k -1 return lose. In this section we prove that: Theorem 5. There is an obstruction-free implementation of an ( 2k+1 3 )-sifter using 6 registers, each of size Θ(log n)-bits, where the atomic operations are: scan all registers and write to a designated register, and any process finishes its compete() method call in a constant number of solo steps.

Recent randomized TAS constructions [START_REF] Alistarh | Sub-logarithmic test-and-set against a weak adversary[END_REF][START_REF] Giakkoupis | A tight RMR lower bound for randomized mutual exclusion[END_REF] are based on randomized sifters, where the number of winning processes is at most f (k) in expectation. Here, however, we use deterministic sifters, where f (k) is a worst-case bound. Two such f (k)-sifters can be combined to obtain an f (f (k)) sifter, by letting the losers of the first sifter lose, and the winners of the first sifter call compete() on the second sifter. Hence, combining O(log n) ( 2k+1 3 )-sifter objects yields a 1-sifter. A 1-sifter is a weak leader election protocol.

Hence, Theorem 1 follows from Theorems 5, 4 and 3. The remainder of this section is devoted of the proof of Theorem 5.

Sifter implementation

To aid intuition for our sifter implementation, we first consider a very simple obstruction-free sifter object, A. Object A consists of an array of three registers, each of which can hold one process identifier, and supports two operations: 1) scan of all three registers, which returns a triple of process identifiers, called a signature and 2) write to a specified register. Each process p alternates between writing and scanning. When p writes, it writes its own identifier to a register of A that did not contain p in its preceding scan. The goal of any process, p, is to achieve a clean-sweep meaning that its scan returns signature (p, p, p). In this case, p terminates with win. If, however, while trying for a clean-sweep, p's scan returns a signature that contains more copies of a different identifier than it has copies of p, then p terminates with lose. Any process that runs alone for six steps without losing, will return win. Furthermore, not all processes can return lose. To see this, let w be the last write to A and let p be the writer of w. If process p returns lose, then there is a process q that occupies two positions in p's last scan, so q cannot return lose. Therefore, A is an implementation of an obstruction-free sifter object.

Object A, however, is not a very efficient sifter. Suppose that while a clean-sweep is being achieved by one process, two other processes cover two distinct registers of A. Then these covering processes can over-write the clean-sweep, and be made to again cover two distinct registers. Now a new process can run under the cover and achieve a clean sweep. By repeating this scenario, executions are easily created where all but one process returns win. Also, notice that to create another winner after a clean-sweep, such an obliteration of the clean-sweep by two (or three) over-writes is also necessary.

To reduce the number of processes that can return win to at most a constant fraction of those that compete, the core idea is to prevent processes that participate in overwriting a clean-sweep, from covering again, without some process losing. This is achieved, in our algorithm, by adding to A a second similar (but not identical) component, B. Component B is an array of three registers, each of which can hold a pair consisting of a process identifier and a signature. Each scan now returns the content of both A and B, and a write by p can be either a write of p to a register of A, or a write of (p, sp) to a register of B, where sp is a signature. Each process begins by competing on component A and still strictly alternates between writing and scanning.

If process p, competing on component A, gets a scan with signature of A equal to s, where the identifiers in s are all distinct and one of them is p, then p leaves A to compete on component B while remembering s. (Notice that, if p does not get such a scan and it does not immediately return lose, then p is in at least two positions in s. Therefore, its last write could not have been part of an over-write of a cleansweep.) By writing the pair (p, s) to registers of B, p tries to achieve a clean-sweep of B (meaning a scan by p shows each of the 3 registers of B contains (p, s)). There are two ways that process p can lose while playing on component B. First, p loses if, while trying to achieve a clean-sweep of B, one of p's scans shows a signature of A different from s. Second, p loses if its scan shows that for some other process q, (q, s) occupies at least 2 positions of B. That is, p only returns to continue competing on component A if it achieves a cleansweep of B while each of its scans satisfies 1) the signature of A is s, and 2) no other process with signature s occupies more than one register of B.

Our sifter implementation is presented in Figure 1.

Intuition for correctness proof

Our proof will establish that not all processes can return lose, and at most one more than 2/3 of the processes that participate can return win. While the proof has to attend to several subtleties and substantial detail, there are several insights that aid our intuition. Consider the three ways that a process can return lose. Let us say p loses on A if process p loses while playing on component A because the signature of A in its last scan contained more occurrences of some other process than occurrences of p. We say p signatureloses on B if process p with signature s, loses while trying to achieve a clean-sweep of B, because one of p's scans shows a signature of A different from s. We say p process-loses on B if process p loses because its scan shows that for some other process q, (q, s) occupies at least 2 positions of B.

For the intuition that not all processes return lose, consider the last write, say w, to A, and let p be the process that executes w. Process p cannot lose on A because if it did, then in p's last scan there is some process, q = p, that occupies 2 positions on A, and that process cannot return lose without first writing to A after w. Similarly, p cannot signature-lose on B because, again, that would imply a write to A after w. So suppose p process-loses on B. Then we show that there is some other process, say q, that has the same signature as p and is competing with p, and q cannot process-lose on B. Process q also cannot signature-lose on B or lose on A without a write to A happening after w. Now consider the intervals in an execution between the final of processes that return win (achieve a cleansweep of A). If processes return win, there are -1 such intervals. We associate a losing process with each of these intervals as follows. (1) For any process, p, if p loses on A, then associate p with the interval that contains the last write by p. Similarly, (2) for any process q that signature-loses on B, associate q with the interval that contains its last write.

Let I be an interval without an associated losing process via either (1) or (2). We will prove that there is a subinterval I of I and either two or three processes that, during I , move from A to B and finish competing on B using some signature, say s, while the signature of A remains s. Now we focus on the execution during I . Since B has three registers, after any clean-sweep on B, a subsequent clean-sweep on B requires (at least) two processes to over-write the previous clean-sweep. These over-writers must have signature s, because, otherwise, an over-writer has a signature different from that of A and would signature-lose on B, implying that I already has an associated losing process via [START_REF] Aghazadeh | Space-and time-efficient long-lived test-and-set[END_REF]. If there are two processes with signature s then I can have at most one clean-sweep, and if there are three processes then I can have at most two clean-sweeps. Therefore, at least one of the two or three processes competing on B with signature s cannot return win, and (3) one such process is associated with I. Notice, however, that this process could withhold its last write in order to be assigned to a later interval via [START_REF] Aghazadeh | Space-and time-efficient long-lived test-and-set[END_REF]. Therefore, using these three rules of association, we assign a losing process to every interval, and no process is assigned to more than two of these intervals. Thus there are at least ( -1)/2 processes that cannot return win.

Notation and terminology

A losing scan is a scan by a process such that this process will return lose in its next step, without doing any further shared memory operation. A winning scan is a scan by a process such that this process will return win in its next step, without doing any further shared memory operation. For each winning scan there exists a last write by the process that performs this scan. We call this write a winning write. For an execution E, let s1, s2, . . . , s k be the sequence of winning scans in E and let q1, q2, . . . , q k denote the corresponding sequence of processes that performed these scans. Observe that ∀i, 1 ≤ i ≤ k, si is preceded by a winning write wi performed by qi. Furthermore, ∀i, 1 ≤ i ≤ k, si must happen before wi+1 because at si all registers in A contain qi's id however, at wi+1, qi+1 has written its own id everywhere in A. Hence winning scans and winning writes strictly interleave. That is, the order of winning scans and writes in E is w1, s1, w2, s2, . . . , w k , s k .

Given an execution E = op 1 , op 2 . . ., we denote the contiguous subsequence of E starting at op i and ending at the operation immediately before op j by E[op i : op j ). In our analysis we are interested in intervals between any winning scan and the next winning write. A sifting interval is a subsequence of an execution that starts at some winning scan and ends at the operation immediately before the next winning write. Observe that all sifting intervals are disjoint. Also because there has been a preceding winning scan, no register of A contains ⊥ in any sifting interval. Given sifting interval I = E[s * : w * ), let scanner(I) denote the process that executes s * and writer(I) denote the process that executes w * . If an execution contains k winning scans, then it has k -1 disjoint sifting intervals.

A signature is an ordered triple of identifiers. A signature (p0, p1, p2) is full if for any i, j ∈ {0, 1, 2}, i = j implies pi = pj. The following lemmas concern properties of executions. Terms such as before, after, next, previous, precedes, and follows are all with respect to the order of operations in an execution. A local variable x in the algorithm is denoted by xp when it is used in the method call invoked by process p.

Proof of correctness

Lemma 6. Suppose at scan s, A = (p0, p1, p2) is a full signature. For any i ∈ {0, 1, 2}, if pi writes to A after s, then its first write after s into A is not to A[i].

Proof. Let wi be the first write by pi to A after s. Let si be the scan by pi preceding wi. If si happens before s, then there is no write to A by pi in the interval E[si : s). At s, A[i] = pi, hence at si, A[i] = pi. Suppose si happens after s. At s, A[i] is the only location that contains pi, and there is no write to A by pi in the interval E[s : si) and si is not a losing scan. Therefore, at si, A[i] = pi. In either case, by Line 11, wi is a write to A[pos] where pos = i. Lemma 7. Suppose at scan s, A = (p0, p1, p2) is a full signature. Let w be the first write to A after s. Then w changes the signature of A.

Proof. Let q be the writer of w. If q / ∈ {p0, p1, p2}, then since q writes its own id, it changes the signature of A. If q ∈ {p0, p1, p2}, then by Lemma 6, a different location from A[i] is written by q. Hence w changes the signature of A.

Shared Objects:

• A[0, 1, 2] is an array of registers. Each array entry stores a value from P ∪ {⊥} and is initially ⊥.

• B[0, 1, 2] is an array of registers. Each array entry stores a pair (id, sig), where id ∈ P ∪ {⊥}, and sig is a triple from the set (P ∪ {⊥}) 3 . Initially, id = ⊥ and sig = (⊥, ⊥, ⊥).

Notation: for any array X and value v, we define num(v, X) := |{i :

X[i] = v}|.
Algorithm 1: compete() if ∃ q ∈ P, q = p, num((q, sig), b) ≥ 2 then 18 return true

1 pos := 0 2 while true do 3 A[pos].write(p) 4 a := scan(A) 5 if ∀ i ∈ {0, 1, 2}, a[i] = p then 6 return win 7 if ∃ q ∈ P, num(p, a) < num(q, a)
19 if ∀ i ∈ {0, 1, 2}, b[i] = (p, sig) then 20 return false 21 Let index ∈ {0, 1, 2} s.t. b[index] = (p, sig);
Figure 1: Implementation of a sifter for process p ∈ P Lemma 8. Suppose at scan s1, A = (p0, p1, p2) is a full signature. Let w be the first write to A after s1. Let s2 be any scan after w such that at s2, A = (p0, p1, p2). Then:

1. for some i, i ∈ {0, 1, 2}, pi calls knockout(σ) and returns false in the interval E[w, s2), where σ = (p0, p1, p2), and 2. for all i, i ∈ {0, 1, 2}, pi performs at least one write to A in the interval E[w : s2).

Proof. By Lemma 7, w changes the value of A by writing to A[i] for some i ∈ {0, 1, 2}. Since at s2, A[i] = pi, pi must perform a write to A[i] in the interval E[w : s2). By Lemma 6, the first write by pi, say, w i 1 to A in the interval E[w : s2) is to A[j] where j = i. Thus pi must perform at least two writes to A in the interval E[w : s2). Let s i 2 and w i 2 denote the second and third shared memory steps by pi in compete() method call during E[w : s2) and let σ be the signature of A at s i 2 . Immediately after w, no location in A contains pi. In the interval E[w : s i 2 ), pi writes only once and s i 2 is not a losing scan. Hence at s i 2 , pi appears in A[j], and this is pi's only location in A. Therefore, σ is full and σ = (p0, p1, p2). This implies pi calls knockout(σ) after s i 2 . Finally, because w i 2 is a write to A after s i 2 , pi must return false from this knockout call, proving 1.

By way of contradiction assume there is a k ∈ {0, 1, 2}, p k does not perform any write to A in the interval E[w : s2). Because at s2, A[k] = p k , no process writes to A[k] in the interval E[w : s2). In particular, since pi wrote to

A[i] and to A[j] in E[w : s2), k /
∈ {i, j}. Furthermore, to return A[j] to pj, pj must over-write w i 1 in the interval E[w i 1 : s2). By Lemma 6, the first write by pj, say w j 1 , to A in the interval E[w : s2) is to a location different from A[j], and by assumption it cannot be to A

[k]. So w j 1 is to A[i]
. Therefore, pj must do a later write, w j 2 , (not necessarily its next write) to A[j] in this interval. Let s j 2 be the scan by pj preceding w j 2 . At s j 2 , pj ∈ A. However,

pj = A[k]
because, by assumption, A[k] is not over-written, and

pj = A[j] because pj's next write is to A[j]. Therefore pj = A[i],
implying by Line 11 that (j -1) mod 3 = i. Recall that at s i 2 , pi = A[j], and pi's next write is to A[i]. Hence, by Line 11, (i -1 mod 3) = j. However, (i -1 mod 3) = j and (j -1 mod 3) = i is impossible. Hence p k must perform at least one write to A during E[w : s2), proving 2. Lemma 9. Suppose at scan s, A = σ is a full signature, and there is an i ∈ {0, 1, 2} such that B[i] = (p, σ). Let w (respectively, wi) be the last write to A (respectively, B[i]) preceding s. Then, w precedes wi.

Proof. By way of contradiction suppose wi precedes w. Then at p's scan that precedes wi, A must have signature σ. Let ŝ be the most recent preceding scan before w in which the signature of A is σ. Let ŵ be the first write to A in E[ŝ : s). This write exists because w ∈ E[ŝ : s). The write wi does not precede ŵ because, by Lemma 8 item 1, there is process that executes a complete knockout(σ ) in E[ ŵ : s), where σ = σ , and in this execution that process over-writes every register in B.

We now show that wi / ∈ E[ ŵ : w). By Lemma 8 item 2, p must write to A in the interval E[ ŵ : s). Since p did no operations between ŵ and wi, this required write would be after wi and before w. This is impossible because p does a scan after wi, before this write. Since the signature of A between wi and w is not σ, this scan would be a losing scan.

Lemma 10. There is no execution in which all processes return lose.

Proof. By way of contradiction, assume that there is an execution in which all processes return lose. Let u be the process that performs the last write to A, let w A u be that write, and let σ be the signature of A after w A u . Let su be the last scan by u. Then u returns lose in Line 8 or 10.

)-Sifter using 6 O(log n)bit registers, if a linearizable scan() is available.

Optimizing the sifter for TAS

We presented the sifter object with the smallest possible sizes for components A and B. Both consist of 3 registers. However a natural question is whether or not the space can be reduced by increasing the size of B. In fact, if we use a B component of size 4 instead of 3, for sufficiently large n, the space result for TAS is slightly smaller because fewer sifters are required. Here is the intuition. Suppose that B has size b. For every sifting interval that is not slow we associate a process that performs its last write to A and returns lose subsequently. For every slow sifting interval there exists at least two processes that invoke knockout with the same signature σ. One possibility in this case is that, from these two processes, one gets knocked out in B and performs its second last write in this interval and returns lose subsequently. The only way to have both of these processes returned false from knockout(σ), is by obliterating the trace of the first process that returns false so the other one can also return false. This obliteration can happen only by accumulating at least b-2 processes that have performed their second last writes in previous sifting intervals and are poised to perform their last writes. Therefore, the worst case of our analysis is when there are b -2 sifting intervals such that in each, one process performs its second last write, followed by a single sifting interval, I, in which these b -2 processes perform their last writes and return lose.

RANDOMIZED TEST-AND-SET

We can combine our TAS algorithm with existing algorithms and techniques from [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF][START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF], to obtain a randomized TAS implementation from registers that uses logarithmic space, and has almost constant, O(log * n), expected step complexity against an oblivious adversary. Next we present such an implementation, that has the properties stated in Theorem 2.

In [START_REF] Giakkoupis | An O( √ n) space bound for obstruction-free leader election[END_REF]Theorem 2] it was shown that any obstruction-free TAS algorithm, in which any process finishes after at most b steps if it runs solo, can be transformed into a randomized one with the same space complexity, where each process finishes after at most O b(n + b) log(n/δ) steps with probability at least 1 -δ, for any 0 < δ < 1. Since b = O(log n) for our obstruction-free algorithm (see Theorem 1), it follows that it can be transformed into a randomized algorithm without increasing its logarithmic space, and with each pro-cess finishing in at most O(n log 2 n) steps, both in expectation and w.h.p.

To achieve the O(log * n) step complexity, we combine the above randomized algorithm with another randomized TAS construction proposed in [START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF]. The construction in [START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF] uses a chain of n sifter objects F1, . . . , Fn alternating with n deterministic splitters S1, . . . , Sn, and a chain of n 2-process consensus objects C1, . . . , Cn. (A splitter returns win, lose, or continue, such that at most one process wins, not all processes lose, and not all continue.) A process p proceeds by accessing the sifters in increasing index order. If p loses in some sifter Fi then it loses immediately in the implemented TAS; if it wins sifter Fi, it tries then to win splitter Si. If p loses Si, it loses also the TAS; if Si returns continue, p continues to the next sifter, Fi+1; and if p wins Si, it switches to the chain of 2-process consensus objects. In the last case, p then tries to win Ci, Ci-1, . . . , C1 (in this order). If it succeeds, it wins the TAS, otherwise it loses.

In [START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF], a randomized sifter implementation from s ≥ 1 single-bit registers is proposed. In this implementation each process takes O(1) steps, and if at most 2 s processes access the sifter then at most O(s) of them win in expectation. Further, for s = log n, we have that w.h.p. at most O(log 2 n) processes win.1 Finally, if s = 2 and k processes access the sifter, then at most k/2 + 1 processes win in expectation. In the following, we will refer to the above sifter object as GW-sifter of size s.

The TAS implementation in [START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF] uses n GW-sifters of size log n each, and thus requires Θ(n log n) registers in total. We modify this implementation as follows: The first sifter object, F1, is a GW-sifters of size log n, as before. The next = √ log n sifters, F2, . . . , F +1 , are GWsifters of size √ log n. Then, the next m = 3 log n sifters, F +2 , . . . , F +m+1 are GW-sifters of size 2. Finally, sifter F +m+2 is the randomized variant of our TAS algorithm described earlier. All objects Fi, Si, and Ci for i > + m + 2 are dismissed.

It is straightforward to verify that this implementation uses Θ(log n) registers (note that O(1) registers are needed to implement each of the objects Si and Ci). The reason we can use sifters of size only √ log n instead of log n starting from the second sifter, is that, w.h.p. at most O(log 2 n) processes win the first sifter (of size log n), as we mentioned earlier. (So, in fact, it would suffice that those sifters be of size Θ(log log n) < √ log n.) Then from the analysis in [START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF] we have that in expectation only the first O(log * n) sifter objects are used, and with probability 1 -O(1/ log n), at most the first O(log log n) < sifters are used. Thus, only with probability O(1/ log n) the constant-size sifters will be used. Since in each of these sifters half of the processes lose in expectation, and we have m = 3 log n such sifters, it follows that with probability 1 -O(1/n 2 ) no process will access the last sifter, F +m+2 . From the above, it follows that the expected value of the maximum number of steps by a process is O(log

* n) + O(1/ log n) • 3 log n + O(1/n 2 ) • O(n log 2 n) = O(log * n).

then 8 return lose 9 if

 9 num(p, a) = 1 then 10 if knockout(a) then return lose 11 Let pos ∈ {0, 1, 2} s.t. a[(pos -1) mod 3] = p and a[pos] = p Algorithm 2: knockout(sig) 12 index := 0; 13 while true do 14 B[index].write((p, sig)); 15 (a, b) := scan(A, B); 16 if a = sig then return true; 17

3 b- 1 n + 2 sifters each of size 3 + 3 b- 1 nlog 3 2 n

 3123312 These last writes manage to prevent a new process from being knocked out in B during interval I. Hence, for every b -1 sifting intervals there are at least b -2 losers. Suppose k processes invoke compete(). If k processes return win, then by definition, there are k -1 sifting intervals. Therefore there are at least b-2 b-1 (k -1) processes which have invoked compete() and cannot return win. Since b-2 b-1(k -1)+k ≤ b-2 b-1 (k -1) +k ≤ k, we have k ≤ ( b-1 2b-3 )k + b-2 2b-3. Thus, we need at most log 2b-b. Therefore the space complexity of our test-and-set object is at most (3 + b)(log 2b-+ 2). For b = 4 this function is less than 9.5 log n + 14. For b = 3, the space used in the worst case by our algorithm is at least 6 ≥ 10.25 log n. So we can conclude that for n ≥ 218.46 , our algorithm requires less space when component B has 4 registers instead of 3.

This property is not shown in[START_REF] Giakkoupis | On the time and space complexity of randomized test-and-set[END_REF], but follows from standard probabilistic arguments.Grants program of NSERC, and the INRIA Associate Team RADCON.

Acknowledgements

This research was undertaken, in part, thanks to funding from the Canada Research Chairs program, the Discovery

First consider the case in which u returns lose in Line 8. At su, num(u, au) is not equal to 0 because the last write to A is performed by u and su happens after w A u . Therefore, num(u, au)= 1 and there is a process y such that in su, num(y, au) = 2. Let w A y be the last write by y to A. Since u performs the last write to A, w A y precedes w A u . Because no process writes y to A after w A y and no process writes to A after w A u and, later, at su, num(y, au) = 2, it follow that num(y, A) ≥ 2 for the entire execution after w A y . Therefore any scan by y after w A y must satisfy num(y, ay)≥ 2. This implies y cannot return lose, contradicting the assumption.

Next consider the case in which u returns lose in Line 10. This implies u calls knockout(σ) after w A u from which it returns true in Line 16 or in Line 18. But u cannot return true in Line 16 because the value of array A remains σ after w A u . Therefore u returns true in Line 18.

Let S = {q | ∃i, B[i] = (q, σ) at some point after w A u }. By Lemma 9, for each q ∈ S, q performs a write (q, σ) to B after w A u and, by assumption, subsequently does a losing scan. Because u returns true in Line 18, S is not empty. For each q ∈ S, q cannot return lose at Line 8 because this would imply q writes to A after w A u . Therefore q returns lose at Line 10 implying that q returns true at Line 16 or Line 18. It does not return true in Line 16 because sig q = σ and the value of A remains σ after w A u . Therefore for each q ∈ S, q returns true in Line 18, following a losing scan that is after w A u . Let z be the last process in S to do its losing scan, sz. At sz two registers in B contain (z , σ), where z = z. Thus, between the last write by z and the last scan by z , these two registers in B contain (z , σ). So after z 's last scan at most one register of B contains an id not equal to z . Therefore z cannot return true in Line 18, contradicting the assumption that the last scan of z is a losing scan.

Lemma 11. Suppose an interval between a write and the next scan by the same process, say p, contains a winning write. Then the scan by p is a losing scan.

Proof. At the winning write all registers in A contain the id of the process that performs this winning write. In the sub-interval from the winning write to the scan by p there is no write by p. Since only p writes its id, at p's scan, num(p, ap) = 0. Hence p returns lose after this scan.

Observation 12. Every sifting interval contains at least two writes to A.

Proof. Consider the sifting interval

Since w * is a winning write, writer(I) must have performed at least two writes to A before w * , and these two writes must be after the previous winning scan, which is s * .

A sifting interval that does not contain a write to A by a process whose next scan is a losing scan is called a slow sifting interval.

Lemma 13. For any slow sifting interval I, there exists a signature σ = (q0, q1, q2) and a set Z ⊆ {0, 1, 2} satisfying: |Z| = 2 and for each z ∈ Z during I, qz performs a write and then a scan in compete() and then invokes knockout(σ) and becomes poised to write (qz, σ) to B. Furthermore, there is no write to A between these two scans.

Proof. Let I be E[s * : w * ).

Suppose that w A 1 , w A 2 , . . . , w A is the sequence of all writes to A during I. By Observation 12, ≥ 2. For each i, 1 ≤ i ≤ , let si denote the next scan by the process that executes w A i . Each si is at Line 4 following wi at Line 3 of compete(). Let S denote the set of all these scans. Let Î denote the interval E[w A 2 : w * ). By Lemma 11, if si happens after w * then si is a losing scan and hence E[s * : w * ) is not a slow sifting interval. Therefore ∀i, 1 ≤ i ≤ , si occurs in E[w A i : w * ). Let q be the process that performs s1. At s * , num(scanner(I), A) = 3. Because only one write happens to A during E[s * : w A 2 ), q would return lose at Line 8 if s1 precedes w A 2 implying E[s * : w * ) is not a slow sifting interval. Hence ∀i,

). Since scans happen in these -1 intervals, by the pigeonhole principal, there is a j, 2 ≤ j ≤ such that (at least) two scans in S, say s and s occur in E[w A j : w A j+1 ). Because no process performs two scans in compete() without writing to A in between, s and s are performed by two distinct processes say qz and q z . Because E[s * : w * ) is a slow sifting interval, neither qz nor q z return lose at Line 10. Since no write happens to A during E[w A j , w A j+1 ), the scans by qz and q z in compete() return the same signature for A, say, σ where σ contains qz and q z . Therefore qz and q z both invoke knockout(σ).

Lemma 14. Let s be the scan by p immediately before p invokes knockout(σ) and s be any scan by p in this invocation. Let w be the first write to A after s. If w precedes s , then s is a losing scan.

Proof. Since p invokes knockout(σ), σ is a full signature and p is in σ. By way of contradiction suppose s is not a losing scan. Hence at s , the signature of A is σ. Therefore, by Lemma 8(point 2), p writes to A in the interval E[w : s ). This is a contradiction because p is performing knockout(σ) in this entire interval and there are no writes to A during the knockout method call.

Lemma 15. For every slow sifting interval I, there is a process p that performs a write during I and either the first or the second scan by p following this write is a losing scan.

Proof. Let I = E[s * : w * ) be a slow sifting interval. By Lemma 13, there exists a full signature σ = (q0, q1, q2), a set Q ⊆ {q0, q1, q2} satisfying 2 ≤ |Q| ≤ 3 and for each q ∈ Q during I, q performs a write to A and a scan in compete() and calls knockout(σ) and becomes poised, at Line 14, to write (q, σ) to B[0]. Furthermore, there is no write to A between these scans. Let ŝ be the earliest of these scans. At ŝ, the signature in A is full and at w * the same id is in all locations of A. Hence there is at least one write to A in E[ŝ : w * ). Let w be the first write to A in E[ŝ : w * ).

Suppose there is q ∈ Q, such that q performs a scan, say s, in Line 15 of its current call to knockout after w. Then by Lemma 14, s is a losing scan. Since q writes at least once in E[s * : w * ) and at most once after w, it follows that q performs its last or second last write during E[s * : w * ), and so s is either q's first or second scan following this write, and the lemma holds.

Otherwise, all processes in Q execute at least one write and perform their last scan of their current call to knockout before w. We partition this case into three subcases.

Case 1: There is q ∈ Q such that q calls knockout(σ) and returns true (Line 16 or 18). Then q's last scan before returning true is a losing scan, and the lemma follows.

Case 2: For each process q ∈ Q, q's current knockout call returns false and there is a process p / ∈ Q that performs a write wp to B with value (p, σ ) in the interval E[ŝ : w) where σ = σ. When p did its scan in compete() just before invoking knockout(σ ), the signature of A was σ . At wp, the signature of A is σ = σ , so there is a write to A between this scan by p and wp. Hence, by Lemma 14, p's next scan after wp is a losing scan, and again the lemma follows.

Case 3: For each process q ∈ Q, q's current knockout call returns false and there is no write to B in E[ŝ : w) that contains a signature different from σ. We show that this case is impossible. Let S be the set of last scans of knockout calls by processes in Q. Let s be the last scan and s be the second last scan in set S. Let q and q be the processes performing s and s respectively. Since q returns false, all three registers in B contain (q , σ) at s . After s , there can be at most one write to B by q . Because q 's next scan after such a write would be a losing scan, contradicting that q returns false.

Lemma 16. For every sifting interval, there is a process p and a write w by p satisfying: either the first operation by p or the third operation by p that follows w is a losing scan.

Proof. For any sifting interval that is not slow, the lemma holds by definition. For any slow sifting interval, the lemma follows from Lemma 15, because each process alternates between writes and scans.

Lemma 17. If k processes invoke the compete() method, then at most 2k+1 3 processes return win.

Proof. If k processes return win, then by definition, there are k -1 sifting intervals. By Lemma 15, for each sifting interval there is a process that performs its last or second last write and it cannot return win. Hence there are at least k -1 2 processes which have invoked compete() and cannot return win.

.

Lemma 18. The Sifter implementation is obstruction-free where each process terminates in O(1) solo steps.

Proof. Suppose a process, p, begins a solo run while it is executing knockout. If it returns true in either Line 16 or Line 18, then it terminates due to Line 10. Otherwise in each iteration of the while loop, it writes a new location in B. Therefore after three iterations, all locations in B contain (p, sig p ), and p returns false in Line 20. When p executes knockout during its solo run, the value of A is equal to sig p because otherwise p returns true from its knockout call. In sig p , exactly one location in A contains p and no other process writes to A after it returns from its knockout call. Hence p writes two more times to A and, by Line 6 returns win.

Suppose p starts its solo run in a compete() call. After at most one write it performs a scan. Then it either returns win due to Line 5 or returns lose in Line 8, or it invokes a knockout call. If it calls knockout, then by the argument above it terminates. By Lemmas 17 and 18, the algorithm in Figure 1 implements an obstruction-free ( 2k+1