Mathieu Durand

Jérôme Morville

Daniele Romanini

Shot-noise limited measurement of sub-ppt birefringence phase shift in a high finesse cavity

Keywords: numbers: 42.25.Lc, 07.60.Fs, 42.65.Hw, 42.50.Xa

We report on a novel approach to high sensitivity anisotropy measurements using a high finesse cavity locked by optical feedback to a diode laser. We provide a simple and effective way to decouple the weak anisotropy of interest from the inherent mirror's birefringence whose drift may be identified as the key limiting parameter in cavity-based techniques. We demonstrate for the first time a shotnoise limited phase shift resolution up to now inaccessible in an optical cavity, readily achieving the state of the art level of 3 × 10 -13 rad.

Ultimate performance in the definition of the polarization state of light plays a key role in fundamental physical investigations. Detecting changes in a polarization state is widely used to study optical effects in crystals, biological systems or polymers. It has also demonstrated its ability to provide powerful tests of our understanding of light-matter interaction by the observation of magnetochiral birefringence [1], magnetoelectric Jones and linear birefringence [2,3] or magnetoelectric Jones dichroism [4].

Today, observing the vacuum in a field acting on the polarization of light is one of the all-optical candidates to probe the photon-photon scattering, a fundamental feature of QED [5]. The 2 photons interaction through the creation of virtual electron-positron pairs yields to change of vacuum properties such the Kerr birefringence (induced by an transverse electric field), the Cotton-Mouton birefringence (induced by a transverse magnetic field) or the magnetoelectric birefringence (induced by transverse electric and magnetic fields) [6]. The strength of these nonlinear interactions scales with the QED correction of the Lagrangian 8α 2 3 45m 4 c 5 ≃ 7 × 10 -30 m 3 J -1 where m is the electron mass, which yields to an induced phase shift in vacuum as weak as 3 × 10 -17 rad/T 2 m for optical wavelengths in the case of an external transverse magnetic field.

At such a low level, the contribution of new light scalar/pseudo-scalar particles such as axions that couple to photons should also manifest itself as a sizeable deviation from the QED prediction [7]. We may also recall that, even if finally attributed to instrumental artefact [8], the PVLAS collaboration aiming at the detection of the Vacuum Magnetic Birefringence [9], interpreted a thought-to-be signal as induced by intracavity axion production [10]. The interest in axions, providing the answer to the strong-CP problem, lies beyond Particle Physics and overlaps with Cosmology since such particle is con-sidered as a serious dark matter candidate [11][12][13][14].

Probing polarization state changes using high sensitivity provided by a high finesse cavity is expected to be very promising. As noticed by Hall et al. [15] the ultimate shot-noise limited sensitivity, together with milliwatt optical power and state of the art magnetic fields (10 T), may resolve the QED predicted birefringence in vacuum, but up to now no cavity-based measurement was able to approach this fundamental limit. As pointed out by authors of advanced experiments [15,16] this is due to the drift of the inherent residual birefringence of high reflectivity (HR) cavity mirrors. In this letter we present a novel approach unaffected by this problem and demonstrate for the first time a shot-noise limited phase shift resolution using an optical cavity, down to the state of the art level of 3.10 -13 rad. We believe that this approach, which works well in the limit of very high cavity finesse, is a major step towards the measurement of effects like the vacuum birefringence.

Let us begin by considering that the effect of any intracavity anisotropy (mirror coating, Kerr or Cotton-Mouton birefringence, etc) is lifting the degeneracy of cavity polarization modes. For each transverse cavity mode two eigenvectors of polarization are then defined by different resonance frequencies. One way to access the intracavity anisotropy is therefore to measure the mode splitting [15,17]. Hall et al. achieved a phase sensitivity of 10 -9 rad/ √ Hz per pass across a dynamic range of seven orders of magnitude using this method [15]. However, in the limit of weak mode splittings, with partial spectral overlap of the resonance profiles, another scheme is available. As in usual anisotropy measurements, the sample is sandwiched between crossed polarizers. The cavity is illuminated by 45 • polarized light relative to its birefringence axes, which excites both polarization modes (approximately linear and orthogonal). The ratio between the crossed and the parallel signals from the analyzer is then proportional to the square of the intracavity polarization change. This idea was first applied to detect small circular dichroisms induced in an atomic vapor by a polarized saturating field [18], and then generalized to different polarization effects (Faraday rotation, Cotton-Mouton effect, Kerr effect, circular dichroism) by the same group [19]. Although limited in dynamic range, this approach appears to provide the best performances in term of sensitivity [16].

In high finesse cavities, the first source of birefringence is HR mirror birefringence. Its phase shift per reflection, around 10 -6 rad, is four orders of magnitude above the Kerr or the Cotton-Mouton birefringence induced in atomic gases for typical electric or magnetic field values under standard temperature and pressure (STP) conditions. Given the small round-trip mirror birefringence, the combined effect of both mirrors is equivalent (to the first order) to that of a single birefringent element. Its phase shift is bounded between the difference and the sum of the two mirror's phase shifts following a sinusoidal function of the angle between their birefringence axes. One way to eliminate the combined mirror birefringence would be to use mechanical stress to equalize their phase shifts and then orient the axes orthogonally. Then, by modulating the field inducing the gas birefringence and by adding outside the cavity a much larger ellipticity, the measurement dependency with the weak Kerr or Cotton-Mouton birefringence would be linearized and the useful signal would thus be enhanced [16]. However, the measurement becomes very sensitive to any change of the combined mirror birefringence, which may rapidly produce a large signal offset. In particular, thermal stress induced by intracavity optical field buildup has been highlighted [15] as the main limitation of the achievable sensitivity in mode splitting measurements. When using the crossed polarizers approach, mirror birefringence inhomogeneities combined with mechanical drift was suggested as the main noise source [16]. In this Letter we present a method to profitably exploit the mirror birefringence as a DC bias around which the weak induced ellipticity is modulated. This, as with an externally added ellipticity [16], linearizes the response to the useful signal, but above all it offers the unique advantage of a measurement free of mirror birefringence drift, with ideal averaging properties allowing to approach the ultimate limits. Indeed we demonstrate shot noise performance in an application to the measurement of Kerr effect in gases.

In order to fully benefit from the use of a high finesse cavity, it is necessary to lock the laser frequency to the exact center of a cavity mode. To reach this objective, different servo-locked configurations have been established [20,21], that by Pound-Drever-Hall being the most popular. An attractive alternative is to take advantage of the frequency locking that occurs when a semiconductor laser is coupled to a high finesse cavity by a weak resonant optical feedback (OF) [22]. The simultaneous and drastic linewidth reduction is so effective that the optically locked diode laser emission may be regarded as monochromatic compared to the sub-kHz cavity resonance. Usually, to separate the OF from the direct reflection of the cavity input mirror, particular cavity and injection configurations (V-cavity or confocal cavity) are used [22]. As demonstrated by Morville et al. [23], a simpler axisymmetric two-mirror cavity configuration is exploitable: the cavity mirror birefringence allows resonant OF to be selected by its modified polarization. For an external-cavity diode laser (ECDL) in the Littrow configuration, an OF as a fraction of laser power in the range of 10 -6 to a few 10 -4 acts in the perturbative regime of the free-running laser and forces optical locking. This corresponds to a mirror birefringence value in the range of 10 -7 to a few 10 -6 assuming a finesse of 250 000 and a cavity transmission of 10%. Because of the OF, the ECDL frequency is no longer defined by its free-running value (depending on injection current and grating orientation), but mostly by the cavity resonance frequency and the OF phase. Thus, the laser frequency may be locked to the exact resonance center by servo controlling the OF phase and the injection current thanks to a modulation/demodulation scheme of the cavity transmission similar to the one proposed by Ohshima et al. [24].

A scheme of our experimental setup for gas-phase Kerr effect measurement is shown in Fig. 1. A 3 mW diode laser beam (λ = 810 nm) is first circularized by anamorphic prisms, then focused into a very high finesse cavity (250 000) in order to mode-match its T EM 00 mode. The cavity of 52 cm long is formed by two mirrors of 50 cm of radius of curvature and by a glass tube in which the gas circulates as a laminar flow under STP conditions. The transverse electric field is generated by applying a voltage between two 47 cm long electrodes separated by 3 mm and inserted in the glass cell on both sides of the optical axis.

The polarizer P followed by the quarter-wave retarder (a Fresnel rhomb) constitute an optical isolator against the direct cavity reflection which preserves the incident (circular) polarization. On the other hand, the resonant intracavity field is sensitive to the HR coating birefringence, and its polarization is appreciably different from the incident one [19,23]. Light resonating inside the cavity is therefore partially returned through the isolator as the OF. The linearly polarized probe exploited in [19,23] is here replaced by circularly polarized light. This makes the orientation of the mirrors and the electrodes independent of the laboratory frame and should reduce the optical-field-induced mirror birefringence [15].

The PC servo-control (dashed box) generates a reference modulation at frequency f which is applied to the laser frequency. By lock-in phase detection on the cavity transmission (photodiode PD1), an error signal is then generated to correct small resonance frequency drifts by acting on the OF phase through a PZT mounted mirror. The modulation frequency is limited by the cavity bandwidth (∼ 1 kHz) and has been fixed to 800 Hz corresponding to the quietest spectral range. The diode laser current source and the mechanical environment are stable enough that correction of the OF phase alone is sufficient to keep the exact resonance for about one hour.

