Wael Guibène
email: wael.guibene@eurecom.fr

Hessam Moussavinik
email: hessam.moussavinik@iet.ntnu.no

Aawatif Hayar
email: a.hayar@greentic.uh2c.ma

Combined Compressive Sampling and Distribution Discontinuities Detection Approach to Wideband Spectrum Sensing for Cognitive Radios

Keywords: Compressed sensing, compressive sampling, spectrum sensing, cognitive radio, distribution discontinuities, algebraic detection, sensing algorithm, wideband, change point detection

This paper 1 presents a new sensing technique for cognitive radio systems which combines algebraic tools and compressive sampling techniques. The proposed approach consists of the detection of spectrum holes using spectrum distribution discontinuities detector fed by a compressed measurements. The compressed sensing algorithm is designed to take advantage from the primary signals sparsity and to keep the linearity and properties of the original signal in order to be able to apply algebraic detector on the compressed measurements. The complexity of the proposed detector is also discussed and compared with the energy detector as reference algorithm. The comparison shows that the proposed technique outperforms energy detector in addition to its low complexity.

I. INTORDUCTION

Recently, compressed sensing/compressive sampling (CS) has been considered as a promising technique to improve and implement cognitive radio (CR) systems. The increasing demand for spectrum from various wireless devices and networks emerges the technical society to use the radio spectrum more efficiently. Cognitive radio is an smart wireless communication system that is able to promote the efficiency of the spectrum usage by exploiting the free frequency bands in the spectrum, namely spectrum holes [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF]. Detection of spectrum holes is of the first steps of implementing a cognitive radio system. In wideband radio one may not be able to acquire a signal at the Nyquist sampling rate due to the current limitations in Analog-to-Digital Converter (ADC) technology [START_REF] Cands | Compressive sampling[END_REF]. Compressive sensing makes it possible to reconstruct a sparse signal by taking less samples than Nyquist sampling, and thus wideband spectrum sensing is doable by CS. An sparse signal or a compressible signal is a signal that is essentially dependent on a number of degrees of freedom which is smaller than the dimension of the signal sampled at Nyquist rate. In general, signals of practical interest may be only nearly sparse [START_REF] Cands | Compressive sampling[END_REF]. And typically the wireless signal in open networks are sparse in the frequency domain since depending on location and at some times the percentage of spectrum occupancy is low due to the idle radios [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], [START_REF] Tian | Compressed sensing for wideband cognitive radios[END_REF]. In CS a signal with a sparse representation in some basis can be recovered from a small set of nonadaptive linear measurements [START_REF] Davenport | Detection and estimation with compressive measurements[END_REF]. A sensing matrix takes few measurements of the signal, and the original signal can be reconstructed from the incomplete and contaminated observations accurately and sometimes exactly by solving a simple convex optimization problem [START_REF] Cands | Compressive sampling[END_REF], [START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF]. In [START_REF] Candes | Decoding by linear programming[END_REF] and [START_REF] Candes | Near-Optimal signal recovery from random projections: Universal encoding strategies?[END_REF] conditions on this sensing matrix are introduced which are sufficient in order to recover the original signal stably. And remarkably, a random matrix fulfills the conditions with high probability and performs an effective sensing [START_REF] Davenport | Detection and estimation with compressive measurements[END_REF], [START_REF] Candes | An introduction to compressive sampling[END_REF]. Apart from reconstructing the original signal, detection is more required and interesting in the context of cognitive radio. Generally, for detection purposes it is not necessary to reconstruct the original signal, but only an estimate of the relevant sufficient statistics for the problem at hand is enough. This leads to less required measurements and lower computational complexity [START_REF] Duarte | Sparse signal detection from incoherent projections[END_REF]. We are interested to skip the estimation of the original signal and directly use the measurements for detection purpose, and so reduce the complexity of the system as much as possible.

In [START_REF] Tian | Compressed sensing for wideband cognitive radios[END_REF] a wavelet-based detection approach using CS to identify the spectrum holes is introduced. To find the frequency band boundaries they derive a convex optimization formulation that the solution gives the band boundaries of the spectrum without requiring to reconstruct the original signal. In this paper we develop a combined compressive sampling and distribution discontinuities detection technique based on algebraic method for the sensing task of identifying the spectrum holes. The proposed algebraic detector is a linear detector and we would like to feed the algorithm directly with the compressed measurements. For this purpose we find a proper sensing matrix that gives the possibility of feeding the algebraic detector with the measurements directly. The rest of the paper is organized as follows. Section II states the motivation and problem formulation. Section III details the proposed sensing technique based on combined compressive sampling and distribution discontinuities detection. Section IV is dedicated to performance results, and section V concludes this paper.

II. MOTIVATION AND PROBLEM FORMULATION IN THE CONTEXT OF SENSING IN CR

A. Motivation

The increasing demand for spectrum from various wireless devices and networks emerges the technical society to use the radio spectrum more efficiently. Measurements lead by the FCC (Federal Communication Commission) in the USA have shown that in some regions and/or at some day intervals up to 70 percent of the statically allocated spectrum is left idle [START_REF]Spectrum policy task force report[END_REF]. Facing this inefficient usage of spectrum, the FCC recommends deploying unlicensed users in the wireless networks. These unlicensed users, also called secondary user (SU), are allowed to use those idle wireless resources only when the licensed users, also called primary user (PU), is not using them so they do not interfere with their transmissions. In order to make such a concept of spectrum sharing feasible, SUs are cognitive radios (CRs) deployed in the primary networks. CR as introduced by Joseph Mitola [START_REF] Iii | An Integrated Agent Architecture for Software Defined Radio[END_REF] is a self aware and intelligent device that can adapt itself to the wireless environment changes by first detecting them, and then adapting its radio parameters to the new opportunities. Cognitive radio technique is an smart wireless communication system that is able to promote the efficiency of the spectrum usage by exploiting the idle frequency bands in the spectrum, namely spectrum holes [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF]. Detection of spectrum holes is of the first steps of implementing a cognitive radio system. Different statistical approaches already exist. The easiest to implement and the reference one in terms of complexity is the energy detector (ED) [START_REF] Urkowitz | Energy detection of unknown deterministic signals[END_REF]. Nevertheless, the ED is highly sensitive to noise and does not perform well in low signal to noise ratio (SNR). Other advanced techniques based on signals modulations and exploiting some of the transmitted signals inner features were also developed [START_REF] Sahai | A tutorial on spectrum sensing: fundamental limits and practical challenges[END_REF]. For instance, the cyclostationary features detector (CFD) exploits the built-in cyclic properties of the PU received signal. The CFD has a great robustness to noise compared to ED but its high complexity is still a consequent drawback. Other techniques that were developed by researchers at Eurécom Institute are based on model selection tools and entropy investigation [START_REF] Zayen | Blind spectrum sensing for cognitive radio based on signal space dimension estimation[END_REF]- [START_REF] Haddad | Cognitive radio sensing information-theoretic criteria based[END_REF]. An important issue of complexity in spectrum sensing by cognitive radio is the sampling rate used to sample the received signal at a CR. Specially that usually the spectrum to be sensed is wide which makes the sampling more challenging. In wideband radio one may not be able to acquire a signal at the Nyquist sampling rate due to the current limitations in Analog-to-Digital Converter (ADC) technology [START_REF] Cands | Compressive sampling[END_REF]. Furthermore, cooperative sensing is generally required to detect hidden nodes to a CR, that is several CR nodes sense the spectrum cooperatively to detect PUs and available holes.

