Serge Troubetzkoy

APPROXIMATION AND BILLIARDS

This survey is based on a series of talks I gave at the conference "Dynamical systems and Diophantine approximation" at l'Instut Henri Poincaré in June 2003. I will present asymptotic results (transitivity, ergodicity, weak-mixing) for billiards based on the approximation technique developed by Katok and Zemlyakov. I will also present approximation techniques which allow to prove the abundance of periodic trajectories in certain irrational polygons.

Introduction.

The use of approximation techniques in dynamical systems was apparently started in 1941 by Oxtoby and Ulam [OxUl] who proved that for a finite-dimensional compact manifold with a non-atomic measure which is positive on open sets the set of ergodic measure-preserving homeomorphisms is generic in the strong topology. In 1967 Katok and Stepin [KaSt] proved the genericity of of ergodicity and weak-mixing for certain classes of interval exchange transformations. The approximation method was first applied to polygonal billiard by Katok and Zemlyakov who, using the fact that for rational polygons the directional billiard is minimal in almost all directions, proved that the typical irrational billiard is topological transitive (i.e. has dense orbits) [KaZe].

In this survey we will first reprove the Katok Zemlyakov result and then give further developments based on this idea. Then we will discuss another approximation result, based on inhomogeneous diophantine approximation, to conclude that there are many periodic billiard orbits in irrational parallelograms and related polygons.

Background.

In this section we give the necessary background on billiards, more details can be found in the surveys [Ta], [MaTa]. The billiard flow in a domain P ⊂ R 2 is defined as follows: a point mass moves freely inside P and when it reaches the boundary it is reflected following the usual law of geometric optics, the angle of incidence equals the angle of reflection. The first return map to the boundary of P is called the billiard map. The billiard map preserves a natural measure sin θ ds dθ where s is the arc length parameter on ∂P and θ ∈ S 1 is the angle between the direction of the billiard motion and the direction of the boundary.

A polygon is called rational is all the angles between sides are rational multiples of π. For rational polygons there is a well known construction of invariant billiard surfaces. Suppose the angles are of the form m i π/n i . Consider the group G(P ) generated by the reflections in the sides of P and let O(P ) ⊂ S 1 be the linearization of G(P ). The group O(P ) is simply the dihedral group D N generated by the reflections in lines through the origin that meet at angles π/N. Here N is the least common multiple of the n ′ i s. Consider the phase space of the billiard flow P × S 1 , and let R θ be its subset of points whose second coordinate belongs to the orbit of θ under D N . Since every trajectory changes directions at reflections by elements of D N we have that R θ is an invariant set. In fact it is a flat surface (possibly) with conical singularities.

To construct R θ (for θ = kπ/N) consider 2N disjoint parallel copies P 1 , P 2 , . . . , P 2N of P . Consider the O(P ) orbits {θ 1 , θ 2 , . . . , θ 2N } of θ. Consider a pair (P i , θ i ). Fix a side of P i and reflect θ i in this side, this yields a θ j . Paste the given side of P i and P j . Doing this for each i yields the surface. For example the billiard in the square has a torus as invariant surface while the invariant surface for the billiard in the in the right triangle with angle π/8 is of genus two (see Figure 1).

Old approximation results for polygons.

It is not very difficult to prove that the billiard flow/map restricted to R θ is minimal for all but countably many θ. We are now ready to state and prove Katok-Zemlyakov's result. Consider the space X of simply connected n-gons. Note that this space is not compact since n-gons can degenerate into n ′ gons with n ′ < n. Thus we say that a property is typical if for any compact set K ⊂ X the property holds for a dense G δ subset of K.1 Theorem 3.1. [KaZe] The billiard in a typical polygon is topologically transitive.

Proof. Let D ⊂ R2 be the disc. Identify the phase space of the billiard flow in each n-gon with D × S 1 and assume that this identification depends continuously on the polygon. Let B i be a countable basis for the topology of D × S 1 .

Fix an nonempty open set U k ⊂ D × S 1 (the choice of this set will be made precise below) and let K k ⊂ K be the set of n-gons P such that there exists a billiard trajectory starting in U k that visits all (the images of) the sets B 1 , . . . , B k in the phase space of the billiard flow in P . Each K k is open, and their intersection is a G δ set.

To see denseness let Y q be the set of rational n-gons with angles πp i /q i , with p i , q i co-prime and the least common multiple of the q i at least q. For every P ∈ Y q each invariant surface M θ is 1/q dense in the phase space. Therefore for every k there exists q such that for every P ∈ Y q the surface M θ (for all θ) intersects U k and all the (images of) the sets B 1 , . . . , B k in the phase space of the billiard flow in P . Since M θ has a dense trajectory for all but countably many θ we have Y q ⊂ X k . Thus since Y q is dense in the space of n-gons, the set K k is as well. It follows that ∩K k is dense.

Let P be a polygon in ∩K k . The choice of U 1 is arbitrary. Let Ũ1 ⊂ U 1 be a nonempty compact neighborhood. Suppose we have inductively chosen a nonempty compact neighborhood Ũk-1 ⊂ U k-1 . Let U k ⊂ Ũk-1 be open. Since P ∈ K k we can find a billiard trajectory starting in U k that visits each B 1 , . . . , B k . By continuity there is an compact neighborhood U k ⊂ Ũk-1 such that each trajectory in U k visits B 1 , . . . , B k within a bounded time T k . Thus any x ∈ ∩U k = ∩ Ũk has a dense trajectory, possibly singular. 2

To see that there are non-singular trajectories it suffices to produce an uncountable collection of such dense trajectories. Since there are only countably many saddle connections, i.e. orbits segments starting and ending at a vertex, most of the dense trajectories are not saddle connections. If such a trajectory is singular, i.e. the nth iterate arrives at a vertex, then the (forward) orbit starting at time n + 1 is dense and non-singular.

Thus we modify the construction to produce a Cantor set (an uncountable set) of points with dense trajectories. To do this choose Ũk be the disjoint union of 2 k nonempty compact neighborhoods such that each neighborhood contains exactly two of the neighborhoods of Ũk+1 and such that there is a billiard trajectory in each of the neighborhoods which visits the sets B 1 , . . . , B k .

In 1986, Kerckhoff, Masur and Smillie, using Teichmüller theory, proved that the directional billiard flow is uniquely ergodic for almost every direction [KeMaSm]. The surfaces M θ are not only 1/q dense in the phase space, but also approximately well distributed. Combining these two facts and no other new ideas one can conclude: Theorem 3.2. [KeMaSm, Ka, PoSt] The billiard in a typical polygon is ergodic.

Let φ : N → R + such that lim q→∞ φ(q) = 0. Let P be a n-gon with angles α 1 , . . . , α n . We say that P admits approximation by rational polygons at rate φ(q) if for every q 0 > 0 there is q > q 0 and positive integers p 1 , . . . , p n each co-prime with q such that |α i -πp i /q| < φ(q) for all i.

Vorobets has proven the following constructive ergodicity result: Theorem 3.3. [Vo] Let P be a polygon that admits approximation by rational polygons at the rate φ(q) = 2 2 2 2 q -1 , then the billiard flow in P is ergodic.

I proved the following theorem:

Theorem 3.4. [START_REF] Troubetzkoy | Recurrence and periodic billiard orbits in polygons[END_REF] The billiard map in a typical polygon is totally ergodic, i.e. T n is ergodic for all n ∈ N.

Both the constructive ergodicity and the total ergodicity theorems are proven by using an alternative version of the proof of the result of Kerckhoff, Masur and Smillie based on a combination of ideas of Masur and Boshernitzan [START_REF] Masur | Lower bounds for the number of saddle connections and closed trajectories of a quadratic differential, Holomorphic functions and moduli[END_REF][START_REF] Boshernitzan | A condition of minimal interval exchange maps to be uniquely ergodic[END_REF].

In 1999 I applied the approximation method to infinite polygons [START_REF] Troubetzkoy | Billiards in infinite polygons[END_REF]. My result was improved by Degli Esposti, Del Magno and Lenci who showed:

Theorem 3.5. [DeDeLe] Suppose p n is a monotonically decreasing sequence of positive numbers satisfying p n = 1. Let

P = ∪ n≥0 [n, n + 1] × [0, p n ].
Then the billiard in a typical P is ergodic for a.e. direction.

Here the topology on the space of such P is given by the metric

d(P, Q) := |p n -q n | = Area(P △Q).
To prove this result approximate P by finite polygons from the class, i.e. q n ≡ 0, for n ≥ N.

4.

Old approximation results for convex smooth tables.

Let C be a strictly convex billiard [Rü, Do].

In 1990 Gruber noticed that we can apply the approximation ideas of the previous section to prove contrasting results for the low smoothness case.

Theorem 4.3. [Gr] The C 0 -typical convex billiard table has the following properties: d) it is topologically transitive.

a) it contains no caustics, b) it is strictly convex, c) it is of class C 1 ,
To prove the topological transitivity we approximate a convex table by finite polygons with increasing number of sides.

In fact, using approximation teachings and the results of Kerckhoff, Masur and Smillie one can easily conclude that Theorem 4.4. C 1 -typical C 1 -convex billiard table is strictly convex and ergodic.

5. New results on smooth tables.

With A. Stepin we have have improved Gruber's result. To describe our result we begin by a new characterization of weak mixing.

5.1. Weak mixing. Let (X, β, µ) be a probability space and T : X → X a measure preserving transformation. T is weak mixing iff

∀A, B ∈ β : lim n→∞ 1 n n-1 k=0 |µ(T -k A ∩ B) -µ(A)µ(B)| = 0 iff ∀A, B ∈ β: there exists J = J(A, B) ⊂ N of full density (i.e. (#n ∈ J : n ≤ N)/N → 1) such that lim n∈J→∞ µ(T -k A ∩ B) = µ(A)µ(B). A set J ⊂ N is called full if J contains arbitrarily long runs, i.e. ∀N, ∃k s.t. {k, k + 1, . . . , k + N} ⊂ J.
Theorem 5.1. [StTr] T is weak-mixing iff ∀A ∈ β there exists J full such that

lim n∈J→∞ µ(T -k A ∩ A) = µ(A) 2
Proof. First we claim that T is ergodic. Suppose T -1 (A) = A mod 0. By invariance we have µ(T -n A ∩ A) = µ(A), but by mixing along full sequences this quantity converges to µ(A) 2 for n ∈ J. Thus µ(A) = 0 or µ(A) = 1. Now we are ready to prove that T is weak-mixing. Suppose not, then there exists a Kronecker factor ( X, β, μ, T ), i.e. a rotation T on a compact Abelian group X such that the following diagram commutes:

X T ---→X   π   π X T ---→ X Fix  ∈ β such that 0 < μ( Â) < 1 and let A := π -1 ( Â).
Then since T is a rotation, there is a quasi-periodic sequence n i such that μ( T -n i  ∩ Â) ≈ μ( Â) and thus

µ(T -n i A ∩ A) = μ( T -n i  ∩ Â) ≈ μ( Â) = µ(A)
which contradicts fullness.

= ρ H + ρ C 1 .
Theorem 5.5. [StTr] Weak-mixing is typical in B 2

We remark that P CC ⊂ B 2 ⊂ C 1 and that every table in P CC is C 2 except at a finite number of points. Furthermore the set of strictly convex tables is residual in B 2 convex , thus the generic table in B 2 convex is strictly convex and weak-mixing.

Back to polygonal billiards.

Recently Avila and Forni have shown that a.e. interval exchange not of rotation type is weak-mixing [AvFo]. Furthermore, for almost every translation surface they can show that the directional flow is weakmixing. A priori, these results do not hold for polygonal billiards. Thus the results obtained by Stepin and myself stated here are conditional.

Let W Mix c be the set of rational polygons for which at least c% of the ergodic components are weak-mixing. Note that the square and the equilateral triangle are not in W Mix c for any c > 0. The result of Avila-Forni gives hope that all but finitely many rational polygons are in W Mix 1 . Theorem 6.1. [StTr] 1) If there exists c > 0 such that W Mix c is dense in the set of polygons then weak-mixing is generic for polygonal billiards.

2) Either there exists m such that W Mix 1 m is somewhere dense in the set of polygons (and hence weak-mixing is on 2nd category for polygonal billiards) or ∪ m W Mix 1 m is nowhere dense.

Angular recurrence and periodic billiard orbits.

The billiard orbit of any point which begins perpendicular to a side of a polygon and at a later instance hits some side perpendicularly retraces its path infinitely often in both senses between the two perpendicular collisions and thus is periodic.

7.1. History and notation. In 1991 Ruijgrok conjectured based on numerical evidence that for any irrational triangle almost every orbit which starts perpendicular to a side is twice perpendicular and thus periodic [Ru]. Here almost every is with respect to the length measure on the side. In 1992 Boshernitzan [START_REF] Boshernitzan | Billiards and rational periodic directions in polygons[END_REF] and independently Galperin, Stepin and Vorobets [GaStVo] proved this conjecture for all rational polygons. In this case the set of non-periodic perpendicular orbits is a finite set. In 1995 Cipra, Kolan and Hansen proved this conjecture for all right triangles [CiHaKo]. Apparently these four articles are completely independent of each other.

Applying Theorem 3.4, I obtained the first approximation result in this direction.

Theorem 7.1. [START_REF] Troubetzkoy | Recurrence and periodic billiard orbits in polygons[END_REF] The conjecture is true for dense G δ of n-gons with n -2 angles fixed rational multiples of π.

Billiards are not affected by similarity, thus it is convenient to fix two corners, say at the origin and the point (1, 0). For triangles if we fix one angle to be a rational multiple of π then the set of triangles is an interval parametrized by one of the other angles. This theorem says that for a dense G δ subset of (any compact subset of) this interval the conjecture is true.

To discuss our results on billiards in parallelograms we must introduce some more notation. For the moment we assume that P is convex. We will describe the billiard map T as a transformation of the set X of rays which intersect P . Let θ be the angle between the billiard trajectory and the positive x-axis. Consider the perpendicular cross section X θ to the set of rays whose angle is θ. The set X θ is simply an interval. Let w be the arc-length on X θ .

For a non-convex polygon we must differentiate the portion of rays which enter and leave the polygon several times. The above construction can be done locally, yielding the set X θ which consists of a finite union of intervals. Let w be the unnormalized length measure on X θ .