A flip-flop digital circuit is used to generate an inphase square modulation at frequency Ω = f /2 which is applied to the transverse electric field inducing the Kerr gas birefringence. A fraction (∼ 4%) of the OF power feeding back from the cavity is deflected by a beamsplitter (BS) onto a low noise amplified photodiode (PD2): providing the birefringence signal. With respect to polarization analysis in transmission, this analysis in reflection allows to use a single set of high quality polarizer plus Fresnel rhomb which may be adjusted with high precision. The very critical tilt of the rhomb is optimized by setting the laser in scanning mode while looking at fringes from a thick etalon (not shown in the figure) and minimising the direct cavity reflection effects. The resulting extinction factor of this analyzer has been evaluated at better than 10 -6 [25]. The PD2 output is then demodulated at Ω by a lock-in amplifier, whose output is digitized together with the DC components of PD1 and PD2 using a 16-bit data acquisition system (NI USB 6251). The Ω and DC levels of PD2 are then normalized by dividing out the DC component of the cavity transmission (PD1).

Finally, the total observable cavity anisotropy ρ, which is the ratio of the birefringence signal over the cavity transmission, can be written in a similar way to [19] as a sum of its DC and Ω components [25]: with

ρ = ρ DC + ρ Ω • cos(Ω • t) (1)
ρ DC = κ • F 2 • π 2 • φ 2 M (2a) ρ Ω = κ √ 2 • F π 2 • φ M φ g (2b)
where φ g is the phase shift induced by the Kerr effect in the gas while φ M is that associated with the cavity mirrors. The slow axes of these birefringences need to be aligned in order to maximize the useful signal, which is one of the optimization steps of our scheme. From these relations it is clear that measuring ρ DC and ρ Ω , together with the cavity finesse F and the BS reflection coefficient κ (which would be 1 in the case of direct polarization analysis at the cavity output) immediately yields the Kerr phase shift

φ g = π F • 1 √ 2•κ • ρΩ √ ρDC .
From Eq. (2b) it seems tempting to increase the DC bias through φ M in order to improve the system resolution. However, each component of the ratio used to obtain ρ Ω depends on the DC bias which leads to non trivial resolution dependency upon the DC bias value. Given that the ρ Ω noise is mainly due to the weakest component, which is the small birefringence signal, the theoretical shot-noise limited resolution is illustrated in Fig. 2 (dashed line) as a function of the DC bias φ M . It is approximately constant below π/F , but rapidly increases above this threshold due to the spectral splitting of the two eigenmodes which becomes larger than their linewidth. A complete analysis, however, needs to account for additional noise sources: photodetector noise (input noise of the current amplifier, thermal noise of the transimpedance gain, quantization noise at the digitalizer stage) and cavity transmission power fluctuations. The latter has two origins: the intrinsic diode laser power fluctuations and its residual frequency fluctuations. Nor- malized to the shot noise, the cavity transmission fluctuations are proportional to the birefringence signal while the photodetector noise is inversely proportional to it. This counterbalancing behavior leads to an optimum of resolution as a function of DC bias as shown in Fig. 2 (thick line). It is noteworthy that theory predicts a shotnoise-limited measurement provided that φ M is around 0.1 • π/F . For a finesse of 250 000, this yields an optimal combined mirrors birefringence of 10 -6 rad. Since the intrinsic coating birefringence of our mirrors is slightly greater than this value, a simple adjustment of their relative orientation allowed this condition to be achieved. Fig. 3 presents the experimental Kerr phase shift distributions and their Gaussian fits for four settings of the modulated electric field. These distributions are obtained from measurements of ρ Ω and ρ DC after application of Eqs. (2a) and (2b) in the above optimal experimental conditions. The test gas used is nitrogen at near STP conditions. Integration time for an elementary phase shift measurement is one second, and each distribution is formed by several thousand points. The standard deviation of these distributions is 4 × 10 -12 rad and defines the weakest value of Kerr anisotropy which can be resolved in one second. The experimental resolution agrees perfectly with the theoretical estimation including the contribution of the relevant noise sources shown in Fig. 2 (black dot). By increasing the integration time, the measured Allan variance of the phase shift shown Fig. 4 a) indicates that the resolution continues to drop with a white noise dependence to the value of 3 × 10 -13 rad at 800 s, the maximal integration time currently limited by the laser frequency servo loop. This limit could be overcome by also controlling this drift as shown in a similar setup [25] wherein the exact resonance could be maintained for more than ten hours. In Fig. 4 b), the simultaneously measured Allan variance of the HR mirror birefringence is shown and its evolution clearly illustrates that indeed the mirror birefringence value drifts as fast as 1/f 2 . This demonstrates the ability to decouple the two measurements.

In conclusion we have shown an effective way to cancel out the drift of the mirror birefringence in very weak anisotropy measurement in a high finesse cavity. This new method has been applied to the detection of the Kerr effect in nitrogen and has demonstrated for the first time a resolution at the shot-noise limited level. The resolution of 3.10 -13 rad is three order of magnitude better than previously reported Kerr birefringence measurement. Finally this technique may constitute a major step towards the vacuum birefringence detection using a polarization state probe.

FIG. 1 :

 1 FIG. 1: Experimental setup. ECDL, Extended Cavity Diode Laser; APP, anamorphic prism pairs; BS, beam splitter; PZT, piezoelectric transducer; P, polarizer; PD, amplified photodiode; Σ, summation; , integrator stage.

FIG. 2 :

 2 FIG. 2: Kerr phase-shift resolution as a function of the DC bias. Dashed line: photon-noise limited, thick line: technical noise, black dot: our experiment. I0 is the cavity transmitted power, S the photodiode responsivity and e the electron charge. Our parameters: I0 = 240 µW, F = 250 000 and S = 0.5 A/W.

FIG. 3 :

 3 FIG. 3: Nitrogen phase shift distributions for 1 s measurements at four electric field levels: (a) E = 0 V/m; (b) E = 1.3 × 10 3 V/m (only the Gaussian fit is shown); (c) E = 2.7 × 10 3 V/m; (d) E = 6.4 × 10 3 V/m.

FIG. 4 :

 4 FIG. 4: Simultaneously measured Allan variance for a) the Kerr phase shift induced in nitrogen by E = 9 10 3 V/m and b) the phase shift induced by the HR mirror. Error bars are from the statistical errors from the calculation of the Allan variance, which have the usual property of growing at longer integration times.


Marc Le Romancer
email: marc.leromancer@univ-brest.fr

Mélusine Gaillard

Claire Geslin

Daniel Prieur

Viruses in extreme environments

Keywords: bacteriophages, deep sea subsurface environment, deserts, extreme environments, hot springs, hydrothermal vents, hypersaline habitats, polar ecosystems, viral diversity, viral abundance

The tolerance limits of extremophiles in term of temperature, pH, salinity, desiccation, hydrostatic pressure, radiation, anaerobiosis far exceed what can support non extremophilic organisms. Like all other organisms, extremophiles serve as hosts for viral replication. Many lines of evidence suggest that viruses could no more be regarded as simple infectious "fragments of life" but on the contrary as one of the major components of the biosphere. The exploration of niches with seemingly harsh life conditions as hypersaline and soda lakes, Sahara desert, polar environments or hot acid springs and deep sea hydrothermal vents, permitted to track successfully the presence of viruses. Substantial populations of double-stranded DNA virus that can reach 10 9 particles per milliliter were recorded. All these viral communities, with genome size ranging from 14 to 80 kb, seem to be genetically distinct, suggesting specific niche adaptation. Nevertheless, at this stage of the knowledge, very little is known of their origin, activity, or importance to the in situ microbial dynamics. The continuous attempts to isolate and to study 3 viruses that thrive in extreme environments will be needed to address such questions. However, this topic appears to open a new window on an unexplored part of the viral world.

Introduction