In such scenarios, the amount of data processing at each CR node, in both centralized and decentralized schemes, and the amount of data exchange between CR nodes and the fusion center in the centralized scheme are important factors in complexity and power consumption of the system. Also, high number of samples, sampled at Nyquist rate, increase the power consumption and complexity at CR nodes. In order to actualize sensing in wide spectrum and to reduce the complexity and power consumption at CR nodes, sampling at a smaller rate than Nyquist rate, while reconstruction or detection of signal is accurately possible, is a prominent key. Hence, compressive sampling or compressed sensing (CS) becomes a promising solution in realization of cognitive radio and reducing the complexity and power consumption. Compressive sampling enables us to do the sampling at a smaller rate than Nyquist rate, sometimes much smaller, and accurately reconstruct the sparse signal, or perform detection or estimation. The first step of cognitive radio is to sense the spectrum and identify the spectrum holes, or in other words, detect the occupied frequency bands. Typically the wireless signal in open access networks is sparse in the frequency domain since depending on location and at some times the percentage of spectrum occupancy is low due to the idle radios [START_REF] Haykin | Cognitive radio: brain-empowered wireless communications[END_REF], [START_REF] Tian | Compressed sensing for wideband cognitive radios[END_REF]. For example, we can model the spectrally sparse wideband signals as

s(t) = N -1 j=0 β j e i2πjt/N , t = 0, • • • , N -1 (1)
where N is very large but the number of nonzero coefficients β j is much less than N . In this sense we can say that the signal is spectrally sparse [START_REF] Candes | An introduction to compressive sampling[END_REF]. Therefore, we would like to implement spectrum sensing in the context of cognitive radio by performing compressed sensing combined with distribution discontinuities detection. To avoid signal reconstruction burden we find a sensing matrix that enables the algebraic detector properly works while accepting the compressed samples directly as input.

-

6 f PSD f 0 • • • f N Fig. 1.
An example of power spectral density vs. the frequency of a spectrally sparse wideband signal. PSD stands for power spectral density and f is frequency.

B. Problem Formulation

Let us consider a discrete representation of the received signal given by:

x(n) = A n s(n) + e(n) (2)
where A n is modeling the channel, s(n) represents the discrete signal, that is s(t) sampled at Nyquist rate, and e(n) ∼ N (0, σ 2 I n ) is i.i.d. Gaussian noise where I n is an identity matrix of size n.

We would like to distinguish between two classified hypothesis H 0 and H 1 :

H 0 : x(n) = e(n) (3) H 1 : x(n) = A n s(n) + e(n) (4)
where H 0 means that the sensed frequency band is white containing only noise and H 1 means that the sensed frequency band is occupied with a signal corrupted by noise. The key parameter of all spectrum sensing algorithms are the false alarm probability P F and the detection probability P D . P F is the probability to determine a frequency band as occupied while it is free, thus P F should be kept as small as possible.

P F = P (H 1 |H 0 ) = P (a signal (user) is present|H 0 ) (5)
P D is the probability to determine a frequency band as occupied when there exists a signal, thus P D should be kept as large as possible.

P D = 1 -P M = (6) 1 -P (H 0 |H 1 ) = 1 -P (no signal (user) is present|H 1 )
where P M denote the probability of missed detection. To design the optimal detector on Neyman-Pearson criterion, we try to maximize the overall P D under a given overall P F . In order to infer on the nature of the received signal, we calculate a threshold for each of the detectors. The decision threshold is determined using the required probability of false alarm P F given by [START_REF] Davenport | Detection and estimation with compressive measurements[END_REF]. The threshold T h for a given P F is determined by solving the equation:

P F = P (a signal is present|H 0 )) = 1 -F H0 (T h) (7)
where F H0 denote the cumulative distribution function (CDF) under H 0 . The algebraic approach is able to detect the signal distribution discontinuities and find their positions in the spectrum, having the complete signal (Nyquist rate samples) as input to the detector. The problem is that sampling a wideband signal with Nyquist rate is constrained due to the reasons highlighted in section I. In order to make the detection possible with less number of samples or smaller sampling rate, relatively to Nyquist rate, we would like to implement compressed sensing technique. In this sense by considering the sparseness of the signal we observe the received signal compressively with a smaller rate than Nyquist rate such as:

y = Φx + e (8)
where y ∈ R M is the compressed measurements, Φ is the sensing matrix, x ∈ R N is the received signal like A n s(n) as above, e is the additive noise, and M ≪ N . It is shown that with some conditions on Φ it is possible to recover x accurately based on y.

We would like to use the compressed samples directly to detect the frequency holes without recovering the signal itself.

Since the algebraic detection of distribution discontinuities is a linear approach we should find a proper sensing matrix that makes it possible to use the compressed samples as the input to the linear detector. In following section we discuss about compressed sensing and the selection of the sensing matrix.

III. COMBINED COMPRESSIVE SAMPLING AND DISTRIBUTION DISCONTINUITIES DETECTION

A. Compressed Sensing Let x ∈ R N be a signal with expansion in an orthonormal basis Ψ as

x(t) = N -1 j=0 α j ψ j (t), t = 0, • • • , N -1 ( 9
)
where Ψ is the N × N matrix with the waveforms ψ j as rows. To use convenient matrix notations we can write the decomposition as x = Ψα or equivalently, α = Ψ * x where Ψ * denotes conjugate transpose of Ψ. A signal x is sparse in the Ψ basis if the coefficient sequence α is supported on a small set. We say that a vector α is S-sparse if its support {j : α j = 0} is of cardinality less or equal to S [START_REF] Cands | Compressive sampling[END_REF]. Consider that we would like to recover all the N coefficients of x, vector α, from measurements y about x of the form

y m = x, φ m = N -1 n=0 φ mn x[n], m = 0, • • • , M -1 (10) or y = Φx = ΦΨα = Θα (11)
where we are interested in the case that M ≪ N , and the rows of the M × N sensing matrix Φ are incoherent with the columns of Ψ. Then it is shown that signal x can accurately and sometimes exactly be recovered, considering that the recovered signal x ⋆ is given by x ⋆ = Ψα ⋆ , and α ⋆ is the solution to the convex optimization program

min α∈R N ||α|| l1 subject to ΦΨ α = Θ α = y (12)
where ||α|| l1 := N j=1 |α j |. The compressed sensing (CS) theory states that there exists a measuring factor c > 1 such that only M := cS incoherent measurements y are needed to recover x with high probability. We also have to mention that except l 1 -minimization solution other methods such as greedy algorithms in [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF] exist for recovering the sparse signal [START_REF] Cands | Compressive sampling[END_REF], [START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF], [START_REF] Candes | An introduction to compressive sampling[END_REF], [START_REF] Duarte | Sparse signal detection from incoherent projections[END_REF], [START_REF] Donoho | Compressed sensing[END_REF], [START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF]. In case of noisy measurements, i.e., y = Φx + e, where e is noise with ||e|| l2 ≤ ǫ, [START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF] shows that solution to