For every direction θ let F θ be the set of x ∈ X θ whose forward orbit never returns parallel to x. A polygon is called angularly recurrent if for every direction θ we have w(F θ ) = 0. Angularly recurrent polygons satisfy the conclusion of Ruijgrok's conjecture, almost every perpendicular orbit is periodic! There is no reason to think that a polygon chosen at random should be angularly recurrent, this property is much stronger than Poincaré recurrence which only implies that almost every point comes back close to itself (angles close not equal!).

A polygon P is called a generalized parallelogram if all sides of P are parallel to two fixed vectors. Note that a right triangle unfolds to a rhombus and thus results for generalized parallelograms hold also for right triangles.

In 1996 Gutkin and I generalizing the result of Cipra, Kolan and Hansen proved that all right triangles and all generalized parallelograms are angularly recurrent [GuTr]

Y = dim U B Y = dim LB Y . Let s ∈ [0, ∞]. The s-dimensional Hausdorff measure H s (Y ) of a subset Y of R n
is defined by the following limit of covering sums:

H s (Y ) = lim ǫ→0 (inf{ ∞ i=1 ( diam U i ) s : Y ⊂ ∞ i=1 U i and sup i diam U i ≤ ǫ}).
It is easy to see that there exists a unique s 0 = s 0 (Y ) such that H s (Y ) = ∞ for s < s 0 and 0 for s > s 0 .

The The following theorem shows that we can do better that 1/2 for well approximable directions in a given parallelogram or for all directions in a parallelogram with well approximable angle.

Theorem 7.2. [ScTr] Fix a generalized parallelogram with irrational angle α. For any θ such that (θ + pα)/π < p -µ has infinitely many solutions p ∈ N. Then

dim LB (F θ ∩ U θ ) ≤ 1 µ + 1 . Similarly dim LB (F θ ∩ D θ ) ≤ 1 µ+1 provided the angle θ -α/2 is µ-well approximable.
Two questions naturally arise, for a fixed generalized parallelogram how many directions have small F θ and for a fixed direction θ 0 how many parallelograms have a small F θ 0 ?

Our answer to these question required new and recent results in diophantine approximation. 7.4. New number theoretic results. For µ ≥ 1 and ω ∈ S 1 let A µ,ω := {t ∈ S 1 : t + pω < p -µ for infinitely many p ∈ N}.

Minkowski's classical theorem states that if µ = 1 then A µ,ω consists of all t ∈ S 1 such that t is not in the orbit of ω.

Using different techniques Schmeling and I and independently Y. Bugeaud have shown:

Theorem 7.3. [ScTr], [Bu] For any µ > 1 we have dim H (A µ,ω ) = 1/µ.

For µ ≥ 1 and t ∈ S 1 let B µ,t := {ω ∈ S 1 : t + pω < p -µ for infinitely many p ∈ N}.

The other result we need to apply is a recent one of Levesly:

Theorem 7.4. (Levesly [Le]) For any µ > 1 we have dim H (B µ,t ) = 2 1 + µ .

Remark: this is a classical theorem of Jarnik for t = 0.

Besides the applications to billiards these results can be used to analyze the rotation driven dynamical variant of the classical Dvoretzky covering of the circle [FaSc]. More recently we have studied dynamical diophantine approximation for the circle doubling map [FaScTr].

7.5. Application to billiards. We reply to the first question, for a fixed generalized parallelogram how many directions have small F θ ? Let C s := {θ : dim LB (F θ ∩ U θ ) ≤ s}.

Theorem 7.5. [ScTr] For all s ∈ [0, 1/2] dim H (C s ) ≥ s 1 -s .

The set C s is residual with box dimension 1.

Proof. This follows immediately from Theorems 7.2 and 7.3.

We turn to the second question, for a fixed direction θ 0 how many parallelograms have a small F θ 0 ? Let D s := {α ∈ S 1 : dim LB (F θ 0 ∩ U θ 0 ) < s for all generalized parallelograms with angle α}.

Theorem 7.6. [ScTr] For θ 0 fixed and s ∈ [0, 1/2] we have

dim H D s ≥ 2s.
The set D s is residual and has box dimension 1.

Proof. This follows immediately from Theorems 7.2 and 7.4.

Figure 1 .

 1 Figure 1. Invariant surfaces.

  table. A compact convex set K is a caustic of C if the boundary of C is obtained by wrapping a string around K, pulling it tight at a point and moving the point around K while keeping the string tight. If a billiard orbit is tangent to a caustic once, then it is tangent to it in-between every pair of bounces.

In 1979 Lazutkin showed: Theorem 4.1.

[La]

If C is a sufficiently smooth strictly convex billiard table then the table contains "many" caustics.

Many means the union of the caustics has positive area.

Corollary 4.2. The billiard in a sufficiently smooth strictly convex table is not ergodic, not even topologically transitive.

The proof of Lazutkin's result is based on KAM theory. Lazutkin's original proof need the table to be C 553 . Rüssmann's version of KAM can be used to replace 553 by 8, and finally R. Douady's version of KAM shows that 7 is sufficient

  5.2. Hyperbolic billiards. Instead of approximating a smooth table by polygons we approximate by certain hyperbolic tables. Namely consider a polygon P . Replace each vertex with a (small) circular arc such that 1) the resulting table is C 1 and 2) the focusing circles lie inside the table. We call such tables B-tables and if the original polygon is convex then CT-tables. We can slightly improve the smoothness is the table is convex, or piecewise concave-convex. Let PCC be the class of C 1 piecewise convex-concave billiard domains. Because of the piecewise monotonicity of the derivative, locally the second derivative exists almost everywhere. Consider the Hausdorff distance ρ H between the second derivative of the boundaries of such tables. Let B 2 be the closure of the class of B-tables in the topology induced by the metric ρ

	Theorem 5.2. (Bunimovich [Bun]) For any B-tables each ergodic com-
	ponent is open (mod 0) and the billiard on each ergodic component is
	mixing, K-mixing, Bernoulli.
	Theorem 5.3. (Chernov, Troubetzkoy [ChTr]) Any CT-table is er-
	godic, hence mixing, K-mixing, Bernoulli.

5.3. Back to C 1 billiards.

Theorem 5.4.

[StTr]

The billiard flow/map in a C 1 -typical C 1 billiard table is weak-mixing.

Sketch of the proof: If the table is convex we approximate by billiards from the class of CT-tables introduced above. Fix a CT-table and a finite collection of sets. For all tables sufficiently close to the fixed table we can find an arbitrarily long run of times such that these sets approximately mix along this run.

If the table is not convex then we do not have a nice class of ergodic tables like the CT-class. To prove the theorem we approximate the table by polygons to obtain generic ergodicity. Then we approximate by B-tables to get the weak-mixing. 5.4. Convex tables.

  . 7.2. Dimensions. Let Y ⊂ R n . Let N(ǫ) denote the minimal number of ǫ balls needed to cover Y . The lower box dimension of Y , denoted by dim LB Y is given by The upper box dimension dim U B is defined similarly, replacing the lim inf by lim sup. If dim U B Y and dim LB Y both exist and are equal, we define the box dimension of Y to be this value, and write dim B

	lim inf ǫ→0	log N(ǫ) log 1/ǫ	.

  number s 0 is called the Hausdorff dimension of Y and is denoted by dim H Y . Standard arguments give that dim H Y ≤ dim LB Y ≤ dim U B Y 7.3. Approximation questions. With Jörg Schmeling we showed that for all generalized parallelograms dim LB (F

θ ) ≤ 1/2 for all θ

