S Fergani
email: soheib.fergani@gipsa-lab.grenoble-inp.fr

O Sename

L Dugard
email: luc.dugard@gipsa-lab.grenoble-inp.fr

A LPV/H ∞ Global Chassis Controller for performances Improvement Involving Braking, Suspension and Steering Systems

Keywords: Vehicle dynamics, Braking, Suspension, Steering, LPV, H ∞ control

This paper is concerned with the design of a multivariable Global Chassis Controller (GCC), using LP V /H ∞ robust controllers for suspension, active steering and electro-mechanical braking actuators which aim at improving comfort and safety performance in critical driving situations. The proposed solution is to schedule the three control actions (braking, steering and suspension) according to the driving situation evaluated by a specific monitor. In emergency cases, the GCC provides a working hierarchical use of the 3 controllers, depending on the dangerousness of the driving situation. Simulations on a complex nonlinear full vehicle model, subject to critical driving situations, show the reliability and robustness of the solution.

INTRODUCTION

Automotive light vehicles are complex systems involving different dynamics. On one side, vertical, roll and pitch behaviors are often related to comfort performances (even if roll is also linked to safety characteristics, [START_REF] Gáspár | Toward global chassis control by integrating the brake and suspension systems[END_REF]), and are rather slow dynamics. On the other hand, safety performances are mainly characterized by the longitudinal, lateral and yaw dynamics. This paper aims at controlling all those dynamics with a GCC design strategy. The new trends in vehicle dynamic control (either commercial or heavy) are to synthesize multivariable controllers able to achieve both comfort and safety according to the vehicle driving situation (e.g. normal, dangerous or critical) and to enhance performances using the available actuators. This led to an increasing research in this area. Some interesting results have been already obtained. In [START_REF] Gáspár | The design of an integrated control system in heavy vehicles based on an LPV method[END_REF], a heavy vehicle Linear Parameter Varying (LPV) model was introduced with a scheduled robust control, involving suspensions and braking actions. In [START_REF] Chou | Global vehicle control using differential braking torques and active suspension forces[END_REF], an interesting nonlinear control law involving suspension and braking actuators for commercial cars was developed. More recently, [START_REF] Falcone | Predictive active steering control for autonomous vehicle systems[END_REF] a model predictive approach (involving online optimization) using braking and steering actuators proposed. Following our previous studies [START_REF] Doumiati | Gain-scheduled lpv/hinf controller based on direct yaw moment and active steering for vehicle handling improvements[END_REF], Poussot-Vassal et al. (2011a), [START_REF] Poussot-Vassal | Vehicle dynamic stability improvements through gain-scheduled steering and braking control[END_REF]) a new LPV Global Chassis Control is developed in this paper, using EMB at the rear axle, AS at the front axle and active suspensions actuators. The main objective is to enhance the vehicle handling and safety properties during critical driving situations (eg, large lateral accelerations, ...). Thanks to two high level monitoring parameters, a coordinated control of the three kinds of actuators (Active Steering, Electro-Mechanical Braking, and active suspension actuators) is obtained. Indeed, while the lateral dynamics (yaw control) is handled by the braking/steering control, the control of the vertical dynamics using the suspension actuators is actually scheduled according to the level of emergency situations, allowing to set (in real time) the suspension performance from "soft" (normal situation) to "hard" (critical situation). This control approach is performed in the H ∞ /LP V framework. The interest of the proposed GCC is that, more than a simple controller, it provides a hierarchical use of the control actions. First, when a dangerous situation is detected through the braking monitor R b , the braking action is limited accordingly in order to bring back the force into the linear stable zone of the tire characteristic. To efficiently handle critical situations, the active steering and the active suspensions are activated, thanks to the use of a scheduling parameter R s function of the braking monitor R b . The whole strategy allows to improve the road handling and to save energy, thanks to a smart progressive activation and coordination of the braking, suspension and steering actuators, according to the driving situation. The paper is structured as follows: Section 1 provides introductive elements and notations. Section 2 briefly introduces the models used for synthesis and validation purpose, together with their limitations. In Section 3, the main contribution of the paper, in addition to the monitoring strategy for braking, is to coordinate the three actuators (steering, braking and suspension) to enhance the vehicle performances. Performance analysis is done in Section 4 through time domain simulations performed on a complex nonlinear full vehicle model. Conclusions and discussions are given in the last Section. Throughout the paper, the following notation will be adopted: index i = {f, r} and j = {l, r} are used to identify vehicle front, rear and left, right positions re-

VEHICLE MODELING

Dynamical equations: In this paper, a full nonlinear vehicle model is involved. This model and the corresponding parameters are detailed in [START_REF] Poussot-Vassal | Vehicle dynamic stability improvements through gain-scheduled steering and braking control[END_REF]. It reproduces the vertical (z s ), longitudinal (x), lateral (y), roll (θ), pitch (φ) and yaw (ψ) dynamics of the chassis. It also models the vertical and rotational motions of the wheels (z usij and ω ij respectively), the slip ratios

(λ ij = vij -Rij ωij cos βij max(vij ,Rij ωij cos βij )
) and the center of gravity side slip angle (β cog ) dynamics as a function of the tires and suspensions forces. The dynamical equations are given in equation ( 1), where F txi = F tx il + F txir , F tyi = F ty il + F tyir , F tzi = F tz il + F tzir and F szi = F sz il + F szir , (i = {f, r}). This model will be used in simulation for validation purpose (see Section 4). The main interest of the full vehicle model is that it takes into account nonlinear load transfer, slipping and side slip angles that are essential phenomena entering in the tire force, and consequently, in the global chassis dynamics, especially in dangerous driving situations. Suspensions model: Suspensions are usually modeled by a spring and a damping element. In real vehicles, their characteristics are nonlinear (see e.g. [START_REF] Zin | Robust LPV -H ∞ control for active suspensions with performance adaptation in view of global chassis control[END_REF]). Here, as long as the main focus is on the longitudinal, lateral, yaw behaviors and since active suspensions are considered, without loss of generality, linear models are assumed for stiffness and damping as:

F szij = k ij (z sij -z usij ) + c ij ( żsij -żusij ) + u H∞ ij (2)
where k ij : the stiffness coefficient, c ij : the damping coefficient and u H∞ ij : the suspension control. Actuators dynamic: in the paper, the considered actuators are modeled as first order low-pass transfer functions:

• The active suspension systems:

Ḟsuspij = τ (F 0 suspij -F suspij ) (3)
where τ = 200rad/s is the actuator cut-off frequency. F 0 suspij and F suspij are the suspension controller and actuator outputs, respectively.

• The EMB actuators, providing the braking torque:

Ṫbrj = ̟(T 0 brj -T brj ) (4)
where, ̟ = 70rd/s is the actuator cut-off frequency, T 0 brj and T brj are the rear braking controller and actuator outputs respectively. In this paper, only the rear braking system is used to avoid coupling phenomena occurring with the steering system and because it affects more the vehicle yaw behavior than the front one does (j = r, l).

• The AS actuator providing an additional steering angle: δ+ = κ(δ 0 -δ + ) (5) where, κ = 10rd/s is the actuator cut-off frequency, δ 0 and δ + are the steering controller and actuator outputs respectively. This actuator is constrained between [-5, +5] degrees.

MAIN RESULT: GCC STRUCTURE, SYNTHESIS AND SUPERVISION

This section is devoted to the description of the main result of this paper, namely, the multivariable Global Chassis Controller (GCC) involving front active steering, rear braking and active suspension actuators (see Fig. 1).

The objective is to improve handling and safety in critical situations, first, by using the rear braking actuators, then to activate the steering action and set the active suspension dampers to "hard" in order to improve the car handling performances. Conversely, during normal situations, the steering is deactivated, the braking action is attenuated, and the suspension dampers are set to "soft" to improve passengers comfort. The idea is that the GCC uses the monitoring parameters to generate the braking torques that aim at improving handling performances and enhancing the passengers safety when critical driving situations appear. It also provides

                             vx = -F tx f cos(δ) + F txr + F ty f sin(δ) /m -ψv y vy = -F tx f sin(δ) + F ty r + F ty f cos(δ) /m + ψv x zs = -F sz f + F szr + F dz /m s zusij = F szij -F tzij /m usij θ = (F sz rl -F szrr )t r + (F sz f l -F sz f r )t f + mh vy /I x φ = F sz f l f -F szr l r -mh vx )/I y ψ = l f (-F tx f sin(δ) + F ty f cos(δ)) -l r F ty r + (F tx f r -F tx f l )t f cos(δ) -(F txrr -F tx rl )t r + M dz /I z ωij = (R ij F txij -T f bij )/I w βcog = (F ty f + F ty r )/(mv x ) + ψ (1)