Extremophiles include organisms from the three domains of life, Archaea, Bacteria and Eukarya, which thrive in extreme environments that are characterized by physico-chemical conditions close to the limit values in which an organism can live. As bacteria and archaea are almost omnipresent on the planet and have evolved for over 3.5 billion years, "extremophile" conjures up images of prokaryotes, especially from the domain Archaea. Although archaea are present in many moderate environments, they are still primarily considered extremists, flourishing in habitats that brave the physical limits for life, such as sulfur-rich hot acid springs and geysers, deep-sea environment and deep sea hydrothermal vents, hypersaline and soda lakes or strictly anoxic ecosystems (see review in [START_REF] Rothschild | Life in extreme environments[END_REF].

The specific feature of Extremophiles is their remarkable capabilities to adapt to extreme conditions in term of pH, salinity, desiccation, hydrostatic pressure, radiation, anaerobiosis that would be inevitably lethal for non extremophilic organisms. Extremophiles thrive at temperatures exceeding 80°C and even more than 100°C at hyperbaric pressure (extreme thermophiles in hydrothermal vents) while others live at subzero temperatures (psychrophiles in sea ice). Extreme piezophiles, which can withstand the enormous hydrostatic pressure associated with great depths, grow well in the deep sea and even in deep subsurface sediments as deep as 1000 meter below the seafloor (mbsf) under anaerobic conditions. Extremophiles are also able to cope with environments of very low water activity and develop well in desert or saturated brines (extreme halophiles) while acidophiles and alkalophiles live in extremely acid and alkaline waters at pH values below 2 and exceeding 10, respectively. In proportion to the multiplicity of physical and geochemical constraints in an extreme ecosystem, organisms that thrive under the seemingly harsh conditions are most of the times polyextremophiles.

Like all other organisms, extremophiles serve as hosts for viral replication. Viruses and virus-like elements (i.e. satellite virus, satellite RNA and viroids) are the smallest infectious biological entities (see http://www.ncbi.nlm.nih.gov/ICTVdb/origin2.htm). Since they are not autonomous -they depend on a cellular host for replication -viruses have been considered as not really alive for a long time. Many lines of evidence have definitely suggested that they could no more be regarded as simple infectious "fragments of life" but on the contrary as one of the major components of the biosphere, who have probably played a key role in the early cellular evolution and that have a profound influence on cellular life (e.g. genome plasticity, biochemical adaptations required to life in extreme environments).

Viruses exist wherever cellular life is found and span the three domains of life. But the extent of viral ubiquity and diversity still remains largely unknown. The recently accumulated knowledge on the number of viruses, from marine environments at least, shows that they probably encompassed all other forms of life in abundance on the earth and represent a vast reservoir of biodiversity [START_REF] Fuhrman | Marine viruses and their biogeochemical and ecological effects[END_REF][START_REF] Wommack | Virioplankton: viruses in aquatic ecosystems[END_REF][START_REF] Weinbauer | Ecology of prokaryotic viruses[END_REF][START_REF] Rohwer | Global phage diversity[END_REF][START_REF] Suttle | Viruses in the sea[END_REF][START_REF] Edwards | Viral metagenomics Nat[END_REF][START_REF] Breibart | Here a virus, there a virus, everywhere the same virus?[END_REF]. The universal tree of life can thus be considered as immersed into a virtual viral ocean [START_REF] Bamford | Do viruses form lineage across different domains of life?[END_REF]. As new niches are explored for life, especially in extreme environments, presence of viruses is readily detected and an amazing number of (new) viruses is discovered.

The aim of this present mini-review, that was inspired following discussions at the workshop entitled "Investigating Life in Extreme Environments", organised by the European Science Foundation (Sant Feliu de Guixols, Spain, 5-8

November 2005), is to give a brief overview of the recent findings about viruses thriving in extreme conditions.

Extreme halophilic viruses

Liquid water is an absolute requirement for metabolic activity and growth. The high concentration of ions in hypersaline environments is one of the major factors affecting microbial activity because the dissolved substances make the water partly unavailable to microorganisms.

Hypersaline habitats, which can vary considerably in ionic composition, are rather common in hot, dry areas throughout the world. Despite seemingly harsh conditions, these environments can be productive ecosystems where halophiles that include a range of organisms (archaea, green algae, cyanobacteria, bacteria) easily cope with osmotic stress and even can withstand in saturated NaCl [START_REF] Madigan | Extremely halophilic Archaea In[END_REF].

If the first extremophilic and halophilic virus was discovered fortuitously in 1974, consistent reports on the occurrence of viruses in such extreme habitats raised in the early 1980s from halobacteria [START_REF] Dyall-Smith | Haloarchaeal viruses: how diverse are they?[END_REF].

Viruses in hypersaline environments

Assessing the viral abundance in the hypersaline Dead Sea where magnesium concentration exceeds 50%, quantities of virus-like particles that reach easily 10 7 particles ml -1 were reported [START_REF] Oren | Occurrence of viruslike particles in the Dead Sea[END_REF]. In their study of solar salterns, Guixa-Boixareu and co-workers [START_REF] Guixa-Boixareu | Viral lysis and bacterivory as prokaryotic loss factors along a salinity gradient[END_REF] showed that both virus-like particles abundance and diversity increased with salinity and reached about 10 9 virus particles ml -1 at salinities higher than 25%. Hypersaline environments are also important reservoirs of viruses that exhibit a large genomic diversity with genome sizes varying from 10 kb to 533 kb. [START_REF] Sandaa | Virioplankton community structure along a salinity gradient in a solar saltern[END_REF]. Pulsed-field electrophoresis analysis showed that the viral population structure vary along a salinity gradient from near seawater (40 ‰) to saturated sodium chloride brine (370 ‰). Populations of virus-like genome ranging in size from 32 kb to 340kb were preponderant within 40 ‰ to 220 ‰ salinity gradients, whereas ponds with salinity higher than 220 ‰ contained virus-like genomes with size ranging from 10 to 189 kb. As changes in the total prokaryotic community structure depending on salinity were also recorded, this suggests that viral populations have a dynamic, which probably depends on their hosts' ecology [START_REF] Sandaa | Virioplankton community structure along a salinity gradient in a solar saltern[END_REF].

Considering the morphological diversity of viruses in hypersaline environments, direct observations with electronic microscope revealed a majority of lemon-shaped particles resembling the archaeal Fuselloviruses, while only some virus-like particles were of head-tail morphology [START_REF] Oren | Occurrence of viruslike particles in the Dead Sea[END_REF]. In other hand all halophilic viruses isolated from this type of habitat until now infect archaea, most of them (12/15) have a head-and-tail morphology (Fig. 1, Table 1) reminiscent of bacteriophages belonging to the three main families Myoviridae, Siphoviridae and Podoviridae, highlighting the remarkable morphological similarity between archaeal and bacterial tailed phages. Only three viruses exhibiting different morphotypes more closely related to those of hyperthermophilic archaeoviruses were also characterized. These haloviruses were the spindle-shaped His1 (Fig. 2), His2 which is pleomorphic and the spherical SH1 (Fig. 3). Such differences between direct observations and laboratory specimens suggested that characterized viruses probably did not reflect the real in situ morphological diversity. The bias resides perhaps in the fact that hosts cells easily isolated and cultivated in laboratory are not the dominant species of the natural haloarchaeal flora in hypersaline environments [START_REF] Dyall-Smith | Haloarchaeal viruses: how diverse are they?[END_REF].

All halophilic viruses described until now have genomes which consist of linear double-stranded DNA. Looking at the genome sequences, only little sequence similarity (less than 10%) with bacteria, bacteriophages and eukaryotic viruses were observed. This phenomenon could be partly due to isolation caused by such particular ecosystem [START_REF] Dyall-Smith | Haloarchaeal viruses: how diverse are they?[END_REF]. However, there are also strong genetical relationships between different haloviruses, as shown by the haloviruses фCh1 and фH which share up to 97% nucleotide identity, while their hosts, isolated from distinct and geographically distant sites, are phylogenetically different [START_REF] Klein | Natrialba magadii virus Ch1: first complete nucleotide sequence and functional organization of a virus infecting a haloalkalophilic archaeon[END_REF][START_REF] Tang | HF2: a double-stranded DNA tailed haloarcheal virus with a mosaic genome[END_REF]. The haloviruses HF1 and HF2 also have genomes that share up to 99 % nucleotide identity in the first 60 % of their sequence. However, the remainder part shows a significant divergence (87 % identity) due to numerous base changes and insertion/deletion events. This significant shift in sequence similarity suggests a recent recombination event between either the two halovirus or with another HF-like halovirus. This recombination occurrence seems to be rather common among viruses from hypersaline waters [START_REF] Tang | Haloviruses HF1 and HF2: evidence for a recent and large recombination event[END_REF][START_REF] Bath | His1 and His2 are distantly related, spindle-shaped haloviruses belonging to the novel virus group, Salterprovirus[END_REF]).

Viruses in alkaline lakes

Even if the water chemistry of soda lakes is similar to hypersaline lakes, solar salt evaporation ponds and deep-sea hypersaline basins, alkaline lakes differ by the high levels of carbonate minerals in the surroundings rocks that maintain pH ranging between 10 and 12. In addition, Ca 2+ and Mg 2+ are virtually absent because they precipitate out at high pH and carbonate concentrations [START_REF] Madigan | Extremely halophilic Archaea In[END_REF].

Bacterial abundances and seasonal changes in community composition were recorded in the past decades, but no previous reports on the occurrence of viruses merged before 2004 from such extreme habitat until Jiang and co-workers tackled the virus populations in Mono Lake, which is a large alkaline (pH~10), moderate hypersaline lake lying at the western edge of Great Basin in California [START_REF] Jiang | Abundance, distribution and diversity of viruses in alkaline hypersaline Mono Lake, California[END_REF].

In this peculiar environment, viral abundance (from 1.10 8 to 1.10 9 ml -1 ) is among the highest observed in any natural aquatic system examined so far. Pulse-field gel To date, only one lytic phage, named Mono1, has been isolated and partly characterized from this viral population (Table 1). Surprisingly, this virus strain infects a bacterial host, which is closely related to Idiomarina baltica previously isolated from surface water of the central Baltic Sea. Using Mono1 dsDNA genome as probe in hybridization experiments also revealed seasonal fluctuations in viral communities.

Viruses in deserts

In deserts, that are extremely dry and exposed to extremes of UV light irradiation and temperature variation, water is always a very limiting factor for life. Nonetheless, eukaryotic and prokaryotic microorganisms have adapted to these extreme conditions and have been found in hot desert such as the Atacama Desert of Chile [START_REF] Evans | Microbiotic crusts and ecosystem processes[END_REF].

A recent study, carried out on surface sands collected from 13 different locations in the Sahara Desert in Morocco and Tunisia, reported for the first time the presence of viruslike particles. These particles exhibit a great diversity of morphotypes representative of the three major bacteriophage families: Myoviridae, Siphoviridae and Podoviridae (Table 1). In addition, pulse-field gel electrophoresis of doublestranded DNA, extracted from the enriched bacteriophages preparations, suggests also a genetic diversity with the presence of at least four potential intact viral genomes ranging in size from 45 kpb to 270 kpb [START_REF] Prigent | A diversity of bacteriophage forms and genomes can be isolated from the surface sands of the Sahara Desert[END_REF].

Viruses in polar environments

Extreme cold environments such as high-altitude glaciers, polar permafrost, the Dry Valleys of Antarctica, which are the coldest and driest desert on the earth, as well as sea ice, also provide habitats from microbial life (Staley & Gosink 1999). Annual sea ice in the Arctic develops important and dynamic microbial communities [START_REF] Grossi | Sea ice microbial communities. III. Seasonal abundance of microalgae and associated bacteria, McMurdo Sound, Antarctica[END_REF][START_REF] Kottmeier | Sea ice microbial communities. VII. Bacterial production in annual sea ice of Mc Murdo Sound, Antartica[END_REF]Smith et al. 1989). In Antarctica, microorganisms, including prokaryotes and microeukaryotes thrive in sea ice and cold water [START_REF] Thomas | Antarctic sea ice-a habitat for extremophiles[END_REF]. Several well-documented studies reported the presence of viruses and the relationship between viral and bacterial production in Arctic and Antarctic sea ice and in perennially ice-covered lakes located in Taylor Valley, Antarctica.

