Dominique Malicet

Kathryn Mann

Cristóbal Rivas

Michele Triestino

Ping-pong configurations and circular orders on free groups

Keywords: Primary 20F60, 57M60. Secondary 20E05, 37C85, 37E05, 37E10

We discuss actions of free groups on the circle with "ping-pong" dynamics, i.e. dynamics determined by a finite amount of combinatorial data. As a natural extension of the work started in [21], we show that the free group F n admits an isolated circular order if and only if n is even, in stark contrast with the case for linear orders. Following [2], we also exhibit examples of "exotic" isolated points in the space of all circular orders on F 2 . As an application, we obtain analogous results for the linear orders on the groups F n × Z.

Introduction

Let G be a group. A linear order, often called a left order on G is a total order invariant under left multiplication. Left-invariance immediately implies that the order is determined by the set of elements greater than the identity, called the positive cone. However, it is often far from obvious whether a given order is in fact determined by only finitely many inequalities, or whether a given group admits such a finitely determined order. This latter question turns out to be quite natural from an algebraic perspective, and can be traced back to [START_REF] Arora | Centralizers in free lattice-ordered groups[END_REF] for the special case of free groups. McCleary answered this shortly afterwards, showing that F n admits no finitely determined orders [START_REF] Mccleary | Free lattice-ordered groups represented as o-2 transitive l-permutation groups[END_REF].

The question of finite determination gained a topological interpretation following Sikora's definition of the space of linear orders on G, denoted LO(G) [START_REF] Sikora | Topology on the spaces of orderings of groups[END_REF]. This is the set of all linear orders on G endowed with the topology generated by open sets U ( ,X) := { | x y iff x y for all x, y ∈ X} as X ranges over all finite sets of G. Finitely determined linear orders on G are precisely the isolated points of LO(G). This is the simplest instance of the general theme that topological properties of LO(G) should correspond to algebraic properties of G.

Using both algebraic and dynamical methods, we now know many families of groups which do and do not admit isolated (i.e. finitely determined) orders. Examples that do not include free abelian groups [START_REF] Sikora | Topology on the spaces of orderings of groups[END_REF], free groups [START_REF] Mccleary | Free lattice-ordered groups represented as o-2 transitive l-permutation groups[END_REF][START_REF] Navas | On the dynamics of (left) orderable groups[END_REF], free products of arbitrary linearly orderable groups [START_REF] Rivas | Left-orderings on free products of groups[END_REF], as well as some amalgamated free products such as fundamental groups of orientable closed surfaces [START_REF] Alonso | Orderings and flexibility of some subgroups of Homeo+(R)[END_REF]: they all fail to admit isolated left orders. Large families of groups which do have isolated orders include braid groups [START_REF] Dehornoy | Ordering braids[END_REF][START_REF] Dubrovina | On braid groups[END_REF], groups of the form x, y | x n = y m (n, m ∈ Z) [START_REF] Ito | Dehornoy-like left orderings and isolated left orderings[END_REF][START_REF]A remarkable family of left-ordered groups: central extensions of Hecke groups[END_REF], and groups This result appears to give the first examples of any group G with a finite index subgroup H (in this case F n × Z ⊂ F m × Z, for n = m mod 2) such that LO(G) and LO(H) are both infinite, but only one contains isolated points.

Theorem 1.1 also has an interesting consequence regarding the space of marked groups (see [START_REF] Champetier | Limit groups as limits of free groups[END_REF] for an introduction to the subject). It is known that, in the space of marked groups, the set of groups enjoying a linear order is closed. Surprisingly, it follows form Theorem 1.1 that enjoying an isolated linear order is neither a closed, nor an open property. Indeed, F 2 × Z approaches F 3 × Z (when changing the generating set) and also F 3 × Z approaches F 4 × Z (see [8, §2.3]). We state this observation as: Corollary 1.2. In the space of finitely generated marked groups, having an isolated linear order is neither a closed, nor an open property. Remark 1.3. In different terms, the previous corollary says that while the property of enjoying a linear order can be expressed in the first-order logic theory of a group, this is not the case for isolated linear orders. More precisely, the property P : "the group G admits an isolated linear order" is expressed by no set of first-order sentences (i.e. involving finitely many universal quantifiers). Indeed, as explained in [START_REF] Champetier | Limit groups as limits of free groups[END_REF], groups satisfying an equation given by a first-order sentence describe a closed set in the space of marked groups.

The main thrust of this work, giving the tools for Theorem 1.1, is the study of circular orders on F n and actions of F n on the circle. It is well known that, for countable G, admitting a linear order is equivalent to acting faithfully by orientation-preserving homeomorphisms on the line. By analogy, a circular order is an algebraic condition (specifically, a type of 2-cocycle) equivalent to acting faithfully by orientation-preserving homeomorphisms on S 1 . An action of G on S 1 will lift to an action of a central extension of G by Z on the line, giving a correspondence between circular and linear orders and putting many dynamical tools at our disposal.

Analogous to LO(G), one can define a space of circular orders CO(G). In [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF], the second and third authors showed that a circular order on F n is isolated if and only if a corresponding action on the circle, has what they called ping-pong dynamics. They gave examples of isolated circular orders on free groups of even rank, but the odd rank case was left as an open problem, which we answer here in the negative: Theorem 1.4. F n has isolated circular orders if and only if n is even.

We prove this by developing a combinatorial tool for the study of ping-pong actions (similar to Markov partitions), inspired by the work in [START_REF]On the ergodic theory of free group actions by real-analytic circle diffeomorphisms[END_REF] and [START_REF] Alvarez | Markov partitions and locally discrete groups of real-analytic circle diffeomorphisms[END_REF], which should have applications beyond the study of linear and circular orders (see Theorem 3.11). These are defined and motivated in the next section. Sections 3 and 4 give the application to the study of circular and linear orders, respectively, and the proofs of Theorems 1.1 and 1.4. Remark 1.5. Similarly to Corollary 1.2, one can also prove that the set of groups admitting isolated circular orders is neither closed nor open in the space of marked groups. A ping-pong action of (Γ, S) on S 1 is a representation ρ : Γ → Homeo + (S 1 ) such that there exist pairwise disjoint open sets D(a) ⊂ S 1 , a ∈ S ∪ S -1 , each of which has finitely many connected components, and such that ρ(a) S 1 \ D(a -1 ) ⊂ D(a). We further assume that if I and J are any connected components of D(a), then Ī ∩ J = ∅.

We call the sets D(a) the ping-pong domains for ρ.

Remark 2.2. In [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF] the ping-pong domains are assumed to be closed. The definition above is slightly more general. For this reason later we will introduce Convention 3.6, to recover the definition in [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF].

The reader may notice that, for a given ping-pong action ρ of (Γ, S), there can be many choices of sets D(a) satisfying the property in Definition 2.1. For instance, if ρ is a ping-pong action such that a∈S∪S -1 D(a) = S 1 , then one may choose an arbitrary open set I disjoint from a∈S∪S -1 D(a) and replace D(a 1 ) with D(a 1 ) ∪ I, leaving the other domains unchanged. These new domains still satisfy ρ(a) S 1 \ D(a -1 ) ⊂ D(a). Later we will adopt a convention to avoid this kind of ambiguity.

Why ping-pong actions?

The classical ping-pong lemma implies that ping-pong actions are always faithful, and a little more work shows that the action is determined up to semi-conjugacy by a finite amount of combinatorial data coming from the cyclic ordering and the images of the connected components of the sets D(a) (see Definition 2.6, [START_REF]Basic partitions and combinations of group actions on the circle: a new approach to a theorem of Kathryn Mann[END_REF]Thm. 4.7] or Lemma 3.4 below). In particular, one can think of ping-pong actions as the family of "simplest possible" faithful actions of F n on S 1 , and it is very easy to produce a diverse array of examples. Perhaps the best-known examples are the actions of discrete, free subgroups of PSL(2, R) on RP 1 . For these actions, one can choose domains D(a) with a single connected component. Despite their simplicity, ping-pong actions are quite useful. For instance, in [START_REF] Alvarez | Markov partitions and locally discrete groups of real-analytic circle diffeomorphisms[END_REF] ping-pong actions were used in the discovery of the first examples of discrete groups of real-analytic circle diffeomorphisms that act minimally and are not conjugate to a subgroup in a cover of PSL(2, R) (Example 3.9 originates from [START_REF] Alvarez | Markov partitions and locally discrete groups of real-analytic circle diffeomorphisms[END_REF]). This was a by-product of a series of works on longstanding open conjectures by Hector, Ghys and Sullivan, concerning the relationship between minimality and ergodicity of a codimension-one foliation (see for instance [START_REF] Deroin | On the question of ergodicity for minimal group actions on the circle[END_REF][START_REF]On the ergodic theory of free group actions by real-analytic circle diffeomorphisms[END_REF][START_REF] Filimonov | Structure of groups of circle diffeomorphisms with the property of fixing nonexpandable points[END_REF]). In general, it is very easy to study the dynamic and ergodic properties of a ping-pong action, and this program has been carried out by many authors [START_REF] Cantwell | Foliations and subshifts[END_REF][START_REF]Leaves of Markov local minimal sets in foliations of codimension one[END_REF][START_REF] Inaba | Resilient leaves in transversely projective foliations[END_REF][START_REF] Mañé | Hyperbolicity, sinks and measure in one-dimensional dynamics[END_REF][START_REF] Matsumoto | Measure of exceptional minimal sets of codimension one foliations[END_REF].

Basic properties

Lemma 2.3. Given a ping-pong action of (Γ, S), there exists a choice of ping-pong domains D(a) such that ρ(a) S 1 \ D(a -1 ) = D(a) holds for all a ∈ S ∪ S -1 .

Proof. Let ρ be a ping-pong action with sets D(a) given. We will modify these domains to satisfy the requirements of the lemma. For each generator a ∈ S (not the symmetric generating set), we shrink the domain D(a), setting

D (a) := ρ(a) S 1 \ D(a -1 ) .
Applying a -1 to both sides of the above expression, we clearly get ρ(a -1 )(D (a)) = S 1 \ D(a -1 ). Moreover, since the connected components of D(a) have disjoint closures, and the same holds for D(a -1 ), and hence also for D (a), we also have ρ(a -1 ) D (a) = S 1 \ D(a -1 ), or equivalently