an additive steering angle and sets the suspension active dampers to "hard", providing then the maximum help to the driver and avoiding emergency situations.

The monitoring strategy

The aim of the monitoring is first to evaluate the driving situation and then to tune brake, steer and suspension control objectives to overcome conflicting effects. This strategy, introduced by the authors in Poussot-Vassal et al. (2011a) to schedule braking and steering action, is extended here to the three control actions. In a real car, such a block may be much more complex, but here, since as far as attitude and yaw stability are concerned, the following strategy, based on the measurement of the longitudinal slip ratio of the rear wheels (s rj ) is efficient while being simple. As previously introduced, two monitor variables are computed :

(1) Braking monitor: R b = min j=l,r (r bj ), is a function of the absolute value of the slip ratio (|s rj |). r bj is defined as a relay (hysteresis like) function: → 0 when 'on', → 1 when 'off'. The switch 'on' (resp. 'off') threshold is s + (resp s -) (see [START_REF] Poussot-Vassal | Vehicle dynamic stability improvements through gain-scheduled steering and braking control[END_REF]). When the slipping is low, the vehicle is in a normal situation, hence R b → 1. When the slip ratio raises and becomes greater than s + , a critical situation is detected, then R b → 0. As R b is function of the slip ratio, the choice of s + (resp. s -) is done according to the tire friction curve. Here (and in a general case), s + = 9% and s -= 8%, in order to delimitate the linear and peak tire friction force with the unstable part of the tire. See in Section 3.2.1 how the braking controller is tuned according to the R b parameter and its role in the control strategy.

(2) Suspension and Steering monitor: R s is defined as :

Rs      → 1 when 1 > R b > R 2 crit = R b -R 1 crit R 2 crit -R 1 crit when R 1 crit < R b < R 2 crit → 0 when 0 < R b < R 1 crit (6)
when R b > R 2 crit (= 0.9), i.e. when low slip (< s -) is detected, the vehicle is not in an emergency situation and R s is set to 1. When R b < R 1 crit (= 0.7), i.e. when high slip occurs (> s + ), a critical situation is reached and R s is set to 0. Intermediate values of R b will give intermediate driving situations. Hence, as explained in Section 3.2.2, in the first case, the suspension dampers will be set to "soft" to enhance comfort and there is no need to use a steering assistance. In the second case, the suspension control is "hard" to improve road handling and the steering assistance is essential to enhance the car handling and passengers safety (intermediate performances will be reached for R b values in between).

In the following, all controllers are derived thanks to the LPV/H ∞ methodology in order to meet the monitor requirements. Such a synthesis makes it possible to smoothly change the control performances thanks to the parameters (here R b and R s ), guaranteeing internal stability (avoiding switching) and minimizing the H ∞ norm.

Global chassis control design

The GCC is developed in two steps. First the steering/braking controllers are designed using the linear bicycle model. The suspension controller is synthesized using the linear vertical full car model. In each case the LP V /H ∞ controllers scheduled by the monitoring parameters R s and R b , are developed using the approach dedicated to polytopic systems.

Problem formulation for the design of the braking/steering control

Let introduce first the extended bicyle model described in Eq.( 7).

The considered LP V /H ∞ control problem is described in Fig( 2) with the following scheduled weighting functions :

• W e ψ = 10 s/500+1 s/50+1 , is used to shape the yaw rate error (e ψ = ψrefψ) • W vy = 10 -3 , attenuates the lateral acceleration

• W T b rj (R b ) = (1 -R b ) s/10̟+1 s/100̟+1 , attenuates the yaw moment control input • W δ 0 (R s ) = R s s/κ+1
s/10κ+1 , attenuates the steering control input according to value of R s where ̟ (κ) is the braking (steering) actuator cut-off frequency.

• When R b → 1, the tire is in the linear zone, there is no risk of locking; the weighting function gain of W T b rj is chosen to be low. Therefore, the braking control is activated. • When R b → 0, a high slip ratio is detected, and a critical situation is detected, the tire may lock, so the gain of the weighting function is set to be high. This allows to deactivate the braking signal and therefore, a natural stabilisation of the slip dynamic is achieved.

On the other hand, when the driving situation is dangerous and presents high risk for passengers, the steering control

  vy ψ β   =        -C f -C r mv v - -C f l f + C r l r mv 0 -C f l f + C r l r I z v -C f l 2 f -C r l 2 r I z v 0 0 1 + l r C r -l f C f mv 2 - C f + C r mv        v y ψ β +       C f m - 1 m 0 C f l f I z 0 t r RI z C f mv 0 1 mv       δ F dy T brj (7)
is activated through W δ 0 (R s ). The steering action depends on the varying parameter R s which depends on the driving situation monitored by the parameter R b , with R s (.) ∈ P Rs and P Rs := {R s ∈ R : R s ≤ R s ≤ R s } (where R s = 0.1 and R s = 1).

+ - ψref (v)
We ψref GCC(Rb, Rs)

WT brj (Rb)

Wδ0(R s ) Bicycle W vy ψ z1 z2 z3 z4
Tb rj , δ 0

  ẋ z y   =   A(R(.)) B 1 (R(.)) B 2 C 1 (R(.)) D 11 (R(.)) D 12 C 2 0 0     x w u   (8)
where x includes the state variables of the system and of the weighing functions, w = F dy and u = [δ 0 , T brj ] are the exogenous and control inputs respectively

; z = [z 1 , z 2 , z 3 , z 4 ] = [W e ψ e ψ , W vy vy , W T b rj (R b )T brj , W δ 0 (R s )δ 0 ]
holds for the controlled output, and y = ψref (v) -ψ is the controller input ( ψref (v) is provided by a reference bicycle model as the one described in ( 7)). Notice that the LPV model ( 8) is affine w.r.t parameters R s and R b and can be described as a polytopic system, i.e. a convex combination of the systems defined at each vertex formed by P R (.), namely Σ(R(.)) and Σ(R(.)).

Problem formulation for the design of the suspension control

The control of the vertical dynamics is ensured through the suspension system, in order to achieve frequency specification performances, see [START_REF] Poussot-Vassal | Optimal Skyhook control for semi-active suspensions[END_REF] and [START_REF] Sammier | Skyhook and H ∞ control of active vehicle suspensions: some practical aspects[END_REF]. According to the driving situation given by R b and as soon as a critical one is detected, the parameter R s decreases . The steering control is therefore activated and the suspension control is tuned to enhance roadholding. This controller is tuned, thanks to the LPV/H ∞ techniques using a full linear vertical model and the following generalized plant, (see Fig. 3) including parameterized weighting functions :

where

W zs (R s ) = R s s 2 +2ξ11Ω11s+Ω11 2
s 2 +2ξ12Ω12s+Ω12 2 is shaped in order to reduce the bounce amplification of the suspended mass (z s ) between [0,12].

W θ (R s ) = (1 -R s ) s 2 +2ξ21Ω21s+Ω21 2 s 2 +2ξ22Ω22s+Ω22
2 attenuates the roll bounce amplification in low frequencies. The parameters of these weighting functions are obtained using genetic algorithm optimization as in [START_REF] Do | An LPV control approach for semi-active suspension control with actuator constraints[END_REF]. W u = 3.10 -2 is set to shape the control signal.