[ScTr]

.

This detail is often overlooked in the literature.

This detail is also often overlooked in the literature.


A R Balasubramanian

Nathalie Bertrand

Nicolas Markey

Parameterized verification of synchronization in constrained reconfigurable broadcast networks

published or not. The documents may come

Introduction

There are numerous application domains for networks formed of an arbitrary number of anonymous agents executing the same code: prominent examples are distributed algorithms, communication protocols, cache-coherence protocols, and biological systems such as populations of cells or individuals, etc. The automated verification of such systems is challenging [START_REF] Suzuki | Proving properties of a ring of finite-state machines[END_REF][START_REF] German | Reasoning about systems with many processes[END_REF][START_REF] Esparza | Keeping a crowd safe: On the complexity of parameterized verification (invited talk)[END_REF][START_REF] Bloem | Decidability of Parameterized Verification[END_REF]: its aim is to validate at once all instances of the model, independently of the (parameterized) number of agents. Such a problem can be phrased in terms of infinite-state-system verification. Exploiting symmetries may lead to efficient algorithms for the verification of relevant properties [START_REF] Emerson | Symmetry and model checking[END_REF].

Different means of interactions between agents can be considered in such networks, depending on the application domain. Typical examples are shared variables [START_REF] Hague | Parameterised pushdown systems with non-atomic writes[END_REF][START_REF] Esparza | Parameterized verification of asynchronous shared-memory systems[END_REF][START_REF] Bouyer | Reachability in networks of register protocols under stochastic schedulers[END_REF], rendez-vous [START_REF] German | Reasoning about systems with many processes[END_REF], and broadcast communications [START_REF] Esparza | On the verification of broadcast protocols[END_REF][START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF]. In this paper, we target ad hoc networks [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF], in which the agents can broadcast messages simultaneously to all their neighbours, i.e., to all the agents that are within their radio range. The number of agents and the communication topology are fixed once and for all at the beginning of the execution. Parameterized verification of broadcast networks checks if a specification is met independently of the number of agents and communication topology. It is usually simpler to reason about the dual problem of the existence of an initial configuration (consisting of a network size, an initial state for each agent, and a communication topology) from which some execution violates the given specification.

Several types of specifications have been considered in the literature. We focus here on coverability and synchronization: does there exist an initial configuration from which some agent (resp. all agents at the same time) may reach a particular set of target states. Both problems are undecidable; decidability of coverability can be regained by bounding the length of simple paths in the communication topology [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF].

In the case of mobile ad hoc networks (MANETs), agents are mobile, so that the communication links (and thus the neighbourhood of each agent) may evolve over time. To reflect the mobility of agents, Delzanno et al. studied reconfigurable broadcast networks [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF][START_REF] Delzanno | On the complexity of parameterized reachability in reconfigurable broadcast networks[END_REF]. In such networks, the communication topology can change arbitrarily at any time. Perhaps surprisingly, this modification not only allows for a more faithful modelling of MANETs, but it also leads to decidability of both the coverability and the synchronization problems [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF]. A probabilistic extension of reconfigurable broadcast networks has been studied in [START_REF] Bertrand | Playing with probabilities in reconfigurable broadcast networks[END_REF][START_REF] Bertrand | Distributed local strategies in broadcast networks[END_REF] to model randomized protocols.

A drawback of the semantics of reconfigurable broadcast networks is that they allow arbitrary changes at each reconfiguration. Such arbitrary reconfigurations may not be realistic, especially in settings where communications are frequent enough, and mobility is slow and not chaotic. In this paper, we limit the impact of reconfigurations in several ways, and study how those limitations affect the decidability and complexity of parameterized verification of synchronization.

More specifically, we restrict reconfigurations by limiting the number of changes in the communication graph, either by considering global constraints (on the total number of edges being modified), or by considering local constraints (on the number of updates affecting each individual node). We prove that synchronization is decidable when imposing constant local constraints, as well as when imposing global constraints depending (as a divergent function) on the number of agents. On the other hand, imposing a constant global bound makes synchronization undecidable. We recover decidability by bounding the maximal degree of each node by 1.

Broadcast networks with constrained reconfiguration

In this section, we first define reconfigurable broadcast networks; we then introduce several constraints on reconfigurations along executions, and investigate how they compare one to another and with unconstrained reconfigurations.

Reconfigurable broadcast networks

Definition 1. A broadcast protocol is a tuple P = (Q, I, Σ, ∆) where Q is a finite set of control states; I ∈ Q is the set of initial control states; Σ is a finite alphabet; and ∆ ⊆ (Q × {!!a, ??a | a ∈ Σ} × Q) is the transition relation.

A (reconfigurable) broadcast network is a system made of several copies of a single broadcast protocol P. Configurations of such a network are undirected graphs whose each node is labelled with a state of P. Transitions between configurations can either be reconfigurations of the communication topology (i.e., changes in the edges of the graph), or a communication via broadcast of a message (i.e., changes in the labelling of the graph). Figures 1 and2 respectively display an example of a broadcast protocol and of an execution of a network made of three copies of that protocol.

Formally, we first define undirected labelled graphs. Given a set L of labels, an L-graph is an undirected graph G = (N, E, L) where N is a finite set of nodes; E ⊆ P 2 (N) 3 (notice in particular that such a graph has no self-loops); finally, L : N → L is the labelling function. We let G L denote the (infinite) set of Llabelled graphs. Given a graph G ∈ G L , we write n ∼ n whenever {n, n } ∈ E and we let Neigh G (n) = {n | n ∼ n } be the neighbourhood of n, i.e. the set of nodes adjacent to n. For a label , we denote by |G| the number of nodes in G labelled by . Finally L(G) denotes the set of labels appearing in nodes of G.

The semantics of a reconfigurable broadcast network based on broadcast protocol P is an infinite-state transition system T (P). The configurations of T (P) are Q-labelled graphs. Intuitively, each node of such a graph runs protocol P, and may send/receive messages to/from its neighbours. A configuration (N, E, L) is said initial if L(N) ⊆ I. From a configuration G = (N, E, L), two types of steps are possible. More precisely, there is a step from (N, E, L) to (N , E , L ) if one of the following two conditions holds: An execution of the reconfigurable broadcast network is a sequence ρ = (G i ) 0≤i≤r of configurations such that for any i < r, there is a step from G i to G i+1 and ρ strictly alternates communication and reconfiguration steps (the latter possibly being trivial). An execution is initial if it starts from an initial configuration.

An important ingredient that we heavily use in the sequel is juxtaposition of configurations and shuffling of executions. The juxtaposition of two configurations