min α∈R N ||α|| l1 subject to ||Θ α -y|| l2 ≤ ǫ (13)
recovers the sparse signal with an error at most proportional to the noise level. Also, [START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF] discuss the conditions for stable recovery from noisy measurements. We are interested in doing the spectrum holes detection using algebraic approach directly from the compressed measurements without reconstructing the original signal itself. For this reason we must find out the appropriate sensing matrix according to the detection technique. The proposed detection technique is a linear algebraic algorithm. This technique uses the Fourier transform of the observed signal to detect the occupied frequency bands in the observed spectrum. Therefore the compressed measurements of the observed signal must keep the linearity and properties of the original signal in order to apply the detection algorithm successfully on the compressed measurements. To find the sensing matrix we start by looking at the Fourier transform of the signal x ∈ R N .

X l = N -1 n=0 x[n] exp(-ωln), l = 0, • • • , N -1 (14)
where ω = 2πi N and i is the imaginary unit. The Fourier transform of the measured signal is

Y k = M-1 m=0 y[m] exp(-ωkm), k = 0, • • • , M -1. (15)
From ( 11) we replace y[m] and we have

Y k = M-1 m=0 ( N -1 n=0 φ mn x[n]) exp(-ωkm), k = 0, • • • , M -1 (16
) where φ mn denotes the element of Φ at the cross of row m and column n. Then by linearity properties we have

Y k = N -1 n=0 M-1 m=0 φ n [m] exp(-ωkm)x[n], k = 0, • • • , M -1 (17)
where φ n [m] denotes the m th element of the n th column vector of Φ, φ n , and we see that

M-1 m=0 φ n [m] exp(-ωkm) = Φn k , k = 0, • • • , M -1 (18)
that is the Fourier transform of the n th column vector of Φ, Φn . Then from ( 17) and ( 18)

Y k = N -1 n=0 Φn k x[n], k = 0, • • • , M -1. ( 19
)
And, as we said, in order to feed the detection algorithm directly by the compressed measurements we seek that

Y k (ω) = aX l (ω), k ∈ {0, • • • , M -1}, l ∈ {0, • • • , N -1} (20
) where a > 0 is a constant. From [START_REF] Donoho | Compressed sensing[END_REF] and to satisfy [START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF] we find that

Φn k = a exp(-ωzn), z ∈ {1, • • • , N }, k = 0, • • • , M -1 (21)
and therefore from inverse Fourier transform we have

φ n = aδ(n -z), z ∈ {1, • • • , N } (22)
which means that any row vector of the sensing matrix is a Dirac function, that is, only one column of each row is nonzero. Now that the general format of the sensing matrix is clear, we should find a way to generate it. The Φ T matrix can be generated by randomly selecting M columns of an identity matrix I N . Φ is given by transpose of Φ T , and we define a = 1 to make sure that the columns of the sensing matrix are unit-normed. So the sensing matrix Φ that we acheived has a form like this

Φ ∼    0 1 0 • • • 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 • • • 0 1 0 0    M×N . ( 23
)
This form of sensing matrix gives us the opportunity to use the compressed measurements directly as input to the algebraic detection algorithm and thus avoiding the computation complexity of reconstructing the original signal. Following, the algebraic detection technique with compressed measurements as the input to the algorithm is explained.

B. Algebraic Detection Based on Compressive Sampling

The algebraic detection (AD) is a new approach based on advanced differential algebra and operational calculus. In this method, the primary user's presence is rather casted as a change point detection in its transmission spectrum [START_REF] Guibene | Development and implementation of an algebraic detector for spectrum sensing[END_REF]. In this approach, the mathematical representation of the spectrum of the compressed measurements, i.e., the observed signal Y n in frequency domain, is assumed to be a piecewise P th polynomial signal expressed as following:

Y n = K k=1 Y k [n k-1 , n k ](f )p k (n -n k-1 ) + E n (24)
where Y k [n k-1 , n k ] is the characteristic function, p k is a polynomial series of order P , E n is the additive corrupting noise, K is the number of subbands defined in the frequency range of observation interest, and n = f fs is the normalized frequency, where f s is the sampling frequency and f is the signal frequency. Let us define the clean version of the received signal S n as:

S n = K k=1 Y k [n k-1 , n k ](f )p k (n -n k-1 ) (25)
And let b, the frequency band, is such that one and only one change point occurs in the interval

I b = [n k-1 , n k ] = [ν, ν+b], ν ≥ 0. Denoting S ν (n) = S(
n ν = 0 if S ν is continuous 0 < n ν ≤ b otherwise (26)
Then, the primary user presence on a sensed sub-band is equivalent to find 0 < n ν ≤ b on that band. The AD gives the opportunity to build a whole family of spectrum sensing detectors, depending on a given model order P . Depending on this model order, we can show that performance of the AD is increasing as the order P increases. The proposed algorithm is implemented as a filter bank which composed of P filters mounted in a parallel way. The impulse response of each filter is:

h k+1,n = (n l (b-n) P +k ) (k) (l-1)! , 0 < n < b 0, otherwise (27)
where

k ∈ [0 • • • P -1] and l is chosen such that l > 2 × P . The proposed expression of h k+1,n , k ∈ [0 • • • P -1]
is determined by modeling the spectrum with a piecewise regular signal in frequency domain and casting the problem of spectrum sensing as a change point detection in the primary user transmission [START_REF] Guibene | Development and implementation of an algebraic detector for spectrum sensing[END_REF]. Finally, in each detected interval [n νi , n νi+1 ], we compute the following equation:

λ k+1 = nν i+1 m=nν i W m h k+1,m X m ( 28
)
where M is the number of samples of the observed signal, W m is the weight for numeric integration defined by:

W 0 = W M = 0.5 W m = 1 otherwise (29)
In order to infer whether the primary user is present in its interval, a decision function is computed as following:

Df = P k=0 λ k+1 (n ν ) (30)
The decision is made by comparing the threshold T h to the mean value of the decision function over the detected intervals.

IV. SIMULATIONS

In this section we investigate the performance of the proposed algorithm in comparison with the energy detector (ED). First we consider a frequency band in the range of [50, 250]MHz, in order to compare the compressive sensing using the algebraic method and the wavelet approach introduced in [START_REF] Tian | A wavelet approach to wideband spectrum sensing for cognitive radios[END_REF]. The signal is fully described in [START_REF] Tian | A wavelet approach to wideband spectrum sensing for cognitive radios[END_REF]. During the observed burst of transmissions in the network, there 6 bands, with frequency boundaries at n ν 6 n=0 = [50,120,170,200,220,224,250]MHz. Comparing with the wavelet approach, in the algebraic detection technique change points are detected only in one shot, while in the wavelets approach, many detections have to be conducted and fused to make a final decision. Figure 2 shows the algebraic detection performance on this signal. Now, comparing the proposed compressed sensing algorithm to the reference algorithm, let us give some key notes on the ED. ED is the most common method for spectrum sensing because of its non-coherency and low complexity. The energy detector measures the received energy during a finite time interval and compares it to a predetermined threshold. That is, the test statistic of the energy detector is:

M m=1 y m 2 (31)
where M is the number of samples of the received signal y. Traditional ED can be simply implemented as a spectrum analyzer. A threshold used for primary user detection is highly susceptible to unknown or changing noise levels. Even if the threshold would be set adaptively, presence of any in-band interference would confuse the energy detector. Since the complexity of sensing algorithms is a major concern in implementation and ED is well known for its simplicity, we choose ED as the comparison reference. Denoting N the number of Nyquist samples of the observed signal y and P the model order of AD, we show that the complexity of AD is P N and the complexity of ED is N . From these results, we clearly see that the exploited sensing algorithm has a comparable complexity to the energy detector. For the proposed AD based compressed sensing algorithm, the complexity is equal to: P M N N = P M , where M is the number of compressed measurements of the received signal and M ≪ N . Table I In order to achieve realistic and well founded simulations, DVB-T signals based on DVB-T 2K recommendations are used as the signals to be sensed. This choice can be justified by the fact that almost all licensed primary networks are DVB-T and secondary users are CR deployed in these networks. The signal parameters are given in Table II. Figure 3 shows the performance of the following simulated detectors: energy all have the same complexity and the figure 3 shows that AL 50% 2 have a much better performance than ED and at low SNRs it is outperforming AD 1 .

Another key metric in the sensing problems is the receiver operating characteristics (ROC) curve which helps giving an idea about the reliability of the proposed technique. For instance we plot the ROC curve at SN R = -25dB for ED, AD 1 and AL 50% 2 . Figure 4 shows how reliable the compressed sensing technique is, as the detector operates at high probability of detection under a low false alarm rate.

V. CONCLUSION

We present in this work a new sensing technique which combines compressive sampling and algebraic method to detect spectrum holes. In a first step, we designed a compressed sensing matrix which keeps the linear properties of the sampled primary signal. Then, we applied the compressed measurements to algebraic detector to localize spectrum distribution discontinuities and identify spectrum holes. The analysis of the complexity of the proposed technique shows that it can be dramatically reduced when the model order of the algebraic detector increases. The performance comparison at different sampling rates shows that the new designed scheme achieves better performance than energy detector while preserving a low computational complexity.

  n+ν), n ∈ [0, b] as the restriction of the signal in the interval I b and redefine the change point n ν relatively to I b such as:

Fig. 2 .

 2 Fig.2. Edge detection using the algebraic technique. The signal in red is the original signal, the one in blue is the noisy observation with SNR=-8dB. The black signal is the computed decision function and the green stars are the detected change points.

Fig. 3 .

 3 Fig. 3. P D vs. SNR at P F =0.05; AD P :Algebraic detection of order P ; ED: Energy detector; M N :Compression ratio.

Fig. 4 .

 4 Fig. 4. ROC curve at SNR=-25dB; AD P :Algebraic detection of order P ; ED: Energy detector; M N :Compression ratio.

  summarizes the complexity of each detector.

	Sensing technique	Complexity
	Energy detector	N
	Algebraic detector	PN
	Combined compressive sampling and	PM
	distribution discontinuities detection

TABLE I COMPLEXITY

 I COMPARISON OF THE THREE SENSING TECHNIQUES; M ≪ N .

TABLE II THE

 II TRANSMITTED DVB-T PRIMARY USER SIGNAL PARAMETERS detector (ED), first order algebraic detector (AD 1 ), AD 1 with compression rate of M/N = 20%, 30%, 40% and 50% and a second order algebraic detector (AD 2 ) with M/N = 50%. We note that ED, AD 1 and AD 50% 2

The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement SACRA n ˚249060, SENDORA, and the SAM-POS/WISENET Project, which is funded by the Research Council of Norway under the contract number 176875/S10 and 176724/I30.


Dan Alistarh
email: alistarh@epfl.chhagit@cs.technion.ac.il

Hagit Attiya

Rachid Guerraoui
email: guerraoui@epfl.chtravers@labri.fr

Corentin Travers

Early Deciding Synchronous Renaming in O(log f ) Rounds or Less

Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the running time adapts to the actual number of failures f in the execution. We show that, surprisingly, renaming can be solved in constant time if the number of failures f is limited to O( √ n), while for general f ≤ n -1 renaming can always be solved in O(log f ) communication rounds. In the wait-free case, i.e. for f = n -1, our upper bounds match the Ω(log n) lower bound of Chaudhuri et al. [12].

Introduction

Unique names, or identifiers, are a fundamental prerequisite for solving a variety of problems in distributed computing. While in many settings unique names are available, they often come from a very large, practically unbounded namespace, which reduces their usefulness. The renaming problem [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], in which a set of processes need to be assigned names from a namespace of small size, is one of the fundamental problems in distributed computing, and a significant amount of work, e.g. [START_REF] Alistarh | Optimal-time adaptive strong renaming, with applications to counting[END_REF][START_REF] Alistarh | The complexity of renaming[END_REF][START_REF] Attiya | Renaming in an asynchronous environment[END_REF][START_REF] Attiya | Adaptive and efficient algorithms for lattice agreement and renaming[END_REF][START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF][START_REF] Brodsky | Fully-adaptive algorithms for long-lived renaming[END_REF][START_REF] Burns | The ambiguity of choosing[END_REF][START_REF] Castañeda | New combinatorial topology bounds for renaming: The upper bound[END_REF][START_REF] Herlihy | The topological structure of asynchronous computability[END_REF][START_REF] Moir | Fast, long-lived renaming (extended abstract)[END_REF], studied its solvability and complexity in fault-prone distributed systems.

Much of the work on the renaming problem, whether in shared-memory [START_REF] Alistarh | Optimal-time adaptive strong renaming, with applications to counting[END_REF][START_REF] Attiya | Adaptive and efficient algorithms for lattice agreement and renaming[END_REF] or in messagepassing systems [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], has focused on the asynchronous case, in which the processes' steps or messages may be delayed arbitrarily by the scheduler. However, real world systems experience long periods where delays are bounded, and inter-process communication is synchronous, even though processes may still fail by crashing. The complexity of renaming in such a synchronous setting, where processes communicate by message-passing, was investigated by Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] and Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. In brief, they found that for n processes, up to n -1 of which may fail by crashing, there exist algorithms that assign a tight namespace of names 1, . . . , n names in O(log n) rounds of communication. Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] also showed a matching lower bound.

The analysis in these papers only focused on the case where the maximum number of processes, n -1, may fail by crashing during an execution. However, the Ω(log n) lower bound of [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] does not exclude algorithms that terminate faster when the actual number of failures f in the execution is less than n -1. Such speculative algorithms, also known as early deciding, are known to exist for consensus [START_REF] Pease | Reaching agreement in the presence of faults[END_REF] and set agreement [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF]. Early-deciding protocols achieve consensus in O(f ) communication rounds [START_REF] Dolev | Early stopping in byzantine agreement[END_REF], and k-set agreement in O( f k ) rounds [START_REF] Gafni | The complexity of early deciding set agreement[END_REF]. It is therefore natural to ask what is the time complexity of early deciding synchronous renaming in a message-passing system. The answer to this question does not appear trivial: for example, a successful strategy for renaming [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] was for each process to obtain a new bit from its name by running a simple one round symmetry-breaking protocol-after Θ(log n) rounds, each process has a unique name from 1 to n. However, it is hard to speed up this approach to obtain more bits for the process's name in rounds where there are few failures, without breaking name uniqueness. Another approach [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], where each process proposes a name in each round based on what every other process proposed in previous rounds, until there are no collisions, turns out to be very difficult to analyze when the adversary has a limited budget of f failures.

In this paper, we overcome these challenges, and present the first early-deciding upper bounds for renaming. In short, we find that the complexity of the problem is strongly coupled with the relation between n, the number of processes and f , the failure budget of the adversary. We show that there exists an algorithm that ensures a tight namespace of n names, and terminates in a constant number of rounds in every execution where f ∈ O( √ n), and, in O(log f ) rounds, otherwise. The existence of a constant-time renaming algorithm for non-trivial f is surprising, since the early-deciding bounds for consensus [START_REF] Dolev | Early stopping in byzantine agreement[END_REF] and set agreement [START_REF] Gafni | The complexity of early deciding set agreement[END_REF] are linear in f irrespective of the relation with the total number of processes n.