K susp (R s ) - - z defij Σ vert -W zs (R s ) -z 1 -W θ (R s ) -z 2 u H∞ ij W u z 4 Fig. 3. Suspension system generalized plant. Remark 1. When R b > R 2
crit , the braking is in the linear zone (tire stable zone), hence, suspensions are tuned to improve comfort (i.e. R s → 1). Conversely, when R b < R 1 crit , the braking becomes critical, hence, suspensions are hard (i.e. R s → 0). When R s → 1 (resp. → 0), the suspension tends to improve comfort while deteriorating road-holding (and reciprocally). For deeper insight on the design, see earlier papers of the authors (Poussot-Vassal et al. (2011a)). The originality relies on the scheduling of the weighting functions that makes the controllers for suspension and steering be activated simultaneously when a critical driving situation is detected, while the braking torque is penalized to avoid wheel locking, to provide better stability and handling to the vehicle.

According to Fig. 3, the following parameter dependent suspension generalized plant (Σ gv (R s )) is obtained:

Σ gv (R s ) :=    ξ = A(R s )ξ + B 1 w + B 2 u z = C 1 ξ + D 11 w + D 12 u y = C 2 ξ + D 21 w + D 22 u (9) where ξ = [χ vert χ w ] T ; z = [z 1 z 2 z 3 ] T ; w = [z rij F dx,y,z M dx,y ] T ; y = z defij ; u = u H∞ ij ;
χ w are the vertical weighting functions states.

The LPV system (Eq.9) includes a single parameter and can be described as a polytopic system, i.e, a convex combination of the systems defined at each vertex of a polytope defined by the bounds of the varying parameter.

SIMULATION RESULTS

Some frequency domain plots are provided to analyse the performances of the lateral and vertical controllers. Time domain simulations are performed on the full nonlinear vehicle model given in Section 2, including nonlinear suspensions forces. In,the sequel, the performances obtained by the proposed gain-scheduled controller, denoted as 'LPV', are analyzed and compared to the Renault Mégane Coupé car (without control, denoted as 'Reference car') and, for sake of completeness, with a simple LTI/H ∞ controller (without scheduled gains), denoted as 'LTI'. Note that the LT I/H ∞ controller is obtained by solving the previous H ∞ problems frozen with R s = 0.1 and R b = 0.9. The following scenario is used:

(1) the vehicle runs at 130km/h in straight line, (2) 5cm bump on the left wheels (from t = 0.5 to 1s), (3) a double line change manoeuvre is performed (from t = 2 to 6s) by the driver, (4) lateral wind occurs at vehicle's front, generating an undesirable yaw moment (from t = 2.5 to 3s), (5) 5cm bump on the left wheels, during the manoeuvre (from t = 3 to 3.5s),

The resulting monitored signals are obtained (see Fig. 4). shows that the braking monitor R b (thanks to the slip ratio measure) attenuates the control gain of the braking controller (compared to LTI controller) in order to reduce the torque control (see Fig. 9) and brings back the slip ratio close to the linear zone. It shows also that the maximum braking forces are not efficient enough to stabilize the vehicle when the critical situation appears. At this moment, the scheduling parameter R s takes the value that provides the necessary assistance to driver, either by giving an additional steering δ + and setting the suspension dampers to "hard" to enhance roadholding. This control strategy allows to reduce lateral accelerations and to enhance yaw rate tracking and stability, compared to the non controlled one (see Fig. 5 and6).

Good improvements of the chassis displacement and roll motion are shown in Fig. 7 and8, thanks to the coordination between the three actuators, which allows to get a significant improvement of the desired performances. Fig. 11 shows the steering control contribution for the LTI and LPV case. The steering control seems saturated, but in fact it is scheduled with the varying parameter R s .

According to the driving situation, the value of R s changes, but this value can stay constant over a short period of time, and the output of the steer control will have a behavior similar to the saturated one. Remark 2. In the previous simulations, the LTI control strategy gives good results. However, since the rear wheels lock during the manoeuvre as shown in Fig. 9 and 10 with a very high risk of loss of manoeuvrability and safety degradation, the LPV control remains the best way of dealing with the braking issues. Moreover, it enhances performances and stability, using the previously presented integrated control strategy. Furthermore, the LTI controller uses all the actuators simultaneously, without any coordination (i.e, more energy consumption in the LTI case then in the proposed LPV strategy since the actuators actions are activated only when necessary).

CONCLUSION

In this paper, a new LP V /H ∞ GCC strategy is developed, including braking, steering and suspension actuators in order to improve the performances and to handle critical driving situations. Simulations of a consistent representative driving situation, performed on a complex nonlinear model, have shown the efficiency of the proposed approach.

The authors stress that one of the advantages of the braking method used is that the exact knowledge of the tire force curve is not needed to guarantee good performances.

As well, the strategy previously developed can be used with other braking strategies (in particular with the local ABS, see [START_REF] Tanelli | Sliding mode slip-deceleration control for brake-by-wire control systems[END_REF]).

As a perspective, extensions to semi active suspension will be considered following the recent authors works in that field (see [START_REF] Savaresi | Semi-Active Suspension Control for Vehicles[END_REF]).

Fig. 1 .

 1 Fig. 1. Global chassis control Implementation scheme.

Fig. 2 .

 2 Fig. 2. Generalized plant for braking steering control synthesis. The generalized plant corresponding to Fig 2 is LPV and can be modeled as,

Fig. 4 .

 4 Fig. 4. Monitoring signals

Fig. 9 .

 9 Fig. 9. Rear right/left Breaking torque.

Fig. 10 .

 10 Fig. 10. Rear right/left Breaking torque.

Fig. 11 .

 11 Fig. 11. LPV Steer control input δ + (left), LTI Steer control input δ + (right).

  R ij = R -(z usij -z rij ) the effective tire radius, m = m s + m us f l + m us f r + m us rl +m usrr the total vehicle mass, δ = δ d + δ + is the steering angle (δ d , the driver steering input and δ + , the additional steering angle provided by steering actuator, see Section 3) and T bij the braking torque provided by the braking actuator (see Section 3). The model parameters are those of a Renault Mégane Coupé (see Table.1). They were obtained during a collaborative study with the MIPS laboratory in Mulhouse, through identification with the real data.

	Symbol	Value	Unit	Signification
	ms	350	kg	suspended mass
	mus f j	35	kg	front unsprung mass
	mus rj	32.5	kg	rear unsprung mass
	Ix; Iy; Iz	250; 1400; 2149	kg.m 2	roll, pitch, yaw inertia
	Iw	1	kg.m 2	wheel inertia
	t f ; tr	1.4; 1.4	m	front, rear axle
	l f ; lr	1.4; 1	m	COG-front, rear distance
	R	0.3	m	nominal wheel radius
	h	0.4	m	chassis height
	Table 1. Renault Mégane Coupé parameters
	spectively. Then, index {s, t} holds for forces provided
	by suspensions and tires respectively. {x, y, z} holds for
	forces and dynamics in the longitudinal, lateral and ver-
	tical axes respectively. Then let v = v 2 x + v 2 y denote the
	vehicle speed,

This work was supported by the French National Research Agency, in the context of the project ANR BLAN 0308


Evangelos Bampas

Anissa Lamani
email: anissa.lamani@u-picardie.fr

Franck Petit
email: franck.petit@lip6.fr

Mathieu Valero
email: mathieu.valero@lip6.fr

Self-Stabilizing Balancing Algorithm for Containment-Based Trees

Keywords: self-stabilization, balancing algorithms, containment-based trees

Containment-based trees encompass various handy structures such as B+-trees, R-trees and M-trees. They are widely used to build data indexes, range-queryable overlays, publish/subscribe systems both in centralized and distributed contexts. In addition to their versatility, their balanced shape ensures an overall satisfactory performance. Recently, it has been shown that their distributed implementations can be faultresilient. However, this robustness is achieved at the cost of unbalancing the structure. While the structure remains correct in terms of searchability, its performance can be significantly decreased. In this paper, we propose a distributed self-stabilizing algorithm to balance containment-based trees.

Self-Stabilizing Balancing Algorithm for Containment-Based Trees

Evangelos Bampas * , Anissa Lamani † , Franck Petit ‡ , and Mathieu Valero §

I. INTRODUCTION

