Antoine Beugnard

Ali Hassan

A Calculus for a New Component Model in Highly Distributed Environments

Keywords: Software Components, Formal Models, Component Assembly, Automatic Design Checker, Mobile and Pervasive Computing

published or not. The documents may come

A calculus for a new component model in highly distributed environements

Introduction

During the last years new distributed platforms have emerged, often qualified as highly distributed environments (HDE). HDEs still include powerful and robust machines but they are rather composed of resource-constrained and mobile devices such as laptops, personal digital assistants (or PDAs), smartphones, GPS devices, sensors, etc [START_REF] Hoareau | Middleware support for the deployment of ubiquitous software components[END_REF]. Moreover, these devices communicate using a variety of dependable and undependable fixed and wireless networks.

This fundamental change in the deployment environment was not accompanied by a theoretical software model that provides deep understanding and systematic solutions to build compatible software systems [START_REF] Cardelli | Abstractions for mobile computation, Secure Internet Programming, Security Issues for Mobile and Distributed Objects[END_REF].

As Malek et al. [START_REF] Malek | An architecture-driven software mobility framework[END_REF] have noticed "transparency (i.e. hiding distribution, location, and interaction of distributed objects) is considered a fundamental concept of engineering distributed software systems, as it allows for the management of complexity associated with the development of such systems". This is usually achieved through the utilization of a middleware layer that has as a main function (among others) to make remote calls appear as local calls. That is correct for stable distributed systems, however, this same concept, distribution transparency, has been shown to suffer from major shortcomings when applied extensively in HDEs [START_REF] Malek | An architecture-driven software mobility framework[END_REF].

That leaves us in the following situation: there is excessive and increasing need to build complex mobile and pervasive systems for entertainment and professional uses. And at the same time, the fundamental engineering techniques available are inherited from stable distributed environments, and suffer from several drawbacks and weaknesses when utilized in these new environments. The only available answer currently is applying ad-hoc techniques to overcome these drawbacks and weaknesses.

This work is a direct response to the above mentioned challenge. First we propose a paradigm shift from remote communication transparency to localization being the first class concern. In other words, we no more hide or abstract location, on the contrary, we acknowledge all aspects related to location including the specification of devices, the networking paradigms they use, the different network specifications available, security features, and all related characteristics of the deployment environment. We discuss the limitations of current component models, the paradigm shift needed, and selected set of related work in section 2.

To achieve the above mentioned objective, we propose in section 3 a novel component model called cloud component (CC). This model includes the expected deployment environment in its definition, i.e. we raise the importance of deployment environment to be equal to the functionality required from the component. The other important feature of this novel model is that it is fundamentally distributed. A single CC is usually distributed over many dis-tant hosts, the specification of these hosts are considered and fundamentally acknowledged during the development process of this CC, and all aspects related to communication, coordination, and quality of service are migrated to be internal to the border of the CC.

A software component can be thought of as unit of assembly3 . This is true for all component models including cloud component model. In this paper we propose a new approach to assemble CCs using systematic methodology that maintains the properties of CC model. CC assembly is a tool to build large systems using CCs as building blocks. Moreover, we present a technique to automatically check the validity of this assembly. Cloud component assembly and checking are presented in section 4.

The cloud component model and CC assembly are presented informally and formally with a mathematical notation. The informal notation allows for faster comprehension of the general concepts. While the formal notation opens the door for a wide range of theoretical topics including component type inference, subtypes, etc, and provides a precise language to describe details. In addition, formal methods allow the designer to produce machine readable designs where automated tools can verify specific properties at design time, which in turn, increases the level of confidence in the correctness of design. We conclude with a brief summary of our proposals and some future work.

Highly Distributed Environments -HDE

The emergence of mobile devices such as portable notebook computers, tablet computers, PDAs, and mobile phones, and the advent of various wireless networking solutions make computation possible anywhere [START_REF] Mikic-Rakic | Software architectural support for disconnected operation in highly distributed environments[END_REF][START_REF] Mikic-Rakic | Architecture-level support for software component deployment in resource constrained environments[END_REF][START_REF] Mikic-Rakic | Software architectural support for disconnected operation in distributed environments[END_REF]. In this paper, we define highly distributed environments as a target platform of our work. These networks include distributed systems with laptops and wireless networks, mobile systems, and pervasive systems. These networks violate many familiar assumptions about the behavior of distributed environments, and demand new techniques to build compatible and optimized software [START_REF] Cardelli | Abstractions for mobile computation, Secure Internet Programming, Security Issues for Mobile and Distributed Objects[END_REF], especially at the architectural level of the software development process.

The characteristics that the HDE infrastructure imposes include [START_REF] Mikic-Rakic | Software architectural support for disconnected operation in distributed environments[END_REF][START_REF] Cardelli | Abstractions for mobile computation, Secure Internet Programming, Security Issues for Mobile and Distributed Objects[END_REF][START_REF] France | Model-driven development of complex software: A research roadmap[END_REF][START_REF] Hoareau | Composants ubiquitaires pour reseaux dynamiques[END_REF]]: 1-Mobility of hardware, data, and code. 2-Heterogeneity of software and devices. 3-Volatility of hardware and software components. 4-Small devices, highly constrained resources, dynamic resources. 5-Connectivity failure are not rare; disconnected operations. 6-High bandwidth and low latency are no more available in continuous and dependable manner. 7-Software components communicate using a variety of interaction paradigms (e.g.,

SOAP messaging, media streaming).

In spite of the above challenges that permeate the entire traditional software development life cycle, software in these systems are expected to obey the following constraints [START_REF] France | Model-driven development of complex software: A research roadmap[END_REF][START_REF] Mikic-Rakic | Software architectural support for disconnected operation in highly distributed environments[END_REF][START_REF] Hoareau | Composants ubiquitaires pour reseaux dynamiques[END_REF][START_REF] Malek | An architecture-driven software mobility framework[END_REF]]: 1-Customized implementation: the implemented software need to be efficient, customized, and can be deployed on resource constrained devices. 2-Correctly respond to runtime changes in the environment. 3-Preserve dependability and quality of service in this highly dynamic environment.

Current component models limitations

The concept of software components has been widely adopted because of its attractive and powerful encapsulation attributes [START_REF] Crnkovic | A classification framework for software component models[END_REF][START_REF] Lau | Software component models, Software Engineering[END_REF]. Lau et al. noted: "Encapsulation has the potential to counter complexity" [START_REF] Lau | Software component models, Software Engineering[END_REF].

After analyzing several component technologies such as CCM and EJB for industry and Fractal and SOFA for academia, we found that they follow a common paradigm. These component models rely on strong assumptions, and they emulate local call on top of distributed networks, and finally they consider any deviation from their implicit or explicit assumption as exceptions. All of these points are considered limitations with regards to HDEs. For more detailed discussion on these limitations, please refer to appendix A.

Paradigm shift with cloud components

To overcome these limitations, we propose a new component model called Cloud Component (CC) which is a novel extension to the 'Medium' concept proposed by Beugnard et al [START_REF] Cariou | An architecture and a process for implementing distributed collaborations[END_REF][START_REF] Matougui | Two ways of implementing software connections among distributed components[END_REF]. CC encompasses all features provided by currently existing component models and, moreover, is especially designed to be used in the above mentioned complex environments. CC model provides the capability of the instantiation of its interface(s) on each host that potentially needs to access the service provided by this CC [START_REF] Cariou | An architecture and a process for implementing distributed collaborations[END_REF]. This will make the service access explicitly local. In other words, if we want our component to be accessed at some host, we need to deploy an interface instance at that host. It is evident that this instance will have some sort of remote communication with other entities inside the component, but this is internal with respect to the component border as explained in figure 1.

Migrating the communication to be internal inside the CC border has significant contribution to the overall architecture of distributed applications. In figure 1 (left) the server provides a service S which is accessible in sites A, B, and C. If the resources at site A are not enough, or the connectivity at site C is not adequate, or simply the configuration of site B is not compatible, the service S of component Com is not accessible, i.e. useless.

With CC, figure 1 (right), this is not the case. Cloud component comCC has its interface S instantiated on sites A, B, and C. Using it is simply a local access of a locally available service. S at the three sites provides the same (or similar) functionality, however, it is possible (and highly probable in this case) to be implemented using completely different approaches. For example, in site A special arrangements should be carried out to handle the extremely limited resources and the mobile networking. In site C, constraints of site A are relaxed, as result, different implementation technologies are utilized. The same argument holds for site B, where there are stable fixed networking and power supply, and rather advanced resources. At this site, there is no need for the implementation to be prepared to handle complexities that arise in sites such as A or C.

In other words, we allow several implementations of the same functionality to exist side by side. The variation of implementation is driven by the variation of deployment environment, i.e. the characteristics of the hosts where interfaces will be instantiated, and the characteristics of connectivity available for each host. For the interface S to be instantiated on site A, there need to be implementation variant that is compatible with the characteristics of site A. This compatibility is checked statically before the instantiation of the system and each of its roles but is out of the scope of this article.

Related Work

Didier Hoarau et al. deal with the challenges of HDEs [START_REF] Hoareau | Composants ubiquitaires pour reseaux dynamiques[END_REF][START_REF] Hoareau | Distribution of a hierarchical component in a non-connected environment[END_REF][START_REF] Hoareau | Middleware support for the deployment of ubiquitous software components[END_REF]. However, their solution has different scope from ours. First, they expand the already existing component model Fractal. Second, they only model and handle the disconnection of network connection among all characteristics of HDE.