Our second result is an algorithm that improves on the constants in the asymptotic notation, terminating in log f + 5 rounds, and assigning names from 1 to 2n.

The first algorithm is a slight modification of a result by Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. His protocol is based on a novel connection between synchronous renaming and the approximate agreement problem [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]. In brief, processes assign temporary ranks to each process identifier that they receive, and perform approximate agreement to converge on an approximate rank for each initial process identifier, within a carefully chosen approximation factor. Each process returns this approximate rank, rounded to the nearest integer, as its name: the protocol ensures that, upon termination, the approximate ranks are far enough apart so that no two processes decide on the same rank. Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF] showed that this protocol ensures a tight namespace, preserves the order of the initial identifiers, and terminates in O(log n) rounds in all executions.

Our main contribution is analyzing this protocol for general f , and showing that it terminates in constant time if f ∈ O( √ n), and in O(log f ) rounds otherwise. Our analysis characterizes the optimal adversarial strategy for arbitrary values of the parameters n and f -we achieve this by carefully bounding the approximation factor of the approximate agreement protocols relative to the number of failures that the adversary expends in each round, showing that this factor goes down fast, and the algorithm terminates very quickly, if the adversary does not fail a significant fraction of the processes in each round.

The second renaming algorithm we present is simpler, and achieves better constants in the asymptotic notation, while relaxing the size of the namespace to 2n. The protocol is split in two phases: In the first phase, each process identifies a set of names it is interested in, whose size is proportional to the number of failures that the adversary expends in the phase. In the second phase, processes proceed to progressively halve the size of the set of names they are interested in, until each set is a singleton. At this point, each process may adopt the single name in its set. The key technical difficulty is in assigning each process the "right" set of names at the end of the first phase, so that there are always enough names for the set of participants. To ensure this, we need to relax the total size of the namespace that processes are interested in to be of size 2n. The halving procedure in the second phase is similar to the O(log n) round algorithm by Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF].

We therefore show that the time complexity of early-deciding renaming is upper bounded by O(log f ) synchronous rounds for general f , and can be constant for non-trivial f ∈ O( √ n). Both algorithms are adaptive, since they do not know the number of participants n in advance; they also adapt to the number of failures f in the execution. Roadmap. We present the problem statement and the model in Section 2, and give an overview of related work in Section 3. In Section 4, we present the analysis of the tight renaming algorithm, while the second algorithm can be found in Section 5. We conclude with a discussion of open questions in Section 6.

Model and Problem Statement

Model. We consider a standard synchronous message passing system with n processes p 1 , . . . , p n . Initially, processes have unique identifiers from a namespace of unbounded size. Time is divided into rounds, and the processes' clocks are synchronized. Each round proceeds as a sequence of send, receive, and process steps, in which processes may send and receive messages, and perform local computation if necessary. We assume that at most t < n processes may fail by crashing. If crashed, a process stops taking further steps in the execution; a process may fail to send any subset of its messages in rounds in which it crashes.

Let f denote the number of failures in the current execution. We focus on early-deciding algorithms, that adapt their time complexity to the actual number of failures in the execution, i.e. whose running time is a function of f only.

Renaming. The renaming problem [START_REF] Attiya | Renaming in an asynchronous environment[END_REF] requires that each correct process eventually returns a name, and that the names returned should be unique. The size of the resulting namespace should only depend on the parameters n. The tight renaming problem requires that the size of the namespace be exactly n; otherwise, we say that the solution is loose. Approximate Agreement. Consider a small real number > 0. In the -approximate agreement problem [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF], each process p i starts with a proposal v i , which is a real number. An approximate agreement algorithm must satisfy the following properties: (1) Each correct process eventually decides a value d i ; (2) For any correct processes p i and p j , |d i -d j | ≤ ; (3) For any correct process p , there are processes p i and p j with initial values v i and v j , such that v i ≤ d ≤ v j . Notation. Throughout this paper, log denotes the logarithm base two. Moreover, we write log f instead of log f . To simplify notation, we assume that f ≥ 1, which allows us to consider running times of O(log f ) rounds.

Related Work

The renaming problem was introduced in [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], where the authors also provide a wait-free solution using (2n -1) names in an asynchronous message-passing system, and show that at least (n + 1) names are required in the wait-free case. This lower bound on the namespace size for the case of asynchronous solutions was improved to (2n -2) by Herlihy and Shavit [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF], and Rajsbaum and Castañeda [START_REF] Castañeda | New combinatorial topology bounds for renaming: The lower bound[END_REF]. (This lower bound holds when n is a power of a prime number.)

Considerable research has analyzed the upper and lower bounds for renaming in asynchronous setting, in particular in shared memory e.g., [START_REF] Alistarh | Optimal-time adaptive strong renaming, with applications to counting[END_REF][START_REF] Alistarh | The complexity of renaming[END_REF][START_REF] Attiya | Adaptive and efficient algorithms for lattice agreement and renaming[END_REF][START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF][START_REF] Brodsky | Fully-adaptive algorithms for long-lived renaming[END_REF][START_REF] Burns | The ambiguity of choosing[END_REF][START_REF] Moir | Fast, long-lived renaming (extended abstract)[END_REF]. For a detailed description of these results, we refer the reader to e.g., [START_REF] Alistarh | Optimal-time adaptive strong renaming, with applications to counting[END_REF].

On the other hand, there has been relatively little work on the complexity of synchronous renaming. Herlihy et al. [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] considered wait-free renaming in a synchronous message-passing system, identical to the one we consider in this paper. They prove a lower bound of Ω(log n) rounds on the time complexity of the problem in runs where t = n -1 processes may crash, and provide a matching algorithm that achieves tight renaming with time complexity log n + 3 in every execution. In contrast, our algorithms are early deciding, in that they adapt to the actual number of failures f in the current execution, deciding in O(log f ) rounds. On the other hand, the lower bound argument of Herlihy et al. [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] applies to our algorithms as well1 , implying a lower bound of Ω(log n) rounds in executions where f = n -1.

In [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF], Okun presents a synchronous message-passing algorithm for tight renaming algorithm with O(log n) time complexity. His algorithm is based on a novel connection between renaming and approximate agreement. In brief, processes perform approximate agreement on the rank of each initial identifier, until they are certain that no two processes obtain the same rank. In this paper, we extend this technique by providing a new analysis for minor variation of his algorithm, proving that its running time is in fact O(log f ) in executions with f failures, which is asymptotically optimal.

A Tight Renaming Algorithm