Several tree families are based on a containment relation. Examples include B+-trees [START_REF] Bayer | Organization and maintenance of large ordered indices[END_REF], R-trees [START_REF] Guttman | R-trees: a dynamic index structure for spatial searching[END_REF], and M-trees [START_REF] Ciaccia | M-tree: An efficient access method for similarity search in metric spaces[END_REF]. They are respectively designed to handle intervals, rectangles, and balls. Their logarithmic height ensures good performance for basic insertion/deletion/search primitives. Basically they rely on a partial order on node labels. They can be specified as follows:

1) Tree nature. The graph is acyclic and connected.

2) Containment relation. Every non-root node n satisfies label(n) ⊑ label(f ather(n)). 3) Bounded degrees. The root has between 2 and M children, each internal node has between m and M children (M ≥ 2m). 4) Balanced shape. All leaves are at the same level. In a distributed context, no node has a global knowledge of the system as each node has only access to its local information. As a consequence, the aforementioned invariants should be expressed as "local" constraints; at the level of a node. Operations preserving or restoring those invariants should also be "as local as possible".

Preserving the tree nature has been addressed in previous work [START_REF] Bianchi | Stabilizing peerto-peer spatial filters[END_REF], [START_REF] Jagadish | Vbi-tree: A peer-to-peer framework for multi-dimensional indexing schemes[END_REF], [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF]. It is tightly related to the distribution model of the structure, the centralized case being far less stressing. The containment relation is easy to preserve as node labels can be "enlarged" or "shrunk". The bounded node degrees are ensured with split or collapse primitives when a node has too many or too few children, respectively. The balanced shape of the tree is especially important in terms of performance; in conjunction with node degree bounds, it ensures that the tree has logarithmic height. A number of approaches have been proposed in the literature in order to balance tree overlays. However, these solutions have many limitations in particular when applied to containment-based tree overlays.

The works in [START_REF] Bianchi | Stabilizing peerto-peer spatial filters[END_REF], [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF] have the extra property of being selfstabilizing. A self-stabilizing system, as introduced in [START_REF] Edsger | Self-stabilizing systems in spite of distributed control[END_REF], is guaranteed to converge to the intended behavior in finite time, regardless of the initial states of nodes. Self-stabilization [START_REF] Edsger | Self-stabilizing systems in spite of distributed control[END_REF] is a general technique to design distributed systems that can handle arbitrary transient faults.

Figure 1 shows the overlay lifecycle borrowed from [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF]. Rectangles refer to states of the distributed tree. Transitions are labelled with events (join and faults) or algorithms (repair and balance) triggering them 1 . Initially the tree is empty, then some peers join the overlay building a searchable tree. The balancing algorithm eventually balances the tree. In case of joins the tree may become unbalanced. In case of faults the tree may become disconnected. The repair algorithm eventually reconnects the tree and fixes containment relation. The distinction between searchable and balanced states emphasizes a separation of concerns between correction and performance. Basically repair is about correction, while balance is about Balanced Disconnected Searchable join balance repair faults Fig. 1: Containment-based tree overlay lifecycle. The overlay is balanced when all invariants are ensured, searchable when all but the fourth invariant are ensured, and disconnected when at least the tree nature invariant is violated. performance. It is also interesting to point out that if the balance algorithm is self-stabilizing, then the join algorithm does not have to deal with performance. Moreover, if the repair algorithm is self-stabilizing, a peer quitting the overlay does not have to communicate with any other peer; departures can be handled as faults.

A. Related Work

DR-tree [START_REF] Bianchi | Stabilizing peerto-peer spatial filters[END_REF] is a distributed version of R-trees [START_REF] Guttman | R-trees: a dynamic index structure for spatial searching[END_REF] developed to build a brokerless peer to peer publish/subscribe system. Each computer stores a leaf and some of its consecutive ancestors. The closer node to the root stored by a computer is called its "first node". Each computer knows some ancestors of its first node; from its grand father to the root. The tree may become unbalanced in case of faults. When a computer detects that the computer storing the father of its first node is crashed, it broadcasts a message in the subtree starting from its first node. All leaves belonging to that subtree will be reinserted elsewhere starting from an ancestor of the crashed peer's first node. As a consequence, no balancing primitive is used. However, up to half of the nodes of the tree may have to be reinserted (if faults occur near the root). SDR-tree [START_REF] Du Mouza | SD-Rtree: A scalable distributed rtree[END_REF] is an indexing structure distributed amongst a cluster of servers. Its main aim is to provide efficient and scalable range queries. It builds balanced full binary trees satisfying containment relation. Each computer stores exactly one leaf and one internal node. Instead of classic split and collapse operations, this paper extensively uses subtree heights to guarantee the balanced shape of the structure. They adapt the concept of rotation [START_REF] Landis | An algorithm for the organization of information[END_REF] to multidimensional data. However they don't mention how to repair the structure in case of crashes.

VBI [START_REF] Jagadish | Vbi-tree: A peer-to-peer framework for multi-dimensional indexing schemes[END_REF], a sequel of BATON [START_REF] Jagadish | Baton: a balanced tree structure for peer-to-peer networks[END_REF], is a framework to build distributed spatial indexes on top of binary trees. It provides default implementations for all purely structural concerns of binary trees: maintaining father and children links, rotations, etc. Developers only have to focus on several operations, mostly related to node labeling (such as split and collapse). However, despite their interesting approach of mapping any tree on a binary one, they do not provide a handy way to parameterize the system. While modifying node degree bounds should be a simple way to tune system performances, the fixed degree of the core structure (a tradeoff between reusability and performance) cannot be bypassed.

The solution proposed in [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF] also deals with full binary trees satisfying containment relation. The distribution is the same as in the SDR-tree; each computer stores exactly one leaf and one internal node. The core contribution of this paper is to prove that if the leaf and the internal node held by each machine are randomly chosen, then the graph between computers (namely, the communication graph) is very unlikely to be disconnected in case of faults. More precisely, faults disconnect the logical structure, but not the communication graph. This paper proposes an algorithm exploiting the connectivity of the communication graph to repair the logical structure restoring the tree nature, containment relation and bounded node degrees. This approach is shown as much cheaper than [START_REF] Bianchi | Stabilizing peerto-peer spatial filters[END_REF], both in terms of recovery time and cost in messages. However the restored tree can be slightly unbalanced and the restoration of its shape is not addressed in the paper.

The algorithm proposed in [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF] has the desirable property of being self-stabilizing. There exist several distributed, selfstabilizing algorithms in the literature that maintain a global property based on node labels, e.g., [START_REF] Herman | Available stabilizing heaps[END_REF], [START_REF] Bein | Snap-stabilizing optimal binary search tree[END_REF], [START_REF] Caron | Snap-stabilizing prefix tree for peer-to-peer systems[END_REF]. The solutions in [START_REF] Herman | Available stabilizing heaps[END_REF], [START_REF] Bein | Snap-stabilizing optimal binary search tree[END_REF] achieve the required property (resp. Heap and BST) by reorganizing the key in the tree. They have no impact on the tree topology. The solution in [START_REF] Caron | Snap-stabilizing prefix tree for peer-to-peer systems[END_REF] arranges both node labels (or, keys) and the tree topology. None of the above self-stabilizing solutions deal with the balanced property.

B. Contribution

In this paper, we first show that edge swapping can be used as a balancing primitive. Then we propose a distributed self-stabilizing algorithm balancing any containment-based tree, such as B+-trees [START_REF] Bayer | Organization and maintenance of large ordered indices[END_REF], R-trees [START_REF] Guttman | R-trees: a dynamic index structure for spatial searching[END_REF] and M-trees [START_REF] Ciaccia | M-tree: An efficient access method for similarity search in metric spaces[END_REF]. Our algorithm can be used in [START_REF] Du Mouza | SD-Rtree: A scalable distributed rtree[END_REF], [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF] to enhance the performance of repaired trees, or in [START_REF] Jagadish | Vbi-tree: A peer-to-peer framework for multi-dimensional indexing schemes[END_REF], [START_REF] Jagadish | Baton: a balanced tree structure for peer-to-peer networks[END_REF] as a "core" balancing mechanism. We further prove the correctness of the algorithm and investigate its practical convergence speed via simulations.

C. Roadmap