Marija Mikic-Rakic provides a sophisticated response to one challenge proposed by HDEs, which is the discontinuity of services where the system needs to continue functioning in the near absence of the network [START_REF] Mikic-Rakic | Software architectural support for disconnected operation in distributed environments[END_REF]. This work proposes a redeployment solution as part of a middleware called Prism-MW. work and tools to support the complete software engineering life-cycle for the development of HDE applications [START_REF] Malek | An architecture-driven software mobility framework[END_REF]. While their tools help overcome the challenges posed by HDEs, these challenges become natural details in our novel component model, where they can be handled systematically.

Cloud Component Model

We chose the name Cloud Component since our component model encompasses physical borders and hence hides the technologies, implementation variants, and architecture choices used to conform to the physical topology of the underneath infrastructure. Our approach in presenting cloud component model is based on two different notations: the informal notation and the mathematical/formal notation. The informal notation is easier to understand and is highly dependent on figures, while the formal notation is more compact, more precise, and less ambiguous. The formal notation allows us to communicate precise details easier, and allows us to easily present statements and proofs.

The definition of cloud component

Definitions 1 to 5 collectively form the definition of cloud component.

Definition 1: Roles

Let C 1 be a cloud component with single interface S as illustrated in figure 2 (left). S is defined through an Interface Definition Language -IDL. We assume S defines the signature of provided and required functions of C 1 . The contract of this interface could be more sophisticated, but we restrict its definition for the sake of simplicity.

A cloud component can have several interfaces : P, Q, R, etc. We call these interfaces 'roles' because their identification (set of functions they gather) is guided by the way the component can be used through this interface. The cloud component in figure 2 (middle) has two roles: S and R.

Definition 2: Cardinality

Each cloud component can have several roles. In addition, the role is allowed to have several instances, i.e., several carbon copies of the same IDL. The total number of instances of a role in a running version of the component is called: the cardinality of the role. In figure 2 (middle) the role S has cardinality one and the role R has cardinality two. Combined with location property (explained later), this approach will encapsulate the communication and all its details and semantics inside the component.

Definition 3: Connection

Once the component border is defined, the connection rules can be defined. In order to suppress ambiguity of 1-to-many or many-to-many connections identified in [START_REF] Matougui | Two ways of implementing software connections among distributed components[END_REF] we allow a role to connect to only one role of another cloud component in a one-to-one connection.

This rule applies at the instance level, when cloud components are actually implemented. In order to allow a 1-to-many or many-to-many connectivity, we use 'role cardinality'.

Definition 4: Multiplicity

Cardinality is a number k ∈ N . We can allow more complex structure by not specifying k (at some point of the design). Instead, we put constraints on k called multiplicity. For example a role R can have multiplicity [1..5], [1.. * ], or simply * . At this level of definition, we are not bounded by decidability features but only consider constraints definition.

Definition 5: Location

Each role is assigned a location to run on. The location in the most basic form is a computing host/device. In figure 2 (middle) a cloud component has two different roles, S and R. Role S has one instance that is located at the host Server. The role R has two instances that are located at the host Client. Figure 2 (right) presents a cloud component that has two different roles, S and R. Role S has one instance that is located at the host Server. The role R has two instances one of them is located at the host Client 1 and the other is located at host Client 2.

One should not mix our definition of location with the geographic location. Our model does not define or recognize geographic location, rather, we acknowledge location as a computing/electronic device that might be mobile or not. It is fundamental to assert that location is integral part to the CC definition, in other words, without location specification the cloud component definition will not be complete. Finally, and at design and implementation stages, the collection of all locations are called 'the expected deployment environment.'

Formal definition of cloud component

A single cloud component is defined using the following four-tuple: (i) A finite set of roles Λ. (ii) A finite set of multiplicities for these roles µ. (iii) A set of possible deployment environments L. Each L is either a finite set of hosts H, or a finite set of host types T . (iv) A function Z that maps roles to location types or hosts.

Ω ≡ (Λ, µ, L, Z)
The following formally defines the cloud component com in figure 2 (right): Ωcom ≡ (Λ, µ, L, Z) where:

Λ = {ΛS, ΛR} µ = {(ΛS, 1), (ΛR, 2)} L = {{T Server, T Client 1, T Client 2}} Z : ΛS ↓ T Server, ΛR ↓ T Client 1, ΛR ↓ T Client 2
The formal definition is read as follows: the CC com is defined using its four-tuple. The set of roles contains two roles: role type S and role type R. Role type S has multiplicity 1, and role type R has multiplicity 2. The set of expected deployment environments has only one set, which contains three host types: host type Server, host type Client 1 , and host type Client 2 . Finally Z can be read as: The role S is localized at host of type Server. Role R has two instances, one is localized at host of type Client 1 and the other is localized at a host of type Client 2 . Symbols used to construct the formal notation are summarized in table B.1 in appendix B.

Formal definition of cloud component based system

Generally, a software component can be thought of as 'unit of composition'. This is true for all component models including cloud component model. In CC model, roles are the only access points of the component. A role can serve as a connection port where component C 1 connects to other component C 2 as in figure 3 (left). We choose to assembly components in specific architecture to achieve our desired system specifications. As result we have σ the set of assembly rules that includes the dependency rules between CCs, and all role connections. Cloud component assembly will be discussed in detail in section 4. A system built using cloud components consists of:

S

(i) A finite set of cloud components Ω.

(ii) A finite set of multiplicities for these cloud components M . (iii) A set of assembly rules σ. (iv) A set of possible deployment environments L.

As result, the system type is fully defined using the "four-tuple" notation:

S ≡ (Ω, M , σ, L)
Finally we define the system instance Ŝ. Let S be a CC based system that is defined as above. Ŝ is an instance of that system and is defined using the following five-tuple:

(i) The system type S that we want to instantiate.

(ii) The function τ that takes a cloud component as a parameter and returns the number of instances of it. (iii) The function K that takes a role as a parameter and returns its cardinality, i.e. number of instances. (iv) The deployment environment L which is a finite set of hosts H. (v) The function Z that maps Γ4 to L.

Ŝ ≡ (S, τ, K, L, Z)

First constraint -one-to-one

An instance of role S can connect to one instance only of any other role at any time instance. We raised the importance of this constraint from being a recommended design choice to be a fundamental model constraint for several reasons. One of these reasons is to remove ambiguities in the connections. Another and important reason is to control the design precisely, and to be able using this control to ensure the delivery of the expected non-functional properties. As an example, let us take the role S in figure C.1 from the banking example in appendix C. And suppose S is hosted by some regular desktop. If S is expected to have 10 connections, i.e. 10 clients that want to use the video service, is completely different from S is expected to have 10 6 connections at the same time. The difference exists in the design, implementation, and the deployment host (probably a normal desktop will not be able to serve 10 6 connections). This difference should be recognized from the very early stages in the design, and this is done in CC model by setting the multiplicity (or cardinality) constraints over roles.

Second constraint -local connections only

Two instances of two roles can connect to each other only if both of them are instantiated at the same host as in figure 3 (right). If they are instantiated at different hosts they simply can not connect to each other. This is a direct result of the paradigm shift discussed in section 2.2. It is fundamental in our model to migrate all remote communications to be internal to the border of the CC itself. This migration means that these remote communications are designed and implemented using the special software development process 5of the CC model, and more important, passed all checks necessary to ensure the quality of service expected.

Third constraint -Connection multiplicity

When there is a connection between two roles, that does not mean that all instances of these two roles should connect to each other. Figure 4 (left) is an update of figure 3 (left) by adding multiplicities to roles S and Q. To understand the connection in this figure we need to see the uncertainty that exist at this phase of design. During runtime, there might be one instance of S and five instance of Q, or nine instances of S and two instance of Q. So how many connections we have at runtime between S and Q? To answer this question we need to remember that the final responsibility of the design is held by the designer himself, we only provide an advanced model and accompanied tools and checkers. To facilitate the assembly design we add the connection multiplicity, which is a range [min..max], where min is the minimum number of connections that must exist at runtime, and max is the maximum number of connections that might exist at runtime, as in figure 4 (right). Usually these numbers reflect the need of either of the roles, or both. For example if I have a role W that connects an ATM machine (CC AT M ) to the bank system (role S of CC Agent), I can expect W to need only one connection at runtime, i.e.

Formal definition of cloud component assembly

CC assembly is based on the connection operator ⊗, which is a binary operator that takes two CC roles and returns true if the designer explicitly listed those two roles to be connected (this is done in σ as described later), otherwise it returns false. The set of assembly rules is called σ and is defined using the following context free grammar:

E → { I } I → IJ, | IJ | ǫ J → (Ωvar.Λvar ⊗ Ωvar.Λvar, int, int)
Where var and int are terminals such that: var represents any string of characters and int represents a positive integer. This grammar will recognize the following syntax: σ = {(Ωname.Λname ⊗ Ωname.Λname, min, max), (Ωname.Λname ⊗ Ωname.Λname, min, max), ..., (Ωname.Λname⊗Ωname.Λname, min, max)}.

The following shows the assembly in figure 4 (right) using formal notation: σ = {(ΩComA.ΛS ⊗ ΩComB.ΛQ, 2, 4)} In general we can write: σ = {(ΩComA.ΛS ⊗ ΩComB.ΛQ, m, n)} This connection has the following semantics: at least m instance of S connect to m instance of Q, and at most n instance of S connect to n instance of Q. This is correct for one and only one instance of each cloud component. .m] in figure 5. We start with level one, and depending on the value of i we move to level two where we inspect the value of m. The label(s) on the arrows leading to the decision level indicate the decisions made on the upper two levels.

Remark

The connection operator ⊗ is symmetric: ΩComA.ΛS ⊗ ΩComB.ΛQ ⇐⇒ ΩComB.ΛQ ⊗ ΩComA.ΛS The above statement is read as follows: role S is connected to role Q if and only if role Q is connected to role S. .m] are related as in figure 6. Cases presented in figure 6 can be reduced to the following four cases:

Assembly checking algorithm

(i) i ≤ e & m ≤ e ⇒ Valid (ii) i ≤ e & e ≤ m ⇒ Warning (iii) e < i ≤ f ⇒ Warning (iv) f < i ⇒ Error
The same argument holds for the two ranges [g..h] and [i..m] in figure 5.

Depending on the numbers, we have three cases:

(i) Valid: in this case we do not have a chance of connection problems at runtime if the instantiation of roles respected the design. (ii) Warning: in this case the designer need to be careful because even if the instantiation respected the minimum requirements, we might face invalid situations. For example, if e < i ≤ f , and at runtime we have only e instances of S (legal situation), and we need i connections to S. This situation will produce runtime error. As result, before asking for i connections to S, the application must instantiate at least i instances of S (possible because i ≤ f ). (iii) Error: here we do not have enough instances of the role to satisfy the minimum connections need.

A role (specifically, role type) is not limited to be connected to only one other role, rather, this number is unlimited. At runtime, this role is expected to have several instances, where each instance is connected to one other role. This is assembly normal form B and presented in figure 7 (left). To check this assembly we need to get it back to normal form A in figure 5. We call this conversion from the form normal form B to normal form A: assembly reduction -phase one. For role S in figure 7 this is accomplished as in figure 7 (right).

Formally: Let σ = {(S ⊗ Q 1 , a 1 , b 1 ), (S ⊗ Q 2 , a 2 , b 2 ), • • • , (S ⊗ Q n , a n , b 2 )}.
After assembly reduction -phase one, we get:

σ = {(S, Q, a, b)} such that: a = n i=1 a i , b = n i=1 b i ,
and Q is virtual role for checking only. This is for role S only and must be done for all other roles that have connections to more than one role.

Figure 8 presents CC assembly normal form C. The connection here has the following semantics: at least i instance of S(resp.Q) connect to i instance of Q(resp.S), and at most m instance of S(resp.Q) connect to m instance of Q(resp.S). This is correct for one and only one instance of each cloud component. More over, CCs ComA and ComB have multiplicities [a..b] and [c..d] respectively.

Because of the multiplicities of the CCs, we are unable to use the checking procedure used for normal form A directly on normal form C. To be able to check this assembly, we will follow several assembly reductions starting The objective of this phase is to end up with the connection multiplicity [x..y] using the rule: 'for x we choose the max of the mins, and for y we choose the max of the maxs'. Formally: x = max{ia, ic}, and y = max{mb, md}. By the end of this phase we will get back to normal form A that can be checked directly as in figure 9.

The algorithm in figure 10 is fully implemented using C programming language, and used to check the banking system example in appendix C.

Conclusion and Future Work

Highly distributed environments pose a number of challenges for software development process. In this paper we propose a novel component model, the cloud component, that converts the above mentioned challenges into regular and systematic software development details and tasks. Moreover, we proposed a formal notation to describes our component model. This formal notation is more compact, more precise, and less ambiguous. The formal notation allows us to communicate precise details easier, and allows us to easily present statements and proofs. Finally, we developed a formal model to build large systems using CCs as building blocks, and developed an algorithm to check the validity of the assembly, and implemented an automatic assembly checker based on that algorithm.

Several remaining challenges form the scope of our future work. The most important challenge is related to the deployment environment modeling, and designing an effective algorithm to be the basis of an automatic deployment checker that checks the compatibility between cloud components and the actual environment where we are trying to deploy. We have investigated techniques to accomplish this task, these techniques include Ontology and F-Logic (Object Logic) for modeling. Moreover, we investigated several algorithms that depend on reasoning based queries for automatic deployment checker.

A Current component models limitations

After analyzing several component technologies, we found that they follow a common paradigm. These component models rely on strong assumptions, and they emulate local call on top of distributed networks, and finally they consider any deviation from their implicit or explicit assumption as exceptions. All of these points are considered limitations with regards to HDEs as we explain in the following:

Rely on strong assumption A common way to distribute a componentbased application consists of installing each component instance on a host; the distribution then refers to the fact that a component can make distant invocations to the services implemented by another component [START_REF] Hoareau | Distribution of a hierarchical component in a non-connected environment[END_REF][START_REF] Matougui | Two ways of implementing software connections among distributed components[END_REF]. This type of architecture usually relies on rather strong assumptions [START_REF] Hoareau | Distribution of a hierarchical component in a non-connected environment[END_REF]: (i) The stability of the execution platforms (the component server is highly available -usually with backup recovery system) (ii) All hosts have sufficient resources which include processing power, memory, and power supply. (iii) The connectivity is reliable and has good characteristics (low latency, enough bandwidth, stable, no disconnections, etc.). In general, an application designed using this architecture can not be installed and executed on deployment environments with hosts that are potentially volatile and limited in resources, especially when disconnected network operation and weak consistency of the characteristics of the connectivity are possible or frequent, which is the case in HDEs [START_REF] Hoareau | Distribution of a hierarchical component in a non-connected environment[END_REF][START_REF] Hoareau | Middleware support for the deployment of ubiquitous software components[END_REF].

Emulation The distributed component models mentioned above share a common goal: making aspects related to the distribution transparent to both the application programmer and the users. They hide distribution by making remote call appears to the caller as local call, but to some ad-hoc and limited exceptions (see next point). However, by hiding distribution, these mechanisms do not incorporate aspects related to disconnections, mobility, and all other complexities mentioned in the previous section [START_REF] Hourdin | SLCA, composite services for ubiquitous computing[END_REF]. In general, distributed applications are designed using the same techniques as a centralized application [START_REF] Hoareau | Composants ubiquitaires pour reseaux dynamiques[END_REF][START_REF] Tibermacine | Enforcing architecture and deployment constraints of distributed component-based software[END_REF].

Exceptions Most common component technologies were not originally designed for HDE. Therefore, they consider any deviation from the strong assumptions mentioned above such as inaccessibility of a machine or the unavailability of certain resources as exceptions. The treatment of the various changes that may occur within the network is usually done by adding code to adapt to these new events. This code will increase the complexity of applications [START_REF] Hoareau | Composants ubiquitaires pour reseaux dynamiques[END_REF][START_REF] Tibermacine | Enforcing architecture and deployment constraints of distributed component-based software[END_REF] with specific and ad-hoc extensions and poor methodological guidelines.

Typical HDE applications are highly distributed, decentralized, and mobile. Therefore, they are highly dependent on the underlying network [START_REF] Mikic-Rakic | Software architectural support for disconnected operation in highly distributed environments[END_REF][START_REF] Mikic-Rakic | Architecture-level support for software component deployment in resource constrained environments[END_REF][START_REF] Mikic-Rakic | Software architectural support for disconnected operation in distributed environments[END_REF]. We believe that the successful paradigm in stable distributed networks 'remote communication' or 'distribution transparency' is no more dependable in highly distributed environments HDE. There is fundamental need to move from hiding the underlying network into acknowledging all its aspects and details. It is possible to achieve that by introducing the concept 'location'. We call this a paradigm shift from 'distribution transparency' to 'localization'.

By location we mean the physical actual computing device where software runs, and that ranges from simple mobile phone to large super computing machine. Modeling location at early design stages will better reflect communication, mobility, and heterogeneity of devices.

Instead of delaying the distribution of software components over the computing devices until the deployment phase, we propose integrating this concept to the very early stages of software development process, especially architecture. Mapping software components to the deployment environment is called 'localization'. Several models and techniques are proposed in this work to facilitate this approach. The localization of components is revised and refined during the development process until we reach the final deployment plan of the whole application.

It is clear that when we attach location property to a software component, we -either explicitly or implicitly -attach information related to the resources available in this location, the communication paradigms available, the power supply type, and the security features, etc. This information will help (guide) the design and implementation of the system itself.

Acknowledging the properties of the target infrastructure at the very early stages of software development process will help us develop customized software for that infrastructure. This software will utilize the resources to the maximum or near maximum, and at the same time will tolerate the weaknesses and treat the previously considered exceptions as survivable expected events.

B Symbols

Cloud Components and CC based systems can be described using formal/mathematical notation. In this appendix we present the elements and symbols of this notation/language in table B.1.

C Example -Banking System

In this appendix we presnt a simple banking system to explain the algoritm proposed in section 4.

Fig. 1 .

 1 Fig. 1. Left: Distributed component model (CCM, EJB, .Net, etc) -remote access; no control over the underneath infrastructure. Right: Cloud component model -local access; the component is responsible for remote communication.

Fig. 2 .

 2 Fig.2. Left: CC style with a single interface S. Middle: CC with two roles, cardinality, and location. Right: CC com with two roles and three hosts.

Fig. 3 .

 3 Fig. 3. Left: Two CCs are composed using roles S and Q. Right: Two CCs AlphaCC has two role instances A and B, and BetaCC has two role instances C and D. A, C, and D are hosted by desktopOne, while B is hosted by desktopT wo. Therefore, the connection between A and C is legal, whereas the connection between B and D is not permitted.

Fig. 4 .

 4 Fig. 4. The importance of the 'connection multiplicity'. Left: No information. Right: The multiplicity of the connection is defined: [2..4].

  [1..1]. On the other hand I expect S to allow zero or more connections at runtime, i.e. [0.. * ]. Please see figure C.1 in appendix C.

Fig. 6 .

 6 Fig.6. The relation between the two ranges [e..f ] and [i..m] in figure5. We start with level one, and depending on the value of i we move to level two where we inspect the value of m. The label(s) on the arrows leading to the decision level indicate the decisions made on the upper two levels.