ρ(a -1 ) S 1 \ D (a) = D(a -1 ).
This is what we needed to show. Convention 2.4. From now on, we assume all choices of domains D(a) for every ping-pong action are as in Lemma 2.3. Remark 2.5. In particular, Convention 2.4 implies that for each a ∈ S, π 0 (D(a)), the set of connected components of D(a), has the same cardinality than π 0 (D(a -1 )). Definition 2.6. Let ρ be a ping-pong action of (Γ, S). The ping-pong configuration of ρ is the data consisting of 1. The cyclic order of the connected components of a∈S∪S -1 D(a) in S 1 , and 2. For each a ∈ S ∪ S -1 , the assignment of connected components

λ a : π 0   b∈S∪S -1 \{a -1 } D(b)   → π 0 (D(a))
induced by the action.

Note that not every abstract assignment λ a as in the definition above can be realized by an action F 2 → Homeo + (S 1 ). However, one way to produce some large families of examples is as follows.

Example 2.7 (An easy construction of ping-pong actions). For a ∈ S, let X a and Y a ⊂ S 1 be disjoint sets each of cardinality k(a) for some integer k(a) ≥ 1 such that every two points of X a are separated by a point of Y a . Choose these so that all the sets X a ∪ Y a are pairwise disjoint as a ranges over S. Let D(a) and D(a -1 ) be neighborhoods of X a and Y a , respectively, chosen small enough so that all these sets remain pairwise disjoint. Now one can easily construct a piecewise linear homeomorphism (or even a smooth diffeomorphism) ρ(a) with X a as its set of attracting periodic points, and Y a as the set of repelling periodic points such that ρ(a) S 1 \ D(a -1 ) = D(a). The assignments λ a are now dictated by the period of ρ(a) and the cyclic order of the sets X a and Y a .

While the reader should keep the method above in mind as a source of examples, we will show in Example 3.12 that not every ping-pong configuration can be obtained in this manner. However, the regularity (PL or smooth) in the construction is attainable in general: Lemma 2.8. Given a ping-pong action ρ 0 of (Γ, S) with domains {D 0 (a)} a∈S∪S -1 following Convention 2.4, one can find another ping-pong action ρ of (Γ, S) such that:

1. The action ρ is piecewise linear.

2. Denoting by D(a) the domains of ρ, there exists µ > 1 such that for any a ∈ S ∪ S -1 , one has

ρ(a) | D(a -1 ) ≥ µ.
3. The actions ρ 0 and ρ have the same ping-pong configuration.

Proof. Given a ping-pong action of (Γ, S) with domains {D 0 (a)} a∈S∪S -1 following Convention 2.4, for each a ∈ S ∪ S -1 , replace the original domains by smaller domains D(a) ⊂ D 0 (a), chosen sufficiently small so that the largest connected component of D(a) is at most half the length of the smallest connected component of S 1 \ D(a -1 ). We require also that D(a) has exactly one connected component in each connected component of D 0 (a). Now define ρ(a) as a piecewise linear homeomorphism that maps connected components of S 1 \ D(a -1 ) onto connected components of D(a) linearly following the assignment λ a . Definition 2.9. For each a ∈ S, we define an oriented bipartite graph Γ a as follows:

• The set of vertices is formed by the connected components of D(a) and D(a -1 ).

• There is an oriented edge from an interval I + ∈ π 0 (D(a)) to an interval I -∈ π 0 (D(a -1 )) if and only if, denoting by J + the connected component of S 1 \ D(a) that is right adjacent to I + , one has ρ(a -1 )(J + ) = I -.

• Similarly, there is an oriented edge from I -∈ π 0 (D(a -1 )) to I + ∈ π 0 (D(a)) if and only if, denoting by J -the connected component of S 1 \ D(a -1 ) that is right adjacent to I -, one has ρ(a)(J -) = I + .

Proposition 2.10. Consider a ping-pong action ρ : Γ → Homeo + (S 1 ) of a free group (Γ, S). Then for each generator a ∈ S there exists an integer k(a) such that the graph Γ a is an oriented 2k(a)-cycle.

We give the proof of this proposition dividing the arguments into different lemmas.

Lemma 2.11. Each vertex in Γ a has exactly one outgoing edge.

Proof. As a direct consequence of Convention 2.4, we have that for any s ∈ S ∪ S -1 and connected component J of S 1 \ D(s -1 ) there exists a connected component

I ∈ π 0 (D(s)) such that ρ(s)(J) = I.
This implies that each vertex of Γ a has at least one edge going out from it. On the other hand, it is clear from Definition 2.9 of the graph that there is at most one edge going out from any vertex.

Lemma 2.12. The graph Γ a is a disjoint union of nontrivial cycles.

Proof. After Lemma 2.11, we need to prove that each vertex I ∈ π 0 (D(s)), s = a ±1 has a unique incoming edge. This is clear, since there cannot be two distinct connected components of S 1 \ D(s -1 ) whose image by ρ(s) is exactly I.

Lemma 2.13. The graph Γ a is connected.

Proof. Let I -be a connected component of D(a -1 ) and consider the connected component J + of S 1 \ D(a) such that ρ(a -1 )(J + ) = I -. Let I + 1 and I + 2 be the connected components of D(a) (possibly the same) which are adjacent to J + . By Definition 2.9 of the graph Γ a , the intervals I + 1 , I -, I + 2 are consecutive vertices in a same cycle of the graph. And vice versa: if three intervals I + 1 , I -, I + 2 are consecutive vertices, then J + := ρ(a)(I -) is the connected component of S 1 \ D(a) adjacent to both I + 1 and I + 2 . This proves that if I + 1 and I + 2 are consecutive connected components of D(a) in S 1 , then they belong to the same cycle in Γ a . Hence we easily deduce that all connected components of D(a) are in the same cycle in Γ a . Hence the same holds for the components of D(a -1 ).

Proof of Proposition 2.10. Fix a generator a ∈ S. The previous Lemmas 2.12 and 2.13 imply that the graph Γ a is a connected cycle. As the graph is bipartite, it must have an even number of edges, whence the statement.

Left-invariant circular orders

We begin this section by recalling definitions and basic properties. A reader familiar with circular orders may skip to Section 3.1.

Definition 3.1. Let G be a group. A left-invariant circular order is a function c : G × G × G → {0, ±1} such that 1. c is homogeneous: c(γg 0 , γg 1 , γg 2 ) = c(g 0 , g 1 , g 2 ) for any γ, g 0 , g 1 , g 2 ∈ G; 2. c is a 2-cocycle on G: c(g 1 , g 2 , g 3 ) -c(g 0 , g 2 , g 3 ) + c(g 0 , g 1 , g 3 ) -c(g 0 , g 1 , g 2 ) = 0 for any g 0 , g 1 , g 2 , g 3 ∈ G;
3. c is non-degenerate: c(g 0 , g 1 , g 2 ) = 0 if and only if g i = g j for some i = j.

We denote by CO(G) the space of all left-invariant circular orders on G, endowed with the topology as a subset of {0, ±1} G×G×G (with the product topology).

Although spaces of left-invariant linear orders have been well-studied, there are very few cases in which understand completely the topology of CO(G). A classification of groups such that CO(G) is finite is given in [START_REF] Clay | On the number of circular orders on a group[END_REF]. Other sporadic examples are known, for instance it is fairly easy to see that CO(Z) is homeomorphic to a Cantor set. Given that left-orders on free groups are well understood, a natural next case of circular orders to study is CO(F n ).

Our main tool here is the following classical relationship between circular orders and actions on S 1 (see [START_REF] Calegari | Circular groups, planar groups, and the Euler class[END_REF][START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF]).

Proposition 3.2. Given a left-invariant circular order c on a countable group G, there is an action

ρ c : G → Homeo + (S 1 ) such that c(g 0 , g 1 , g 2 ) = ord (ρ c (g 0 )(x), ρ c (g 1 )(x), ρ c (g 2 )(x)) for some x ∈ S 1 ,
where ord denotes cyclic orientation.

Moreover, there is a canonical procedure for producing ρ c which gives a well-defined conjugacy class of action. This conjugacy class is called the dynamical realization of c with basepoint x.

See [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF] for a description of this procedure, or [START_REF] Ghys | Groups acting on the circle[END_REF] for the analogous linear order case. Note that modifying a dynamical realization by blowing up an orbit of some point y / ∈ ρ(G)(x) results in a nonconjugate action that still satisfies the property c(g 0 , g 1 , g 2 ) = ord (ρ c (g 0 )(x), ρ c (g 1 )(x), ρ c (g 2 )(x)). However, this blown-up action cannot be obtained through the canonical procedure.

Remark 3.3. The above proposition actually characterizes countable circularly orderable groups as groups admitting a faithful action on S 1 . Indeed, given a faithful action ρ of G on S 1 , we can induce a circular order on G. If for the action ρ there is a point x with trivial stabilizer, then the induced order is simply defined by looking at the cyclic order of points in the orbit of x:

c(g 1 , g 2 , g 3 ) := ord(ρ(g 1 )(x), ρ(g 2 )(x), ρ(g 3 )(x)).
However it is not always possible to find such a point (for instance, this is impossible for the natural action of Thompson's group T on S 1 ) and we refer the reader to [5, Thm. 2.2.14] for the general case. 2In the case of ping-pong actions, however, there is always a point with trivial stabilizer. Precisely, we have: Lemma 3.4. Suppose that ρ is a ping-pong action of (Γ, S) with domains D(a). If x 0 ∈ S 1 \ a∈S∪S -1 D(a), then the orbit of x 0 is free and its cyclic order is completely determined by the cyclic order of the elements of {π 0 ( a∈S∪S -1 D(a)) , {x 0 }} and the assignments λ a .

The proof is obtained by a careful reading of the standard proof of the classical ping-pong lemma. See [21, Lemma 4.2] for details.

Isolated circular orders on free groups

In this section we will use ping-pong actions to answer a question of [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF] that asked which free groups admit isolated circular orders, proving Theorem 1.4 from the introduction. First, we introduce some tools.

Let G be any group, and ρ : G → Homeo + (S 1 ). Recall that, if G does not have a finite orbit, then there is a unique closed, G-invariant set contained in the closure of every orbit, called the minimal set of ρ(G) and denoted Λ(ρ). If Λ(ρ) = S 1 , the action is called minimal. Otherwise, Λ(ρ) is homeomorphic to a Cantor set and ρ permutes the connected components of S 1 \ Λ(ρ). In general the permutation action can have many disjoint cycles, however, this is not the case for dynamical realizations: In the case of ping-pong actions of free groups (of rank at least 2), there are no finite orbits, and invariance of the minimal set immediately implies that Λ(ρ) ⊂ a∈S∪S -1 D(a). When the union a∈S∪S -1 D(a) does not cover the whole circle, Λ(ρ) is a Cantor set. Up to blowing up one orbit (which does not change the class of semi-conjugacy of the action), we may assume that this condition holds, and more strongly, from now on we assume the following. Convention 3.6. In a ping-pong action of (Γ, S), we will assume that D(s) ∩ D(t) = ∅ holds for every two distinct s, t ∈ S ∪ S -1 . Remark 3.7. Under Convention 3.6 we have the stronger inclusion Λ(ρ) ⊆ a∈S∪S -1 D(a).

The following theorem relates circular orders and ping-pong actions. Theorem 3.8 ([21] Thm. 1.5). Let Γ = F n be a free group. A circular order c ∈ CO(Γ) is isolated if and only if its dynamical realization ρ c : Γ → Homeo + (S 1 ) is a ping-pong action satisfying Convention 3.6.

As a concrete example we have

Example 3.9. Let ρ : F 2 → PSL(2, R) be a discrete, faithful representation corresponding to a hyperbolic structure on a genus 1 surface with one boundary component. Then ρ is the dynamical realization of an isolated circular order.

More generally, take ρ as above, and let ρ be any lift of the action above to PSL (k) (2, R). Then ρ is the dynamical realization of an isolated circular order. (See [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF]Lemma 4.14]). For ρ, and hence for ρ, we can choose ping-pong domains such that the connected components of the sets D(a) ∪ D(a -1 ) and D(b) ∪ D(b -1 ) alternate.

With the tools above, we may now provide the Proof of Theorem 1.4. If n is even, then the representation of Γ into PSL(2, R) coming from a hyperbolic structure on a genus n/2 surface with one boundary component gives an isolated circular order, as explained in [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF]. (By taking lifts to cyclic covers, one can in fact obtain infinitely many isolated circular orders in distinct equivalence classes under the action of Aut(F n ) on CO(G).)

For the case where n is odd, we need more work. Suppose that ρ :

F n → Homeo + (S 1
) is a dynamical realization of an isolated circular order on Γ = F n (we do not assume yet n is odd), and fix a generating set S = {a 1 , . . . , a n }. In particular we have that the ping-pong action satisfies Convention 3.6 and that the connected components of S 1 \ Λ(ρ) form a unique orbit. Let c 0 , . . . , c r be the connected components of S 1 \ Λ(ρ) that are not contained in any domain D(s).

Suppose that c i has endpoints in D(s) and D(t), for some s = t. Then, for any generator u / ∈ {s -1 , t -1 }, we have that ρ(u)(c i ) ∈ D(u). Also, from Remark 3.7 we have that ρ(s -1 )(c i ) and ρ(t -1 )(c i ) belong to {c 0 , . . . , c r }. This implies that c i and c j are in the same orbit (which they do) if and only if they are equivalent under the relation ∼ generated by

c i ∼ ρ(t -1 )c i if c i ∩ D(t) = ∅, for t ∈ S ∪ S -1 .
We now use a clever argument to show that if n is odd, then the number of equivalence classes under this relation cannot be 1.

We aim to build a surface Σ by starting with the disc D and gluing another disc to ∂D for each generator a ∈ S as we next explain. For each generator a ∈ S, let k(a) be the integer given by Proposition 2.10. Let P a be a 4k(a)-gon (topologically a disc) with cyclically ordered vertices v 1 , v 2 , . . . , v 4k(a) . Choose a connected component I = [x 1 , y 1 ] of D(a) and glue the oriented edge v 1 v 2 to I so as to agree with the orientation of I ⊂ S 1 . Then glue the edge v 3 v 4 to the connected component of D(a -1 ) containing ρ(a -1 )(x 1 ), according to the orientation in S 1 . Let y 2 denote the other endpoint of this connected component, and glue v 5 v 6 to the connected component of D(a) containing ρ(a)(y 2 ). Iterate this process until all edges v 2j-1 v 2j have been glued to S 1 = ∂D. Note that the remaining (unglued) edges of P a correspond exactly to the edges of the graph Γ a from Definition 2.9. Repeat this procedure for each generator in S. (A cartoon of the result of this procedure for the ping-pong action of Example 3.12 is shown in Figure 3.1.) Because of Proposition 2.10, the gluing of P a described adds one face and 2k(a) edges to the existing surface. Therefore after all the polygons P a (as a ranges over the generators) have been glued, we will have a surface Σ of Euler characteristic χ(Σ) ≡ n + 1 mod 2. Since χ(Σ) is also congruent to the number of its boundary components mod 2, to finish the proof of Theorem 1.4 it is enough to show the following Claim. The number of boundary components of the surface Σ is exactly the number of ∼-equivalence classes of the c i 's.

Indeed, since the number of ∼-equivalence classes of the c i 's is 1, the Claim and the above discussion implies that 1 ≡ n + 1 mod 2, which implies that n = rank(F n ) is even.

Proof of Claim. Indeed, ∂Σ ∩ {c 0 , . . . , c r } has one connected component in each interval c i . By construction, if c i has endpoints in D(s) and D(t), then ∂Σ ∩ c i is joined to ρ(t -1 )c i ∩ ∂Σ and ρ(s -1 )c i ∩ ∂Σ by edges of P s and P t respectively. Moreover, each edge of P s ∩ ∂Σ plays the role of one of these connectors. It follows that components of ∂Σ captures the equivalence classes described above.

Remark 3.10. Note that n even is not a sufficient condition to ensure that a ping pong action of F n comes from a dynamical realization (equivalently, that Σ has one boundary component). For instance one may consider a group generated by two sufficiently large powers of hyperbolic elements of PSL(2, R) with non-crossing axes when seeing them acting on H 2 .

The proof above can be improved to give a statement about general ping-pong actions: Theorem 3.11. Let Γ = F n be the free group of rank n with generating system S. Consider a ping-pong action ρ of (Γ, S) satisfying Conventions 2.4 and 3.6. Let Λ(ρ) be the minimal invariant Cantor set for the action. Then the number of orbits of connected components of the complement

S 1 \ Λ(ρ) is congruent to n + 1 mod 2.
Proof. Compared to the proof of Theorem 1.4, we only need to observe the following:

Claim. Let c 0 , c 1 , . . . , c r be the connected components of S 1 \ Λ(ρ) that are not contained in any domain D(s). Then each orbit of the connected components of S 1 \ Λ(ρ) under the action of Γ contains some c i . Proof of Claim. Suppose I is a connected component contained in some D(s). By Lemma 2.8, we can take ρ(s) to be piecewise linear, and such that each ρ(s -1 ) expands D(s) uniformly, increasing the length of each connected component by a factor of some µ > 1, independent of s. Iteratively, assuming that ρ(s

k s k-1 • • • s 1 )(I) ⊂ D(s -1 k+1 ), then the length of ρ(s k+1 s k • • • s 1 )(I) is at least µ k+1 length(I)
. This process cannot continue indefinitely, so some image of I is not contained in a ping-pong domain.

As a consequence, to count the number of orbits of the action of Γ on connected components of S 1 \ Λ(ρ), we need only to count the number of equivalence classes of the c i 's (with respect to the orbit equivalence relation). This is done as in the proof of Theorem 1.4, with the help of the surface Σ defined by gluing polygons.

Exotic examples

We conclude this section with discussion of new examples of ping-pong configurations and isolated orders, i.e. those that, even after an automorphism of the group, cannot arise from the construction in Example 2.7.

Example 3.12. The example described in Figure 3.1 (left) is not realized by a ping-pong action in PSL(2, R), neither in any cover of it. Indeed, ρ(b) has 2 hyperbolic fixed points, while ρ(a) has four.

Observe that the ping-pong configuration for ρ(b) alone is atypical, in the sense that it is not the classical ping-pong configuration for a hyperbolic element in PSL( 2 This ping-pong configuration gives a surface with one boundary component, so it corresponds to an isolated circular order in CO(F 2 ). See Figure 3.1 (right).

Observe that one can create several examples of this kind, by choosing ρ(b) to have two hyperbolic fixed points, but with an arbitrarily slow contraction (i.e. with N connected components for D(b), N ∈ N arbitrary) and then choosing ρ(a) to be a N -fold lift of a hyperbolic element in PSL(2, R).

The classification of all isolated circular orders for F 2 does not seem an easy task, at least at first glance.

Left-invariant linear orders on F n × Z

The main purpose of this section is to prove Theorem 1.1, stating that F n × Z admits an isolated linear order if and only if n is even.

Preliminaries

Before proceeding to the proof of Theorem 1.1, we recall some (more or less) classical tools.

As for circular orders, linear orders on countable groups have a dynamical realization (see for instance [START_REF] Deroin | Groups, orders and dynamics[END_REF]Prop. 1.1.8]). One quick way of seeing this is thinking of a linear order as a special caso of circular order. Indeed, given a linear order on a group G, one defines the cocycle c by setting, for distinct

g 1 , g 2 , g 3 ∈ G c (g 1 , g 2 , g 3 ) = sign(σ),
where σ is the permutation of the indices such that g σ(1) ≺ g σ( 2) ≺ g σ [START_REF] Arora | Centralizers in free lattice-ordered groups[END_REF] . In more sophisticated terms, one can show that linear orders correspond exactly to 2-cocycles c which are coboundaries (see for instance [21, §2]). Thus, the construction of the dynamical realization sketched in the proof of Proposition 3.2 may be performed also for a linear order. The result is an action on the circle with only one global fixed point, which one can view as an action on the line with no global fixed point. Conversely a faithful action on the real line ρ : G → Homeo + (R) can be viewed as a faithful action on the circle with a single fixed point, and from it the induced orders will be linear orders on G (cf. Remark 3.3).

Next, we recall the notion of convex subgroups and their relationship to isolated orders.

Definition 4.1.

A subgroup C in a linearly-ordered group (G, ) is convex if for any two elements h, k ∈ C, and for any g ∈ G, the condition h g k implies g ∈ C.

Remark 4.2. Let G be a countable group and consider a dynamical realization ρ of (G, ) with basepoint x. Then, if C is a convex subgroup, the interval