G = (N, E, L) and G = (N , E , L ) is the configuration G ⊕ G = (N N , E E , L ⊕ ), in which L ⊕ extends both L and L : L ⊕ (n) = L(n) if n ∈ N and L ⊕ (n) = L (n) if n ∈ N .
We write G 2 for the juxtaposition of G with itself, and, inductively, G N for the juxtaposition of G N -1 with G. A shuffle of two executions ρ = (G i ) 0≤i≤r and ρ = (G j ) 0≤j≤r is an execution ρ ⊕ from G 0 ⊕ G 0 to G r ⊕ G r obtained by interleaving ρ and ρ . Note that a reconfiguration step in ρ ⊕ may be composed of reconfigurations from both ρ and ρ . We write ρ ⊕ ρ for the set of shuffle executions obtained from ρ and ρ .

Natural decision problems for reconfigurable broadcast networks include checking whether some node may reach a target state, or whether all nodes may synchronize to a set of target states. More precisely, given a broadcast protocol P and a subset F ⊆ Q, the coverability problem asks whether there exists an initial execution ρ that visits a configuration G with L(G) ∩ F = ∅, and the synchronization problem asks whether there exists an initial execution ρ that visits a configuration G with L(G) ⊆ F . For unconstrained reconfigurations, we have: Theorem 2 ( [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF][START_REF] Delzanno | On the complexity of parameterized reachability in reconfigurable broadcast networks[END_REF][START_REF] Fournier | Parameterized verification of networks of many identical processes[END_REF]). The coverability and synchronization problems are decidable in PTIME for reconfigurable broadcast protocols. Remark 1. The synchronization problem was proven decidable in [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF], and PTIME membership was given in [11, p. 41]. The algorithm consists in computing the set of states of P that are both reachable (i.e., coverable) from an initial configuration and co-reachable from a target configuration. This can be performed by applying iteratively the algorithm of [START_REF] Delzanno | On the complexity of parameterized reachability in reconfigurable broadcast networks[END_REF] for computing the set of reachable states (with reversed transitions for computing co-reachable states).

Example 1. Consider the broadcast protocol of Fig. 1 with I = {q 0 }. From each state, unspecified message receptions lead to an (omitted) sink state; this way, each broadcast message triggers a transition in all the neighbouring copies.

For that broadcast protocol, one easily sees that it is possible to synchronize to the set {q 4 , q 6 , q 8 }. Moreover, three copies are needed and sufficient for that objective, as witnessed by the execution of Fig. 2. The initial configuration has three copies and two edges. If the central node broadcasts a, the other two nodes receive, one proceeding to q 5 and the other to q 7 . Then, we assume the communication topology is emptied before the same node broadcasts b, moving to q 2 . Finally the node in q 5 connects to the one in q 2 to communicate on c and then disconnects, followed by a similar communication on d initiated by the node in q 7 .

Natural constraints for reconfiguration

Allowing arbitrary changes in the network topology may look unrealistic. In order to address this issue, we introduce several ways of bounding the number of reconfigurations after each communication step. For this, we consider the following natural pseudometric between graphs, which for simplicity we call distance.

Definition 3. Let G = (N, E, L) and G = (N , E , L ) be two L-labelled graphs. The distance between G and G is defined as dist(G, G ) = |E ∪ E \ (E ∩ E )|
when N = N and L = L , and dist(G, G ) = 0 otherwise.

Setting the "distance" to 0 for two graphs that do not agree on the set of nodes or on the labelling function might seem strange at first. This choice is motivated by the definition of constraints on executions (see below) and of the number of reconfigurations along an execution (see Section 2.3). Other distances may be of interest in this context; in particular, for a fixed node n ∈ N, we let dist n (G, G ) be the number of edges involving node n in the symmetric difference of E and E (still assuming N = N and L = L ).

Constant number of reconfigurations per step. A first natural constraint on reconfiguration consists in bounding the number of changes in a reconfiguration step by a constant number. Recall that along executions, communication and reconfiguration steps strictly alternate.

Definition 4. Let k ∈ N. An execution ρ = (G i ) 0≤i≤r of a reconfigurable broad- cast network is k-constrained if for every index i < r, it holds dist(G i , G i+1 ) ≤ k.
Example 1 (Contd). For the synchronization problem, bounding the number of reconfigurations makes a difference. The sample execution from Fig. 2 is not 1-constrained, and actually no 1-constrained executions of that broadcast protocol can synchronize to {q 4 , q 5 , q 6 }. This can be shown by exhibiting and proving an invariant on the reachable configurations (see Lemma 10).

Beyond constant number of reconfigurations per step. Bounding the number of reconfigurations per step by a constant is somewhat restrictive, especially when this constant does not depend on the size of the network. We introduce other kinds of constraints here, for instance by bounding the number of reconfigurations by k on average along the execution, or by having a bound that depends on the number of nodes executing the protocol.

For a finite execution ρ = (G i ) 0≤i≤r of a reconfigurable broadcast network, we write nb comm(ρ) for the number of communication steps along ρ (notice that r/2 ≤ nb comm(ρ) ≤ r/2 since we require strict alternation between reconfiguration and communication steps), and nb reconf(ρ) for the total number of edge reconfigurations in ρ, that is nb reconf

(ρ) = r-2 i=0 dist(G i , G i+1 ). Definition 5. Let k ∈ N.
An execution ρ of a reconfigurable broadcast network is said k-balanced if it starts and ends with a communication step, and satisfies

nb reconf(ρ) ≤ k • (nb comm(ρ) -1).
This indeed captures our intuition that along a k-balanced execution, reconfigurations on average update less than k links.

Finally, we will also consider two relevant ways to constrain reconfigurations depending on the size of the network: first locally, bounding the number of reconfigurations per node by a constant; second globally, bounding the total number of reconfigurations by a function of the number of nodes.

We first bound reconfigurations locally. Definition 6. Let k ∈ N. An execution ρ = (G i ) 0≤i≤r of a reconfigurable broadcast network is k-locally-constrained, if, for every node n and for every index

i < r, dist n (G i , G i+1 ) ≤ k.
One may also bound the number of reconfigurations globally using bounding functions, that depend on the number of nodes in the network:

Definition 7. Let f : N → N be a function. An execution ρ = (G i ) 0≤i≤r of a reconfigurable broadcast network is f -constrained, if, writing n for the number of nodes in G 0 , it holds dist(G i , G i+1 ) ≤ f (n) for any i < r.
Notice that if f is the constant function n ∈ N → k for some k ∈ N, f -constrained executions coincide with k-constrained ones, so that our terminology is nonambiguous. Other natural bounding functions are non-decreasing and diverging. This way, the number of possible reconfigurations tends to infinity when the network size grows, i.e. ∀n. ∃k. f (k) ≥ n.

Remark 2. Coverability under constrained reconfigurations is easily observed to be equivalent to coverability with unconstrained reconfigurations: from an unconstrained execution, we can simply juxtapose extra copies of the protocol, which would perform extra communication steps so as to satisfy the constraint. When dealing with synchronization, this technique does not work since the extra copies would also have to synchronize to a target state. As a consequence, we only focus on synchronization in the rest of this paper.

Classification of constraints

In this section, we compare our restrictions. We prove that, for the synchronization problem, k-locally-constrained and f -constrained reconfigurations, for diverging functions f , are equivalent to unconstrained reconfigurations. On the other hand, we prove that k-constrained reconfigurations are equivalent to k-balanced reconfigurations, and do not coincide with unconstrained reconfigurations.