In Section II, we argue that edge swapping is practically better suited than rotations to balance containment-based trees. In Section III, we present the model we use to describe our algorithm. In Section IV, we propose a distributed selfstabilizing algorithm that relies on edge swapping to balance any containment-based tree. In the same section, we prove the termination and correctness of the algorithm. In Section V, we investigate the practical termination time of our algorithm via simulations. Section VI contains some concluding remarks and possible directions for future work.

II. BALANCING PRIMITIVE

Let α ∈ N. A tree is balanced iff all its nodes are balanced. A node is balanced iff the heights of any pair of its children differ at most by α. In the remainder of this paper, we make two assumptions: • α ≥ 1.

• each non-leaf node has at least two children. The assumption on α is weaker than those of [START_REF] Du Mouza | SD-Rtree: A scalable distributed rtree[END_REF], [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF], [START_REF] Jagadish | Vbi-tree: A peer-to-peer framework for multi-dimensional indexing schemes[END_REF] and still ensures logarithmic height of the tree [START_REF] Luccio | On the height of height-balanced trees[END_REF]. The degree assumption is also weaker than those of [START_REF] Du Mouza | SD-Rtree: A scalable distributed rtree[END_REF], [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF], [START_REF] Jagadish | Vbi-tree: A peer-to-peer framework for multi-dimensional indexing schemes[END_REF] and allows more practical tree configurations.

Basically, a balancing primitive is an operation that eventually reduces the difference between the heights of some subtrees by modifying several links of the tree. Those link modifications may have some semantic impact if they break node labeling invariants.

A. Rotation

In BST [START_REF] Cormen | Introduction to Algorithms[END_REF] and AVL [START_REF] Landis | An algorithm for the organization of information[END_REF], the well known rotation primitive is used to ensure the balanced shape of the tree. However, when dealing with structures relying on partially ordered data, rotations do have a semantic impact. Moreover, in a distributed context, if a node n and its father or grandfather concurrently execute rotations, they may both "write" f ather(n). It follows that the use of distributed rotations requires synchronization to preserve tree structure.

B. Edge swapping

Given two edges (a, b) and (c, d), swapping them consists in exchanging their tails (resp. heads). Formally, swap((a, b), (c, d)) modifies the edges of the graph as follows:

E(G) := E(G) -{(a, b), (c, d)} + {(a, d), (c, b)}.

III. MODEL

In this paper, we consider the classical local shared memory model, known as the state model, that was introduced by Dijkstra [START_REF] Edsger | Self-stabilizing systems in spite of distributed control[END_REF]. In this model, communications between neighbours are modeled by direct reading of variables instead of exchange of messages. The program of every node consists in a set of shared variables (henceforth referred to as variable) and a finite number of actions. Each node can write in its own variables and read its own variables and those of its neighbors. Each action is constituted as follows:

< Label >::< Guard > < Statement >
The guard of an action is a boolean expression involving the variables of a node u and its neighbours. The statement is an action which updates one or more variables of u. Note that an action can be executed only if its guard is true. Each execution is decomposed into steps.

The state of a node u is defined by the value of its variables. It consists of the following pieces of information:

• An integer value which we call the height value or height information of node u. • Two arrays that contain the IDs of the children of u and their height values. For the sake of generality, we do not make any assumptions about the number of bits available for storing height information, thus the height value of a node can be an arbitrarily large (positive or negative) integer.

The configuration of the system at any given time t is the aggregate of the states of the individual nodes. We will sometimes use the term "configuration" to refer to the rooted tree formed by the nodes.

Definition 1: We denote by C(t) the configuration of the system at time t ≥ 0. For a node u, we denote by h u (t) the value of its height variable in C(t), by h ⋆ u (t) its actual height in the tree in C(t), by S u (t) the set of children of u in C(t), and by S ⋆ u (t) the set of nodes in the subtree rooted at u in C(t). Let C(t) be a configuration at instant t and let I be an action of a node u. I is enabled for u in C(t) if and only if the guard of I is satisfied by u in C(t). Node u is enabled in C(t) if and only if at least one action is enabled for u in C(t). Each step consists of two sequential phases executed atomically: (i) Every node evaluates its guard; (ii) One or more enabled nodes execute their enabled actions. When the two phases are done, the next step begins. This execution model is known as the distributed daemon [START_REF] Burns | On relaxing interleaving assumptions[END_REF]. To capture asynchrony, we assume a semi-synchronous scheduler which picks any nonempty subset of the enabled nodes in the current configuration and executes their actions simultaneously. We do not make any fairness assumptions, thus the scheduler is free to effectively ignore any particular node or set of nodes as long as there exists at least one other node that can be activated.

Definition 2: We refer to the activation of a non-empty subset A of the enabled nodes in a given configuration as an execution step. If C is the configuration of the system before the activation of A and C ′ is the resulting configuration, we denote this particular step by C -→ A C ′ . An execution starting from an initial configuration C 0 is a sequence C 0 -→ A1 C 1 -→ A2 C 2 -→ . . . of execution steps. Time is measured by the number of steps that have been executed. An execution is completed when it reaches a configuration in which no node is enabled. After that point, no node is ever activated.

If a node was enabled before a particular execution step, was not activated in that step, and is not enabled after that step, then we say that it was neutralized after that step.

Definition 3: Given a particular execution, an execution round (or simply round) starting from a configuration C consists of the minimum-length sequence of steps in which every enabled node in C is activated or neutralized at least once.

Remark 1: To simplify the presentation, we will assume throughout the rest of the paper that the arrays containing the IDs of the children of each node and copies of their height values are consistent with the height values stored by the children themselves in the current configuration of the system. It should be clear that maintaining these copies up to date can be achieved with a constant overhead per execution step.

IV. SELF-STABILIZING BALANCING SOLUTION

In this section, we present our self-stabilizing algorithm for balancing containment-based trees, we provide some termination properties, and we prove that any execution converges to a balanced tree.

Assuming that each node knows the correct heights of its subtrees, a very simple distributed self-stabilizing algorithm balances the tree: each node uses the swap operation whenever two of its children heights are "too different". However, in a distributed context, height information may be inaccurate. This inaccuracy could lead the aforementioned naive balancing algorithm to make some "wrong moves." For example, in Figure 2, assume that c "thinks" that its own height is 4 and e "thinks" that its own height is 9 while their actual heights are respectively 10 and 8; the illustrated swap would actually unbalance the tree. On one hand, maintaining heights in a self-stabilizing fashion is easy and ensures that height information will eventually be correct. On the other hand, no node can know when height information is correct; as a consequence, height maintenance and balancing have to run concurrently. But their concurrent execution raises an obvious risk: the swap operation modifies the tree structure and could thus compromise the convergence of the height maintenance subprotocol.

Basically, the algorithm that we propose in this section consists of two concurrent actions: one maintaining heights, the other one balancing the tree. We formalize both actions and prove that their concurrent execution converges to a balanced tree.

A. Algorithm

At any time t, each node u is able to evaluate the following functions and predicates for itself and its children: When there are more than one possible return values for max(x) and min(x), an arbitrary choice is made. For simplicity, we can consider that the candidate node with the smallest ID is returned, although this will not be crucial for our results.