Figure 5

 5 Figure5presents the general case of assembly, which is defined as normal form A assuming there is a single instance of the CC. The connection here has the following semantics (as mentioned in the definition): at least i instance of S(Q) connect to i instance of Q(S), and at most m instance of S(Q) connect to m instance of Q(S). This is correct for one and only one instance of each cloud component ComA and ComB. The two ranges [e..f ] and [g..h] are not related in any way since cloud components may have been designed independently. On the other hand, the two ranges [e..f ] and [i..m] are related as in figure6. Cases presented in figure6can be reduced to the following four cases:

Fig. 7 .Fig. 8 .

 78 Fig. 7. Left: CC assembly normal form B. Multiple connections -role S is connected to three roles Q1, Q2, and Q3. Right: Role S after assembly reduction -phase one.

Fig. 9 .Fig. 10 .

 910 Fig. 9. The result after reduction phase two and three on figure 8-CC multiplicities are completely removed.

Fig. C. 1 .

 1 Fig. C.1. The banking system in normal form C. Up: Enterprise Edition. Down: Limited Edition

Fig. C. 2 .

 2 Fig. C.2. The output generated by the assembly checker. Up: For Enterprise Edition. Down: For Limited Edition

  In CC model, roles are the only access points of the component. A role can serve as a connection port where component ComA connects to other component ComB as in figure3(left).

	P	ComA	S 0..10	Q 2..5	ComB	R	P	ComA	S 0..10 2..4	Q 2..5	ComB	R
	4 Cloud Component Assembly
	4.1 Assembly Constraints

  Fig. 5. CC assembly normal form A. Ranges are always consistent (i.e. min max).

	P	ComA	S e..f	i..m	Q g..h	ComB	R
	Level one	1	i<=e	2	e<i<=f	3	f<i
	Level two	1	m<=e	2	e<m<=f	3	f<m
			1.1		1.2 2.2	1.3 2.3	3.3
	Decision level	Okay		Warning		Error

Email: Antoine.Beugnard@telecom-bretagne.eu

Email: ali.hassan@telecom-bretagne.eu

In this article we prefer to use the word assembly rather than composition since the output of this operation (assembly) is not a software component.

Γ is defined in appendix B.

We propose a novel software development process to build CCs and CC based systems. The description of this process is out of the scope of this article and we will propose it in future publication.

Concept

symbol can be reduced to [0..M AXIN T ] for computations. In this example the system is built using three CCs. The Bank CC is responsible for all database systems, security, transactions, and accounts. It is basically the backbone of the system. The Agent CC is the filter that any access to Bank will pass through. In other words, nobody can directly access Bank CC. AT M CC is installed over all ATM machines to allow customers to access their accounts, and perform bank transactions. Similarly, Internet CC is installed on the customers devices to allow them to access their accounts using internet banking.

We encoded this example using the formal language presented in this paper, and used the automatic assembly checker to check the design. The assembly checker generated the output presented in figure C.2.

The checker reports expected warnings and errors. For instance the error reported (figure C.2 -right) on the system described figure C.1 (bottom) is due to the too many instantiations of the ATM and Internet CCs.


Sana Fathallah
email: fathalla@unice.fr

Ben Abdenneji

Stéphane Lavirotte
email: stephane.lavirotte@unice.fr

Jean-Yves Tigli
email: jean-yves.tigli@unice.fr

Gaëtan Rey
email: gaetan.rey@unice.fr

Michel Riveill
email: michel.riveill@unice.fr

A Dynamic mechanism for solving Interfering Adaptations in Ubiquitous Computing Environment

Keywords: self-adaptation, software composition, interference resolution, graph transformation

Dynamic adaptation is a central need in Ubiquitous computing. In this kind of system, it is frequent to see the appearance of interference, when there are several adaptations to be applied on the application. In this paper, we present an automatic mechanism for dynamic interference resolving. Applications and adaptations will be represented by graphs; then we apply graph transformation rules to compute at runtime the solution.

Introduction

Ubiquitous computing relies on objects of our daily life. These devices are able to communicate together and they constitute the software infrastructure, on which the ubiquitous system is based. In such kind of systems, applications are designed based on components assembly or orchestration of services. They can be represented using graphs where nodes are the entities (components or services) and edges model the interaction between these entities. Because of devices mobility, the graph modeling the application must be continually adapted to consider the changes of the environment (appearance/disappearance of devices). So, the system should react automatically and transparently by applying adaptations. An adaptation, which can also be modeled as a graph, specifies behaviors to be integrated into the initial graph (application). As a consequence, an adaptation changes the graph structure of the application by adding or modifying links and/or nodes. In addition, adaptations have to be written without a priori knowledge of the other adaptations of the system. So, during the step of adaptation, it is possible to have some modifications which can be attached in common points of the graph: we call these interferences.

Researchers in self adaptation applications have used different techniques to deal with interferences. Zhang et al. [START_REF] Zhang | Aspect composition in the motorola aspect-oriented modeling weaver[END_REF] specify adaptations precedence at modeling level. However, interferences occur at runtime; so the resolution must be applied at runtime. Dinkelaker et al. [START_REF] Dinkelaker | The art of the meta-aspect protocol[END_REF] propose to dynamically change the adaptation composition strategies according to the runtime state of application. In this approach, if we add a new adaptation to the system, the developer should study its relationship with the other adaptations, which is a complex task. From these works, we can conclude that the proposed techniques cannot remove all interferences. To alleviate this problem, we propose to merge automatically interfering adaptations without preventing interferences explicitly. Our mechanism guarantee the independence between adaptations that can be composed whatever their order, and that can be added or removed easily to the system. Since adaptations are designed independently, they can interfere. Our solution is to merge them. This is possible due to the knowledge of the semantic of some nodes of the graph. Our graphs have two classes of nodes. Whitebox nodes (are operators that explain their semantics) and Blackbox node (are devices; they encapsulate the functionalities that can be only accessed by their ports, without knowing their semantics). The interference resolution process can be divided into two steps. The first step is the interference detection. The input of this step is the graph G which is obtained from the superposition of all graphs of adaptations on the graph of the initial application. On the graph G, we add a specific component  (Fus) to mark all interference problems. The second step is interference resolution. Since we work at graph level, the resolution will be a transformation of the graph G to the graph G'. Therefore, we need to define graph transformation rules that specify how to merge all known semantic nodes. We have defined a set of merging rules which derived from previous works [START_REF] Tigli | WComp Middleware for Ubiquitous Computing: Aspects and Composite Event-based Web Services[END_REF]. A graph transformation rule has the form of r:LR. It can be performed if there is an occurrence of L in the host graph G. The rule execution implies to: (1) remove L and (2) add the R graph. The figure 1 represents an example of the graph transformation rule. It shows the merging of the semantic known operator IF (the conditional behavior) and a message send. The conditional behavior "IF" is specified by three parts. "X" node represents the condition to be evaluated. When "X" is True, we execute the node "A", otherwise "B" will be executed.

Our composition mechanism is independent from application's implementation because it occurs on the graph G, which abstracts all details. The main property of our composition is the symmetric. This property consists of three sub-properties: associativity, commutativity and idempotency. It means that there is no order in which composition process should be applied. As a consequence, adaptations are independent of each other and it can be composed in an unanticipated manner. These properties allow the adaptation process to be deterministic. To enable the merging of these interfering rules with the previous properties, we constrain the adaptation language. Whatever the language used to write the adaptation, it must be based on a limited set of operators with a well-known semantic that can be merged. In our implementation, 6 operators were defined; which implies the definition of 16 graph transformation rules.


Léon Lim
email: leon.lim@telecom-sudparis.eu

Denis Conan
email: denis.conan@telecom-sudparis.eu

Sana Fathallah
email: fathalla@unice.fr

Ben Abdenneji

Stéphane Lavirotte
email: stephane.lavirotte@unice.fr

Jean-Yves Tigli
email: jean-yves.tigli@unice.fr

Gaëtan Rey
email: gaetan.rey@unice.fr

Michel Riveill
email: michel.riveill@unice.fr

Antoine Boutet
email: antoine.boutet@inria.fr

Eiko Yoneki
email: eiko.yoneki@cl.cam.ac.uk

Toward a Solution to Partitionable Group Membership for MANETs

Keywords: MANETs, dynamic partitionable systems, partitionable group membership, abortable consensus self-adaptation, software composition, interference resolution, graph transformation Social Media, User Classification

Context of the study

Ubiquitous computing environments are characterised by a diversity of mobile nodes and networks, and in particular, mobile ad-hoc networks. Mobile Ad-hoc NETworks (MANETs) are self-organising networks that lack a fixed infrastructure, and due to nodes arrivals, departures, crashes and movements, they are very dynamic networks. The topology changes occur both rapidly and unexpectedly and nodes (processes) can dynamically enter and leave the system. Thus, a distributed system built over MANETs can be partitioned. Distributed systems that are built over MANETs must be partition-tolerant, that is network partitioning may result in a degradation of services, but not necessarily in their unavailability. Fault-tolerant applications in partitionable system models generally rely on the two services of Group Communication System: (1) group membership service and (2) reliable multicast service. Informally, group membership specifies the view a process has on the current group it belongs to whereas reliable multicast provides reliable message diffusion within the same group. In this work, we focus on the group membership service, and more precisely, on group membership services for partitionable systems built over MANETs.

Part II

Papers