In Artic sea ice, viral abundance was recorded to be very high as showed by direct counts (9.10 6 ml -1 to 3.10 8 ml -1 ).

This value, which was 10-to 100-fold greater than the concentration of viruses in the underlying sea water (1.1.10 6 ml -1 ), corresponded with the bacterial abundance in sea ice compared to the water column. Viral proliferation appeared to be enhanced in sea ice relative to open water. Moreover, the virus-to-bacteria ratios were among the highest reported in natural samples, providing the first account of viruses as a dynamic component of sea ice microbial communities [START_REF] Maranger | Viral and bacterial dynamics in Arctic sea ice during the spring algal bloom near Resolute, N.W.T., Canada[END_REF].

Three distinct phage-host systems (Table 1), which are highly dependent of low temperature conditions, were also Interestingly, samples of Ross Sea pack ice in Antarctic revealed that the range of total viral abundance was similar with the concentration found in Artic sea ice (between 5.2 10 6 ml -1 to 3.5 10 8 ml -1 ). TEM observations showed that the viruses, which compose the population, are large, with 40% icosahedral, 37% spherical and 23% lumpy forms, and all of them likely infect microeukaryotes [START_REF] Gowing | Large viruses and infected microeukaryotes in Ross Sea summer pack ice habitats[END_REF].

In Antarctic perennially ice-covered lakes, which are microbially dominated ecosystems, virus densities seemed to be less important than in sea ice with a maximum value that reached 3.4 10 7 ml -1 . Nevertheless, this virus abundance was higher than in other freshwater or marine systems and the viral population appeared to be highly active in the water column. Many of viruses were found to be large icosahedral specimens, morphologically similar to double-stranded DNA viruses isolated from temperate environments that infect photosynthetic and non-photosynthetic flagellates [START_REF] Kepner | Viruses in Antarctic lakes[END_REF].

Viruses in deep subsurface sediments

The deep subsurface biosphere is one of the least-understood habitats on Earth, even though the huge microbial biomass therein likely plays an important role on global biogeochemical cycles. Recently, the Ocean Drilling Program (ODP) revealed that chemolithotroph microbes thrive in anoxic reducing environments under oceans and continents to depths of >1000 m despite harsh conditions (i.e.

high hydrostatic pressure, anaerobiosis and low concentration in organic nutrients). Prokaryotic biomass in deep marine sediments exceeds 10 5 microbial cells cm -3 even at depths close to 1,000 mbsf [START_REF] Parkes | Deep bacterial biosphere in Pacific ocean sediments[END_REF][START_REF] Parkes | Recent studies on bacterial populations and processes in subseafloor sediments: a review[END_REF].

Viruses in extreme thermal environments

Live has also adapted to hot temperatures. Given that early branching organisms could have been hyperthermophiles

among Archaea and thermophiles among Bacteria, looking for viruses in such extreme environment may provide interesting information about virus evolution in the early cellular life. The recent observations indicated that terrestrial and oceanic hydrothermal environments represent a bottomless reservoir of a truly remarkable morphological and genomic viral diversity.

Viruses from terrestrial hot springs

Early studies on viruses of hyperthermophiles were pioneered in the laboratory of Wolfram Zillig in the 1980s. A systematic screening of surface hot springs located in Japan, Iceland, New Zealand, Italy, Russia and the United States led to the isolation of an unprecedented diversity of new viruses (Fig. 4) [START_REF] Rice | Viruses from extreme thermal environments[END_REF][START_REF] Rachel | Remarkable morphological diversity of viruses and virus-like particles in hot terrestrial environments[END_REF]Prangishvili and Garrett, 2005).

The vast majority of the hyperthermophilic viruses isolated from acidic or neutral hot springs (>80°C) were found to infect a broad spectrum of members of the extremely thermophilic Crenarchaeaota, including representatives of the genera Sulfolobus, Thermoproteus, Acidianus, Pyrobaculum (Table 1). Based on their exceptional morphology and genomic properties the 2006). Few significant sequence matches were obtained with either bacterial or eukaryal genes and very few genes have been assigned functions. However, there is some evidence that a 37-kDa coat protein of the Sulfolobus turreted icosahedral virus (STIV) can generate a tertiary and quaternary structure similar to that of capsid proteins of bacterial and animal viruses, despite the lack of significance gene similarity. This suggests that some viruses may have a common ancestor that precedes the division into three domains of life [START_REF] Rice | The structure of a thermophilic archaeal virus shows a double-stranded viral capsid type that spans all domains of life[END_REF][START_REF] Khayat | Structure of an archaeal virus capsid protein reveals a common ancestry to eukaryotic and bacterial viruses[END_REF]. The fact that for most of these viruses, analysis of their genomes showed little or no similarity to genes in the public databases suggests that all these newly discovered viruses employ novel biochemical mechanisms for viral functions.

All viruses of acidophilic hyperthermophiles (except TTV1 and ATV) are non lytic and persist in host cells in a stable state (pseudolysogeny or "carrier state"). It was hypothesized that such a survival strategy was beneficial for viruses, helping them to avoid direct exposure to the harsh conditions of the host habitat (Prangishvili andGarrett 2004, 2005).

However, hyperthermophilic viral populations, which can reach concentrations of a million viruses per milliliter, were also reported to be resistant to shifts to lower temperature in their natural ecosystem [START_REF] Breitbart | Phage community dynamics in hot springs[END_REF]). Breitbart and co-workers showed that more than 75 % of phage particles collected from Californian hot springs remained physically intact when incubated on ice. Moreover, they are dynamic and actively produced in situ with a population turnover time of one or two days. As viruses are the only known microbial predators in this extreme environment, they exert likely an important influence on the microbial community via a high virus-mediated microbial mortality.

Viruses from deep sea hydrothermal vents

Deep-sea-vent areas are one of the most extreme habitats on Earth. They are characterized by high hydrostatic pressures, hot (400°C) to warm (10-30°C) temperatures and the hydrothermal fluids are acidic, reduced and enriched with chemicals including heavy metals, methane and hydrogen sulphide (Prieur 1997).

Recently, systematic searches carried out on samples collected in various geographically distant hydrothermal sites revealed high and unexpected abundance and diversity of viruses in deep-sea hydrothermal vents. Viral abundance was recorded to be high as showed by direct counts (1.45.10 5 to 9.9.10 7 ml -1 ). High viral abundance at active vents, relative to those in surrounding waters, indicated viral production and hence, virus mediated microbial mortality [START_REF] Ortmann | High abundances of viruses in deep-sea hydrothermal vent system indicate viral mediated microbial mortality[END_REF].

Considering the morphological diversity, direct observations with electronic microscope revealed a great morphological diversity. With the exception of the filamentous and rod-shaped morphotypes which are also known for the Bacteria, the morphologies seemed to be characteristic of archaeal viruses. Indeed, the lemon-shaped type prevailed and novel pleomorphic morphologies such as "spoon-shaped" and spindle particles with bipolar expansions were also discovered. The exotic morphological similarities exhibited by viruses from both deep-sea and terrestrial hot environments are very astonishing. For example, the presence of lemon-shaped viruses in diverse extreme environments (salterns, subsurface anaerobic sediments, acidic thermophilic continental solfatara and deep-sea vents) in addition to the fact that this morphotype has never been found among the Bacteria or Eucarya strengthens the idea of their specificity to the archaeal domain and probably reflects a deep evolutionary history within this domain (Geslin et al. 2003a).

One of these deep-sea hyperthermophilic viruses was successfully purified and was further characterized (Table 1).

This virus, named PAV1, is lemon-shaped (120 nm x 80 nm)

with a short tail terminated by fibers and infects the hyperthermophilic euryarchaeota Pyrococcus abyssi. PAV1 persists in the host strain in a stable carrier state. PAV1

genome consists of a double-stranded circular DNA of 18 kb, which is also present in high copy number in a free form in the host cytoplasm. Viral genome comparisons with all other archaeal, bacterial or eukaryal viruses do not reveal any significant similarity (Geslin et al. 2003b).

Concluding remarks

Despite the ubiquity of viruses, until recently relatively little was known about viruses in extreme environments because in many instances the extreme growth conditions required by extremophiles have precluded a search for viruses. However, over the past few years our knowledge of viruses in extreme environments considerably increased.

Tracking viruses in ecological niches with seemingly harsh conditions has been successful and the presence of virus populations has been consistently detected in all the explored environments. All viral communities appeared to be substantially abundant to the populations rate that are often greater than in standard environments (e.g. 10 9 ml -1 in solar salterns, 3.5 10 8 ml -1 in Antarctic sea ice). All viruses isolated so far from extreme environments are double-stranded DNA viruses with moderate genomic complexity (the genome size range from 14 to 80 kb). It is conceivable that this very stable form of genome may be necessary to face harsh constraints of extreme habitats. It could also explain why no RNA virus has been isolated yet, especially from hot environments.

However, PFGE analysis used to depict the viral community structure (e.g. in desert and hypersaline habitats environments) produces evidence of a more complex diversity with the recovering of uncharacterized large dsDNA viruses.