I := inf h∈C ρ(h)(x) , sup h∈C ρ(h)(x)
has the following property:

for any g ∈ G, ρ(g) either fixes I or ρ(g)(I) ∩ I = ∅. It is easy to see that the family of convex subgroups of a linearly ordered group (G, ) forms a chain: if C 1 , C 2 are two convex subgroups of (G, ), then either C 1 ⊂ C 2 or C 2 ⊂ C 1 . Moreover, for any convex subgroup C ⊂ G, the group G acts on the quotient (G/C, C ) by order-preserving transformation, where, by definition, f C ≺ C gC if and only if f c ≺ gc for every c, c ∈ C (this definition makes sense because C is convex). In particular, this implies that if C is convex in (G, ), then any linear order on C may be extended to a (new) order on G by declaring

id g ⇔ C ≺ C gC if g / ∈ C, id g if g ∈ C.
Elaborating on this, one can show the following lemma (see [START_REF] Deroin | Groups, orders and dynamics[END_REF]Prop. 3.2.53] or [24, Thm. 2] for details). Let us also introduce a dynamical property that implies that an order is non-isolated: It was implicit in the work by Navas [START_REF] Navas | On the dynamics of (left) orderable groups[END_REF] as well as in [START_REF] Rivas | Left-orderings on free products of groups[END_REF], that if the dynamical representation coming from an order is flexible, then the order is non-isolated. An explicit proof can be found in [START_REF] Alonso | Orderings and flexibility of some subgroups of Homeo+(R)[END_REF]Prop. 2.8]. Also, a characterization of isolated (circular or linear) orders in terms of a strong form of rigidity (i.e. strong non-flexibility) can be found in [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF]. Lemma 4.5. Let G be a discrete, countable group and let ρ 0 the dynamical realization of an order with basepoint x ∈ R. 3 If ρ 0 is flexible, then is non-isolated in LO(G).

As mentioned in the introduction, in order to prove Theorem 1.1 we consider the interplay with circular and linear orders on groups. For this purpose we now recall the notion of cofinal elements. Definition 4.6. An element h in a linearly-ordered group (G, ) is called cofinal if: for all g ∈ G, there exists m, n ∈ Z such that h m g h n .

(4.2) Remark 4.7. When considering a dynamical realization ρ with basepoint x, a cofinal element is an element with no fixed point: if (4.2) is not verified for h ∈ G, take

x * := inf{ρ(g)(x) | h n g for every n ∈ Z}.
This is a fixed point for h.

Given a group G with a circular order c, there is a natural procedure to lift c to a linear order c on a central Z-extension on G [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF][START_REF] Želeva | Cyclically ordered groups[END_REF]. With respect to this order, the central Z -or more precisely a generator of Z -is cofinal. The following statement appears as Proposition 5.4 in [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF]: One last crucial notion is that of crossings: Definition 4.9. Let G be a group acting on a totally ordered space (Ω, ). The action has crossings if there exist f, g ∈ G and u, v, w ∈ Ω such that:

1. u ≺ w ≺ v.
2. g n u ≺ v and f n v u for every n ∈ N, and

3. there exist M, N in N such that f N v ≺ w ≺ g M u.
Remark 4.10. When considering the dynamical realization, a crossing is simply given by two elements whose graphs are crossing, as pictured in Figure 4.1. Lemma 4.11 ([14] Cor. 3.2.28). Let C be a convex subgroup of (G, ) and suppose that the (natural) action of G on (G/C, C ) has no crossings. Then there exists a homomorphism τ : G → R with C in its kernel. Moreover, if C is the maximal convex subgroup of (G, ), then C agrees with the kernel of τ .

Isolated linear orders on F n × Z

As a consequence of Proposition 4.8, we know that F 2n × Z admits isolated linear orders, namely, any that comes from lifting an isolated circular order on F 2n . Further, if

0 → Z → Ĝ π → G → 1
is a central Z-extension of G, then any linear order on Ĝ in which Z is cofinal gives a canonical circular order on G, which we denote by π * ( ), as follows. Let z be the generator of Z such that z id. Since z is cofinal, for each g ∈ G, there exists a unique representative ĝ ∈ π -1 (g) such that id ĝ ≺ z. Given distinct elements g 1 , g 2 , g 3 ∈ G, let σ be the permutation such that

id ĝσ(1) ≺ ĝσ(2) ≺ ĝσ(3) ≺ z.
Define π * ( )(g 1 , g 2 , g 3 ) := sign(σ). One checks that this is a well defined circular order on G. In the proof of Proposition 5.4 of [START_REF] Mann | Group orderings, dynamics, and rigidity[END_REF], it is shown that π * is locally injective when G is finitely generated. This implies that an isolated linear order of F 2n+1 × Z with cofinal center would produce an isolated circular order of F 2n+1 . This we know is not possible after Theorem 1.4. Thus, to finish the proof of Theorem 1.1 it is enough to show the following: Proposition 4.12. Let F be a free group, and a linear order on G = F × Z in which the central factor is not cofinal. Then is non-isolated.

As a warm-up and tool in the proof, we give a short proof of a special case.

Lemma 4.13. Let F be the free group of infinite rank and G = F × Z. Then no order in LO(G) is isolated.

Proof. Let f 1 , f 2 , . . . be a set of free generators of the free factor F and g the generator of the central factor Z. Let be any order on G and ρ 0 its dynamical realization. For any fixed n ∈ N, we can define a representation ρ n : G → Homeo + (R) by setting

ρ n (g) = ρ 0 (g), ρ n (f k ) = ρ 0 (f k ) if k = n, ρ 0 (f n ) -1 if k = n.
It is easy to see that the actions ρ n are all free and pairwise non-semi-conjugate one to another. So they determine distinct orders n , which converge to in LO(G) as n → ∞.

Proof of Proposition 4.12. If F has rank one or infinite rank, it is easy to see that they do not admit isolated orders. Indeed, in the former case the group G is free abelian hence it has no isolated order [START_REF] Sikora | Topology on the spaces of orderings of groups[END_REF], in the latter case we have seen this in Lemma 4. [START_REF]On the ergodic theory of free group actions by real-analytic circle diffeomorphisms[END_REF].

So from now on we assume that F has finite rank ≥ 2. Looking for a contradiction, we let be a linear order on G which is isolated and in which the center is not cofinal. This means that in the dynamical realization ρ of (G, ), the Z = z factor acts with fixed points (Remark 4.7). In fact, the fixed points of z accumulate to both ∞ and -∞, because F commutes with z and if this was not the case, there would be a global fixed point for G.

Call I the connected component of R \ Fix(z) that contains the basepoint x 0 of ρ (which is a bounded interval), and let C = Stab G (I). Claim 1. C is a convex subgroup of (G, ). Moreover, z is cofinal in (C, ).

Proof of Claim. If h, k ∈ C and g ∈ G verify

h(x 0 ) < g(x 0 ) < k(x 0 ), then for any n we also have z n h(x 0 ) < z n g(x 0 ) < z n k(x 0 ); as z is central, this implies hz n (x 0 ) < gz n (x 0 ) < kz n (x 0 ). (4.3)

Assume, without loss of generality, that z(x 0 ) > x 0 . Then, as n → ∞, the sequence of points z n (x 0 ) converges to the rightmost point of I, which is fixed by both h and k. We deduce from (4.3) that also g fixes this point. Repeating this argument considering the limit in (4.3) as n → -∞, we get that also the leftmost point of I is fixed by g. Hence g ∈ C, as wanted.

Finally by Remark 4.7, the fact that z has no fixed points in I implies that z is cofinal in (C, ).

Claim 2. C has infinite index in G.

Proof of Claim. If C had finite then the G-orbit of the interval I would be bounded. This would imply that the dynamical realization has a global fixed point, which is absurd.

Since C is a convex subgroup, if the restriction of to C is non-isolated, then we can approach by approaching its restriction to C. So going forward we assume that the restriction of to C is isolated.

If the chain of convex subgroups of is infinite, then Lemma 4.3 implies that is non-isolated and we are done. So, we also assume from now on that the chain of convex subgroups of G is finite. Hence we can let C be the smallest convex subgroup properly containing C. In this way, to show that is non-isolated, it is enough to show that is non-isolated in C, or, what is the same, we can restrict to the case where C is the maximal convex subgroup of G.

For our first claim observe that C admits a decomposition of the form F * × Z, where F * is a subgroup of F . Claim 3. F * is a non trivial free group of even rank. Proof of Claim. Since the restriction of to C = F * × Z is isolated, as before, Lemma 4.13 implies that F * cannot have infinite rank. Moreover, F * cannot be trivial as then the action of G would be semi-conjugated to an action of F , thus making very easy to perturb the action of F × Z and thus the order (recall that free groups have no isolated orders [START_REF] Mccleary | Free lattice-ordered groups represented as o-2 transitive l-permutation groups[END_REF]). Finally, as z is cofinal in the ordering in C, the argument above Proposition 4.12 shows that F * must have even rank.

Since every (non trivial) normal, infinite index subgroup of F has infinite rank, we conclude from Claim 3 that F * (and thus C) is not a normal subgroup of G. Lemma 4.11 implies that the action of G on (G/C, C ) has crossings, as otherwise C would be normal. In particular, if we collapse I and its G-orbit, we obtain a semi-conjugate action ρ : G → Homeo + (R) which is minimal and has crossings. Note that the center Z = z ⊂ C acts trivially in this action. Claim 4. For any compact K ⊂ R, there exists ρ agreeing with ρ on K, but not semi-conjugate to ρ.

Figure 2 . 1 :

 21 Figure 2.1: Classical ping-pong on two generators

Figure 2 .

 2 1 shows an example of the dynamics of such an action of F 2 = a, b .

Lemma 3 . 5 ([ 21 ]

 3521 Lemma 3.21 and Cor. 3.24). Let ρ : G → Homeo + (S 1 ) be a dynamical realization of a circular order c. Suppose that ρ has a minimal invariant Cantor set Λ. Then ρ acts transitively on the set of connected components of S 1 \ Λ.

Figure 3 . 1 :Figure 3 . 2 :

 3132 Figure 3.1: The surface associated with the exotic example (left), and its boundary component (right).

  , R)ρ(b) has a "slow" contraction on the left half of the circle, as two iterations of ρ(b) are needed in order to bring the external gaps of D(b) ∪ D(b -1 ) into the component of D(b) with the attracting fixed point. See Figure 3.2.