Group membership in dynamic and partitionable systems Group membership consists of two sub-problems [START_REF] Schiper | From Set Membership to Group Membership: A Separation of Concerns[END_REF]: (i) determining the set of processes that are currently up, and (ii) ensuring that processes agree on the successive value of the this set. In the literature, two types of group membership services have emerged: primary-partition [START_REF] Schiper | Brief announcement: dynamic group communication[END_REF] and partitionable [5,2]. Roughly speaking, primary-partition group membership maintains a single agreed view of the group. Such a group membership is intended for classical not-partition-tolerant systems. Since only a single view of the group can exist, primarypartition group membership requires strong assumptions on the system to satisfy the agreement property. These assumptions are strong enough to show that group membership is impossible in systems with crash failures [4]. In contrast to primary-partition ones, partitionable group memberships allow processes to disagree on the current membership of the group. Collaborative applications [3], resource allocation management [1], and distributed monitoring [START_REF] Murray | A Distributed State Monitoring Service for Adaptive Application Management[END_REF] are examples of applications that support permanent partitioning and thus go on running on multiple partitions. Such partitions may present some eventual stability [START_REF] Mostefaoui | From Static Distributed Systems to Dynamic Systems[END_REF] so that liveness of the computation can be guaranteed, that is a stability period lasts long enough so that eventually all the participant nodes of the partition are connected to each other and can communicate in a timely manner. Partitions can merge into larger partitions when the communication links between them are re-established. Thus, partitionable group memberships allow split and merge operations on partitions. By allowing disagreement, they escape from the impossibility result of [4]. However, they run into another fundamental issue. Specifying partitionable group membership for partitionable systems faces two orthogonal goals [4,[START_REF] Pleish | On the Specification of Partitionable Group Membership[END_REF]: (1) the specification must be weak enough to be solvable (implementable); and (2) it must be strong enough to simplify the design of fault-tolerant distributed applications in partitionable systems.

Open issues in the specification of partitionable group membership

To be useful, a partitionable group membership service must ensure at least the virtual synchrony property which is considered in the literature to be a basic property of partitionable membership services [5]. Two prominent specifications of partitionable group membership that ensure virtual synchrony are [5] and [2]. They sketch the two categories of partitionable group membership specifications which have been proposed in the literature and which differ about their liveness property: (1) liveness must hold only in stable partitions [5], and (2) liveness 1 must be ensured in every partition [2]. In [5], the authors define a completely stable partition as "a set of processes that are eventually alive and connected to each other, and the link from any process in this set to any process outside the set is down". The specification of [5] does not ensure liveness of the system when two processes p and q are forever intermittently reachable. This unstable case disappears in the specification of [2] with the consideration of fair channels, and thus [2] guarantees liveness not only in stable partitions. However, as shown in [START_REF] Pleish | On the Specification of Partitionable Group Membership[END_REF], these two specifications are not satisfactory. For instance, the specification in [5] can be satisfied by a "trivial but useless implementation" and the specification in [2] cannot be implemented without strong synchrony assumptions. Furthermore, the system model in both [5,2] is static and the network is initially fully connected.

Partitionable group membership as a sequence of abortable consensus

In our work, we propose a system model that characterises the dynamic behaviour of stable partitions in MANETs. Nodes that stay in a partition during a period that lasts enough are said to be stable, and unstable otherwise. In our model, the liveness property of partitions can be guaranteed even if they are not completely stable. To this means, we have defined a weak stability condition based upon the application-dependant parameter α which is a threshold value used to capture the liveness property of a partition. In each partition, α stable processes are required to execute distributed computations. Then, we propose a way to solve group membership in partitionable systems built over MANETs by adapting the Paxos protocol for such systems. This results in a specification of a form of consensus for partitionable systems called abortable consensus. Abortable consensus (AC) is a combination of two abstractions: eventual α partition-participant detector (♦PPD α ) and eventual register per partition (♦RPP). ♦PPD α is specified to abstract liveness in a partition whereas ♦RPP encapsulates safety in the same partition. The role of ♦PPD α is to make trade-offs between agreement and progress by eventually detecting the stability condition of α processes in a partition and eventually providing the leader among them. The participating nodes are selected among reachable nodes by some stability criterion that may satisfy the stability condition. A stability criterion is a parameter that is used to determine which nodes are the most stable ones. Finally, ♦RPP provides a distributed storage in a partition with a write-once semantics. The acts of locking and storing a value in the register can fail in two cases: (1) in case of contention or (2) in case of nonsatisfied stability condition. The first case is the same as in the original Paxos algorithm: a proposer abandons a proposal if some proposer has begun trying to issue a higher-numbered one, but the consensus instance is not necessarily abandoned. In the second case, the proposer not only abandons the proposal but also the consensus instance if there is no α stable processes in its partition.

Then, the partitionable group membership problem is solved by a transformation into a sequence of AC, where each AC is executed by the participant nodes in the current view. When the decision returned by the abortable consensus is a set of processes α-Set, these processes are the members of the next view. However, unlike a regular consensus, the returned value is not necessarily a value that was proposed by some process. It could be a specific value abort meaning that the consensus has aborted because the stability condition is not satisfied. In this case, processes re-compute their own α-Set, and then begin executing a new AC instance.

Introduction

Ubiquitous computing relies on objects of our daily life. These devices are able to communicate together and they constitute the software infrastructure, on which the ubiquitous system is based. In such kind of systems, applications are designed based on components assembly or orchestration of services. They can be represented using graphs where nodes are the entities (components or services) and edges model the interaction between these entities. Because of devices mobility, the graph modeling the application must be continually adapted to consider the changes of the environment (appearance/disappearance of devices). So, the system should react automatically and transparently by applying adaptations. An adaptation, which can also be modeled as a graph, specifies behaviors to be integrated into the initial graph (application). As a consequence, an adaptation changes the graph structure of the application by adding or modifying links and/or nodes. In addition, adaptations have to be written without a priori knowledge of the other adaptations of the system. So, during the step of adaptation, it is possible to have some modifications which can be attached in common points of the graph: we call these interferences.

Researchers in self adaptation applications have used different techniques to deal with interferences. Zhang et al. [2] specify adaptations precedence at modeling level. However, interferences occur at runtime; so the resolution must be applied at runtime. Dinkelaker et al. [1] propose to dynamically change the adaptation composition strategies according to the runtime state of application. In this approach, if we add a new adaptation to the system, the developer should study its relationship with the other adaptations, which is a complex task. From these works, we can conclude that the proposed techniques cannot remove all interferences. To alleviate this problem, we propose to merge automatically interfering adaptations without preventing interferences explicitly. Our mechanism guarantee the independence between adaptations that can be composed whatever their order, and that can be added or removed easily to the system.

Merging interfering adaptations using Graph Transformation

Since adaptations are designed independently, they can interfere. Our solution is to merge them. This is possible due to the knowledge of the semantic of some nodes of the graph. Our graphs have two classes of nodes. Whitebox nodes (are operators that explain their semantics) and Blackbox node (are devices; they encapsulate the functionalities that can be only accessed by their ports, without knowing their semantics). The interference resolution process can be divided into two steps. The first step is the interference detection. The input of this step is the graph G which is obtained from the superposition of all graphs of adaptations on the graph of the initial application. On the graph G, we add a specific component 8 (Fus) to mark all interference problems. The second step is interference resolution. Since we work at graph level, the resolution will be a transformation of the graph G to the graph G'. Therefore, we need to define graph transformation rules that specify how to merge all known semantic nodes. We have defined a set of merging rules which derived from previous works [3]. A graph transformation rule has the form of r:LAER. It can be performed if there is an occurrence of L in the host graph G. The rule execution implies to: (1) remove L and (2) add the R graph. The figure 1 represents an example of the graph transformation rule. It shows the merging of the semantic known operator IF (the conditional behavior) and a message send. The conditional behaYLRU ³IF´ LV VSHFified by three SDUWV ³;´ node represents the condition to be evaluated. When ³X´ is True, we execute the node ³$´ oWKHUZLVH ³B´ ZLOO EH Hxecuted.

Our composition mechanism is independent IURP DSSOLFDWLRQ ¶V LPSOHPHQWDWLRQ because it occurs on the graph G, which abstracts all details. The main property of our composition is the symmetric. This property consists of three sub-properties: associativity, commutativity and idempotency. It means that there is no order in which composition process should be applied. As a consequence, adaptations are independent of each other and it can be composed in an unanticipated manner. These properties allow the adaptation process to be deterministic. To enable the merging of these interfering rules with the previous properties, we constrain the adaptation language. Whatever the language used to write the adaptation, it must be based on a limited set of operators with a well-known semantic that can be merged. In our implementation, 6 operators were defined; which implies the definition of 16 graph transformation rules.

Understanding community evolution in Complex systems science

Qinna Wang a and Eric Fleury b a qinna.wang@ens-lyon.fr b eric.fleury@inria.fr Complex systems is a new approach in science that studying organized behaviours in computer science, biology, physics, chemistry, and many other fields. By collecting articles containing topic keywords relevant for the field of complex networks from ISI Web of knowledge during 1985-2009, we construct a science network, which connects ∼ 215000 articles according to the proportion of shared references. Moreover, articles' publication time makes it dynamically evolve in time. We here use a two-step approach [3] to explore community evolution and study underlying information behind community changes. We firstly detect communities by applying Louvain algorithm [2] on each snapshot graph, and secondly construct relationships between partitions at successive snapshot graphs [1].

Communities may change, like fusion, split, disappearance and emergence. To construct relationships between communities, we use community predecessor and successor : given a community C i (t) found at time t, its predecessor is community C j (t -1), which has the maximum overlap size among all communities at time t-1, such as C j (t-1) = arg max C k (t-1)⊆P(t-1) |C k (t -1) ∩ C i (t)|; its successor is community C j (t+1), which has the maximum overlap size among all communities at time t+1, such as

C j (t+1) = arg max C k (t+1)⊆P(t+1) |C k (t + 1) ∩ C i (t)|. Given a pair of clusters (X, Y ), we use X → Y to denote that Y is X's successor while X ← Y to denote that X is Y 's predecessor. Besides, we define community C i (t)'s survival is community C j (t + 1) such as C(i)(t) ⇆ C j (t + 1), if and only if C i (t) → C j (t + 1) and C i (t) ← C j (t + 1).
We use the survival to describe one community evolving stable. Furthermore, we also use community predecessor and successor to identify community dynamic events: given a community C(t), if it has more than one predecessors, then C(t) is a merged community; if it has more than one successors, then C(t) split in the next time step; if it has no predecessor, then C(t) is a new community; If it has no successor, then C(t) will vanish; otherwise, it evolves stable. A diagram (see Fig 1) shows several cases involving community dynamic events. We observe nearly all types of community changes: community C 2 emerges at t = 2, community C 3 disappears at t = 3, community C 2 merges into C 1 at t = 4 and community C 4 is split from C 3 at t = 3. For community C 1 , it evolves stable across the total four time steps although it is related to a merge event. It is like the change of C 2 rather than C 1 . After applying our method on Complex Systems Science's snapshots: G(1985-1995), G(1990 -2000), G(1995 -2005), G(2000 -2010), we observe most of communities evolve stable over time, especially communities representing theoretical sciences like chaos theory(CHAOS), systems ecology(ECOLOGY), systems neuroscience(NEURAL NETs) 12 . These stable communities are also involving many change events, especially merges between function applications and science domains such as ISING-MODEL and PHOTOSYSTEM-II merged into chemistry during 1990 -2000. Results on community evolution suggest that theoretical sciences are the foundations of Complex System Science.

1 CHAOS, ECOLOGY and NEURAL NETs are the most popular key words shared by articles in the found communities while chaos theory, systems ecology, systems neuroscience are disciplinarians by considering popular keywords shared by articles in the found communities. For instance, the community nominated by CHAOS representing chaos theory have popular keywords like DYNAMIC, CHAOS, SYSTEM, NONLI-, COMPL-, MODEL, STABI-and so on. 2 Through our method, we found many matching communities sharing the same popular keywords and the same disciplinarians, like CHAOS and ECOLOGY, and many matching communities sharing different popular keywords but representing the same disciplinarians, like biology:nervous system(RAT, BRAIN) whose articles focus on biology functions about humans' brain in place of rats' as time going.

Towards Temporal Mobility Markov Chains

Sébastien Gambs

I. MOBILITY MARKOV CHAINS

In [1], we defined a type of mobility model that we coined as mobility Markov chain (MMC), which can represent in a compact yet precise way the mobility behaviour of an individual. In short, a MMC is a probabilistic automaton in which states represent points of interest (POIs) of an individual and transitions between states corresponds to a movement from one POI to another one. The automaton is probabilistic in the sense that a transition between POIs is non deterministic but rather that there is a probability distribution over the transitions that corresponds to the probability of moving from one POI to another (edges are directed). Note that Markov models are a popular technique that have been used in the past for the study of motion (for instance see [2] for a recent work using hidden Markov networks to extract POIs from geolocated data).

More formally, a MMC is a transition system composed of:

• A set of states P = {p 1 , . . . , p n }, in which each state p i corresponds to a POI (or a set of POIs). These POIs may have been learned for instance by running a clustering algorithm on the trail of mobility traces from an individual or simply by collecting the locations that he has posted on a geolocated social network such as Foursquare or Gowalla. Each state (i.e. POI) is therefore associated with a physical location.Moreover, it is often possible to attach a semantic label to the states of the mobility Markov chain, such as for instance "home" instead of simply p 1 " or "work" instead of p 2 . • A set of transitions, T = {t 1,1 , . . . , t n,n }, where each transition t i,j represents a movement from the state p i to the state p j . Each transition t i,j has a probability assigned to it that corresponds to the probability of moving from state p i to state p j . Sometimes an individual can move from one POI, go somewhere else (but not to one of his usual POIs) and come back later to the same POI. For example, an individual might leave his house to go wash his car in a facility near his home and come back 30 minutes later. This type of behaviour is materialized in the mobility Markov chain by a transition from one state to itself. A MMC can be represented either as a transition matrix or as a directed graph in which nodes correspond to states and there is a directed weighted edge between two nodes if and only if the transition probability between these two nodes is non-null. The sum of all the edges' weights leaving from a state is equal to 1.

For instance, consider for illustration purpose, an individual, that we refer thereafter as "Alice", who has a set of 4 important POIs that she visits often plus some other POIs that are less important to her mobility. In order to represent her mobility behaviour, we could define a MMC composed of 5 states, one for each important POI plus a last one that will contain all the infrequent POIs. Suppose now that we have been able to collect her trail of mobility traces (e.g., by tracking her mobile phone [3]), then possibly we could have learnt the following MMC (Figure 1). For more details, about MMC we refer the reader to [1].

II. INTRODUCING TIME INTO MOBILITY MARKOV CHAINS

In this section, we describe an algorithm for learning Temporal Mobility Markov Chains (TMMC). This algorithm is an extension of the one described in [1] to which we add the temporal aspect. Basically, the gist of this algorithm is to decompose time into n different discrete timeslices. For example, with n = 4, we can observe mobility in one of the following timeslices: morning, afternoon, evening and night. Each POI from the original MMC will thus be represented by n different states in the TMMC, one for each timeslice. end if 13: end for 14: Sort the clusters in f reqP OIs by decreasing order according to their densities 15: for each cluster C i in f reqP OIs (for end if 29: end for 30: Squash all the successive mobility traces sharing the same (time and space) label into a single occurrence 31: Compute all the transition probabilities between each pair of states of the Markov chain 32: return the mobility Markov chain computed take Alice's home for example, which is state p 1 on Figure 1., it will be represented by the states P 1morning , P 1af ternoon , P 1evening and P 1night . Remark that the scale of the timeslicing can be tuned to match the required level of detail. For example, the timeslices can also be winter, spring, summer, autumn or even months or years, . . . In a nutshell, Algorithm 1 starts (line 1) by applying a clustering algorithm on a trail of traces of an individual in order to identify clusters of locations that are significant. Then, in order to reduce the number of resulting clusters, the algorithm merges clusters whose medoids are within a predefined distance d of each other (line 2). Each resulting cluster is considered as a POI, and the medoid of the cluster is considered to be the physical location of the POI. For each cluster (lines 4 to 6), we compute the number of mobility traces inside the cluster (which we call the density of the cluster) and the time interval (measured in days) between the earliest and the latest mobility traces of the cluster (line 5). The POIs (i.e. clusters) are then split (lines 7 to 13) into two categories; the frequent POIs that correspond to POIs whose time interval is above or equal to a certain threshold mintime and the infrequent POIs whose time interval is below this threshold mintime. In the set of frequent POIs (line 14), we sort the POIs by decreasing order according to their densities. Therefore, the first POI will be the denser and the last POI the less dense. Now, we can start to build the temporal mobility Markov chain by creating a state for each tuple < P OI, timeslice > within the set of frequent POIs (lines 15 to 19) and also a last state representing the set of infrequent POIs (line 20). Each state is then assigned a weight that is set to its density. Afterwards (line 21), we come back to the trail of traces that have been used to learn the POIs and we remove all the moving points (whose speed is above ǫ, for ǫ a small predefined value). Then, we traverse the trail of traces in a chronological order (lines 22 to 29) labeling each of the mobility traces either with the tag of closest POI and the appropriate timeslice (line 25) or with the tag "unknown" if the mobility trace is not within d-distance of one of the frequent or infrequent POIs (line 27). From this labeling, we can extract sequences spatio-temporal chunks that have been visited by the individual in which all the successive mobility traces sharing the same label are merged into a single occurrence (line 30). For example, a typical day could be summarized by the following sequence "p home/morning ⇒ p work/morning ⇒ p work/af ternoon ⇒ p sport/af ternoon ⇒ p sport/evening ⇒ "unknown ′′ ⇒ p home/evening ". From the set of sequences extracted, we compute the transition probabilities between the different states of the MMC by counting the number of transitions between each pair of states and then normalizing these probabilities (line 31). If we observe a subsequence in the form of "p i/t ⇒ "unknown" ⇒ p i/t " then we increment the count from the state p i/t to itself (which translates in the graph representation by a self-arrow). Abstract-Routing becomes obsolete in ad hoc dynamic networks. Path maintaining becomes necessary in order to maintain a communication that already started between two entities. In this paper we present a path maintaining algorithm.

1 ≤ i ≤ n -1)
Index Terms-Ad hoc, dynamic, path maintaining

I. INTRODUCTION AND RELATED WORKS

Ad hoc dynamic networks represent a challenging domain of application due to their specifications. Still we find many applications on these networks nowadays, like the vehicular networks, drone networks or even pedestrian networks. The general method to study these networks starts by studying their dynamics. The dynamic changes are closely related to the frequency of neighborhood changes, and the functioning and requirements of the protocols.

Unicast communications in these networks require a continuous communication between the source of the messages and the destination even if they are separated by multiple hops. Many routing protocols exist for mobile networks, like AODV, OLSR and geographic routing among others. But these protocols are not efficient if the dynamic of the network increases to exceed the admitted dynamicity. Not to forget that these protocols require broadcast in general, location services [5] [4] or infrastructure bases, which make them inadequate to highly mobile networks. We should also mention that the need for global knowledge in these protocols increases the control over the network, in order to build or to update the structures needed to maintain routes.

II. CONTRIBUTION

Due to their specificities, dynamic networks do not require routing as those used in networks with fixed topologies or low dynamics. In fact, in mobile networks, the search for a distant destination might be obsolete since the nodes are frequently moving, meaning that the destination might have changed its location by the time the source receives its response. The search for the destination implies the broadcast of messages in order to identify its position. And in case some geographic protocols admit the knowledge of the position of the destination, this means that a location service has already identified this position using broadcasted messages. As explained in [2], the need for unicast communication is in order to maintain a communication that started when the source and the destination were neighbors, and that is needed to pursued for a certain duration. This problem is called path maintaining. This said, the aim of the path maintaing application is to maintain a communication initiated with a path of length 1 and to avoid the flooding of the network with unnecessary messages.

In this paper, we describe the path maintaining algorithm, that we denote PTH. PTH is a path maintaining algorithm that relies on local adjustments of the path. Local adjustment is used in order to avoid having a global knowledge of the network, which implies to flood the network with too much control messages in order to build a global knowledge that might become unusable because of the dynamic. PTH adjusts the path between the source and the destination using neighbor nodes of the broken links in the path. Starting from a direct communication between the source and the destination, PTH interferes when these two entities move apart, and the direct communication between them becomes impossible. At this point, the neighbor nodes of the broken link are used to relay the messages. The same mechanism is used for all the broken links of the path between the source and the destination. PTH relies on three mechanisms: local periodic update for the nodes of the path only, path reduction and path extension. These mechanisms are detailed in the next section.

III. THE PTH ALGORITHM

In this section, we describe our algorithm named PTH for solving the path maintaining problem. It is mainly based on three mechanisms, that we describe in this section: local periodic update, path extension and path reduction.

The first mechanism -local periodic update -allows to deal with neighborhood changes and failures. It relies on periodic diffusion of messages in the neighborhood of the sender. These messages contain some local information regarding the path. Such information is composed by the list of members of the path (eg. u 0 u 1 u 2 u 3 . . . ) (see Figure 1), some flags allowing to determine the sender and the willing receiver of the current message (u 0 u 1 >u 2 u 3 if u 1 is the sender and u 2 the receiver) and an uncertainty flag regarding a member of the path (u 0 u 1 >u 2 ?u 3 (see Figure 1) if u 1 has a doubt on its successor u 2 ). Such a message informs both the predecessor and the successor of the local state of the If a node is already engaged with another reduction, it will not forward the validation message containing the reduction. In the converse case, the node forwards the message and becomes engaged. By this way, in case of two reductions in conflict for a common sub-path, the validated reduction is the one that first sent a validation message into the common subpath. When u j receives the validation message, it confirms the reduction by relaying from now messages of v instead of messages of its old predecessor u j 1 . An engaged node will either leave the path or receive a message without reduction from its predecessor; it stops then being engaged. The same process is used when the reduction is proposed by nodes u i belonging to the path instead of a neighbor node.

IV. PTH VALIDATION AND PERFORMANCES

Whatever are the performance of a given algorithm, the dynamic of the network can lead to failure because it could compromise any communication. Our protocol is able to run even in highly dynamic network but the following requirement is necessary: a neighbor of the path is present during the path extension. This operation is very short (few local messages). By the way, we have a contract between the dynamic and the specifications of our protocol. This has been formalized in [3] under the term of best effort algorithm. A best effort algorithm does its best regarding the dynamic while still ensuring some useful properties for those (users or other protocols) relying on it. More precisely, whenever a topological property is fulfilled, a continuity property is ensured. Here, the topological property is the presence of a neighbor node when two nodes belonging to the path move far each other. The continuity property is the existence of the path from source to destination, the two initiators which were in the same neighborhoods at the beginning. Proof is omitted by lack of place.

PTH has been compared to a basic geographic routing with a location service, and to a traditional broadcast in the same scenario under the Airplug emulator [1] (with 31 cars moving from the UTC laboratory to the train station in Compiègne), and starting from the same initial state. Consider now N the number of messages sent by the source node in the network. While the broadcast flooded the network with 8.4 N messages, the geographic routing with its location service sent to the network 5 N messages, and PTH sent 2.4 N messages. Not to mention that when 31 cars were involved in sending messages for the broadcast or geographic routing, only 6 were involved when running the PTH algorithm.

Member Classification and Party Characteristics in Twitter during UK Election 1 Introduction

Using social media for political discourse is becoming common practice, especially around election time [4]. Different off-line approaches have been proposed for classifying the political leaning of users [3,2]. However, inferring the political orientation of members in real time needs (1) to avoid collecting and using a prohibitive quantity of data for classification and (2) to consider the highly dynamic nature of social media including changes in term of active users, content or social structure.

On the other hand, while several studies have addressed the characterization of user in social networks [1], few works have tried to characterize politic parties. This characterization permits to highlight the main differences between parties, their impact in term of activity and influence, their preferred content, their mood and sentiment, their structure and how they exchange between each other over time. For instance, this information can be useful for political parties or candidates to monitor their impact and to assess and adapt their strategy.

This paper summarizes a case study of member classification and party characterization in Twitter during the 2010 UK general election. By looking at temporal changes in activity, Twitter is shown to react instantly to UK election events. To highlight the main differences between parties, we first characterize the self-identified users as member of a specific party according to several categories. Then, we present a real-time method for deducing user's party affiliation using only basic textual and semantic analysis of the public stream of Twitter. Finally, we discuss key parameters to address the dynamic nature of social media in online classification.

Party Characteristics

To highlight the main differences between parties, we first characterize the self-identified populations (users self-identified as members of specific parties in their Twitter user description) according to several categories: (1) the activity reflects the commitment of the parties to send tweets and to take place in political debates ;

(2) the influence gives an indication on the potential impact of each party ; (3) the social structure reflects both the cohesiveness of the party and the level of exchange and debate between them ; (4) the content shows how the party used hashtags and urls, and the volume of references did to a specific party or political figure ; (5) the sentiment analysis evaluates the sentiment of words in tweets through different directions (self-focus, cognitive, social, positive and negative).

We saw that only few characteristics differ one party to another and made the following observations:

• Activity. Except for a small fraction of users with particular behavior in term of generated tweets, retweets or mentions, the majority of members from all parties exhibited a similar activity. • Influence. Labour members had a better influence, however, Conservative members were better organized to promote their party. • Structure. The retweet graph presents a highly segregated partisan structure where very few links connected different parties. In contrast, the mention graph formed a more heterogeneous structure where no particular clusters were observed. • Content. The usage of hashtags depended on the underlying neutrality of the tag. In addition, each party was more likely to cite certains websites than others especially for blogs which were more political orientated. The similarity in terms of hashtags used showed a high heterogeneity between users in all parties. Moreover, we demonstrated that party members were more likely to make reference to their own party than another. • Sentiment. No particular sentiment direction permitted the differentiation of parties. However we clearly saw that members were more likely to express more positive opinion when they referenced its own party.

User Classification

The goal of this classification is to identify the party to which each person belongs and their evolution from the pattern of tweets. We consider the observed tweet process by events E ∈ {E n } representing the current state of beliefs of the political affiliation of members. Each affiliation probability is represented by an event, Am ∈ {labour, libdem, conservative} for each user where labour + libdem + conservative = 1, containing elementary events A m ∩ E n . The conditional probabilities or evidences P (E n |A m ) are specified to define the affiliation probability. P (A m ) is the uncertainty of model A m . Before the first inference step, the initial prior probability is set uniformly: {P (A)} = { 1 3 , 1 3 , 1 3 }. For each affiliation probability Am, P (A m ) is updated to P (A m |E n ). From Bayes' theorem:

P (A m |E n ) = P (E n |A m )P (A m ) P (E n ) (1)
where P (A m |E n ) is the posterior, the uncertainty of A m after E n is observed ; P (A m ) is the prior, the uncertainty of A m before E n is observed ; and P (En|Am) P (En) is a factor representing the impact of E n on the uncertainty of A m .

We define two evidences based on the main characters identified in the party charateristics analysis. The first is based on the pattern of retweets and highlights the fact that people of similar political persuasion retweet roughly the same thing (highly segregated partisan structure of the retweet graph). Retweets can be easily identified in the tweets stream thanks to the keyword RT. This evidence is defined as the average affiliation probability of both people retweeted by the user or people retweeting the user during the period [E n-1 , E n ]:

P (E n |A m = a) = R∈Retweets P (A = a) R Number of retweets (2)
The second exploits the fact that party members are more likely to make reference to their own party than another. This second evidence is defined as the ratio of tweets referencing one party over the total number of references during the period [E n-1 , E n ]: Finally we define the political affiliation of user according to the best probability in A m (i.e. [0.7, 0.2, 0.1] refers a person who is probably Labour). Ties are broken randomly in case of equiprobabilities.

P (E n |A m = a) = V olume(A m = a) V olume(A m ) (3)
To evaluate our classification algorithm, initial seeds are chosen from the 10% most active users in term of generated tweets from those which are self-identified as member of specific party. We then measure the accuracy by calculating the number of correct predictions of the remaining 90% over the total number of predictions. Table 1 shows the high accuracy produced by our member classification.

Discussions and Conclusions

We summarize here a case study of member classification and party characteristics from Twitter during the 2010 UK general election. The three main differences identified between political parties are (1) the retweet graph presented a highly segregated partisan structure where very few links connect different parties, (2) party members were more likely to make reference to their own party than another, and (3) members were more likely to express more positive opinion when they referenced their own party.

To be able to act in real time, a classification system must not require a prohibitive amount of data. Furthermore, due to the dynamic nature of social media, active users and content can change quickly. In this context, collecting the social structure of every new user or performing linguistic analysis for each new hashtag is inconceivable. The proposed member classification exhibits good performance, can be easily used in real time and fits perfectly to the dynamic nature of social media.

Towards dynamic graph analysis: a position note

Erwan Le Merrer Technicolor, Rennes

Gilles Trédan CNRS, Toulouse

In this note, we elaborate on directions for efficient graph analysis, taking into account the dynamic nature of complex networks.

Introduction and problematic

Tailored network analysis is at the core of some of the most successful Internet stories, as Google search engine for instance [2]. Understanding complex networks is a challenge that receives a growing interest. Interestingly, this challenge is tackled not only by computer scientists, but also by biologists and physicists. Together, these efforts led to the definition of several important methodological tools to extract information from a complex network, such as centralities, sampling, or scale-free property analysis.

However, most of these tools have been defined in a static way, by only providing insights on crawled networks, at some fixed point in time [3]. This is notably counter intuitive, as the complex networks observed are by nature evolving constantly [4]; predictions are doomed to be inaccurate.

At the same time, researchers started to develop models that capture graphs over time. For instance the concept time varying graphs (TVGs) [1] which has been recently recognized as a suitable model to describe the evolution of a network in time, pushed by the development of delay-tolerant and opportunistic networks. The TVG model may then constitutes the next step of understanding complex networks, observing them on a dynamic time dimension.

Adapting the aforementioned static tools to TVGs may seem easy. A trivial solution is to simply take snapshots of the network at fixed intervals in time, and to run the analytical computation on each of these snapshots. This is of course cumbersome if the time interval is small, and even simply not computationally feasible if the observed network is large; this prohibits online use by number of resources limited devices or applications for instance.

Since the scale of each snapshot already forbids the use of expensive algorithms, it is clear to us that analyzing TVGs calls for developing methods to reduce the size of the input dataset1 . The question we ask in this note is then the following one: "How to reduce the computational/memory costs when analyzing TVGs?".

Possible directions

We foresee 4 directions to reduce the global cost in computing characteristics of TVGs: i) observe a subset of relevant nodes over time, ii) concentrate on a subset of relevant snapshots, iii) observe the evolution over time of a set of graph measures and iv) develop/adapt graph measures to TVGs. We will hereafter briefly detail each approach.