• max(x): returns any v ∈ S x (t) such that h v (t) = max w∈Sx(t) h w (t
Each node u executes the algorithm in Figure 3 (the value of stable(⊥) is assumed to be false). Note that the guards G1 and G2 are mutually exclusive and, by definition, the height update action effectively has priority over the edge swapping action. We say that a node is enabled for a height update if G1 is true, or enabled for a swap if G2 is true.

When a node u performs a swap, four nodes are involved: u itself, max(u), min(u), and max(max(u)). We refer to these nodes as the source, the target, the swap-out, and the swap-in nodes of the swap, respectively.

The following proposition can be proved directly from the definitions. We state it without proof.

Proposition 1: If C is a rooted tree with root r, then after any execution step C -→ A C ′ , C ′ is still a directed tree with root r.

B. Termination Properties

In the following section, we will prove that for any initial configuration, every possible execution is completed in a finite number of steps. For the moment, we give two properties of the resulting tree, assuming of course that the execution consists of a finite number of steps.

The proof of the following proposition can be found in Appendix A.

Proposition 2: If the execution is completed, then in the final configuration C(t ⋆ ) all nodes are balanced and have correct height information.

The next proposition, regarding the height of the resulting tree, follows directly from the analysis in [14, Sections II and III]. In our case, the initial conditions of the recurrence studied in [START_REF] Luccio | On the height of height-balanced trees[END_REF] are slightly different, but this does not affect the asymptotic behavior of the height.

Proposition 3: If the execution is completed in time t ⋆ , then in the final configuration h ⋆ r (t ⋆ ) = (log n), where r is the root and n is the number of nodes in the system.

C. Proof of Convergence

We give an overview of the proof with references to the appropriate appendices for the technical parts.

The concept of a "bad node" will be useful in the analysis of the algorithm.

Definition 4 (Bad nodes): In a given configuration

C(t), an internal node u is a bad node if h u (t) ≤ max v∈Su(t) h v (t). A leaf is a bad node if h u (t) < 0.
Intuitively, a bad node is a node that "wants" to increase its height value. The proof of the following key lemma can be found in Appendix B.

Guard

Statement

G1 ¬stable(u)

S1 h u := 1 + max w∈Su h w (or h u := 0 if u is a leaf)

G2 stable(u) ∧ stable(max(u))∧ ¬balanced(u) S2 swap edges (u, min(u)) and (max(u), max(max(u))

Fig. 3: Distributed self-stabilizing balancing algorithm Lemma 4: If C(t) contains no bad nodes, then for all t ′ ≥ t, C(t ′ ) contains no bad nodes.

It will be convenient to view any execution of the algorithm as consisting of two phases: The first phase starts from the initial configuration and ends at the first configuration in which the system is free of bad nodes. The second phase starts at the end of the first phase and ends at the first configuration in which no node is enabled, i.e., at the end of the execution. In view of Lemma 4, the system does not contain any bad nodes during the second phase. We will prove that each phase is concluded in a finite number of steps, starting from the second phase.

1) Second Phase: We prove convergence for the second phase by bounding directly the number of height updates and the number of swaps that may occur during that phase. The fact that there are no bad nodes in the second phase is crucial for bounding the number of height updates. It follows that the number of swaps also has to be bounded, since a long enough sequence of steps in which only swaps are performed incurs more height updates. The detailed proofs of these claims can be found in Appendix C.

Lemma 5: Starting from a configuration with no bad nodes, no execution can perform an infinite number of height updates.

Lemma 6: Starting from a configuration with no bad nodes, no execution can perform an infinite number of swaps.

Lemmas 5 and 6 directly imply the following: Theorem 7: In any execution, the second phase is completed in a finite number of steps.

2) First Phase: For the sake of presentation, it will be helpful to sometimes consider that the root of the tree has an imaginary father r, which is never enabled and always a bad node.

Definition 5 (Extended configuration): We denote by C(t) an auxiliary extended configuration at time t, which is identical to C(t) except that the root node in C(t) has a new father node r with h r (t) = -∞, for all t ≥ 0. The bad nodes induce a partition of the nodes of the extended configuration into components: each bad node belongs to a different component, and each non-bad node belongs to the component that contains its nearest bad ancestor.

Definition 6 (Partition into components): For each bad node b in C(t), the component T b (t) is the maximal weakly connected directed subgraph of C(t) that has b at its root and contains no other bad nodes.

A useful property of this partition is that it remains unchanged as long as the set of bad nodes remains the same. Therefore, in any sequence of steps in which the set of bad nodes remains the same, each component behaves similarly to a system that does not contain bad nodes. In particular, Lemmas 5 and 6 imply that each component is stabilized in finite time, and thus this sequence of steps cannot be infinite. For a complete substantiation of these claims, please refer to the proof of the following lemma in Appendix D. Lemma 8: There cannot be an infinite sequence of steps in which no bad node is activated or becomes non-bad.

We associate a badness vector with each configuration. This vector reflects the distribution of bad nodes in the system and will serve to quantify a certain notion of progress toward the extinction of bad nodes. In particular, we will prove that the badness vector decreases lexicographically in every step in which at least one bad node is activated or becomes non-bad.

Definition 7 (Badness vector):

For t ≥ 0, let b 1 , b 2 , . . . , b | B(t)
| be an ordering of the bad nodes in C(t) by non-decreasing number of bad nodes contained in the path from r to b i , breaking ties arbitrarily. Note that b 1 ≡ r. We define the badness vector at time t ≥ 0 to be the vector

b(t) = (|T b1 (t)|, . . . , |T b | B(t)| (t)|) ,
where the size of a connected component is the number of nodes belonging to that component. We refer the reader to Figure 4 for an example of an extended configuration, its partition into components, and the corresponding badness vector.

Definition 8 (Lexicographic ordering): Consider two badness vectors b = (x 1 , . . . , x k ) and b ′ = (x ′ 1 , . . . , x ′ k ′ ). We say that b ′ is lexicographically smaller than b if one of the following holds:

1) k ′ < k, or
2) k ′ = k and for some i in the range 1 ≤ i ≤ k, x ′ i < x i and x ′ j = x j for all j < i. The proof of the following lemma can be found in Appendix E.

Lemma 9: If at least one bad node is activated or becomes non-bad in step C(t) -→ C(t + 1), then b(t + 1) is lexicographically smaller than b(t).

Lemmas 8 and 9 are the essential ingredients required to prove convergence for the first phase. Appendix F contains the full proof.

Theorem 10: In any execution, the first phase is completed in a finite number of steps.

V. SIMULATION

To investigate the dynamic behavior and properties of our algorithm, we implemented a round based simulator. Each simulation (i) builds a full binary tree, (ii) initializes heights, and (iii) runs the balancing protocol. We used a synchronous daemon to run simulations, i.e., all the enabled nodes of the system execute their enabled actions simultaneously. The impact of non-deterministic daemons and/or the weaker daemon that is required to run our algorithm will be tackled in future work.

In the following, for a given simulation we will denote by n the number nodes of the tree, by h i its initial height (i.e. after generation), by h f its final height (i.e. after balancing) and by t the execution time in rounds.

A. Almost Linear Trees

Intuitively, almost linear trees are stressing for a balancing algorithm because they are "as unbalanced as possible". In the following, for a given n, the initial tree is the structurally unique full binary tree of height ⌈n/2⌉. The only unspecified part of the simulation is the initial height values. It turns out that this has practically a very small impact on termination time. For each n we ran thousands of simulations starting from the corresponding linear tree. For a given n they always converged in the same number of rounds. As a consequence, all runs starting from the same linear tree will have approximately the same results.

Figure 5 shows the termination time of simulations for different numbers of nodes. It contains two curves: the first one is plotted from our experiment and each point stands for an almost linear tree. The second curve is the sum of initial and final tree heights.

This plot tends to show that the round complexity of our algorithm is (n) in the worst case.

B. Random Trees

To showcase the applicability of our algorithm to an existing system, trees are generated using the join protocol of [START_REF] Izumi | Physical expander in virtual tree overlay[END_REF].

Figure 6 shows the distance between the sum of initial and final tree heights and experimental termination times. The vertical axis gives the average variation between h i + h f and experimental termination times. For each n we ran thousands of simulations. Each candlestick sums up statistics on those The greater n is, the closer h i + h f and experimental results are. This result indicates that the average round complexity of our algorithm is (h i + h f ).

VI. CONCLUDING REMARKS

In this work, we propose a new distributed self-stabilizing algorithm to rebalance containment-based trees using edge swapping. Simulation results indicate that the algorithm is quite efficient in terms of round complexity; in fact, it seems that we can reasonably expect (n) to be a worst-case bound, whereas in the average case the running time is closer to (h i + h f ) rounds. Interestingly, this average-case bound also appears in a different setting in [START_REF] Caron | Snap-stabilizing prefix tree for peer-to-peer systems[END_REF]. Note that the conjectured average-case bound is close to (log n) in a practically relevant scenario in which some faults appear (or new nodes are inserted) in an already balanced tree.