(4. 1 )

 1 Moreover, the stabilizer of I is precisely C.Conversely, given a faithful action on the real line ρ : G → Homeo + (R), if an interval I has the property (4.1), then the stabilizer C = Stab G (I) is convex in any induced order with basepoint x ∈ I.

Lemma 4 . 3 .

 43 If (G, ) has an infinite chain of convex subgroups, then is non-isolated in LO(G).

Definition 4 . 4 .

 44 Let G be a discrete, countable group and consider the space of representations Rep(G, Homeo + (R)) endowed with the topology of pointwise convergence. We denote by Rep # (G, Homeo + (R)) the set of representations with no global fixed points.A representation ρ 0 ∈ Rep # (G, Homeo + (R)) is flexible if there are arbitrarily close representations ρ ∈ Rep # (G, Homeo + (R)) which are not semi-conjugate to ρ 0 .

Figure 4 . 1 :

 41 Figure 4.1: A crossing in the dynamical realization.

Proposition 4 . 8 .

 48 Assume that G is finitely generated and c is an isolated circular order on G. If c is the lift of c to G, a central Z-extension of G, then the induced linear order c is isolated in LO( G).

In[START_REF] Baik | Spaces of invariant circular orders of groups[END_REF] Prop. 2.4] the authors propose an alternative way of inducing an ordering of G. However their method is incorrect, as the following example shows: suppose to have three distinct homeomorphisms f, g, h, with f coinciding with g on one half circle and with h on the other half. Then for any point x ∈ S 1 , there are always two equal points in the triple (f (x), g(x), h(x)).

See Proposition 3.2 for the definition.

Acknowledgments

The authors thank Yago Antolín for suggesting Corollary 1.2. K.M. was partially supported by NSF grant DMS-1606254. C.R. was partially supported by FONDECYT 1150691. M.T. was partially supported by PEPS -Jeunes Chercheur-e-s -2017 (CNRS), Projet "Jeunes Géométres" of F. Labourie (financed by the Louis D. Foundation) and the Réseau France-Brésil en Mathématiques.

Proof of Claim. We show this by showing how to perturb ρ in a neighborhood of +∞. For this we fix a compact set K. We want to perturb the generators of G outside K in such a way that the perturbed action is not semi-conjugate to ρ.

Suppose as an initial case that there is a generator, say a, that has a fixed point p outside -and on the right of -K. Then we can change ρ(a) on each component of R \ Fix(ρ(a)) to the right of p, in such a way that perturbed action, say a , satisfies that a (x) ≥ x for all x ≥ p, or a (x) ≤ x for all x ≥ p, while leaving the rest of the generators untouched. Since these two possible perturbations give actions that are not semi-conjugate, this ensures that at least one of them is not semi-conjugate to ρ. Moreover, since p is also a fixed point of ρ(z), one can perform this modification in such a way that a = cρ(a) where c is an element commuting with ρ(z). In particular, the new action extends to a representation of F × Z. This concludes the proof in the case one generator has a fixed point outside K.

For the remaining case, suppose that no generator has a fixed point outside K. We claim that then we can perturb the action ρ to obtain one generator with a fixed point outside K; showing this will be the content of the remainder of the proof. First, since ρ has crossings, for any compact K ⊂ R there is g ∈ G such that R \ Fix(ρ(g)) has a component outside (and on the right of) K. Let J = (j -, j + ) denote one of those components.

Claim ( * ).

There is a free generator a (or an inverse) of F such that ρ(a)(j -) ∈ J, but ρ(a)(j + ) / ∈ J.

Proof of Claim ( * ). If this was not the case, J would satisfy property (4.1) and as observed in Remark 4.2 this would give a convex subgroup properly containing a conjugate of C, which is not possible by the maximality of C.

Let ḡ be the homeomorphism defined as the identity outside J and agreeing with ρ(g) on J. Let a be the generator given by Claim ( * ) and define ρ ḡ by Since ḡ commutes with z, the new action ρ ḡ is a representation of G. Moreover, by changing ḡ by some power if necessary, we have that ρ ḡ(a) has a fixed point in J. This ends the proof of Claim 4.

To finish the proof of Proposition 4.12 (and thus that of Theorem 1.1), note that the flexibility of ρ from Claim 4 implies that the order is non-isolated (Lemma 4.5).


Ante Vilenica

Kristof Hamann

Winfried Lamersdorf

Jan Sudeikat

Wolfgang Renz

An Extensible Framework for Dynamic Market-Based Service Selection and Business Process Execution

Keywords: Service-Oriented Computing, Autonomous Components, Negotiation Framework

Business applications in open and dynamic service markets offer great opportunities for both consumers as well as for providers of services. However, the management of related business processes in such environments requires considerable (often still manual) effort. Specific additional challenges arise in highly dynamic environments which may lead, e.g., to service failures or even to complete disappearance of partners and, consequently, a need to reconfigure related processes. This work aims at generic software support for addressing such challenges mainly by providing an extensible negotiation framework which is capable of performing the tasks of service selection and service execution automatically. Its technical basis are augmented, reusable and highly autonomous service components that can be tailored towards the specific needs of each business process. In addition, the implementation of the negotiation framework includes a simulation component which offers convenient means to study the outcome of different settings of the business environment a priori.

Introduction

State-of-the-art business information systems rely on a high number of different services from various sources as well as on open and flexible business procedures making use of them. Software support for the development of such (distributed) applications profits substantially from a service-oriented software architecture which provides appropriate architectural patterns for the sophisticated and flexible development of information systems that can easily interoperate, change components and therefore cope with the high complexity, dynamicity and demands of modern business environments. In such scenarios, services may typically appear and disappear at any time and may, furthermore, dynamically change their configuration, e.g. their commitment towards a certain application or their respective costs. Such kind of behaviour can be found in particular in domains that use market-based pricing for negotiating contracts between consumers and providers of respective services. These business domains require open market systems with standardized interfaces and various vendors in order to work properly and to have a competitive market. At the same time, the inherent dynamics of such market-based systems complicate the runtime management of applications composed of different services and, thus, require solutions capable to cope with these challenges as autonomously as possible.

For example, think of a computer manufacturer who regularly needs to acquire different well-defined and standardized sub-components like hard-disks, keyboards, RAM etc. for his production line. This scenario reveals a clear demand for an (autonomous) management of this supply process that takes into account different functional and non-functional aspects and that (dynamically) selects the most appropriate service provider at any time in a constantly changing environment. Furthermore, not only the selection but also the execution of the selected service should be automatically monitored and managed -such that, for instance in the case of a service-breakdown, appropriate actions, e.g. instantiation of a new selection process, should be initiated automatically.

Aiming at such scenarios, the work reported in this paper addresses these challenges by proposing a supportive software framework capable of facilitating the autonomous and dynamic selection and execution of service-based applications. It leverages different market-based negotiation protocols in order to determine contract partners as well as various utility-functions for specifying preferences among (potentially conflicting) objectives. Therefore, the approach proposed here enables existing as well as new composed services with the capability to participate in such automatic and autonomous service selection and process execution. Technical basis for the implementation of such dynamic and adaptive service composition is an environment that integrates workflow execution with autonomous software agents [?]. In this approach, software agents represent services which participate in dynamically adaptive business processes. The necessary adaptivity is realised by an underlying management middleware that controls the coordination of all participating software agents. This, in turn, leads to adaptive and autonomous properties of the workflow management itself, e.g., by autonomously deciding which individual agents resp. services are responsible for realising specific complex activities, without effect on the overall workflow goals themselves. This decentralized middleware for the integration of decentralized, self-organizing processes among software agents was already presented in [?].

The remainder of this paper is structured as follows: The next section gives an overview of related work; Section ?? describes the proposed framework for realising automatic service selection and execution in market-based business applications. Section ?? presents parts of a proof of concept implementation of this framework and reports on a case study to show the applicability of the approach before Section ?? concludes the paper with a brief discussion on future work.

Related Work

Service-Oriented Architectures (SOA) provide a paradigm to leverage business integration and to implement loosely-coupled distributed applications. In such an approach, the dynamic binding of services is perceived as an integral part of an SOA since it facilitates a loose coupling between services and hence fosters reusability and dynamic adaptation to changing environments. Service binding assembles two different aspects, service discovery and service selection [?]. Service discovery describes the procedure of locating available services matching given functional demands. In contrast to that, service selection deals with the problem of choosing one service from a set of suitable services. Often, service selection is done by incorporating non-functional requirements, defined by the service requestor [?,?].

However, since most approaches require the service provider to declare the offered non-functional properties, the consumer has to rely on these propositions. Solutions to this problem incorporate trust models in order to rate the reputation of a provider. Vu et al. [?], e.g., propose a probalistic framework for decentralized management of trust and quality while incorporating the credibility of observation data, the multi-dimensionality and subjectivity of quality and trust. Advanced approaches for service selection use a utility function in order to enable service consumers to flexibly differentiate between important and less significant non-functional properties. Approaches such as the work of Hang and Singh [?] provide frameworks which are able to optimize these utility functions.

Regarding dynamic pricing in markets, there has been also work on service selection on behalf of market-based negotiation protocols such as auctions. Wellman et al. give an overview [?] of the several bidding strategies used in the international Trading Agent Competition, a scenario where agents contend for flights, hotel rooms and entertainment. Similar to the assumptions in our work, prices are set dynamically by the market participants. For every product type, there is a different auction type with different properties, such as auction setting (e.g. combinatorial or multi-auction), simultaneity, price predictability, auction length. Hence, the approaches of the bidding agents differ enormously.

Lamparter and Schnizler [?] propose a market-based architecture for trading Web Services. However, they focus on the semantic description of services and bids with ontologies. Service offers and service requests are converted by a preprocessor in order to facilitate the syntactic matching of bids. This allows for the use of existing implementations of the demanded multi-attribute combinatorial double auction.