In this section, we analyze the tight renaming algorithm of Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF] and prove that it terminates in O(log f ) rounds, where f < n is the number of processes that the adversary crashes in the current execution. We begin with a short description of the algorithm; a detailed exposition can be found in the original paper [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. Algorithm Overview. The algorithm is based on a novel connection between renaming and the approximate agreement problem. First, a simple synchronous approximate agreement (AA) algorithm is introduced. Then, the algorithm runs in parallel at most n separate instances of this approximate agreement algorithm, one for each process in the system. The goal is to agree on an approximate rank for each process's initial identifier, which will be the value decided by the corresponding approximate agreement algorithm, rounded to the nearest integer. The key ingredient is to run the approximate agreement algorithm for long enough to ensure that the decision values of the AA protocols corresponding to each initial identifier are sufficiently spaced, ensuring that the rank decided for each process is unique. The Approximate Agreement Algorithm. The algorithm, whose pseudocode appears in Figure 1, proceeds as follows. Each process starts with an initial value v i and a desired approximation factor , which bounds the maximum desired skew between decided values. The process maintains an estimate d i of its decision value, which is updated in every round to the arithmetic average of all values received. Once all the estimates received in a round are within at most of each other, the process returns its current estimate. The Renaming Algorithm. Each process p i starts with an initial name v i . The algorithm, whose pseudocode appears in Figure 2, has two phases.

procedure propose i (v i , ) ; 1 d i ← v i ; 2 for each round r ≥ 0 do 3 broadcast(d i ); 4 δ ← max =j (|d -d j |);
The first phase contains the first three rounds, in which processes exchange their identifiers, in order to identify the parameter n and the relative ranks of their identifiers.

In the second phase, which starts at round four, based on the information computed so far, each process proposes a rank for each participating process to a separate instance of the approximate agreement algorithm in Figure 1. Notice that all these agreement instances run in parallel; all messages by a process in a round (one for each AA protocol in which it participates) are packaged into a single composite message, which each process sends in each round. The approximation factor for all these agreement instances is 1/(10C 2 ), where C 2 is the number of distinct identifiers the process received in round 2 of the first phase. (This factor is chosen such that no two identifiers may receive the same final rank from the approximate agreement instances when rounded to the nearest integer.) The algorithm terminates when all the approximate agreement algorithms terminate, ensuring the desired approximation factor. Name uniqueness. We give a brief overview of the mechanism ensuring name uniqueness; a complete analysis can be found in [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. Recall that, for each initial identifier id, each process p proposes the rank of id multiplied by C 2 /C 3 as the initial value in id's instance of the AA protocol. Obviously, the processes' ranks for the same identifier may be distinct (as a consequence of failures in the first phase). However, a key observation is that they will be distinct in a consistent way: if p proposes rank 6 for id α, and rank 7 for id β > α, then another process q proposing rank 7 for id α will have to propose rank at least 8 for id β. Analyzing the AA protocol, this will imply that, given any process p, its decision values for distinct ids α < β will be at distance at least 1 from each other [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]Theorem 3].

This mechanism might still allow the possibility that two distinct processes decide on the same name when rounding their AA decision value to the nearest integer. This is handled by multiplying the initial ranks with C 2 /C 3 . This ratio is higher than 1 only when a processor observes crashes between the second and third rounds, and the algorithm ensures that for any ids α and β, their corresponding decision values at any two processes p and q are at distance > 1 from each other [18, Lemma 3]. In turn, this implies that no two processes may decide the same name. Analysis. Our key observation is that the variant of the synchronous approximate agreement algorithm of Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF] presented in Figure 1 guarantees the required approximation factor of 1/(10C 2 ) in a constant number of rounds when f > √ n/2, and O(log f ) rounds, otherwise. In turn, this implies that the renaming algorithm terminates within three additional rounds.

To prove this, we first introduce some notation. Let σ(S) be the diameter of a set S, i.e. max a,b∈S (|a -b|).

For any round r > 0 in the execution of the approximate agreement algorithm, let U r be the multiset of distinct values that processes that are active (i.e., send at least one message) in round r have in the beginning of the round.

Let f r be the number of processes that crash in round r; for convenience, denote f 0 = 0. Denote by δ r the fraction of processes that crash in round r from among the processes that did not crash before round r; that is, δ r = f r /(n -r-1 i=0 f i ) We first state the following lemma, bounding the diameter of the set U r+1 depending on the diameter of U r and the fraction of processes that crash in round r; its proof follows [18, Lemma 1].

Lemma 1. σ(U r+1 ) ≤ 2δ r+1 1-δ r+1 • σ(U r ).
The next lemma bounds the number of rounds needed for the approximate agreement algorithm of Figure 1 to achieve a maximum diameter of = 1/(10n) for the set of decisions corresponding to each initial value, when starting with proposal sets of diameter ≤ n. The bound depends on f , the number of failures that the adversary expends in total, and on the number of failures f i which the adversary expends in each round i ≥ 1.

Lemma 2. Consider an execution of the approximate agreement algorithm of Figure 1, starting with an initial set of diameter σ(U 1 ) ≤ n, in which at most f processes crash. Let R be the number of rounds needed for the algorithm to reach a diameter ≤ 1/(10n). The following claims hold:

• If f ≤ √ n/2, then R is a constant. • If √ n/2 < f ≤ n -1, then R ≤ 5 log f + 10.
Proof. We assume n ≥ 6; the claim can be checked for n ≤ 5 by calculation.

The first case is when f ≤ √ n/2. In this case, notice that the fraction of processes that fail in any round of the protocol is at most √ n/n, i.e. δ r ≤ √ n/n, for all r ≥ 1. In turn, by Lemma 1, the diameter of the set of values for the current instance of approximate agreement is reduced by at least 2δ r /(1 -δ r ) ≤ 1/( √ n -0.5) in each round r. Therefore, after the first 10 rounds, the diameter of this set is at most

n ( √ n -0.5) 10 ≤ 1 10n
, for any n ≥ 6.

Therefore the maximum diameter the end of round 10 is ≤ 1/(10n), as claimed.

In the second case, we assume that f > √ n/2. First, notice that δ r , the fraction of active processes that crash in a round r, can be greater than 1/2 in at most log 2 (f +1) +1 distinct rounds. Therefore, any execution of at least 5 log 2 (f + 1) + 10 rounds contains at least 4 log 2 (f + 1) + 9 rounds r in which δ r < 1/2. Lemma 1 implies that the diameter of the set U r at the end of these rounds is at most

n 2 4 log 2 (f +1) +9 ≤ n 2 9 • (f + 1) 4 ≤ 1 10n for all n ≥ 1,
where the last step uses the fact that f ≥ √ n/2. Therefore, in this case, the number of rounds necessary to obtain a maximum diameter of at most 1/(10n) is O(log f ).

We conclude that the resulting renaming algorithm is early deciding, terminating in a constant number of rounds, when f ≤ √ n/2, and O(log f ) rounds, otherwise.

Theorem 3. For any f , 0 ≤ f ≤ n -1, let f = constant if f ≤ √ n/2
, and f = 5 log(f + 1) + 10, otherwise. Then the renaming algorithm in Figure 2 is a tight order-preserving renaming algorithm with time complexity O( f ) and message complexity O(n 2 f ) in executions where f processes fail by crashing.