Equivalence between unconstrained and locally-constrained reconfigurations.

Lemma 8. Let P be a broadcast protocol, F ⊆ Q be a target set, and f be a non-decreasing diverging function. If the reconfigurable broadcast network defined by P has an initial execution synchronizing in F , then it has an f -constrained initial execution synchronizing in F Proof. We first prove the lemma for the identity function Id. More precisely, we prove that for an execution ρ = (G i ) 0≤i≤n , of the reconfigurable broadcast network, there exists a Id-constrained execution ρ = (G j ) 0≤j≤m , whose last transition (if any) is a communication step, and such that for any control state q, |G n | q = |G m | q . We reason by induction on the length of the execution. The claim is obvious for n = 0. Suppose the property is true for all naturals less than or equal to some n ∈ N, and consider an execution ρ = (G i ) 0≤i≤n+1 . The induction hypothesis ensures that there is an f -constrained execution ρ = (G j ) 0≤j≤m with |G n | q = |G m | q for all q. If the last transition from G n to G n+1 in ρ is a reconfiguration step, then the execution ρ witnesses our claim. Otherwise, the transition from G n to G n+1 is a communication step, involving a broadcasting node n of G n labelled with q, and receiving nodes n 1 to n r of G n , respectively labelled with q 1 to q r . By hypothesis, G m also contains a node n labelled with q and r nodes n 1 to n r , labelled with q 1 to q r . We then add two steps after G m in ρ : we first reconfigure the graph so that Neigh G m+1 (n ) = {n i | 0 ≤ i ≤ r}, which requires changing at most |G 0 | -1 links, and then perform the same broadcast/receive transitions as between G n and G n+1 .

For the general case of the lemma, suppose f is a non-decreasing diverging function. Further, let ρ = (G i ) 0≤i≤n be an Id-constrained execution, and pick k such that f (k

• |G 0 |) ≥ |G 0 |. Consider the initial configuration G k
0 , made of k copies of G 0 , and the execution, denoted ρ k , made of k copies of ρ running independently from each of the k copies of G 0 in G k 0 . Each reconfiguration step involves at most |G 0 | links, so that ρ k is f -constrained.

Lemma 9. Let P be a broadcast protocol with F ⊆ Q a target set. If the reconfigurable broadcast network defined by P has an initial execution synchronizing in F , then it has a 1-locally-constrained initial execution synchronizing in F .

k-constrained and k-balanced reconfigurations. We prove here that k-constrained and k-balanced reconfigurations are equivalent w.r.t. synchronization, and that they are strictly stronger than our other restrictions. We begin with the latter: Lemma 10. There exists a broadcast protocol P and a set F ⊆ Q of target states for which synchronization is possible from some initial configuration when unconstrained reconfigurations are allowed, and impossible, from every initial configuration when only 1-constrained reconfigurations are allowed.

A protocol with this property is the one from Example 1, for which we exhibited a 2-constrained synchronizing execution. It can be proved that no 1constrained synchronizing executions exist for this protocol, whatever the number of copies. We now prove the main result of this section:

Theorem 11. Let P be a broadcast protocol and F ⊆ Q. There exists a kconstrained initial execution synchronizing in F if, and only if, there exists a k-balanced initial execution synchronizing in F .

Proof. The left-to-right implication is simple: if there is a k-constrained initial execution synchronizing in F , w.l.o.g. we can assume that this execution starts and ends with a communication step; moreover, each reconfiguration step contains at most k edge reconfigurations, so that the witness execution is k-balanced.

Let ρ = (G i ) 0≤i≤n be a k-balanced execution synchronizing in F and starting and ending with communication steps (hence n is odd). We define the potential (p i ) 0≤i≤n of ρ as the sequence of n + 1 integers obtained as follows:

-p 0 = 0; -p 2i+1 = p 2i + k for i ≤ (n -1)/2 (this corresponds to a communication step); -p 2i+2 = p 2i+1 -dist(G 2i+1 , G 2i+2 ) for i ≤ (n -1)/2 -1 (reconfiguration step).
That ρ is k-balanced translates as p n-1 ≥ 0: the sequence (p i ) 0≤i≤n stores the value of k • nb comm(ρ ≤i )nb reconf(ρ ≤i ) for each prefix ρ ≤i of ρ; being kbalanced means that p n ≥ k, and since the last step is a communication step, this in turn means p n-1 ≥ 0. On the other hand, in order to be k-constrained, it is necessary (but not sufficient) to have p i ≥ 0 for all 0 ≤ i ≤ n.

We build a k-constrained execution by shuffling several copies of ρ. We actually begin with the case where k = 1, and then extend the proof to any k. We first compute how many copies we need. For this, we split ρ into several phases, based on the potential (p i ) 0≤i≤n defined above. A phase is a maximal segment of ρ ≤n-1 (the prefix of ρ obtained by dropping the last (communication) step) along which the sign of the potential is constant (or zero): graphs G i and G j are in the same phase if, and only if, for all i ≤ l ≤ l ≤ j, it holds p l • p l ≥ 0. We decompose ρ as the concatenation of phases (ρ j ) 0≤j≤m ; since ρ is k-balanced, m is even, and ρ 0 , ρ m , and all even-numbered phases are non-negative phases (i.e., the potential is non-negative along those executions), while all odd-numbered executions are non-positive phases. Also, all phases end with potential zero, except possibly for ρ m . See Fig. 3 for an example of a decomposition into phases.

Lemma 12. For any phase ρ

i = G bi • • • G ei of a 1-balanced execution ρ = G 0 • • • G n , there exists κ i ≤ (e i -b i )/2 such that for any N ∈ N, there exists a 1-constrained execution from G κi 0 ⊕ G N bi to G κi 1 ⊕ G N ei .
Proof. We handle non-negative and non-positive phases separately. In a nonnegative phase, we name repeated reconfiguration step any reconfiguration step that immediately follows another (possibly from the previous phase) reconfiguration step (so that if there are four consecutive reconfiguration steps, the last three are said repeated); similarly, we name repeated communication step any communication step that is immediately followed (possibly in the next phase) by another communication step (hence the first three of fours consecutive communication steps are repeated). We first claim that any non-negative phase contains at least as many repeated communication steps as it contains repeated reconfiguration steps. Indeed, any non-repeated communication step in a non-negative phase is necessarily followed by a non-repeated reconfiguration step, and conversely, and non-negative phases have at least as many communication steps as they have reconfiguration steps.

As a consequence, we can number all repeated reconfiguration steps from 1 (earliest) to κ i (latest), for some κ i , and similarly for repeated communication steps. Clearly enough, in a non-negative phase, for any 1 ≤ j ≤ κ i , the repeated communication step numbered j occurs before the repeated reconfiguration step carrying the same number.

We now build our 1-constrained execution from

G κi 0 ⊕ G N bi to G κi 1 ⊕ G N ei .
We begin with a first part, where only the components starting from G bi move:

the first copy starting in G bi follows the execution ρ i until reaching the repeated reconfiguration step number 1. That reconfiguration step cannot be performed immediately as it follows another reconfiguration step. Notice that during this stage, this copy has taken at least one repeated communication step, numbered 1; the second copy then follows ρ i until reaching its first repeated communication step (which must occur before the first repeated reconfiguration step). It takes this communication step, then allowing the first copy to perform its first repeated reconfiguration step; this simulation continues, each time having the l + 1-st copy of the system taking its j-th repeated communication step in order to allow the l-th copy to perform its j-th repeated reconfiguration step. Non-repeated steps can always be performed individually by each single copy. Also, the first copy may always take repeated communication steps not having a corresponding reconfiguration step, as in the first stage of this part.

Notice that the number of copies involved in this process is arbitrary. The process lasts as long as some copies may advance within phase ρ i . Hence, when the process stops, all copies of the original system either have reached the end of ρ i , or are stopped before a repeated reconfiguration step. For the copies in the latter situation, we use the copies starting from G 0 . It remains to prove that having κ i such copies is enough to make all processes reach the end of ρ i .

For this, we first assume that the potential associated with ρ i ends with value zero. This must be the case of all phases except the last one, which we handle after the general case. We first notice that in the execution we are currently building, any repeated communication step performed by any (but the very first) copy that started from G bi is always followed by a repeated reconfiguration step. Similarly, non-repeated communication steps of any copy is followed by a non-repeated broadcast step of the same copy. As a consequence, the potential associated with the global execution we are currently building never exceeds the total number of repeated communication steps of performed by the first copy; hence it is bounded by κ i , whatever the number N of copies involved. As a consequence, at most κ i communication steps are sufficient in order to advance all copies that started from G bi to the end of ρ i . Finally, the case of the last phase ρ m (possibly ending with positive potential) is easily handled, since it has more communication steps than reconfiguration steps.

The proof for non-positive phases is similar.

Pick a 1-balanced execution ρ = G 0 • • • G n , and decompose it into phases ρ 1 • • • ρ m . For each phase ρ i , we write κ i for the total number of repeated reconfiguration steps, and we let κ = 1≤i≤m κ i for the total number of repeated reconfiguration steps along ρ. Notice that κ ≤ n/2. Lemma 13. For every 1-balanced execution ρ = G 0 • • • G n , and for every N ∈ N, there exists a 1-constrained execution from

G N 1 ⊕ G κN em to G N +κN n .
Combining the above two lemmas, we obtain the following proposition, which refines the statement of the Theorem 11:

Proposition 14. For every 1-balanced execution ρ = G 0 • • • G n and every N ≥ κ 2 + κ, there exists a 1-constrained execution from G N 0 to G N n .
We finally extend this result to k > 1. In this case, splitting ρ into phases is not as convenient as when k = 1: indeed, a non-positive phase might not end with potential zero (because communication steps make the potential jump by k units). Lemma 12 would not hold in this case.

We circumvent this problem by first shuffling k copies of ρ in such a way that reconfigurations can be gathered into groups of size exactly k. This way, we can indeed split the resulting execution into non-negative and non-positive phases, always considering reconfigurations of size exactly k; we can then apply the techniques above in order to build a synchronizing k-constrained execution. This completes our proof.

3 Parameterized synchronization under reconfiguration constraints

Undecidability for k-constrained reconfiguration

Although synchronization is decidable in PTIME [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF][START_REF] Fournier | Parameterized verification of networks of many identical processes[END_REF] for reconfigurable broadcast networks, the problem becomes undecidable when reconfigurations are k-constrained.

Theorem 15. The synchronization problem is undecidable for reconfigurable broadcast networks under k-constrained reconfigurations.

Proof. We prove this undecidability result for 1-constrained reconfigurations, by giving a reduction from the halting problem for Minsky machines [START_REF] Minsky | Computation: Finite and Infinite Machines[END_REF]. We begin with some intuition. The state space of our protocol has two types of states:

control states encode the control state of the 2-counter machine; counter states are used to model counter values: for each counter c j ∈ {c 1 , c 2 }, we have a state zero j and a state one j . The value of counter c j in the simulation will be encoded as the number of edges in the communication topology between the control node and counter nodes in state one j ; moreover, we will require that control nodes have no communication links with counter nodes in state zero j . Incrementations and decrementations can then be performed by creating a link with a node in zero j and sending this node to one j , or sending a one j -node to zero j and removing the link.

In order to implement this, we have to take care of the facts that we may have several control nodes in our network, that we may have links between two control nodes or between two counter nodes, or that links between control nodes and counter nodes may appear or disappear at random. Intuitively, those problems will be handled as follows:

we cannot avoid having several control nodes; instead, given a synchronizing execution of the broadcast protocol, we will select one control node and show that it encodes a correct execution of the 2-counter machine; in order to reach a synchronizing configuration, the selected control node will have to perform at least as many reconfiguration steps as broadcast steps. Because we consider 1-constrained runs, it will perform exactly the same number of reconfiguration steps as broadcast steps, so that no useless/ unexpected reconfigurations may take place during the simulation; control nodes will periodically run special broadcasts that would send any connected nodes (except nodes in state one j ) to a sink state, thus preventing synchronization. This way, we ensure that that particular control node is clean. Initially, we require that control nodes have no connections at all. We now present the detailed construction, depicted at Fig. 4 to 7. Each state of the protocol is actually able to synchronize with all the messages. Some transitions are not represented on the figures, to preserve readability: all nodes with no outgoing transitions (i.e., state L halt corresponding to the halting state, as well as states zero j and done i ) actually carry a self-loop synchronizing on all messages; all other omitted transitions lead to a sink state, which is not part of the target set.

M0 L1 M1 L2 M2 M 2 !!start !!i-exit
L i1 i2 i3 i4 i5 i6 i7 M !!i-init ??fr 1 !!i-
Let us explain the intended behaviour of the incrementation module of Fig. 5: when entering the module, our control node n in state L is linked to c 1 counter nodes in state one 1 and to c 2 counter nodes in state one 2 ; it has no other links. Moreover, all auxiliary nodes are either in state free i or in state done i . Running through the incrementation module from L will use one counter node m in state zero j (which is used to effectively encode the increase of counter c j ) and four auxiliary nodes a 1 (initially in state free 1 ), a 2 (in state free 2 ), and a 3 and a 3 (in state free 3 ).

The execution then runs as follows:

a link is created between the control node n and the first auxiliary node a 1 , followed by a message exchange !!i-init; a link is created between n and m, and node a 1 broadcasts !!fr 1 ; a link is created between n and a 2 , and n broadcasts !!i-ask j , which is received by both a 2 and m; a link is created between n and a 3 ; node m sends its acknowledgement !!i-ack j to n; a link is created between n and a 3 ; node n sends !!i-ok j , received by m, a 2 , a 3 and a 3 ; the link between n and a 1 is removed, and a 2 sends !!fr 2 ; the link between n and a 2 is removed, and a 3 sends !!fr 3 ; the link between n and a 3 is removed, and a 3 sends !!fr 3 ; finally, the link between n and a 3 is removed, and n sends !!i-exit.

After this sequence of steps, node n has an extra link to a counter node in state one j , which indeed corresponds to incrementing counter c j . Moreover, no nodes have been left in an intermediary state. A similar analysis can be done for the second module, which implements the zero-test and decrementation. This way, we can prove that if the two-counter machine has a halting computation, then there is an initial configuration of our broadcast protocol from which there is an execution synchronizing in the set F formed of the halting control state and states one j , zero j and done i .