He and Liu [?] suggest to use software agents in order to realize a marketbased service selection framework. However, the resulting framework is nevertheless rather inflexible, since it is limited to the Contract Net protocol and only few non-functional properties are used. Borissov et al. [?] propose an automated bidding system for the allocation of grid-based services. Market platform and bid framework are strictly separated and make use of agent technologies, e.g. for negotiation resp. communication. The BidGenerator automatically performs bids at the market, which allows the usage of two negotiation types. Therefore, BidGenerator implements several bidding strategies, which can be used by the customer in order to obtain a resource in the grid. In summary, the agent paradigm is well suited in order to develop autonomous software components as they are useful for participation in market-based scenarios. Well-established technologies used in agent frameworks, such as negotiation and self-organisation [?], can facilitate the development of according applications. However, there are comparatively few frameworks for market-based service selection, which make use of these technologies. The agent-based approaches introduced in this section, however, do not provide support for advanced service-selection mechanisms, such as trust models and business process integration. Therefore, the next section proposes a flexible agent-based serviceselection framework that facilitates the implementation of market places using different auction types. It supports the integration of service providers and service consumers into the market with respect to their own bidding strategies, utility functions and trust models, and the overall integration in a business process management system.

The Service-Selection Framework

This section presents the proposed framework for an automatic handling of service selection and service execution for market-based business domains. The basic idea of this framework consists of providing a blueprint that contains the necessary components and defines their structure and kind of interaction to achieve the autonomous management functions mentioned in Section ?? rather than proposing and developing new negotiation protocols, utility functions etc. Figure ?? depicts the components of the framework and their structure on an abstract level. It shows that this approach basically uses the SOA approach to build (distributed) applications and takes the Agent paradigm [?] to enrich the management of these applications with proactive and autonomous capabilities.

At the beginning of the service selection phase, the framework expects a business process description which contains the required services and describes the logical-temporal dependencies among them. This description can be provided by applying, e.g., the XML Process Definition Language (XPDL). It is then processed by a process engine which identifies all needed services and sends for each of them a request to the Service Market Agent (SMA). In addition, this request does not only contain the service type to be found but also some other optional properties like a utility function that contains certain concerns regarding time deadlines, fees, quality of service parameters and so forth. Also, the request may specify a certain negotiation (bidding) protocol to be used. For each request, the SMA sends out a service negotiation request message using a negotiation middleware that contains implementations of various negotiation protocols. Then, it depends on the type of negotiation protocol how an appropriate service provider is selected. In order to perform the negotiation task the negotiation middleware additionally has to process service bid messages sent by Service Agents (SA). These agents act on behalf of service providers and try to find contractors that fit best. In summary this approach consists of two agent types, i.e. SMA and SA, that try to find appropriate service partners using a middleware with different negotiation protocols. Details of these components are presented in the following subsections.

Negotiation Middleware

The aim of the negotiation middleware is to propose an infrastructure component that facilitates the reusability and modularity of negotiation protocols and that additionally enables the parallel execution of different negotiation protocols at runtime. Thereby, the negotiation middleware utilizes the approach of coordination spaces [?], that facilitates a clear separation between computation and coordination. Whereas computation denotes the core functions of a component, coordination can be seen as "managing dependencies between activities" [?, p. 90]. In consequence, coordination spaces promote an approach of easy changing the way dependencies are managed among components. This is achieved by a layered approach that contains interchangeable coordination media. In conclusion, different coordination media provide different ways of interdependency management.

From this perspective on, negotiation can be seen as a special type of coordination. Thereby, negotiation can be realized using coordination media that provide implementations of negotiation protocols like the pure ContractNet or extensions of this protocol [?] as well as auctions like Dutch, Vickrey etc.

In order to achieve a loose coupling between the SMA, SA and negotiation media the negotiation middleware uses an event-based architecture. Each of the afore-mentioned components implements a generic publish/subscribe interface which enables the components to publish and perceive events of interest. Therefore, the negotiation middleware uses asynchronous communication which is especially suited for distributed systems to ensure a reasonable performance Figure ?? depicts proposals of patterns that have been implemented (cf. Section ??) for evaluation purpose. The first one (cp. Figure ??) shows the messages sent between an SMA and a negotiation medium. It starts with a message to initiate the negotiation process containing all information necessary for the negotiation medium to process. As soon as the medium has found an appropriate service provider it sends a contract proposal to the SMA. Now, the SMA can decide to accept or reject this contract. The SMA may decide to reject the proposal if it has already received an appropriate offer from another negotiation medium.

Depending on the answer of the SMA the negotiation medium terminates the selection process for this particular service type with a final message that states whether the contract was closed or cancelled.

The proposed communication pattern between SA and negotiation medium is quite similar to the afore described one but has one important difference which relates to the question where to place the negotiation strategy of the SA. Thereby, the negotiation strategy expresses the behaviour of an SA and especially determines the way service bids are computed. One possibility is to place the strategy into the initial service registration message that is sent at the beginning. Then, the negotiation medium is the only place where service providers and service consumers interact according to a negotiation protocol like the Contract Net Protocol. This approach has the benefit of a high efficiency since the negotiation process is handled inside the medium and does not require further communication with SAs. On the other hand this approach has the drawback that SAs have to disclose their bidding strategy to a third party (negotiation medium). For certain service provider this might not be appropriate. Therefore, Figure ?? depicts an optional part of the communication pattern that targets this issue. When the negotiation medium receives a service negotiation request sent by an SMA requesting a certain service type, it searches for all SAs that have registered at the negotiation medium for this particular service type. Then, the negotiation medium sends out a service offer request to these SAs. Now, the SAs can submit an offer without the need to disclose their strategy. Therefore, proposals are sent back to the negotiation medium using a service bid message. Depending on the type of negotiation protocol this optional protocol phase may be iterated several times. Most often iteration is needed if the proposals do not meet the requirements of the SMA. The last part of the communication protocol is equal to the protocol between an SMA and the negotiation medium. It gives the chance to the selected SA, i.e. the SA with the most appropriate bid, to close or reject the service contract (with the service consumer).

As mentioned at the beginning, the framework can implement arbitrary communication patterns. The previous paragraph has presented one possible pattern to illustrate the potential of the framework. The next subsection will present more details regarding the SMA and the SA. It will explain their functionality and show how they can be tailored with respect to certain requirements.

Two Negotiation Proxies: SMA & SA

In order to provide reusable components for the management of automated negotiations in service-based systems, the two agent types SMA and SA are proposed. This approach promotes a clear separation between the core concepts of SOA and the ability to dynamically negotiate contract partners in the domain of market-based pricing. It enables services as well as processes to participate in negotiations by specifying their requirements and preferences in a declarative manner but without the need to implement these functions by themselves. In order to encapsulate the negotiation functions that are needed, two different components have been designed: SMA & SA. Whereas the first one is in charge of service consumers, the latter one deals with service providers. As they act on behalf on another component they are also named negotiation proxies.

The two negotiation proxy types themselves consist of reusable subcomponents, i.e. capabilities [?], which can be divided into mandatory and optional ones. An SMA needs a Service Offer Capability and an Execution Caller Capability. The first one is in charge of handling the selection phase whereas the latter one takes care of the execution phase. Complementary, an SA has a Service Supplier Capability and an Execution Service Capability which correspond to the afore mentioned functions of an SMA.

Therefore, the proposed framework can not only be used for the automated management of the service selection phase but also for the dynamic management of the service execution phase. This aspect is achieved by a collaboration between the SMA and the process engine. Once the process engine has started the execution of the process the SMA is contacted each time a service needs to be executed. Now, the SMA is responsible for requesting the selected service for execution as well as dealing with failures. If the selected service is not available the SMA initiates a new service selection process and tries to find an appropriate substitution for the service. In order to detect service breakdowns happening at runtime the SMA uses a heart beat protocol that determines if a service is alive. Again, if a failure is detected, a new service has to be selected. Additionally, it might happen that a committed service provider, i.e. a service that has signed a contract with a process, decides to break the contract and to participate in another process, e.g. since it gets a better reward. Then, the SMA acts proactively and tries to replace this service in order to avoid a failure when this service has to be executed.

Beside these basic functionalities, the two proxy types can be extended to deal with optional aspects of negotiations like ensuring confidentiality and anonymity among contract partners or using implementations of trust models [?]. Thereby, this paper does not understand trust from a computer security perspective on. Rather, it uses trust to define and measure the reliability / reputation of (possible) contract partners. Reliability tries therefore to quantify the confidence that a stakeholder A has with respect to another one B that it will deliver a service according to a signed contract. Therefore, trust can be seen as an additional important criterion which has to be evaluated in a market-based environment. The interplay of service selections, based on past experiences, and the subsequent adjustment of reputation values leads to an independent dynamic process (cf.

[?] for a systemic evaluation). Whereas direct service selection criteria, such as fees or time deadlines, can be easily evaluated, this does not hold for trust which is an indirect criterion and therefore more difficult to measure.

The actual configuration of the proxies for a certain application is performed at design time using an XML configuration file. For both of the proxy types a separate XML Schema has been developed. For the SMA this schema requires following aspects to be specified: an ordered preference list of negotiation media to use, a utility function that is used to evaluate proposals (with respect to potentially conflicting goals) and a deadline for the negotiation process. Optional aspects can be specified as name value pairs. The schema for the SA specifies following aspects: a list of negotiation media to use, a service offer containing the fees and execution period and a negotiation strategy or a reference to the SA in order to avoid disclosing the strategy. These configuration options allow a flexible reuse of the negotiation proxies. In the following section, the practical realization is introduced and the overall approach is evaluated.

Implementation and Evaluation

This section describes the prototype implementation of the proposed negotiation framework. Furthermore, a case study on an imaginary "computer manufacturer" is briefly presented in order to demonstrate the applicability of the approach. The framework implementation utilizes the Jadex Agent Framework [?]. Besides core functionalities required for the execution of Multi Agent Systems (MAS) it has the capability to perform (automated) simulation experiments as well as to model and execute processes. Therefore, it is capable of handling process descriptions using the Business Process Modeling Notation (BPMN). Hence, Jadex is well suited as a foundation to realize the negotiation framework.

Implemented Components

The framework prototype provides reference implementations of the two agent types SMA & SA. Each agent type utilizes two newly provided capabilities for the handling of the service selection phase as well as for the execution phase (cp. Section ??). Furthermore, the framework prototype includes a negotiation medium that implements a Contract Net Protocol. The design of this protocol is inspired by "the way that companies organize the process of putting contracts out to tender" [?, p. 156] but it has also been used in MAS for distributed problem solving. Finally, the prototype utilizes the Jadex BPMN Engine and therefore contains reference implementations for all mandatory components.