Sample nodes Sampling has been extensively studied and provides accurate results in static contexts. This is probably a very efficient approach to gather the evolution of aggregate values, such as the evolution of the average age of social network users. However unbiased sampling is difficult, and adding the time dimension complexifies the problem.

The question of newcomers is pending: should we only sample nodes originally selected at random? Moreover, such an approach can not answer questions regarding the evolution of the graph structure itself.

Sample snapshots Here, the objective is to reduce the analysis complexity by discarding snapshots that bring little information to concentrate on those conveying more meaning. However, selecting which snapshot is relevant to keep is a non trivial task.

The difficulty is precisely tied to the arbitrarily set interval at with a snapshot should be kept for analysis. If a snapshot is created at each topological change, i.e. appearance/disappearance of a node or edge (called graph centric evolution in [1]), then the sampling rate of those snapshots should be related to their creation. It might as well be of a real interest to sample more snapshots when topological changes occur in the core of the network (or on nodes or edges that have been previously marked as important), than when events occur at the fringe.

Evolution of graph measures

The approach here is to run standard static graph analysis tools on each snapshot independently, and to interpret the obtained time serie. Reusing the static graph analysis toolbox is probably a very good starting strategy. Similarly to node sampling, this strategy has the drawback of only studying the evolution of static graph properties.