We have assumed that nodes keep correct copies of the height values of their children, so that each node can read the height values of its grandchildren by looking at the memory of its children. For simplicity, we have not dealt with the extra synchronization that would be required to maintain these copies up-to-date, but it should be possible to achieve this with a constant overhead per execution step. Furthermore, we have assumed that internal nodes have degree at least two. Degenerate internal nodes with degree one could be accommodated by a bottom-up protocol that runs in parallel and essentially disconnects them from the tree, attaching their children to their parents. Finally, note that in Section II we remarked that edge swaps may have semantic impact if they rearrange nodes so as to violate the containment relation. This can also be fixed by another bottom-up protocol that restores each node's label to the minimum that suffices to contain the labels of its children.

Possible directions for future work include establishing the conjectured upper bounds of (n) and (h i + h f ) for the round complexity. We already have some preliminary results in this direction: the first phase of the algorithm (refer to Subsection IV-C) is indeed concluded in (n) rounds. An extension of this work would be to adapt the proposed algorithm in the message passing model.

It remains to show that no x ∈ B ′ is mapped to v. The only candidate nodes that could be mapped to v are v itself and u, the father of v in C ′ . We know that v ∈ A b , which implies that v ∈ B \ A b , and thus f (v) = v. As for u, we have two cases: If u ∈ B ′ , then u is not even in the domain of f . If u ∈ B ′ , then, by assumption, we must have u ∈ B \ A and thus f (u) = u = v.

For the proof of Lemma By definition of b j and Lemma 23, we also know that any child of any node in any of the components T b1 , . . . , T bj-1 , that was in B, is also in B′ . Therefore, for each i < j, |T ′ bi | = |T bi |. Finally, by Lemma 24, we can assume that b j itself is not the father of any node v ∈ A b and that, for any such node v whose father w was in T bj , at least w no longer belongs to T ′ bj . Therefore, |T ′ bj | < |T bj |.

F. Proof of Theorem 10

By Lemma 9, the badness vector decreases lexicographically whenever at least one bad node is activated or becomes non-bad. By Lemma 8, we cannot have an infinite sequence of steps in which no bad node is activated or becomes nonbad. Moreover, during such a sequence of steps, the set of bad nodes remains the same by Lemmas 13, 14, and 15, and thus the badness vector remains the same by Lemma 22. The theorem follows from these observations and the easy fact that no configuration can have a corresponding badness vector that is lexicographically smaller than the single-component badness vector (n + 1), where n is the number of nodes in the system.

Fig. 2 :

 2 Fig. 2: An example of edge swapping. The fathers of c and e are modified. The label of b needs to be updated.

  Figure 2 contains an illustration. With the algorithm that we present in Section IV, concurrent swaps cannot conflict. The use of this balancing primitive is thus more suitable in a distributed context.

Fig. 4 :

 4 Fig. 4: An illustration of the notions introduced in Definitions 4, 5, 6, and 7. Node labels indicate their height values. Circled nodes represent bad nodes. The dashed edge exists only in the extended configuration and connects the real root of the tree to the artificial node r. Each group of nodes is one component of the partition. The badness vector corresponding to this configuration is (3, 7, 2, 1, 4).

Fig. 5 :Fig. 6 :

 56 Fig. 5: t for almost linear trees

9 ,

 9 we can assume that b ′ and b are of equal length, otherwise the statement holds by Lemma 17. Moreover, we can assume that A b = ∅, otherwise the statement holds by Lemma 23. Since r ∈ A b , there exists a bad node in C whose corresponding component contains the parent of a node in A b . Let b j , j ≥ 1, be the first such bad node in the ordering of Definition 7. By definition of b j , we have that b 1 , . . . , b j ∈ A b . Therefore, by Lemma 23, b 1 , . . . , b j ∈ B′ . By Lemmas 13, 14, and 15, a non-bad node can be turned into a bad node only if, in C′ , it is the father of a node in A b . This implies that b 1 , . . . , b j are the first j bad nodes in C′ according to the ordering of Definition 7.

  If x is a leaf, returns true if and only if h x (t) = 0. • balanced(x): returns true if and only if for all z, z ′ ∈ S x (t), |h z (t)h z ′ (t)| ≤ α.

). If x is a leaf, returns ⊥ (undefined).

• min(x): returns any v ∈ S x (t) such that h v (t) = min w∈Sx(t) h w (t). If x is a leaf, returns ⊥.

• stable(x): returns true if and only if h x (t) = 1 + max w∈Sx(t) h w (t).

A balanced tree might remain balanced or might become searchable in case of faults, while it might remain balanced in case of joins. However for the sake of readability only most stressing -which are also the most likelytransitions are shown.

That is slightly inaccurate: Certain nodes of the component may contain in their children set some bad nodes, which are at the root of other components. From the point of view of the father's component, these bad nodes will behave as if they are leaves whose height value is fixed to some arbitrary value, smaller than the height value of their father. However, it should be clear that this does not change the fact that the component will stabilize after a finite number of steps.

This research was initiated while Evangelos Bampas was with MIS Lab. University of Picardie Jules Verne, France. It was partially funded by french National Research Agency (08-ANR-SEGI-025). Details of the project on http://graal.ens-lyon.fr/SPADES.

APPENDIX

A. Proof of Proposition 2

We prove that each node u is balanced and has correct height information by induction on the actual height of u in C(t ⋆ ).

If h ⋆ u (t ⋆ ) = 0, then u is a leaf and since it is not enabled, h u (t ⋆ ) = 0. Therefore, u has correct height information and is trivially balanced. Assume that all nodes of actual height k or less, where k ≥ 0, are balanced and have correct height information in C(t ⋆ ). Consider a node u at actual height k + 1. Since u is not enabled for a height update, h u (t ⋆ ) = max v∈Su(t ⋆ ) h v (t ⋆ ) + 1. But all children of u are at actual height k or less, therefore the inductive hypothesis and the last equality imply: h u (t ⋆ ) = max v∈Su(t ⋆ ) h ⋆ v (t ⋆ ) + 1 = h ⋆ u (t ⋆ ). Moreover, u is not enabled for a swap, which means that for all children v of u, h v (t ⋆ ) ≥ h u (t ⋆ ) -1α, and because they have correct height information, h ⋆ v (t ⋆ ) ≥ h ⋆ u (t ⋆ ) -1α. Therefore, u has correct height information and is balanced.

B. Proof of Lemma 4

We will use the following notation in this section and in Appendices D and E. Let P = C -→ A C ′ be a step of the execution. The set A is partitioned into subsets A h , A b , and A s , where A h is the set of non-bad nodes which perform a height update, A b is the set of bad nodes which perform a height update, and A s is the set of nodes which are sources of a swap. Let A t be the set of nodes which are targets of a swap and let B and B ′ denote the set of bad nodes in configuration C and C ′ , respectively. For each node u, let S u be the set of children of u in C and S ⋆ u be the set of nodes of the subtree rooted at u in C, and let S ′ u and S ⋆ u ′ be the corresponding sets in C ′ . Finally, let G(A b ) be the subgraph induced by A b in the configuration C.

The following lemma states some very basic properties that are easily derived from the definitions. It will be used implicitly throughout the proofs. We state it without proof.

Lemma 11 (Easy properties):

3) For all nodes u, S ′ u = S u if and only if u ∈ A s ∪ A t . 4) The set of leaves in C ′ is equal to the set of leaves in C. Lemma 12: Let E be a weakly connected component of G(A b ). In C ′ , the nodes of E still induce a weakly connected subgraph which is identical to E. No leaf of E belongs to B ′ .

Proof:

for all nodes v of E. This suffices to prove that the nodes of E induce in C ′ a weakly connected subgraph that is identical to E. Now, let u be a leaf of E. If u is also a leaf in C, then its activation has set its height variable to 0 in C ′ . But u is still a leaf in C ′ , therefore it now has the correct height value and therefore u ∈ B ′ . If u is not a leaf of C, it means that S u is non-empty and S u ∩A b = ∅ (if v ∈ S u ∩A b , then v would also be in E and u would not be a leaf of E). We deduce that each node in S u either decreases or retains its height variable in C ′ . Moreover, by definition of the height update action, node u adjusts its height variable to at least one greater than any of the values of the height variables of its children in C. We conclude that u ∈ B ′ .