It now remains to prove the other direction. More precisely, we prove that from a 1-constrained synchronizing execution of the protocol, we can extract a synchronizing execution in some normal form, from which we derive a halting execution of the two-counter machine.

Fix a 1-constrained synchronizing execution of the broadcast network. First notice that when a control node n reaches some state L (the first node of an incrementation or decrementation module), it may only be linked to counter nodes in state one j : this is because states L can only be reached by sending !!i-exit, !!d-exit, !!t-exit, or !!start. The former two cases may only synchronize with counter nodes in state one j ; in the other two cases, node n may be linked to no other node. Hence, for a control node n to traverse an incrementation module, it must get links to four auxiliary nodes (in order to receive the four fr messages), those four links must be removed (to avoid reaching the sink state), and an extra link has to be created in order to receive message i-ack j . In total, traversing an incrementation module takes nine communication steps and at least nine reconfiguration steps. Similarly, traversing a decrementation module via any of the two branches takes at least as many reconfiguration steps as communication steps. In the end, taking into account the initial !!start communication step, if a control node n is involved in B n communication steps, it must be involved in at least B n -1 reconfiguration steps.

Assume that every control node n is involved in at least B n reconfiguration steps: then we would have at least as many reconfiguration steps as communication steps, which in a 1-constrained execution is impossible. Hence there must be a control node n 0 performing B n0 communication steps and exactly B n0 -1 reconfiguration steps. As a consequence, when traversing an incrementation module, node n 0 indeed gets connected to exactly one new counter node, which indeed must be in state one j when n 0 reaches the first state of the next module. Similarly, traversing a decrementation/zero-test module indeed performs the expected changes. It follows that the sequence of steps involving node n 0 encodes a halting execution of the two-counter machines.

The 1-constrained executions in the proof of Theorem 15 have the additional property that all graphs describing configurations are 2-bounded-path configurations. For K ∈ N a configuration G is a K-bounded-path configuration if the length of all simple paths in G is bounded by K. Note that a constant bound on the length of simple paths implies that the diameter (i.e. the length of the longest shortest path between any pair of vertices) is itself bounded. The synchronization problem was proved to be undecidable for broadcast networks without reconfiguration when restricting to K-bounded-path configurations [START_REF] Delzanno | Parameterized verification of ad hoc networks[END_REF]. In comparison, for reconfigurable broadcast networks under k-constrained reconfigurations, the undecidability result stated in Theorem 15 can be strengthened into:

Corollary 16. The synchronization problem is undecidable for reconfigurable broadcast networks under k-constrained reconfigurations when restricted either to bounded-path configurations, or to bounded-diameter configurations.

Decidability results

f -constrained and k-locally-constrained reconfigurations. From the equivalence (w.r.t. synchronization) of k-locally-constrained, f -constrained and unconstrained executions (Lemmas 9 and 8), and thanks to Theorem 2, we immediately get: Corollary 17. Let k ∈ N and f : N → N be a non-decreasing diverging function. The synchronization problem for reconfigurable broadcast networks under k-locallyconstrained (resp. f -constrained) reconfigurations is decidable in PTIME.

Bounded degree topology. We now return to k-constrained reconfigurations, and explore restrictions that allow one to recover decidability of the synchronization problem. We further restrict k-constrained reconfigurations by requiring that the degree of nodes remains bounded, by 1; in other terms, communications correspond to rendez-vous between the broadcasting node and its single neighbour.

Theorem 18. The synchronization problem is decidable for reconfigurable broadcast networks under k-constrained reconfiguration when restricted to 1-boundeddegree topologies. Sketch of proof. The proof consists in transforming the synchronization problem above into a reachability problem for some Petri net. The Petri net has two kinds of places (plus a few auxiliary places): one place for each state of the protocol, representing isolated nodes (i.e., nodes having no neighbours), and one place for each pair of states of the protocol, representing pairs of connected nodes. Since we restrict to degree-1 topologies, any node of the network is in one of those two configurations. Places representing isolated nodes are simply called isolated places in the sequel, while places corresponding to pairs of connects nodes are called connected places.

An initialization phase stores tokens in the places described above, so as to represent the initial configuration. In a second phase, the Petri net simulates an execution of the reconfigurable broadcast network: communication steps and (k-constrained) reconfiguration steps are easily encoded as transitions of this Petri net: communication steps correspond to moving tokens from one place to the place obtained by updating the states as prescribed by the transitions of the broadcast protocol. Atomic reconfigurations may create or remove links, either consuming two tokens in isolated places and adding a token in the corresponding connected place, or the other way around. We use k auxiliary places in order to count the number of atomic reconfigurations, in order to enforce the k-constraint.

Finally, the Petri net may enter a terminal phase, where it checks synchronization by absorbing all tokens that lie in (isolated or connected) places corresponding to target states. In the end, the simulated execution has been synchronizing if, and only if, no tokens remain in any of the main states.

Conclusion

Restricting reconfigurations in reconfigurable broadcast networks is natural to better reflect mobility when communications are frequent enough and the movement of nodes is not chaotic. In this paper, we studied how constraints on the number of reconfigurations (at each step and for each node, at each step and globally, or along an execution) change the semantics of networks, in particular with respect to the synchronization problem, and affect its decidability. Our main results are the equivalence of k-constrained and k-balanced semantics, the undecidability of synchronization under k-constrained reconfigurations, and its decidability when restricting to 1-bounded-degree topologies.

As future work, we propose to investigate, beyond the coverability and synchronization problems, richer objectives such as cardinality reachability problems as in [START_REF] Delzanno | On the complexity of parameterized reachability in reconfigurable broadcast networks[END_REF]. Moreover, for semantics with constrained reconfigurations that are equivalent to the unconstrained one as far as the coverability and synchronization problems are concerned, it would be worth studying the impact of the reconfiguration restrictions (e.g. k-locally-constrained or f -constrained) on the minimum number of nodes for which a synchronizing execution exists, and on the minimum number of steps to synchronize.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Example of a broadcast protocol

(

  reconfiguration step) N = N and L = L: a reconfiguration step does not change the set of nodes and their labels, but may change the edges arbitrarily; (communication step) N = N, E = E, and there exists n ∈ N and a ∈ Σ such that (L(n), !!a, L (n)) ∈ ∆, and for every n , if n ∈ Neigh G (n), then (L(n ), ??a, L (n )) ∈ ∆, otherwise L (n ) = L(n ): a communication step reflects how nodes evolve when one of them broadcasts a message to its neighbours.

Fig. 3 .

 3 Fig.3. Phases of a 1-balanced execution, and correspondence between repeated communication steps (loosely dotted blue steps) and repeated reconfiguration steps (densely dotted red steps)

Fig. 4 .

 4 Fig. 4. Global view of the part of the protocol for control nodes

Fig. 7 .

 7 Fig. 7. Parts of the protocol for auxiliary nodes

For a finite set S and 1 ≤ k ≤ |S|, we let P k (S) = {T ⊆ S | |T | = k}.

This work has been supported by the Indo-French research unit UMI Relax, and by ERC project EQualIS (308087).