The viral communities seem also to be genetically distinct, suggesting specific niche adaptation and great diversity.

Nevertheless, at this stage of the knowledge, little is known of their origin, activity, or importance to the in situ microbial dynamics and continuous attempts to isolate and to study viruses that thrive in extreme environments will be needed to address such questions. Moreover, several terrestrial extreme environments are still unexplored, e.g. evaporites, subglacial Antarctic lakes like Lake Vostok, where the DNA signature of a thermophilic bacteria (Hydrogenophilus sp.) has been detected [START_REF] Bulat | DNA signature of thermophilic bacteria from the aged accretion ice of Lake Vostok: implications for searching life in extreme icy environments[END_REF] or the stratosphere and its airborne biota.

Exploring the virus diversity in extreme environments,

  electrophoresis revealed length of dsDNA viral genomes ranges from 14 up to 400 kbp, with a majority between 30 kpb to 60 kbp and the analysis of band patterns highlighted at least three dominant clusters of populations defined on the similarities in the viral genome size distribution. Thus, deepwater viral community represents a distinct group from surface and mid-water viral communities suggesting a strong stratification of viral distribution between oxic and anoxic waters.

  isolated and characterized from samples of Artic sea ice collected in north-west of Svalbard. The hosts are psychrophilic bacteria whose closest relatives are Shewanella frigidimarina, Flavobacterium hibernum and Colwellia psycherythrae, respectively. The three phages, which are lytic and host-specific, showed an even more pronounced adaptation to cold temperatures than their hosts did. In fact, phage development was clearly restricted to a lower temperature maximum in comparison to the maximal growth temperature of the host bacterium. Transmission electron microscopy (TEM) observations revealed that these polar phages having a dsDNA genome are morphologically similar to the double-stranded DNA phage families Siphoviridae and Myoviridae and (Borriss et al. 2003).

  Presence of viruses in buried marine sediments was investigated recently after drilling a hole at 228.7 meters below sea seafloor to a depth at 105.1 mbsf and 118.2 mbsf, near the west Canadian coast[START_REF] Bird | Subsurface viruses and bacteria in Holocene/Late Pleistocene sediments of Saanich Inlet, BC: ODP Holes 1033B and 1034B, Leg 169[END_REF]. Analyses revealed the existence of large amounts of viruses. Viral abundances appeared to follow bacterial numbers very closely with an average up to 10 9 g -1 of dry sediment at 105.1mbsf. Even if microbial communities seemed to be stratified in subseafloor sediments, nothing is known about the viral diversity and the interactions between viral and prokaryotic communities. Nonetheless, given the scarcity of eukaryotic bacterivores in deep marine sediments, the only source of mortality by external agents for the bacterial community lies in phage attack. Thus, considering bacterial and viral abundances being highly correlated, viruses appear to be potential actors of subsurface sediments biogeochemistry.

  Lipothrixvidae, stiff rod-shaped Rudiviridae, droplet-shaped Guttaviridae, spherical Globuloviridae, two tailed spindle-shaped Bicaudaviridae and bottle-shaped Ampullaviridae. The International Committee of Taxonomy of Viruses has already approved the first four families. The crenarchaeal viruses showed no clear similarities in their morphologies or at the genomic level to either bacterial or eukaryal viruses, except perhaps members of three viral families. The rodshaped virions of the Rudiviridae and Liphotrixviridae resemble tobamoviruses and closteroviruses of vascular plants, respectively, while those of the Globuloviridae resemble that of viruses of the Paramyxoviridae, which infect vertebrates. The 25 hyperthermophilic viruses isolated so far exhibited double-stranded DNA genomes, linear or circular of 15 to 75 kb, most of them being sequenced and revealing an amazing diversity at the genomic level (Prangishvili et al.

FiguresFigure 1 :

 1 Figures

Figure 2 :

 2 Figure 2: Negative stain electron microscopy of spindle-

Figure 3 :

 3 Figure 3: Negative stain electron microscopy of spherical

Figure 4 :

 4 Figure 4: Transmission electron microscopy of virus and

TABLE : Table 1 :

 :1 Main features of the extremophilic viruses so far characterized in extreme environments.

Acknowledgements

Many thanks to the Editorial Board of Reviews in Environment Science and Bio/Technology for the invitation to contribute this review. MLR and DP thank the European Science Foundation for the invitation to the ESF workshop on "Investigating life in extreme environments" in Sant Feliu de Guixols, Spain, November 2005. Two anonymous reviewers provided very constructive suggestions that improve the paper. MG is funded through a PhD grant from the Ministère National de l'Enseignement et de la Recherche.

Porter K, Kukkaro P, Bamford JK, Bath C, Kivela HM, Dyall-Smith ML and Bamford DH (2005)


Shlomi Dolev
email: dolev@cs.bgu.ac.il.

Swan Dubois

Maria Potop-Butucaru

Sébastien Tixeuil

Stabilizing Data-Link over non-FIFO Channels with Optimal Fault-Resilience

Self-stabilizing systems have the ability to converge to a correct behavior when started in any configuration. Most of the work done so far in the self-stabilization area assumed either communication via shared memory or via FIFO channels.

This paper is the first to lay the bases for the design of self-stabilizing message passing algorithms over unreliable non-FIFO channels. We propose an optimal stabilizing data-link layer that emulates a reliable FIFO communication channel over unreliable capacity bounded non-FIFO channels.

Introduction

Self-stabilization [START_REF] Edsger | Self-stabilizing systems in spite of distributed control[END_REF][START_REF] Shlomi | Self-stabilization[END_REF][START_REF] Tixeuil | Algorithms and Theory of Computation Handbook, Second Edition, chapter Self-stabilizing Algorithms[END_REF] is one of the most versatile techniques to sustain availability, reliability, and serviceability in modern distributed systems. After the occurrence of a catastrophic failure that placed the system components in some arbitrary global state, self-stabilization guarantees recovery to a correct behavior in finite time without external (i.e. human) intervention.

As self-stabilization is usually considered a hard property to satisfy, most related works used a simple communication model where processes can determine the current state of every neighbors (and update their own state accordingly) in an atomic manner (this model is referred to in the literature as the state model or systems with central/distributed daemon). Asynchronous message passing is a more realistic way, compared to the state model, for the communication of processes in distributed systems. In such settings processes communicate by exchanging messages, where sending and receiving message are two separate atomic actions. Transformers for shared memory protocols to act in message passing systems, assuming the existence of FIFO channels, have been suggested, see e.g. [START_REF] Dolev | Self-stabilization of dynamic systems assuming only read/write atomicity[END_REF][START_REF] Shlomi | Self-stabilization[END_REF]. At the core of those transformers are the data-link protocols, that permit to reliably exchange information between neighboring processes in the message passing model. In addition, several self-stabilizing protocols (i.e. [START_REF] Dolev | Empire of colonies: Self-stabilizing and self-organizing distributed algorithms[END_REF][START_REF] Noga Alon | Brief announcement: Sharing memory in a self-stabilizing manner[END_REF]) that are directly written in the message-passing model use an underlying data-link protocol as a building block.

Related Works. The most studied data-link protocol, namely the alternating bit protocol (ABP), was proved to satisfy some stabilization properties [START_REF] Afek | Self-stabilization over unreliable communication media[END_REF][START_REF] Dolev | Resource bounds for self-stabilizing messagedriven protocols[END_REF][START_REF] Burns | Stabilization and pseudostabilization[END_REF]: in any execution of ABP, there exists a suffix that satisfies the specification (i.e. the ABP is pseudo-stabilizing). However, the impossibility to bound the amount of time before this suffix is reached makes the ABP unsuitable for most tasks. In [START_REF] Gouda | Stabilizing communication protocols[END_REF][START_REF] Dolev | Self-stabilization of dynamic systems assuming only read/write atomicity[END_REF], Gouda and Multari and Dolev, Israeli, and Moran independently prove that for a wide class of problems (including data-link construction) guaranteeing self-stabilization when channels have unbounded initial capacity requires some kind of unboundedness in the protocol (either unbounded memory in [START_REF] Gouda | Stabilizing communication protocols[END_REF], the existence of some aperiodic function [START_REF] Afek | Self-stabilization over unreliable communication media[END_REF], or access to a probabilistic variable [START_REF] Afek | Self-stabilization over unreliable communication media[END_REF]). In other words, those approaches require to implement unbounded capacities with finite memory, and are thus unlikely to be actually used in real systems. Also, the expected time before reaching a stable global state depends on the initial contents of communication channels, and is thus unbounded.

Most recent works took the more realistic approach of assuming channels with bounded initial capacity. The token passing protocol in [START_REF] Dolev | Resource bounds for self-stabilizing messagedriven protocols[END_REF] can be used as a self-stabilizing ABP on bounded channels and only uses bounded memory. Howell et al. [START_REF] Howell | Finite-state self-stabilizing protocols in message-passing systems[END_REF] provide another data-link protocol over bounded channels with the additional desirable property that the underlying communication channels are unreliable (i.e. they may loose or duplicate messages). Later, Varghese [START_REF] Varghese | Self-stabilization by counter flushing[END_REF] presented self-stabilizing solutions for a wide class of problems (including data-link) in the same setting using only bounded memory. The FIFO ordering is crucial for the stabilization since solution relies on the fact that a sequence number that is unique in the system is eventually generated and flushes every stale message in transit. A common drawback of all aforementioned self-stabilizing data-link solutions is that they assume a FIFO order on messages in the underlying communication channels.

A notable exception are the protocols provided in [START_REF] Beauquier | Fault-tolerance and self stabilization: impossibility results and solutions using self-stabilizing failure detectors[END_REF] that assumed a non-FIFO message passing system. The main difference with our approach stands in the fact that their system is enhanced with some failure detector whereas we assume a fully asynchronous system.

Another drawback of previously mentioned self-stabilizing data-link solutions is that they do not consider the quantitative impact of faults from the perspective of the upper layer protocol (i.e. the layer that actually uses the data-link). Indeed, starting from an arbitrary global state where channels may initially contain messages of arbitrary content, being able to bound the number of messages sent that are lost or duplicated, or the number of fake messages that are actually delivered to the destination is a very important matter. The bound on the number of faulty messages delivered by a data-link protocol is an important criteria for the data-link usability in larger application, in order to ensure the fault-resiliency of the global protocol stack. To our knowledge, only [START_REF] Dolev | Empire of colonies: Self-stabilizing and self-organizing distributed algorithms[END_REF][START_REF] Delaët | Snapstabilization in message-passing systems[END_REF] addresses, to some extent, this concern. A snap-stabilizing data-link (and global reset) for bounded capacity FIFO channels appears in [START_REF] Dolev | Empire of colonies: Self-stabilizing and self-organizing distributed algorithms[END_REF]. In [START_REF] Delaët | Snapstabilization in message-passing systems[END_REF] a snap-stabilizing solution to the propagation of information with feedback (PIF) problem is presented. The solution can be seen as a data-link protocol when reduced to a 2-processes system. Snap-stabilization implies that any message that is actually sent by the sender process is eventually received by the receiver process, so the number of lost messages is 0. However, we cannot provide bounds on the number of duplications of a given message or on the number of ghost messages (that is, messages that are not sent by the sender but received by the receiver due to the arbitrary content of communication channels in the initial configuration). Concerning the self-stabilizing protocols, only an order of magnitude on those numbers can be inferred from the stabilization time (if m messages sent or received are required to enter a legitimate global state from any arbitrary initialization, then at most m messages could be lost, duplicated, or wrongly delivered). To our knowledge, the question of fault-resilience optimality for data-link protocols has never been raised before, although it has important practical consequences.

Our contribution. Our contribution in this paper is twofold:

1. We define complexity metrics that are related to the fault-resilience of data-link protocols, and present impossibility results in the context of self-stabilization (i.e. the ability to recover from any arbitrary initial global state). In particular, we prove that no data-link protocol can prevent one message duplication, the delivery of a single fake message, or the reordering of a single message.

2. We present a data-link protocol that is optimal with respect to all presented fault-resilience metrics. Moreover, unlike previous self-stabilizing solutions that operate assuming the underlying communication channels preserve FIFO ordering, the channels we consider may indeed reorder messages, having some of them remain in the channel for an arbitrary long time. The strong fault-resilience property exhibited by our protocol makes it particularly suitable for inclusion as a building block in more complex applications.

Paper organization. The paper is organized as follows. Section 2 proposes the network model and hypothesis and then, the data-link problem specification. Section 3 introduces three lower bounds results that justify our optimality claim. In Section 4, we propose our optimal stabilizing data-link protocol altogether with its correctness proof.

Model

System Model

A message-passing distributed system consists of n processes, p 0 , p 1 , p 2 , . . . , p n-1 , connected by communication links through which messages are sent and received. Two processes connected through a communication link are referred in the following as neighboring processes.

As emphasized in [START_REF] Afek | Self-stabilization over unreliable communication media[END_REF] the purpose of a data-link protocol is to reliably transmit messages from one end of a communication medium (link) to the other end. Ideally, messages have to arrive without duplication or loss and in the order they have been sent. Therefore, we focus in the following on the communication between two neighboring processes p i and p j where p i acts as the sender and p j acts as the receiver. The communication link between the two processes p i and p j is denoted in the following (p i , p j ) and is composed of two virtual directed channels (i, j) and (j, i). The channel (i, j) is used to send messages from p i to p j while the channel (j, i) is used to send acknowledgments from p j to p i . In systems where p j is also message sender, two additional virtual channels are used to carry the messages from p j to p i and acknowledgments from p i to p j .

We assume in the following that the capacity of each directed channel is c packets (i.e. low level messages). Note that in the scope of self-stabilization, where the system copes with an arbitrary starting configuration, there is no deterministic data-link simulation that uses bounded memory when the capacity of channels is unbounded [START_REF] Gouda | Stabilizing communication protocols[END_REF][START_REF] Dolev | Resource bounds for self-stabilizing messagedriven protocols[END_REF].

The channels are non-FIFO and not necessarily reliable (i.e. packets may not follow the FIFO order and may be lost). Additionally, their delivery time is unbounded. That is, any non lost packet is received in a finite but unbounded time. Each channel (i, j) is weakly fair in the sense that if the sender sends infinitely often a packet on the channel, then the receiver receives this packet an infinite number of time. Sending a packet to a channel whose capacity is exhausted (i.e. the channel already contains c packets) results in loosing a packet (either a packet already in the channel or the packet being sent).

As we deal with arbitrary initial corruption, a channel may initially contain up to c ghost packets (i.e. packets that have never been sent and contain arbitrary content).

A processor is modeled by a state machine that executes steps. Channels are modeled as sets (rather than queues to reflect the non-FIFO order). For example, the c-bounded channel (i, j) (used to send messages from p i to p j ) is modeled by a c-sized set denoted by s ij .

In each step, a processor changes its local state (i.e. the state of its local memory), and executes a single communication operation, which is either a send operation or a receive operation. The communication operation changes the state of an attached channel. In case the communication operation is a send operation from p i to p j then s ij is a union of s ij in the previous state with the sent packet. If the obtained union does not respect the bound |s ij | ≤ c then an arbitrary message in the obtained union is deleted. In case the communication operation is a receive operation of a (non null) packet m (m must exist in s ji of the previous state), then m is removed from s ji . A receive operation by p i from p j may result in a null packet even when the s ji is not empty, thus allowing unbounded delay for any particular packet. Packet losses are modeled by allowing spontaneous packet removals from the set.

A configuration of the system is the product of the local states of processes in the system and of their incident channels.

An execution is a sequence of configurations,

E = (C 1 , C 2 , . . .) such that C i , i > 1, is obtained from C i-1
when at least one process in the system executes a step.

Problem Specification

The specification we provide in this section is borrowed from [START_REF] Lynch | Distributed Algorithms[END_REF] but we adapt it to the selfstabilizing context. In particular, we introduce the idea to bound the number of lost, duplicated, ghost and re-ordered messages by some constants.

Consider a system of two processors p i and p j . A distributed application needs to send some messages from p i to p j . We say that the application layer of p i sends a message when it requests the communication protocol to carry this message to p j . This message is delivered to p j when the communication protocol releases this message to the application layer of p i . A ghost message is a message delivered to p j whereas p i did not send it previously (due to the arbitrary content of communication channels in the initial configuration). A duplicated message is a message that is delivered several times to p j whereas p i sent it only once. A message is lost when p i sends it but p j never delivers it. A message m is reordered when it is delivered to p j before a message m ′ whereas m has been sent after m ′ by p i . Intuitively, the goal of a Stabilizing Data-Link protocol is to provide a communication black box that ensures some properties on the number of lost, duplicated, ghost and reordered messages starting from any arbitrary configuration. In the sequel, we formally specify the Stabilizing Data-Link problem

We associate to any execution E the sequence

S(E) = m 0 m 1 m 2 . . . of messages sent by p i in E and the sequence R(E) = m ′ 0 m ′ 1 m ′ 2 .
. . of messages delivered to p j in E. Note that we consider that all sent messages are different (even if their actual content are identical, we can distinguish them as external observer of the system). We introduce the following notations. For any sequence W and any integers i and j, W j is the prefix of W of length j and W i is the suffix of W such that W = W i-1 W i . The notation ǫ denotes the empty sequence. For example, R(E) 0 = ǫ. For any message m, we define the m * as the repetition of m an arbitrary number of times (possibly 0). For any sequence W , the sequence W * is the result of the application of the * operator to each message of W .

For any non negative integers α, β, γ, and δ, the (α, β, γ, δ)-Stabilizing Data-Link communication over c-bounded channels satisfies the following properties starting from an arbitrary configuration (with p i and p j being respectively the sender and the receiver) for any execution E:

• α-Loss: The first α messages sent by p i (in the worst case) may be lost.

∃a ≤ α, ∀m ∈ S(E) a , m ∈ R(E)
• β-Duplication: The first β messages delivered to p j (in the worst case) may be duplicated ones.

∃b ≤ β, ∀m ∈ S(E), |{m ′ i = m|m ′ i ∈ R(E)}| > 1 ⇒ m ∈ R(E) b
• γ-Creation: The first γ messages delivered to p j (in the worst case) may be ghost messages.

∃c ≤ γ, ∀m ∈ R(E), m / ∈ S(E) ⇒ m ∈ R(E) c
• δ-Reordering: The first δ messages delivered to p j (in the worst case) may be reordered.

∃d ≤ δ, R(E) d = S(E) *
In the following section, we show that it is impossible to perform a (α, β, γ, δ)-Stabilizing Data-Link communication with β = 0, γ = 0, or δ = 0. Then, we can deduce that a (0, 1, 1, 1)-Stabilizing Data-Link communication achieves optimal fault-resiliency. The above definitions imply that such a communication protocol ensures that R(E) = S(E) or R(E) = m.S(E) (where m is an arbitrary message, it may be present in S(E)) for any execution E. In other words, the sequence of received messages by p j is identical to the sequence of emitted messages by p i excepted the first delivery in the worst case.

Lower Bounds

In this section, we propose three impossibility results related to the possible values for the parameters β, γ, and δ. We prove that the lower bounds for β, γ, and δ parameters is 1. These results confirm the claim that the protocol we propose is optimal since it implements a (0, 1, 1, 1)-Stabilizing data-link.

Theorem 1 There exists no (α, β, γ, δ)-Stabilizing Data-Link communication algorithm over cbounded channels with γ = 0.

Proof: By contradiction, let A be any (α, β, 0, δ)-Stabilizing Data-Link communication algorithm over c-bounded channels must have an instruction that delivers messages to the receiver processor. As the program counter may be corrupted and channels may contain up to c ghost messages in the initial configuration, the receiver processor may execute this instruction during the first step of an execution E. In consequence, the first message of R(E) may be a ghost message m. Hence, we can assume that R(E) 1 = m.

It is possible to construct the execution E such that m / ∈ S(E). In conclusion, we have: ∃m ∈ R(E), m / ∈ S(E) ∧ m / ∈ R(E) 0 = ǫ (recall that ǫ denotes the empty sequence). This is contradictory with the 0-Creation property of A and implies that γ ≥ 1 for any (α, β, γ, δ)-Stabilizing Data-Link communication algorithm over c-bounded channels.

2

Theorem 2 There exists no (α, β, γ, δ)-Stabilizing Data-Link communication algorithm over cbounded channels with β = 0.

Proof: By contradiction, let A be any (α, 0, γ, δ)-Stabilizing Data-Link communication algorithm over c-bounded channels. Following Theorem 1, we have γ > 0. This implies that the first message delivered to p j in an execution E by A may be a ghost message m. Hence, we can assume that

R(E) 1 = m.
It is possible to construct the execution E such that the first (real) message sent by p i to p j and delivered to p j by A is the same message m. This message has been sent by p i only once but has been delivered to p j at least twice. In conclusion, we have:

∃m ∈ S(E), |{m ′ i = m|m ′ i ∈ R(E)}| > 1 ∧ m /
∈ R(E) 0 = ǫ (recall that ǫ denotes the empty sequence). This is contradictory with the 0-Duplication property of A and implies that β ≥ 1 for any (α, β, γ, δ)-Stabilizing Data-Link communication algorithm over c-bounded channels.

2

Theorem 3 There exists no (α, β, γ, δ)-Stabilizing Data-Link communication algorithm over cbounded channels with δ = 0.

Proof: By contradiction, let A be any (α, β, γ, 0)-Stabilizing Data-Link communication algorithm over c-bounded channels. Following Theorem 1, we have γ > 0. This implies that the first message delivered to p j by A in an execution E may be a ghost message m. Hence, we can assume that R(E) 1 = m. It is possible to construct the execution E such that S(E) α+2 = m 0 m 1 . . . m α-1 m α m and ∀i ∈ {0, . . . , α}, m i = m. As A satisfies the α-Loss and the 0-Reordering properties, it follows that ∃i ∈ {0, . . . , α}, R(E) 1 = m i (otherwise, we have a contradiction since either A lost at least α + 1 messages or reordered at least one message, that is contradictory). As m i = m, we obtain a contradiction that shows that δ ≥ 1 for any (α, β, γ, δ)-Stabilizing Data-Link communication algorithm over c-bounded channels. 2 In the next section, we present a protocol that is optimal with respect to α, β, γ, and δ parameters. That is, our protocol satisfies the (0, 1, 1, 1)-Stabilizing Data-Link specification.

4 A (0, 1, 1, 1)-Stabilizing Data-Link Protocol

Presentation of the Protocol

Key ideas of the protocol. The rationale of the protocol consists in adding safety extensions to the well-known alternating bit protocol (a.k.a. ABP). The concept used in the design of the data-link protocol is to let the sender use a mechanism based on the capacity c of communication channels so that the sender can ensure the execution of an operation in the receiver side. More precisely, the receiver acts only upon receiving a packet from the sender. The sender may repeatedly send a particular packet, and each time the receiver receives a packet it acknowledges the packet arrival.

First, the receiver can deliver a message only if c + 1 copies of this message have been previously received: this ensures that at least one of them is genuine (i.e. was actually sent by the sender). Moreover, a message is delivered only if the expected bit alternates with the one of the previously received message (similarly to the ABP) in order to ensure that no message is duplicated. Indeed, the sender may still send copies of the message with the same alternating bit value until it receives a sufficient number of acknowledgments.

Second, the sender will expect for each message sent at least 3c + 2 acknowledgments with a matching alternating bit. As up to c acknowledgments could be ghost, this implies that 2c + 2 of these acknowledgments were actually sent by the receiver. One such acknowledgment could be sent by the received due to bad initialization, c of them could be due to c initial ghost messages in the reverse direction, and the remaining c + 1 can only originate from genuine messages from the sender, that triggered a delivery at the receiver.

At this stage, the protocol does not ensure the 0-Loss property due to the use of the alternating bit. Indeed, if the alternating bit values of the sender and of the receiver are not synchronized at the first delivery, the receiver drops the first message. To avoid this message loss, the sender alternates between actual messages and synchronization messages. In other words, to send a message m, the sender first sends a synchronization message (denoted by < SY N CHRO >) until it receives 3c + 2 acknowledgments of this synchronization message and then send the actual message m until it receives 3c + 2 acknowledgments of m. It follows that only the synchronization message may be lost and the actual message is always delivered to the receiver.

General organization of the system. Our system is organized as follows. The application layer generates messages to be send from p i to p j . To perform this goal, it invokes our stabilizing data-link protocol. Furthermore, this layer invokes procedures provided by the physical channel.

In more details, the stabilizing data-link protocol is composed of two functions: Send (which is executed on the sender side) and Receive (which is executed on the receiver side). When the application layer on the sender side wants to send a message m, it invokes Send(m). Send procedure is blocking, that is if Send is already in execution, the application layer waits its termination whereas the Receive function is always executed on the receiver side. When the Receive function has a message to deliver at the application layer on the receiver side, it executes DeliverMessage(m) that transmits m to the application layer. When the Receive function wants to discard a synchronization message (since this kind of messages is useless to the application layer), it uses the DropMessage function that only deletes the message. Finally, each delivered message is acknowledged to the application layer on the sender side by DeliverAck(m).

Functions Send and Receive must interact with the physical channel in order to exchange messages. For this, we assume that the channel provides two operations. First, it provides an operation to send a message or an acknowledgment, respectively SendPacket(m,ab) and SendPacket(ack,(m,ab)) where m is the message and ab its alternating bit value. This operation puts m (or its acknowledgment) in the channel if it is possible (if this operation leads to more than c messages in the channel, one of them is arbitrarily deleted). Second, it provides an operation to receive a message or an acknowledgment, respectively ReceivePacket(m,ab) and ReceivePacket(ack,(m,ab)) where m is the message and ab its alternating bit value. On the receiver side, ReceivePacket(m,ab) is executed when the channel has a message to deliver and when Receive is not in execution. It sets then m and ab to actual values of the delivered message. In other words, the reception (for the data-link protocol) on the receiver side is message-driven. On the sender side, ReceivePacket(ack,(m,ab)) is executed by the data-link protocol and does polling. That is it checks whether the first waiting message in the channel (if any) matches with an acknowledgment of the parameter (m,ab). It returns true if this is the case, false otherwise. In any case, the first waiting message (if any) is deleted from the channel. The architecture of our system is summarized in Figure 1.

Detailed presentation of the protocol. Our (0, 1, 1, 1)-stabilizing data-link protocol SDL is presented as Figure 2. In the following, we provide details about the two functions Send and Receive.

The function Send takes a message m as parameter and stores the current alternating bit value in the variable ab. First, it alternates the value of ab (line 01) before sending a synchronization message (line 02) using an auxiliary function SendMessage. Then, lines 03 and 04 repeat these instructions with the message m. Once the last invocation of SendMessage returns, it delivers to the application layer the acknowledgment of m using DeliverAck. Now, let us describe the auxiliary function SendMessage. This function repeatedly (while loop of line 02) sends its parameter message m (line 03) until receiving 3c + 2 acknowledgment for this message (line 04-05).

The function Receive takes no parameter and uses two variables. The first one is the alternating bit value of the last delivered or dropped message stored in last delivered and the second one is a queue Q that stores the number of receptions of at most c + 1 different messages. Each element of this queue is a 3-tuple (m, ab, count), where m is a message, ab is an alternating bit value, and count is an integer denoting the number of packets (m, ab) received for the corresponding m and ab since the last DeliverMessage or DropMessage occurred. The queue [] operator takes a message m and a boolean b as operands, and either enqueues (m, ab, 0) (if (m, ab, * ) is not present in Q, then if the queue contained c + 1 elements, the last element of the queue is dequeued) or returns a pointer to the count value associated to m and ab in Q. Any time a tuple value is changed in the queue, this tuple is promoted at the top of the queue (in order to keep in memory the c + 1 latest received messages), and the size of the queue does not change. The ⊥ assignment to a queue Q denotes the fact that Q is emptied. At each reception of a message (m, ab) (line 01), the corresponding entry in the queue is updated (or created if needed) by line 02. If p j already received c + 1 copies of m since the last DeliverMessage or DropMessage occurred (test on line 03) then the queue is emptied (line 10). Moreover, if the alternating bit value of the message is different from last delivered (test on line 04), then the message is either delivered with DeliverMessage (line 06) or dropped with DropMessage (line 08) depending if it is a synchronization message or not (test on line 05). Then, the last delivered value is updated by line 09. Finally, in any case, the message is acknowledged to the sender with line 11.

Correctness Proof

In this section, let p i and p j be two neighboring nodes that execute SDL, p i being the sender and p j the receiver. Let E = (C 1 , C 2 , . . .) be an execution starting from an arbitrary configuration.

We say that a message m ′ is processed by p j when p j executes DeliverMessage (m ′ ) (line 06 of Receive function) if m ′ is a normal message or when p j executes DropMessage (m ′ ) (line 08 of Receive function) if m ′ is a < SY N CHRO > message.

First, we need two preliminaries results related to the result of the execution of the procedure SendMessage by p i depending on the configuration in which p i starts to execute this procedure.

Lemma 1 When p i starts to execute SendMessage (m ′ , ab) in a configuration where ab = last delivered, the message m ′ (either a < SY N CHRO > message or a normal message) and every message parameter to a subsequent invocation of SendMessage is processed by p j in a finite time.

Proof: Consider a configuration C k where ab = last delivered. Assume that p i starts to execute SendMessage (m ′ , ab) in C k . By contradiction, assume m ′ is never processed by p j in the remainder of E. That is, p j never executes lines 06 or 08 in the Receive procedure. In turn, tests on lines 03 or 04 never evaluate to true simultaneously.

As last delivered = ab in C k and last delivered may change only when m ′ is processed (line 09), we know that the test on line 04 is always true (since m is never processed by assumption).

This implies that Q[m ′ , ab] ≥ c + 1 never evaluates to true (test on line 03). This implies that the sender stops sending (m ′ , ab) before the (m ′ , ab) counter reached c + 1, which is impossible. The reason is as follows. In order to stop sending the same message, p i must get 3c+ 2 acknowledgments with the expected content (ack, (m ′ , ab)). If such 3c + 2 acknowledgments are indeed received, this implies that the receiver issued at least 2c + 2 of those acknowledgments, and thus received 2c + 2 packets (m ′ , ab). Consider the first such packet (m ′ , ab) received by p j . If there is no reset of p j 's queue following this packet, the head of the queue now contains an entry (m ′ , ab, * ) that can not be deleted until the receiver resets the entire queue. Indeed, at most c packets are initially present in the receiver's input channel, that can create at most c entries in the queue. Since the queue is of size c + 1, the (m ′ , ab, * ) tuple remains. Now, if the receiver sends c + 1 packets (ack, (m ′ , ab)), it implies that the receiver's queue for entry (m ′ , ab, * ) was incremented c + 1 times, which invalidates the assumption. It follows that m ′ is processed in a finite time.

S(E), m /

∈ S(E) ∧ m / ∈ R(E) 1 . In other words, there exists in E a message m not sent by p i but delivered to p j . Moreover m is not the first message received by p j .

Initially the channel (i, j) may contain at most c ghosts messages. In the worst case, the receiver's queue also contains an entry for each of the ghost with the counters initialized to c or c + 1.

Let (g, ab) be the first ghost message received by p j with alternated bit set to ab. Let us study the two possible cases. First, assume that ab = last delivered. Then p j delivers g (line 06 of Receive procedure) and empties the queue (line 10 of Receive procedure). Second, assume that ab = last delivered. Then p j does not deliver g (due to the test of line 04 of Receive procedure) but it empties the queue (line 10 of Receive procedure).

In both cases, there is at most one ghost message delivered to p j and the queue has been emptied. In turn, it remains now at most c -1 ghosts messages in the channel (i, j). If one of them is received by p j (after an invocation of ReceivePacket), its associated counter cannot reach the value c + 1 (unless p i starts to send the same message but in this case, it is no longer a ghost message) since there are at most c -1 copies of the same message. Consequently, none of the c -1 remaining ghost messages can be delivered, that contradicts the construction of m and proves the result.

2

Lemma 6 SDL satisfies the 1-Reordering property.

Proof: Following Lemma 5, SDL delivers at most one ghost message to p j in E. Let us consider the two following possible cases.

Case 1: SDL delivers no ghost message to p j in E.

According to Lemmas 3 and 4, any message sent from p i is delivered to p j exactly once in this case. Now, observe that any message is delivered to p j between the beginning and the end of the corresponding execution of the procedure Send by p i . Indeed, the message is delivered to p j when it receives the (c + 1)-th copy of the message whereas p i waits to receive the (3c + 2)-th acknowledgment of the message to stop sending it (see proof of Lemmas 1 and 2). Since the Send procedure is blocking for p i , R(E) 0 = R E = S E for any execution E where SDL delivers no ghost message to p j . Hence, ∃d = 0 ≤ 1, R(E) d = S E .

Case 2: SDL delivers one ghost message to p j in E.

Assume that the ghost message delivered by SDL is m. Lemma 5 allows us to state that m is the first message delivered to p j . Then, a similar reasoning to the one of case 1 allows us to conclude that R(E) = m.S(E) for any execution E where SDL delivers one ghost message m to p j and then, R(E) 1 = S E . Hence, ∃d = 1 ≤ 1, R(E) d = S E .

In both cases, we show that SDL satisfies the 1-Reordering property. 2 Now, we can conclude on the following corollary of Lemmas 3, 4, 5 and 6.

Theorem 4 SDL satisfies the (0, 1, 1, 1)-Stabilizing Data-Link Communication specification.

Conclusion

In this paper, we focused on stabilizing data-link protocols over channels of bounded capacity c. First, we introduced some measures for fault-resilience following the specification presented in [START_REF] Lynch | Distributed Algorithms[END_REF] that is suitable to the self-stabilizing setting. Then, we proved lowers bounds on these parameters. Finally, we proposed a stabilizing data-link protocol that emulates FIFO reliable links over unreliable bounded non-FIFO communication environment with an optimal fault-resilience. To achieve this optimal fault-resilience, our protocol sends 6c + 4 packets (and their corresponding acknowledgements) to deliver one message to the application layer. Some interesting open questions follow. Is it possible to achieve optimal fault-resilience with a (significantly) lower message complexity for a given channel capacity c? Recently, some works on snap-stabilizing point-to-point communication [START_REF] Cournier | A snap-stabilizing point-to-point communication protocol in message-switched networks[END_REF][START_REF] Cournier | How to improve snap-stabilizing point-topoint communication space complexity?[END_REF][START_REF] Cournier | Snapstabilizing linear message forwarding[END_REF] across multiples hops have been presented in a coarse grained communication model. Is it possible to extend these results to the more realistic message passing model using our Stabilizing Data-link as a communication black box? If so, is it possible to provide optimal fault resilience as in the one hop case?

Figure 1 :

 1 Figure 1: General organization of our system.

The work started while this author was a visiting professor at LIP6. Research supported in part by the ICT Programme of the European Union under contract number FP7-215270 (FRONTS), Deutsche Telekom, US Air-Force and Rita Altura Trust Chair in Computer Sciences. This work is supported in part by ANR projects SHAMAN, ALADDIN, and SPADES

Proof: Consider a configuration C k where ab = last delivered. Assume that p i starts to execute SendMessage (m ′ , ab) in C k . Since the test in the line 04 of the Receive procedure evaluates to false, the processing of m ′ is not executed. However, since p i keeps sending m ′ and p j acknowledges these packets the SendMessage procedure returns. Note that p i executes line 01 or 03 of the Send procedure before the next invocation of SendMessage procedure.

It follows that the system reaches in a finite time a configuration where ab = last delivered. Then, Lemma 1 implies that every message that is parameter of subsequent invocations of SendMessage is eventually processed by p j .

2 Now, we can prove that SDL satisfies the four properties of the specification (see Section 2.2) starting from any configuration.

Lemma 3 SDL satisfies the 0-Loss property.

Proof: Assume that p i has to send a message m to p j starting from an arbitrary configuration. Note that proofs of Lemmas 1 and 2 imply that any invocation of the Send procedure eventually ends. This implies in turn that p i starts to execute Send(m) in a finite time.

Then, p i invokes first SendMessage with a < SY N CHRO > message as parameter (see line 02 of the Send procedure). Note that this < SY N CHRO > message may be lost if ab = last delivered when p i starts to execute SendMessage by Lemma 2.

Then, following Lemma 2 that we have ab = last delivered when p i starts to execute SendMessage with m as parameter (see line 04 of the Send procedure) since it has executed line 03 of the Send procedure. By Lemma 1, it follows that m is eventually processed by p j . As m is a normal message, this implies by definition that m is delivered to p j in a finite time.

As this result holds whatever the state of the system when p i requests to send m, we obtain that ∀m ∈ S(E), m ∈ R(E). It is sufficient to observe that S(E) = S(E) 0 to obtain the result. 2 Lemma 4 SDL satisfies the 1-Duplication property.

Proof: By contradiction, assume that there exists an execution E of SDL such that ∀b ≤ 1, ∃m ∈ S(E),

In particular, this property is true for b = 1. Hence, ∃m ∈ S(E), 1 . In other words, there exists in E a message m sent by p i delivered several times to p j . Moreover m is not the first message received by p j .

This implies that the line 06 in the Receive procedure is executed several times for the message m. It is impossible and the reason is the following. After the first delivery of m the receiver empties the queue and makes last delivered = ab (see proof of Lemma 2). Note that p i modifies ab only when it stops to send m. Even if p i keeps invoking SendPacket (m, ab) until it receives the 3c + 2 acknowledgments, none of these messages will be delivered since for each of them the test in line 04 in the Receive procedure returns false.

This contradiction implies that only the first message received by p j may be duplicate. The lemma follows.

2

Lemma 5 SDL satisfies the 1-Creation property.

Proof: By contradiction, assume that there exists an execution E of SDL such that ∀c ≤ 1, ∃m ∈ R(E), m / ∈ S(E) ∧ m / ∈ R(E) c . In particular, this property is true for c = 1. Hence, ∃m ∈