Lemma 13: If u ∈ A ∪ B and S ′ u ∩ A b = ∅, then u ∈ B ′ . Proof: Since u is not activated, the value of its height variable remains the same in C ′ . Assume, first, that u ∈ A t . Then, S ′ u = S u (since u ∈ A s , either). Moreover, S ′ u ∩A b = ∅, therefore all nodes in S u = S ′ u either decreased or retained 7 their height variables. From these observations and the fact that u ∈ B, we conclude that u ∈ B ′ . Now, assume that u ∈ A t , and let x ∈ A b be its new child in C ′ . By the definition of the swap guard, the original height variable of node x is strictly smaller than the height variable of u, and it may have decreased even further if x was simultaneously activated for a height update. All other chilren of u in C ′ were also children of u in C, and, by the fact that S ′ u ∩ A b = ∅, we know that they either decreased or retained their height values. From these observations and the fact that u ∈ B, we have that u ∈ B ′ .

Lemma 14:

all its children either retain or decrease their height variable, whereas the height variable of u is adjusted to at least one greater than any of the original values of the height variables of its children. Thus,

By definition of the swap guard, we know that the height variable of x in C ′ is strictly smaller than that of u. All other children of u were also children of u in C and they have either retained or decreased their height variable, therefore u ∈ B ′ .

Lemma 16: To conclude the argument, note that two distinct nodes x, x ′ ∈ B ′ \ B must be the fathers of the roots of two distinct components of G(A b ), and therefore they are associated to two distinct nodes y and y ′ .

Lemma 17:

Proof: One can easily verify that, for any sets B and B ′ ,

Lemma 4 follows immediately from Lemma 17.

C. Missing Proofs from Subsection IV-C1

Lemma 18: For any node u, if h u (t) < h ⋆ u (t), then there exists in C(t) at least one bad node in the subtree rooted at u.

Proof: By induction on the actual height of u. If h ⋆ u (t) = 0, then u is a leaf and, by assumption, h u (t) < h ⋆ u (t) = 0. Therefore, u is a bad node. Now, assume that the statement holds for all nodes with actual height at most k, where k ≥ 0. Consider a node u with h ⋆ u (t) = k + 1 and let v be one of its children with actual height h ⋆ v (t) = k (at least one such child must exist). We can assume that u is not bad, otherwise the

and, by the inductive hypothesis, there exists a bad node in the subtree rooted at v.

Lemma 19: In the second phase, if a node becomes enabled for a height update, it will remain enabled for a height update at least until it is activated.

Proof: Note that a node that is enabled for a height update cannot be the source or the target of a swap, therefore its set of children does not change while it is enabled for a height update. Moreover, its children cannot increase their own height values, so the node will remain enabled for a height update at least until its activation.

Proof of Lemma 5: Consider an execution of the algorithm in which an infinite number of height updates are executed. Since the number of nodes is finite, at least one node must execute a height update an infinite number of times. By the fact that the initial configuration contains no bad nodes and by Lemma 4, each time that node executes a height update, its height variable decreases. At some point, its height variable will become negative and at that point, by Lemma 18, some node in its subtree will become bad. This contradicts with Lemma 4.

Proof of Lemma 6: By Lemma 5, there exists a finite time t 0 after which no height updates are performed. For each node u, let h u denote the value of its height variable at time t 0 and, since it remains constant thereafter, at all subsequent times. Furthermore, for t ≥ t 0 , let Ŝu (t) denote the set of children of u at time t whose height variable is equal to h u -1.

Note that u is enabled for a height update at time t if and only if | Ŝu (t)| = 0. We observe now that in every step, if u is the target of a swap then | Ŝu (t)| is decreased by 1, otherwise it remains the same. By Lemma 19, if | Ŝu (t)| becomes 0 then it remains equal to 0 until u performs a height update.

Suppose, now, for the sake of contradiction, that an infinite number of swaps are performed after time t 0 . For each swap, there exists a node that is the target of that swap. It follows, then, that after at most u | Ŝu (t 0 )| swaps have been performed after time t 0 , all nodes in the system will be either idle or enabled for a height update (idle nodes will include nodes that are so low in the tree that they cannot possibly be the source of a swap and the root of the tree which will not be able to perform a swap since all of its children will be enabled for a height update). At that point, either all nodes are idle and thus the execution is completed, which contradicts with the fact that an infinite number of swaps are performed after time t 0 , or the only choice of the scheduler is to activate a node for a height update, which contradicts with the fact that no height updates are performed after time t 0 .

D. Proof of Lemma 8

In this section, we use some notation introduced in Appendix B. Additionally, in this section and in Appendix E, we will use the following notation. Let C and C′ denote the extended configurations corresponding to C and C ′ , and let B 8 and B′ denote the corresponding sets of bad nodes. Moreover, let {T b } b∈B and {T ′ b } b∈B ′ be the partition of nodes into components for the two configurations, and if T is any such component, let V (T ) denote its set of nodes.

Definition 9 (Swap chain): A swap chain in step P is a maximal-length directed path u 0 , . . . , u σ (σ ≥ 1) in configuration C such that u 0 , . . . , u σ-1 ∈ A s , u 1 , . . . , u σ ∈ A t , and, if σ ≥ 2, u 2 , . . . , u σ are the swap-ins of the swaps performed by nodes u 0 , . . . , u σ-2 , respectively.

Lemma 20 (Properties of swap chains): Let u 0 , . . . , u σ be a swap chain in step P .

1) u 1 ∈ S ′ u0 . 2) In C ′ , the nodes of even order in the swap chain (u 0 , u 2 , . . . ) induce a directed path starting from u 0 . Similarly, the nodes of odd order in the swap chain (u 1 , u 3 , . . . ) induce a directed path starting from u 1 . 3)

S ui . Proof: Property 1 follows immediately from the fact that u 0 is the first node in the swap chain, therefore it is not the target of any swap operation. Property 2 follows from the fact that u 2 , u 4 , . . . are the swap-in nodes for the swaps performed by nodes u 0 , u 2 , . . . respectively and, similarly, u 3 , u 5 , . . . are the swap-in nodes for the swaps performed by nodes u 1 , u 3 , . . . respectively. For Property 3, note that the nodes in the swap chain exchange children only with other nodes in the swap chain.

Lemma 21: | and z ∈ A t , since their father was not the source of a swap. Therefore, the inductive hypothesis applies to each node z ∈ S ′ u and we get:

If u ∈ A s , then u must be the origin of a swap chain. Let V ch be the node set of that swap chain and let

ch is in the subtree of u in C ′ and z ∈ A t . Therefore, the inductive hypothesis applies to each node z ∈ S ′ ch and we get:

By Lemma 22, in a sequence of steps in which no bad node is activated or becomes non-bad, each of the connected components behaves in the same way as a tree that does not contain bad nodes. 2 Therefore, by Lemmas 5 and 6, each component will stabilize in finite time and the bad nodes will be the only candidates for activation. Lemma 8 follows.

E. Proof of Lemma 9

In this section, we use some notation introduced in Appendices B and D. Additionally, in this section we will use the following notation. Let b and b ′ denote the badness vectors corresponding to C and C ′ .

Lemma 23: If at least one bad node becomes non-bad without being activated in step P , then |B ′ | < |B|.

Proof: Let N be the set of bad nodes that become nonbad without being activated. We can partition the set B as follows:

Moreover, we can naturally partition the set B ′ as follows: Proof: We will prove the statement by demonstrating an injection from B ′ to B \ {v}. Consider the function f : B ′ → B where, given x ∈ B ′ , f (x) is defined as follows:

• If x ∈ B \ A b , then f (x) = x.

• Otherwise, f (x) = y where y is any child of x in C ′ such that y ∈ A b . We need to prove that the function f is well-defined and injective. For injectivity, it suffices to show that if x ∈ B \ A b , then f (x) ∈ B \ A b . Indeed, given an x ∈ B ′ such that x ∈ B \ A b , we distinguish two cases: If x ∈ B, then, by Lemmas 13, 14, and 15, x has a child y ∈ A b in C ′ . On the other hand, if x ∈ A b , then by Lemma 12 we know that x is not a leaf of the component of G(A b ) in which it belongs and thus it has a child y ∈ A b in C ′ . Clearly, in both cases, y ∈ B \ A b .