Keeping only an history of past analysis concerning a network may drastically reduce memory needed to track evolution in time, when compared to the snapshot-based approach. Starting from an initial network analysis, algorithms are providing outputs that are compared to previously observed results (one can for instance keep track of network diameter [4]). Only one network snapshot is then required in memory, for each evolution analysis, as compared to an array of snapshots as in the previous solution. The negative side being of course the loss of information when only conserving past measures instead of full network snapshots.

Adapted analytical tools

The approach here is to develop new algorithms suited to TVGs and their natural information redundancy. For instance, in many social networks, such as the co-authorship graph in DBLP, links are never removed. Each snapshot is thus a subset of the following one.

Recycling the results of previous snapshots to empower the current snapshot analysis could then lead to significant optimizations.

There is probably no generic solution for transforming static algorithms into their dynamicityaware counterparts. For most of known tools for graph analysis, even the slightest update of the initial graph might have unpredictable consequence on the algorithm.

Most of all, we believe that some very important TVG metrics are only definable in a dynamic context. Even very simple but interesting questions such as "how long does a link takes to be reciprocal, for a triangle to be closed?" can not be addressed by simply adapting our static toolbox to a dynamic setup.

When collecting data from evolving structures, researchers are often bound to the limitations of the API or available datasets. Thus, it is also important to think about the robustness of these complexity reduction techniques against incomplete datasets. For instance, time sampling is sometimes not under control because of crawling time and delays. It is sometimes hard to ensure the full graph is collected. Moreover, crawling times might lead us to question the association of one snapshot to one point in time.