Beside this mandatory components the prototype offers some optional extensions which enrich its functionality. One targets the chronological order of the phases of a business process. Usually, the selection phase is followed by the execution phase. This might not be appropriate for all types of business processes. Especially processes containing many tasks with a long duration require a different handling since they may face two problems. On the one hand, the selection phase may take too long since there are many tasks which require a negotiation in order to find an appropriate service provider. On the other hand, the dynamic environment of the business process leads to a situation where contract partners may (dis-)appear at any time. Therefore, it is questionable whether it is always reasonable to negotiate contract partners a long time before their service is executed. Rather, the selection of service providers should happen close to their execution in the business process. One possibility offered by the framework in order to cope with these challenges is to relax the strict separation between the selection and execution phases. Tasks of the business process can be annotated with a statement which denotes when a selection process should be initiated for the respective task. Then, the process engine knows which tasks are required in order to start the execution of the business process and which tasks can be selected later. This leads to an approach that is more appropriate for dynamic environments.

Another provided extension targets the issue of trust between contract partners. The extension consists of a trust capability for service providers, service consumers and a trust medium. The first component observes the execution of service providers and logs in order to detect whether a service request was executed successfully or not. The result is published via the event-based trust medium. In this prototype, the trust medium has the function to transmit messages between service providers and service consumers participating in a business domain that incorporates the usage of trust models. Service consumers use the transmitted logs to compute the trust of possible contract partners. Thereby, they may apply different ways to compute the trust since the received messages represent events without dependence on a particular trust model. For example, service consumers may store the logs in a history and use a simple aggregation function to compute the trust level. The modeling of the aggregation function may be inspired by the process of forgetting of the human mind and lead to an exponential function [?]. Nevertheless which evaluation function is taken, the computed level of trust may be part of the service negotiation request message that a SMA sends to the negotiation medium. Then, trust can be used as a criterion for the ranking of bids. Therefore, this approach offers the possibility to realize business markets using trust in a convenient way and it may lead to a situation where service consumers only take bids into account from providers that incorporate trust. Finally, the framework has an additional component which allows the automatic execution of simulation experiments of the implemented application. Besides logging and visualization functions this component allows an easy evaluation of the effects of different bidding strategies. Therefore, the integrated simulation and evaluation component offers valuable support for the development of new components and strategies and it has been used to conduct the simulation experiments presented in Section ??.

Configuration of the Case Study

In order to prove the proposed concept and implemented prototype, a case study has been conducted that exemplarily shows the utilization of the dynamic market-based framework. It allows developers to focus on core aspects of the application domain by relieving them from dealing with low-level aspects related to the service selection and the business process execution in a highly dynamic environment. The conducted case study consists of an acquisition process which can be seen as a sub-process of a supply-chain process of a fictive computer manufacturer. This manufacturer defines the logical-temporal order of tasks of the buying process and expects the negotiation framework to manage the execution of the process automatically -including dealing with service failures. For the ease of evaluation the buying process consists of three sequentially ordered tasks that target the acquisition of hard-disks, keyboards and RAM.

In order to enable an automatic management of the business process, the service consumer (computer manufacturer) needs to express his preferences w.r.t. conflicting objectives like fees, service duration and trust. One common approach for that is to apply a cost-effectiveness analysis [?] and as a part of it to define a utility function that values each objective. Mathematically, a utility function can be defined as U (x) = n i=1 x i • w i where w i expresses the weight of an objective x i . Such a utility function is then used to configure the SMA which acts on behalf of the computer manufacturer. Therefore, the utility function enables the SMA to rank different bids and to choose the most appropriate one.

In the same way as service consumers, service providers need to configure their proxy (SA). The case study assumes that the service providers use a static bidding strategy and will therefore disclose their behaviour to the negotiation medium. Furthermore, the existence of three different types of service providers is assumed. These three classes of agent types have specific characteristics w.r.t. following attributes: fees, duration and trust (cp. Figure ??). In turn, these characteristics influence the bids of service providers. For example, the fees characteristic is used to calculate the fees part of an SA's bid using following function: f (SA) = average fees • (0.5 + SA fees characteristic ). Assuming an average fee of e 1000 this leads to following bids regarding the fees attribute: e 900 (cheap service type), e 1000 (normal service type) and e 1200 (expensive service type). The same type of strategy is also used to compute the duration part of a bid. Whereas the semantics of the attributes fee and duration are self-explanatory the semantics of the attribute trust requires an explanation. For a service provider the trust attribute denotes the probability of a service blackout. A service blackout has two consequences. First, the service provider will not be able to participate in the bidding process (selection phase). Second, the execution of the services that the service provider offers will fail at the moment when a blackout appears (execution phase). The blackout itself is modeled using a function with an exponential distribution. Thereby, the function computes the time between two blackouts of a service provider and takes into account the trust characteristics of the service provider. The higher the trust attribute is, the lower the time is between two blackouts. Then, all the afore described attributes (fee, duration, trust) and settings (bidding strategy, blackout function) are used to configure different SAs to act on behalf of service providers.

In addition to the modelling of the SMA and the SA the case study includes some configuration aspects that are needed to evaluate the outcome of different business strategy scenarios. In spite of all possible conflicting objectives of the computer manufacturer, profit is still the most important objective that determines success (of a business process). Hence, the profit of a business process depends on the costs of its execution. These costs consist of the charges of the service providers as well as of two additional fees: First, the service consumer has to pay a fix amount of money to the negotiation medium for each requested negotiation process. Second, the service consumer may need to pay surcharge if the business process is not finished on time. This charge handles the situation where a process B depends on a process A and A is not accomplished on time. For example, this may happen if A contracts to many services providers with a low trust attribute for the execution of its tasks. These providers have a higher blackout probability and tasks will not be executed on time.

Simulation Results and Evaluation

Based on the described setting of the case study, the negotiation framework is used to evaluate the relation between the configuration of the computer manufacturer's utility function, with a specific focus on the configuration of the trust attribute, and its profit. Here, the sum of all weights of the utility function with the attributes fee, duration and trust is always 1.0 and the value of the weight for the trust attribute is altered from 0.0 to 1.0 with a step size of 0.2. ? depicts the collected results (average values) of the simulations. Since the focus is on the influence of trust, the execution of the business process is iterated many times using a trust model that incorporates an exponential function to compute the trust level of potential service partners. In this way the level of trust, i.e. with respect to service providers, can change accordingly to successful or failed service executions. More specifically, Figure ?? shows the average results computed from 80 simulation experiments per setting. Each experiment iterated the execution of the business process for a period of 60 time units. The simulation assumes that the service consumer will gain on the one hand a revenue of e 2200 for a single execution of the business process. On the other hand it has to pay between e 900 and e 1200 for the execution of the tasks to the service providers, i.e. depending on the fee characteristic, as well as e 700 for each negotiation process. The simulation results reveal a maximum of profit with a weight of 0.6 for the trust whereas weights between 0.0 and 0.2 as well as of 1.0 show the least profit. Figure ?? uses the same collected results of the simulations and depicts the average profit per business process execution.

The results of this case study show that trust has a significant impact on the profit. Taking trust into account, e.g. with a weight of 0.6, pays off with respect to settings without trust, e.g. a weight of 0.0 for the utility function, and increases the profit up to 22%. Furthermore, it can also be seen that configurations with a high trust have almost the same effect on the profit as configurations with no respectively limited trust. The results can be explained as follows. Configurations with a trust value between 0.4 and 0.8 offer the best compromise between reliability, i.e. successful service executions, and costs and have therefore the highest profit. Other configurations have an imbalance and either result in high costs for re-negotiations due to many service failures or choose most often expensive services which limits the profit. Additionally, Figure ?? reveals that the chosen strategies and configurations of the simulation settings reach about 66% of the theoretical maximum of e 600. Of course, this maximum is only achievable without service failures but it can still be seen as a benchmark to compare the outcome of different management strategies within the negotiation framework.

In conclusion, the case study has demonstrated both the applicability of the proposed negotiation framework and the corresponding prototype. The implementation offers the possibility to select and execute business processes in a market-based environment using dynamic and autonomous management components. Also, the evaluation reveals the demand for simulating different management configurations in order to find optimal settings for service consumers as well as for service providers. Therefore, knowledge about the outcome of different settings is the prerequisite for performing management actions autonomously as proposed in this negotiation framework.

Conclusion and Future Work

This work targets dynamic market-based business environments that consist of various stakeholders mostly acting in a selfish way. More specifically, this paper addresses software support for dynamic markets with distributed participants that may (dis-)appear at any time. In order to enable a reliable and adaptable selection as well as execution of services in such an environment, this work proposes a framework which incorporates a service-based system at the core, equipped with autonomous and proactive management components (agents). These components act on behalf of their clients, i.e. service consumers/providers, and are therefore also referenced as negotiation proxies. This enables a clear separation of core application tasks carried out by services and of negotiation tasks carried out by agents. Furthermore, an event-based negotiation middleware is introduced which mediates between the demands of the negotiation proxies. The applicability of the framework is proven by a prototype implementation. Furthermore, this implementation shows the capability of the framework to deal with different types of service failures while ensuring the execution of business processes. The negotiation framework is therefore able to automatically process the tasks of service selection and execution for business processes in a highly dynamic environment. In consequence, this allows for -in major parts -highly autonomous management of complex service compositions as typical for advanced flexible and dynamic business processes.

Future work shall, on the one hand, strive towards providing an autonomic and customizable strategy adaptation component for service providers. The aim of this strategy adaptation component is to enhance the success of service providers, i.e. to increase the profit. Therefore, the component observes the outcome of negotiation processes and tries to improve the biding strategy if it is not satisfying. For example: if an SA has a high rate of getting contracts with a certain price the adaptation component may increase the price. Contrary to that, the component may decrease the price if the SA does not close many contracts with service consumers. On the other hand, it is envisioned to provide additional negotiation media implementations in order to take advantage of the potential of the negotiation framework to execute media in parallel. Then, the strategy adaptation component may also manage the aspect which negotiation media to participate in for the SA autonomously.

Fig. 1 .

 1 Fig. 1. Architecture of the Negotiation Framework and the utilized paradigms

Fig. 2 .

 2 Fig. 2. Exemplary communication pattern

Fig. 3 .

 3 Fig. 3. Characteristics for different agent types

Fig. 4 .

 4 Fig. 4. Profit in dependency of the weight of the trust characteristic

Acknowledgments. The research leading to these results has received funding from Deutsche Forschungsgemeinschaft and from the European Community's Seventh Framework Programme under grant agreement 215483 (S-Cube).