Proof. We focus on early decision, since the other properties follow from Theorem 4 of [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. First, recall that the initial value v for each approximate agreement algorithm is computed locally by each process as rank V (α) • C 2 /C 3 . Since rank V (α)/C 3 ≤ 1, by the definition of C 2 , we obtain that all initial values are between 1 and n. This also implies that our desired approximation factor is at most 1/(10n).

Lemma 2 implies that all instances of approximate agreement that the renaming algorithm executes in parallel terminate in O( f ) rounds, with an approximation factor ≤ 1/(10n). We obtain that the renaming algorithm terminates in O( f ) rounds, as claimed.

A Loose Renaming Algorithm with Improved Round Complexity

In this section, we present a loose renaming algorithm that terminates in log f 1 + 5 rounds and uses at most 2n names, where n is the number of participating processes and f 1 the number of failures that occur in the first round. Our algorithm extends the non-early deciding renaming algorithm by Chaudhuri, Herlihy, and Tuttle [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. The latter algorithm is tight; its round complexity, however, depends solely on n and not on the number of failures among the participating processes. Specifically, the namespace when n processes participate is [1, n] and the algorithm terminates in log n + 2 rounds. In the following, the algorithm of [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] is called the CHT-renaming algorithm.

Algorithm Overview. The pseudo-code of the algorithm appears in Figure 3. It contains two phases.

In the first phase, which consists of the two first rounds (line 1-line 7), each process selects an interval of names in which it wishes to pick its final name. The size of each interval is upperbounded by 4f 1 , where f 1 is the number of processes that fail during the first round. The second phase (line 8-line 16) consists of a variant of the CHT-renaming algorithm. Processes use this procedure to progressively shrink the interval of names they are interested in, until obtaining an interval of size 1. The algorithm ensures that no two processes obtain the same interval of size 1, i.e. a single name. Thus, each process can decide the unique name in its final interval. Moreover, it guarantees that in each round, processes holding the largest intervals reduce their interval by one half. Therefore our algorithm terminates in O(log f 1 ) rounds.

We begin with a brief description of the CHT-renaming algorithm and then explain how each process selects an initial interval of names. Definitions and notations. Before describing the algorithm in more details, we introduce some notations, extending those in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. An interval I of positive integers is well-formed if I is of the form [d2 j + 1, (d + 1)2 j ] for some positive integers d, j. Note that for every pair I, J of well-formed intervals, I ∩ J = ∅ =⇒ I ⊆ J ∨ J ⊆ I. Given a set I of well-formed intervals, we say that interval

I ∈ I is maximal in I if for every J ∈ I, either I ∩ J = ∅ or J ⊆ I.
The CHT-renaming Algorithm Each process p maintains a well-formed interval of names I, which are the names p is interested in. In each round, process p sends its id and the interval it currently holds I. The intervals intersecting with I that p receives are stored in the set I (line 10). p also stores the set of ids of the processes that are conflicting with p, that is, processes that hold an interval intersecting with I in the set P (line 11). If I is maximal in I (line 12), I is split in half, and p picks the bottom half or the top half of I, denoted bot(I) and top(I) respectively, as its new interval (line 13-line 14). More precisely, the new interval of p is bot(I) if the rank of p's identity in P is smaller than |I| 2 . Otherwise, p selects top(I) as its new interval. Finally, if p observes that every interval sent in the round has size 1, it decides the unique name in its interval. Since in each round the size of maximal interval is at least divided by 2, the algorithm terminates after O(log c) rounds, where c is the size of the largest initial maximal interval.

Name uniqueness relies on the following invariant, which is satisfied by the set of intervals I[r] held by the processes at the beginning of each round r: Invariant 1. For every I ∈ I[r], if m processes hold an interval I ⊆ I, then m ≤ |I|. In particular, this means that I is large enough to allow processes with an interval I ⊆ I to decide distinct names in the interval I.

In the original CHT-renaming, the initial interval of each process p is of the form [1, 2 b ], where 2 b is the least power of 2 larger than or equal to the number of participating processes from which p has received a message in the first round. The invariant above is thus initially true. In our algorithm, initial intervals are selected differently, but the invariant is still satisfied. Selection of initial intervals. In the first round, process p broadcasts its id, and ranks its id among the ids it receives (line 2). Let rk p be the rank obtained by p. If, among the ids of the participating processes, the rank of the id of p is i, and f 1 is the number of failures that occur in the first round, then i -

f 1 ≤ rk p ≤ i. (1)
procedure rename i (id i ) ; This is because p may miss at most f 1 messages from processes with id smaller than i. In the second round, p sends its rank together with its id. It then estimates, based on the ranks it receives, the number of failures that occur in the first round. To that end, p evaluates for each interval of names I the difference between the number of processes ranked in I and the size of I (line 4-line 5). The estimate est f of the number of failures is then the maximum over all differences. More precisely,

est f = max I⊆[1,rk max] i∈I h i -|I|.
where rk max is the largest rank received by p and h i is-to the knowledge of p-the number of processes that rank their id i in the first round. The estimation est f is upper-bounded by f 1 , the number f 1 of failures that occur in the first round. To see why, consider an interval I = [a, b]. We have:

i∈I h i ≤ |{q : a ≤ rk q ≤ b}| ≤ |{q : a -f 1 ≤ rank(id q , P ) ≤ b}| ≤ |I| + f 1 , (2)
where P is the set of participating processes and rank(id q , P ) is the rank of id q among the ids of the processes in P . The last inequality follows from Equation 1. Finally, p selects a well-formed interval. This is performed in two steps. First, p chooses two integers d, j such that the well-formed interval [d2 j + 1, (d + 1)2 j ] contains rk p , and 2 j is the least power of 2 larger than or equal to est f . However, by equation (2), at most 2 j + est f ≤ 2 j+1 processes may have their rank contained in [d2 j + 1, (d + 1)2 j ]. Then, in order to satisfy Invariant 1, p selects the interval I = [d2 j+1 + 1, (d + 1)2 j+1 ] as its initial interval. Since a process p that selects an interval ⊆ I has its rank rk p contained in [d2 j + 1, (d + 1)2 j ], at most 2 j+1 = |I| processes select intervals I ⊆ I. Invariant 1 is thus satisfied, which preserves the correctness of the CHT-renaming algorithm. Finally, notice that the size of each initial interval is at most 4f 1 , where f 1 is the number of failures in the first round. Hence the total running time is O(log f 1 ) rounds. Proof of correctness. We first establish some properties of the intervals selected in round 2 (Lemma 4 and Lemma 5). The first lemma shows that the intervals selected in round 2 are "large enough" in the following sense: if I is selected, then at most |I| processes select an interval I ⊆ I. This lemma is the key to showing name uniqueness, i.e., no two processes decide on the same name. Notice also that, as p selects I in round 2, a message id , rk from p must have been received by p in round 2. Therefore, |P I | ≤ |{ id , rk : id , rk is received by p and d2 j + 1 ≤ rk ≤ (d + 1)2 j }| Recall that, at process p, h rank denotes the number of messages of the form id, rank received by p in round 2 (line 4). It thus follows from the definition of the number of failures est f estimated by p (line 5) that:

|P I | ≤ d2 j +1≤i≤(d+1)2 j h i ≤ (d + 1)2 j -d2 j + est f ≤ 2 j+1
The last inequality follows from the fact that, at process p, j = log est f . As I = [d2 j+1 + 1, (d + 1)2 j+1 ], |I| = 2 j+1 . Therefore P I ≤ |I|.

The next lemma is the basis to establish that the size of the namespace is at most twice the number of participating processes. It is the analogue of Lemma 5 in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. Proof. Let p denote a process that selects I in round 2. Since I is selected in round 2, a = d2 j+1 + 1 for some d, j ≥ 0. Moreover, the rank rk p of the identity id p of p according to the ids p receives in round 1 satisfies d2 j + 1 ≤ rk p (line 6). Hence, p receives at least d2 j = a-1 2 identities strictly smaller than or equal to d2 j in round 1. Denote by Q = {q 1 , . . . , q m } the set of processes with id ≤ a-1 2 from which p receives a message in round 1. Note that m ≥ a-1 2 . For each process q i ∈ Q that has not failed by the end of round 2, let rk i the rank of id i among the identities received by q i in round 2. We consider two cases:

• The rank of each process q i ∈ Q is smaller than or equal to a-1 2 . That is, for each q i ∈ Q, rk i ≤ a-1 2 = d2 j or q i has failed by the end of round 2. Hence, if [a i , b i ] is the interval selected by q i , a i < a = 2d j+1 + 1 (line 7). Moreover, as [a i , b i ] and

5 7 Figure 1 : 5 V 7 / 8 for every identifier id ∈ V do 9 11 / 13 Figure 2 :

 71578911132 Figure 1: The Approximate Agreement algorithm.

4 let 7 I 8 /* Round 3 , 4 , 9 broadcast(id, I) ; 10 I 11 P 17 Figure 3 :

 4783491011173 Figure 3: The Loose Renaming Protocol.

Lemma 4 .

 4 Suppose that id, I is selected in round 2. Let P I be the set of processes that select an interval I ⊆ I in round 2. Then |P I | ≤ |I|. Proof. Let p denote a process selects interval I in round 2 (line 7). By the code, I is thus of the form [d2 j+1 +1, (d+1)2 j+1 ]. Consider a process p that sends an interval I = [d 2 j +1 +1, (d +1)2 j +1 ] ⊆ I in round 3. Denote by rk the rank obtained by p in the first round (line 2). By definition of d (line 6), d 2 j + 1 ≤ rk ≤ (d + 1)2 j , and as I ⊆ I, it follows that d2 j + 1 ≤ rk ≤ (d + 1)2 j .

Lemma 5 . 1 2

 51 If I = [a, b] is a maximal interval selected by some process round 2, then there are least aprocesses that either select an interval [a , b ] with b < a at the beginning of round 2 or have failed by the end of round 2.

  [a, b] are well-formed intervals, and [a, b] is a maximal interval, b i < b. Hence, in this case, at least a-1 2 processes select an interval [a , b ], b < a or fails by the end of round 2.

While the original lower bound of Herlihy et al.[START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF] applies only to comparison-based algorithms, an argument by Attiya et al.[START_REF] Attiya | Time bounds for decision problems in the presence of timing uncertainty and failures[END_REF] generalizes this bound to a wider class of algorithms, which includes the ones in this paper.

* Additional supports from ANR projects ALADDIN and DISPLEXITY

• There exists a process q i ∈ Q such that rk i > a-1 2 . Without loss of generality, assume that id 1 < . . . < id m , where id i denotes the id of q i . Let q ∈ Q be the process with the smallest identity for which rk > a-1 2 . q thus receives in round 1 at least a-1 2 identities smaller than its own identity id . Since p receives -1 ids smaller than id , at least a-1 2 -( -1) of those identities are not received by p. Hence, at least a-1 2 -+ 1 processes / ∈ Q fail in the first round. Moreover, by definition of q , each process q i , 1 ≤ i ≤ -1 either fails or has rank rk i < rk p . Hence, by the first item above, if q i does not fail, the interval [a i , b i ] it selects is such that b i < a. Therefore, in total a-1 2 -+ 1 + ( -1) = a-1 2 processes fail by the end of round 2 or select an interval [a , b ] with b < a.

In rounds r ≥ 3, processes apply the CHT-renaming algorithm using the intervals selected in round 2 as initial intervals. The next two lemmas generalize Lemma 4 and Lemma 5, respectively, to the intervals held by the processes at the beginning of each round r ≥ 3.

Lemma 6 (Lemma 4 in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]). Suppose that id, I is sent in round r ≥ 3. Let P I be the set of processes that send an interval I ⊆ I in round r. |P I | ≤ |I|.

Proof. For r = 3, the lemma immediately follows from Lemma 4, as each interval sent in round 3 is selected in round 2. For r > 3, the proof can be found [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. The proof depends solely on the code of the CHT-renaming algorithm and the fact that the lemma is true in the rounds preceding r.

Lemma 7 (Lemma 5 in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]). If I = [a, b] is a maximal interval received by some process p during round r ≥ 3, then there are at least a-1 2 processes that either hold an interval [a , b ] with b < a at the beginning of round r or has failed by the end of round r.

Proof. Again the lemma immediately follows from Lemma 5 for r = 3. For r > 3, we rely on the proof of a similar lemma (Lemma 5) in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. There, it is shown that I = [a, b] is a maximal interval received by some process p during round r ≥ 3, then there are at least a -1 processes that either hold an interval [a , b ] with b < a at the beginning of round r or has failed by the end of round r. A close examination of the proof reveals the same argument (replacing a -1 by a-1

2 ) can be used to prove the lemma.

In each round, processes that hold maximal intervals split their interval in half. As a result, the size of the largest interval is halved in each round. This immediately follows from Lemma 6 in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. Lemma 8. For r ≥ 3, let r denote the size of the largest interval sent in round r. Then r ≥ 2 r+1 .

We have now all the ingredients to establish that the algorithm described in Figure 3 solves loose renaming in O(log f ) rounds.

Theorem 9. The algorithm described in Figure 3 terminates in log f 1 + 5 rounds, where f 1 is the number of failures in the first round. Each non-faulty process decides a distinct name in the interval [1, 2n], where n is the number of participating processes. Proof. Termination. Consider an interval I selected by some process p in round 2. By the code, I = [d2 j+1 + 1, (d + 1)2 j+1 ] for some d, j ≥ 0 and we have j = log f , where f is the number of failures that occur in the first round, as estimated by p. As we have seen in the description of the 11 algorithm (paragraph Selection of initial intervals), est f ≤ f 1 . Therefore, |I| = 2 × 2 j ≤ 4est f ≤ 4f 1 . Therefore, 3 , the size of the largest interval sent in round 3 is smaller than or equal to 4f 1 . Then, as by Lemma 8, the length of the largest interval is divided by two in each round, the size of the largest interval sent in round log f 1 + 5 or earlier is 1. As each non-faulty decides if only interval of size 1 are sent in a round, the algorithm terminates in at most log f 1 + 5 rounds.

Name uniqueness. The proof is the same as in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. Suppose that two processes p and p decide the same name a in round r and r respectively. Suppose without loss of generality that r ≤ r . In the round in which they decide, p and p send the interval I = [a, a], and therefore interval containing [a, a] in every preceding round. Since, when p decides, every interval that contains I received by p is equal to I (line 16), p sends also [a, a] in round r. Hence two processes send the same interval of size 1 in round r: a contradiction with Lemma 6.

Namespace. Again, the proof closely follows the proof in [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. Let p be the process that decides the highest name a. In the round r ≥ 3 in which p decides, it sends the interval [a, a]. Therefore, by LemmaS 7, at least a-1 2 processes other than p either sends an interval [a , b ], with b < a in round r of fail by the end of round r. The number of participating processes n is thus at least n ≥ a-1 2 + 1, from which we conclude that a ∈ [1, 2n].

Discussion

This paper presents the first early-deciding upper bounds for synchronous renaming. We show that, surprisingly, renaming can be solved in constant number of rounds if the number of failures f is limited to O( √ n), while in the general case, renaming can always be solved in O(log f ) communication rounds. In the wait-free case, i.e. for f = n -1, this upper bound is matched asymptotically by the Ω(log n) lower bound of Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in messagepassing systems[END_REF]. It remains an open question whether this is tight for other values of f .