We however believe that each of these directions could be valuable to be explored. It is still unclear which methods are above the others while considering costs, but probably all of them lead to the observation of different interesting phenomena. We yet have to understand their respective relevance to specific contexts.

Fig. 1 .

 1 Fig. 1. Alice's Mobility Markov Chain.

If we Algorithm 1 5 :

 15 Temporal mobility Markov chain algorithm Require: Trail of (mobility) traces M , merging distance d, speed threshold ǫ, time interval threshold mintime, time slices definition timeslices 1: Run a clustering algorithm on M to learn the most significant clusters 2: Merge all the clusters that are within d distance of each other 3: Let listP OIs be the list of all remaining clusters 4: for each cluster C in listP OIs do Compute the time interval and the density of C 6: end for 7: for each cluster C in listP OIs do 8: if C.time interval > mintime then 9: Add C to f reqP OIs (the list of frequent POIs) C to inf reqP OIs (the list of infrequent POIs) 12:

1 A

 1 distributed algorithm for path maintaining in dynamic networks F. El Ali 1 2 , B. Ducourthial 1 2 (1) Université de Technologie de Compiègne (2) CNRS Heudiasyc UMR6599, BP 20529, 60205 Compigne Cedex, France (corresponding author: Bertrand.Ducourthial@utc.fr)

Fig. 1 :

 1 Fig. 1: Local periodic messages

  do Create a state p inf requent representing all the clusters within inf reqP OIs 21: Let M ′ be the trail of traces obtained from M by removing all the traces whose speed is above ǫ 22: for each mobility trace in M ′ do 23:if the distance between the trace and the state p i is less than d and the state p i is the closest state then

	16:	for each time slice t in timeslices do
	17:	Create a state p i/t in the mobility Markov chain
	18:	end for
	19: end for
	20: 24:	determine t the appropriate time slice for the trace
	25:	label the trace with "p i/t "
	26:	else
	27:	label the state with the value "unknown"
	28:

Table 1 :

 1 Performance of our user classification

	Approach	Accuracy
	Bayesian	Retweet Volume	0.70 0.80

Google+ graph has now more than 40e6 users. At the time of this writing, its most famous user receives more than 3000 followers each day.

path, which in turns can then update their own information.

Other nodes not belonging to the path may propose to belong to, in order to repair or shorten it.

The second mechanism -path extension -allows to deal with link breaking. This can appear when two neighbors go far each other (Consider Figure 2, with u 0 u i , u 1 u j and u 6 v for instance). Consider that the link u i , u j in the path breaks. As the node u i sends periodically some messages containing u i >u j , it expects implicit acknowledgment of u j , that is messages without uncertainty, containing u i u j >. This means that u j receives the message of u i and forwards it with the path u i u j >. If it does not receive such messages from u j , it sets the uncertainty flag on its successor u j in its next messages: u i >u j ?. Either u j receives messages of u i with an uncertainty flag on itself (communication u i u j broken) or it does not receive at all messages from u i (communication u i u j broken). In both cases, it will set the uncertainty flag on its predecessor u i in its messages; they will contain: u i ?u j >. Such uncertainty flags allows to neighbors of both u i and u j to propose repairing the path. If a neighbor node v notices such exchanges, it counts the received messages from u i and u j . When a given threshold is reached, v proposes to be relay of the communication by sending u i ?v>u j ?. As several neighbors of both u i and u j may propose to be a relay, u i (closer from the source) chooses the first (say v) and sends u i >vu j ?. Then v sends u i v>u j ?. Then u j sends u i vu j > and the path is repaired (to the condition that a node v was present in the neighborhood of the breaking edge extremities).

The third mechanism -path reduction -consists in reducing the path when possible. This can be done by a node in the path, or neighbor of the path. Consider the case when the reduction between two given nodes u i and u j (where u i precedes u j in the path) can be done by a node v, neighbor of the path (Consider Figure 2, with u 2 u i , u 5 u j and u 7 v for instance) . This node v, by receiving the messages sent by u i and u j simultaneously, observes that it can reduce the path by being a relay between u i and u j .

The proposition of the reduction is done by placing in the path the shortcut denoted by u i -?v-?u j (with the uncertainty flag on the links u i , v and v, u j ). The message sent by v is of the form: . . . u i -?v-?u j . . . v>u j . . .. When u j receives this message, it confirms to v the possibility of reduction, removing the uncertainty on the reduction link v, u j . The node v then asks the permission of u i to be a relay. At this point, u i sends a validation message . . . u i -v-u j > . . . u j . . . to its successor in the path; this message will be relayed until reaching u j .

Indeed, as several overlapping reductions may occur simultaneously, the reduction u i v u j has to be validated by all nodes from u i to u j in the path. This allows to avoid any split of the path into several smaller disconnected paths.