Aaron Harwood

Spyros Voulgaris
email: spyros@cs.vu.nl

Van Maarten

Steen
email: steen@cs.vu.nl

Maarten Van Steen

Cooperative Repair of Wireless Broadcasts

Keywords: Peer-to-Peer, Cooperative Repair, Video Broadcasting

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Background

Wireless broadcasting systems, such as Digital Video Broadcasting [START_REF] Reimers | DVB-the family of international standards for digital video broadcasting[END_REF] (DVB), are subject to interference from the environment, which can result in loss of information and an associated loss of quality for the user. Forward error correction (FEC) and interleaving based schemes involve high overhead on the essentially limited DVB bandwidth. In contrast, a cooperative peer-to-peer repair (CPR) mechanism relies on a primary channel being repaired using a CPR protocol on a secondary channel. We consider the primary channel to be a video stream and we have chosen the ISO/IEC 13818-1 Int. Std. as a case study, which is the standard used for DVB. We propose to use UDP over the Internet as the secondary channel. The ISO/IEC 13818-1 standard describes how to packetize streaming data, such as video and audio streams, for transmission and/or storage. In this case, where the transmission system is unreliable, the standard prescribes the use of Transport Stream (TS) packets of 188 bytes in length. The video and audio MPEG streams (frames) are first encapsulated into a stream of Packetized Elementary Stream (PES) packets, and each PES packet is, in turn, encapsulated into multiple TS packets.

A typical DVB transmitter may be rated at 50kW and supply "adequate" service at up to an 80km radius. In Australia there are over 1300 DVB transmitters totalling over 55.6MW per hour of transmission; or 285k metric tons of CO 2 per year. The use of CPR may help to reduce the total number of transmitters and/or the required power, thereby helping the environment.

Design Decisions and Challenges

Scope of repairing

The cornerstone decision in our work has been the selection of the level at which repair should be applied. Specifically, there are three possibilities. Repairing frames, repairing PES packets, or repairing TS packets. Due to diverse pros and cons, no option constitutes a win-win tradeoff.

We decided to repair TS packets. While it is tempting to consider working at the PES or frame level because these levels provide more semantic information, there are some drawbacks that we identified: less total reliable information at the higher levels, semantic information tends to be optional, TS packets conveniently fit into a UDP packet, and more processing is required at the higher levels. Furthermore, Fig. 1 (a) and (b) shows the distribution of frame and PES packet sizes from a DVB video sample (video using MPEG2 704x576 which prescales to 1024x576). Even at this relatively low resolution (HD television usually allows up to 1920x1080), frame sizes exceed a single UDP packet payload. The variability of frame/PES sizes and inability to fit within a single UDP packet in general would add further complexity to our overall system that we mitigate by working at the TS level.

On the down side, TS packets do not contain unique identifiers, which would be very beneficial. The lack of unique identifiers at the TS level can be overcome by the use of some convenient, mandatory, semantic information contained at the TS level (explained next).

Transport Stream Packets

A DVB receiver, when tuned and locked to a carrier frequency, produces a stream of TS packets -called the raw TS stream. Among other things, every TS packet in the raw stream contains the following key fields: a 13 bit Program Identifier (P ID) that maps the TS packet to an elementary stream, such as a video or audio stream for a given program; a 4 bit Continuity Counter (CC) that is incremented by 1 modulo 16 for each subsequent TS packet in the elementary stream (certain flagged conditions may arise where the CC is not incremented); and a 1 bit Transport Error Indicator (T EI) that is set true by the receiver if the TS packet is erroneous.

The fields listed above are insufficient to synchronize two streams for the sake of cooperative repair. There is no uniquely identifying information in each TS packet, and indeed duplicate TS packets may arise in the stream. However the standard allows a TS packet to contain additional information in an optional Adaption Field, and this optional information contains a 33 bit Program Clock Reference (PCR). The standard requires this optional information to appear at least every 100 milliseconds. PCR values are not sequential. They are, however, monotonously increasing, therefore unique within a stream. The presence of the PCR provides semi-regular, unique stamps on selected TS packets. Thus, we make use of the P CR to synchronize two peers so that cooperative repair can take place.

The Cooperative Repair Algorithm

A repair algorithm relies on two main components: a mechanism to detect missing information, and a naming scheme to uniquely identify this information in requests to external sources.

Detecting Missing Packets

We use the CC field, described in Section 2.2, to detect missing TS packets. This has a clear limitation, as any sequence of k consecutive missing packets maps to a CC gap of k modulo 16. For instance, it is impossible to distinguish between missing a single packet, or 17, 33, and generally 16i+1 consecutive packets. Even worse, missing sequences of exactly a multiple of 16 packets will go undetected.

To assess the frequencies at which different gaps appear in a realistic setting, we analyzed a number of DVB streams recorded at locations with diverse reception qualities. Fig. 1(c) shows the count of CC gaps for three recordings of the same duration (circa 1 minute each), yet of very different viewing qualities: infrequent errors, frequent errors and unviewable. The respective snapshots illustrate characteristically the quality of each stream. As expected, barely tuned streams experience the highest packet loss, and the most CC gaps. Still, the observations of gaps with length 1 (1, 17, 33, etc., consecutive missed packets) are two orders of magnitude more than observations of gaps of length 15 (15, 31, 47 missed packets, etc.). This strongly suggests an inadequacy in the limited length of 4 bits used for the CC to detect missing packets. That, however, occurs only for a negligible fraction of the total losses. Our experiments confirm this observation.

Naming Scheme

In order to be able to name specific units for repair, we introduce the notion of blocks. A block is a sequence of TS packets, consisting of all packets between two consecutive PCRs. The starting and ending PCR values of a block are called its boundaries, and uniquely identify this block across all nodes. Packets within a block are identified relatively to the starting PCR boundary, based on the CC.

When a node receives a PCR packet, it marks the beginning of a new block. By observing the CC in subsequent TS packets, it keeps track of which packets it received, and which it missed. In doing so, it follows an optimistic approach: a CC gap of k ∈ [START_REF] Li | Bopper: Wireless video broadcasting with peer-to-peer error recovery[END_REF]15] is interpreted as a loss of exactly k packets, rather than 16i + k. A zero gap is interpreted as no lost packet, rather than as 16i lost packets. With high probability, the assessment of what has been received is accurate, unless 16 or more consecutive packets were lost at some point. The next PCR marks the end of this block and the beginning of a new one.

The record of which TS packets were received and which are missing, constitutes the block's map. In our system it is represented as a bitstring; 1 stands for received and 0 for missing packet. Note that missing PCRs leads to concatenated blocks that may later be repaired and split to smaller blocks.

Regular Operation

Upon completion of a block the node stores that block in memory, indexed by its boundaries. Then the node checks whether all packets -are believed to -have been received. If not, it invokes a Pull operation on a random other node that is currently tuned to the same TV channel, requesting the missing TS packets. It sends the block boundaries and the block map.

A node receiving a Pull request, looks up its memory for a block with the specified boundaries. It may have it complete, or it may be missing some TS packets too. In either case, it performs a bitwise operation on the two block maps to figure out which of the requested packets it has. It then sends a Push response to the requester, piggybacking zero or more of the requested packets.

Upon receiving a Push response, a node adds the received TS packets to the block in question, updates the block's map, and checks if the block is now complete. If it is still missing packets, it issues a new Pull request on another random node. This is repeated until either the block is complete, or a time threshold called ViewerTimeout has been reached. At that point, the TS packets of the block are handed to the higher layers for decoding and viewing. A second timer, the PullTimeout, is associated with each Pull request. If no response is received for that time, a new Pull request is sent to another random node.

Special Cases and Supporting Mechanisms

A number of special cases may arise, which makes the algorithm nontrivial. A node receiving a request may realize that its own copy of the block in question has more or fewer TS packets than the map received. A node receiving a Pull request may be unable to spot the requested block in its local memory. A node receiving a Pull request may figure out that it has both starting and ending PCR values, but they do not belong to a single block. We have solutions to these special cases that cure most (although not all) error scenarios, which we omit for space considerations.

Like many epidemic protocols, the cooperative repair algorithm relies on communication between peers selected uniformly at random. To that end, we rely on the family of Peer Sampling Service protocols, and specifically Cyclon [START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF], which provides each node with a regularly refreshed list of links to random other peers, in a fully decentralized manner and at negligible bandwidth cost. We omit discussion of this aspect due to space consideration.

Evaluation

Our basic results are obtained through simulations using PeerSim, based on a uniform error model. All nodes experience identical constant error probability for each TS packet. Fig. 2 shows, as a function of the TS packet error rate, the percentage of blocks that were received correctly straight away through broadcasting (darkest), blocks that were initially incomplete but were fully repaired (dark), blocks that were still incomplete when passed on to the higher layer -probably partially repaired (light), and blocks which the node never became aware of, due to some lost PCR (lightest). The four cases represent a Viewer-Timeout of 500ms, 1000ms, 2000ms, and 5000ms, while the PullTimeout was fixed to 600ms for all of them. Clearly, as the ViewerTimeout increases, the ability to know and repair more blocks increases. In fact, ViewerTimeout has a dominant effect in this respect, more so than PullTimeout. E.g., for a mere delay of 5sec, users that would otherwise hardly be able to watch a program, can now enjoy a crystal clear stream. The value of PullTimeout was chosen to be 600ms in this example because this value keeps the upload bandwidth of the nodes below about 1Mbps, in line with residential ADSL2+ limits.

Conclusion and Related Work

The work in [START_REF] Weigle | Peer-topeer error recovery for hybrid satellite-terrestrial networks[END_REF] is closely related to ours -the authors repair satellite broadcasts; however few details are provided in the paper. In [START_REF] Sanigepalli | Using p2p networks for error recovery in mbms applications[END_REF][START_REF] Li | Bopper: Wireless video broadcasting with peer-to-peer error recovery[END_REF][START_REF] Raza | Cooperative peer-to-peer repair for wireless multimedia broadcast[END_REF], some other P2P

  Fig. 1. a-b: Size distribution of frames and PES packets. c-f: CC gap distribution for three sample streams.

approaches use a secondary channel such as 802.11 or Bluetooth, with focus on mobile devices. We omit a detailed description of related work for space considerations. Our results thus far, provide significant motivation for us to continue research in this direction.