Gautier Vanson

Pascale Marange

Eric Levrat

A technical and systematic characterization of circular strategy processes

Keywords: Circular Economy, Circular strategy, Products regeneration, Holistic approach, Requirement, characterization

To deal with environmental, economic and social problems linked to high consumption and intense manufacturing, Europe, ecological associations propose scenarios for the implementation of the circular economy, without saying how to implement them. Several circular strategies (CS) (reuse, remanufacturing, recycling...) enable to regenerate a product and its components throughout its life cycle. Currently, these CS are not implemented in a systemic way, but in a punctual and individual way. The objective is to deepen the knowledge of the global implementation of several CS. To achieve this, the paper proposes to characterise each CS according to the requirements of the entering and leaving products. This technical characterisation allows us to analyse their complementarities and interactions. This characterisation will be illustrated by the example of remanufacturing and resynthesis. Then, an analysis of our proposal is carried out to show the contributions in order to have a holistic approach of the regeneration.

Introduction

Today, governments are urging more and more companies to adopt a circular economy (CE) through laws, or decrees. Indeed, current issues such as linear consumption through mass customization, fashion effects and obsolescence [START_REF] Slade | Made to break: Technology and obsolescence in America[END_REF] are not compatible with the objectives of sustainable development (SD). The literature shows that this consumption mode is a source of environmental problems such as the increase in waste, climate change [START_REF] Ghisellini | A review on circular economy: the expected transition to a balanced interplay of environmental and economic systems[END_REF] and the depletion of natural resources [START_REF] Hazen | Remanufacturing for the circular economy: An examination of consumer switching behavior[END_REF]. In addition, pandemics and wars show how dependent some states are on certain primary resources. [START_REF] Roy | Economic impact of COVID-19 pandemic[END_REF].

The CE concept based on the pillars of SD is defined by [START_REF] Mac | Towards the circular economy[END_REF]: "A CE is an industrial system that is restorative or regenerative by intention and design. It replaces the 'end-of-life' concept with restoration, shifts towards the use of renewable energy, eliminates the use of toxic chemicals, which impair reuse, and aims for the elimination of waste through the superior design of materials, products, systems, and, within this, business models.". Through this definition, the consideration of a systemic vision with several regeneration cycles becomes essential to achieve the objectives of CE. The objective of our work over the last few years is to propose a holistic approach of product regeneration (i.e consider the interactions of different systems and stakeholders in a global view) . In Diez 2016, we defined the regeneration paradigm as [START_REF] Diez | Maintenance as a cornerstone for the application of regeneration paradigm in systems lifecycle[END_REF]: "set of actions, natural or technical, to restore a waste or its constituents to an acceptable state (functional and operational) allowing to extend its life cycle".

In the literature, many works deal with circular strategies (CS), eco-design but there are very few papers that integrate the multiple life cycles and the holistic approach. Thus, a CS standard characterization would help regeneration designers to define an adequate regeneration process for their products in a holistic approach. In order to achieve the SD objectives, a characterization considering environmental, economical and social aspects is necessary. For this first work, only the CS technical aspect is considered. Thus, this article proposes a technical and systematic characterization of CS with a formalization that allows to compare and analyze CS. The final objective is to give a better knowledge of CS to help industrial to adopt CE. This holistic vision will allow them to better apprehend the complexity of CE and the new CE laws implemented by states.

Circular strategies state of the art

In literature, the circular strategies (CS) enable to extend the product life and create loops for circular economy (CE) to recover value for a product, subassemblies/components or material that would otherwise be considered as waste [START_REF] Morseletto | Targets for a circular economy[END_REF]. A literature review enabled the identification of several CS: reuse, repurposing, upgrading, reconditioning, remanufacturing, resynthesis, recycling, energetic valorization and landfill. A systematic review was done for each CS. This complete work is not presented in this article, only few references are used by CS. Each selected reference is considered as the best to describe the CS in a holistic view. The objective of this section is to present the technical CS features identified in the literature. The following elements are analyzed:

-input: the expected level in the product breakdown structure, and the expected product quantity for carrying out a regeneration. -output: the expected level in the product breakdown structure and its nature: does it have the same purpose and the same composition as the incoming product (i.e. is it identical /different to the incoming product (identical finality and composition) or is it improved (identical finality and different composition by additions/subtractions/modifications)) -process: the CS activities and the level of the product breakdown structure that is regenerated. This listed information of the processes will not be developed in the rest of the article but considered as the activities that enable to regenerate an input product.

The literature review shows that CS are developed in a silo view because researchers optimize the CS process activities rather than the life cycle of the

CS Input Output Process Activities
Regeneration level Reuse [START_REF] Cooper | The environmental impacts of reuse: a review[END_REF], [START_REF] Bauer | Characterization of circular strategies to better design circular industrial systems[END_REF] The same input product diagnostic, cleaning and requalification Repurposing [START_REF] Scott | The Intersection of Sustainable Consumption and Anticonsumption: Repurposing to Extend Product Life Spans[END_REF], [START_REF] Bauer | Characterization of circular strategies to better design circular industrial systems[END_REF] The same input product with another finality Upgrading [START_REF] Ijomah | 8 -Refurbishment and reuse of WEEE[END_REF], [START_REF] Pialot | Upgradable PSS": Clarifying a new concept of sustainable consumption/production based on upgradablility[END_REF], [START_REF] Muztoba | Review on upgradability -A product lifetime extension strategy in the context of product service systems[END_REF] Product

The same input product but enhanced diagnostic, cleaning, requalification, replacement, disassembly and Re-Assembly Product Reconditioning [START_REF] Gaur | Closed-loop supply chain configuration for new and reconditioned products: An integrated optimization model[END_REF], [START_REF] Ijomah | 8 -Refurbishment and reuse of WEEE[END_REF] The same input product with few different components Remanufacturing [START_REF] Östlin | Product life-cycle implications for remanufacturing strategies[END_REF], [START_REF] James | Remanufactured products in closed-loop supply chains for consumer goods[END_REF], [START_REF] Hazen | Remanufacturing for the circular economy: An examination of consumer switching behavior[END_REF] Several products subassemblies and components product to be regenerated. Thus, their goal is to regenerate a product with a certain health state only once. Nowadays, CS need to be developed in a holistic vision integrating each other, explaining how to implement them, how to choose a regeneration trajectory between different possibilities and regenerate for several life cycles. In this way, the CE objectives will be achieved, i.e not lose value (recycle a product that could be reused) and preserve the product regeneration potential (regenerate by considering others CS), it's necessary to define a regeneration process in its entirety.

A
Tab. 1 shows some differences and similarities between CS. For example, several CS have common activities which could enable to pool activities and reduce the regeneration cost infrastructures. In addition, CS as reuse, repurposing, upgrading, and reconditioning expect the same input (a product) but have a different output: the same product regenerated for reuse, the same product with a different finality for repurposing etc. These features, which are sometimes close, show that the papers analyzed in literature are not sufficient to analyze CS and to choose the optimal regeneration for a product according to its health state. Indeed, how to choose a CS between these four CS, knowing that each one expects a product to be regenerated as input? What are the technical features that enable us to say whether a regenerated product is different in its finality and composition? A formalization is necessary to deepen the features identified in the literature, to determine which are the technical elements that allow to specify a regenerated product and especially to be able to position how much one CS is different from another by the formalization. A formalization based on the product requirements baseline is proposed. Indeed, it is according to the product's technical features, reflecting its health state, and the CS's capacity to regenerate a product, i.e if a product can access to a CS or not, to be regenerated.

CS characterization and comparison methodology

For regenerating an end-of-life product, a circular strategy (CS) will be chosen according to various economic, environmental, and social constraints, but mainly according to the product's health state. We must also consider the CS's capacity to regenerate the product in order to reach a desired state at the CS's output. So, the product's health state is used to categorize CS, it can be measured according to its initial product requirements.

A requirement is defined by the standard (ISO/IEC 26702:2007) as a "Statement that identifies a product or process operational, functional, or design feature or constraint, which is unambiguous, testable or measurable, and necessary for product or process acceptability". According to [START_REF] Sebok | Guide to the Systems Engineering Body of Knowledge[END_REF], a guide for systems engineering, there are several types of requirements: functional, performance...

It is interesting to choose the product requirements to characterize the CS because the requirements are built in the design phase and constitute a commune baseline for a product family. This baseline is then used in the manufacturing phase which uses this baseline to manufacture product instances. As it is illustrated in Fig. 1, when the products leave the factory, they are considered as new, and all their requirements are satisfied. During the use phase, the product's use will degrade the product's health state, and throughout time some requirements will no longer be satisfied, the product becomes a product to regenerate. Then, depending on the product requirements state, a CS is selected and a regenerated product is obtained. Throughout its life cycle, the product is defined by requirements sets that evolve. The literature has shown that some CS can regenerate a product at multiple levels, and the requirement baselines are different according to the product life phase. Thus, the formalization of a requirement baseline A l,k must be defined according to the product breakdown structure level and the product life phase with:

-The l index to define the level of the product's breakdown structure. The l index can therefore take the value in the interval [1; n], with n the level number in the product's breakdown structure (l = 1 the product level, for l ∈ [2; n -2] the different sub-assemblies levels, l = n -1 the component level and l = n the material level). -The k index, to specify the product's life phase: if the product comes from: manufacturing phase N (New), use phase r (to regenerate) or regeneration phase R (regenerated).

Each requirements set can be decomposed according to the requirement type t:

A l,k = {A l,k t } with t ={F (Functional), Q(Performance)}.
In this first work and to simplify, only the F and Q type are used. A requirement is defined as Req l,k j,t with j the requirement ID. A requirement has a textual definition that can have parameters. To illustrate, a new product A leaving the factory has a requirements baseline composed of a F and a Q requirement subset:

A l,k = {A l,k F , A l,k Q } with A l,k F = {Req 1,N
1,F :"The system must provide a rotation"} and A l,k Q = {Req 1,N 2,Q : "The nominal speed must be between 1000 and 1500 rpm"}

The requirements sets of a new product (A 1,N ) and regenerated product (A 1,R ) product are compared according to their definition and parameters. For that, The 3 operators are defined:

-≡ indicates that the 2 requirements have the same definition and the same parameters. Ex: Req 1,N 1,F ≡ Req 1,R 1,F : "The system must provide a rotation" -= indicates that the 2 requirements have the same definition but with different parameters. Ex: Req 1,N 2,Q = "The nominal speed must be between 1000 and 1500 rpm" compared with Req 1,R 2,Q = "The nominal speed must be between 800 and 1200 rpm" -̸ = indicates that the 2 requirements have different definitions. Ex: Req 1,N 1,F = "The system must provide a rotation" compared with Req 1,R 1,F = "The system must provide a translation"

To compare the requirements sets, augmented same operators are used with the same variables and the requirements number:

-≡ indicates that the 2 sets compared have the same requirements number, with the same definitions and parameters for each requirement. -= indicates that the 2 sets compared have the same requirements number, the same definitions but with different parameters for some requirements. -̸ = indicates that the 2 sets compared have different requirements number, and/or with different definitions. In this case, the operator ⊑ is added to specify whether the set, although different, has the common basic requirements of the product family. For example, the set

A 1,N F with A 1,N F = {Req 1,N 1,F } and A 1,R F = {Req 1,R 1,F , Req 1,R 2,F , Req 1,R 3,F } so, A 1,N F ̸ = A 1,R F because the product number is different but A 1,N F ⊑ A 1,R F because Req 1,N 1,F and Req 1,R 1,F
have the same definition.

To categorize CS, the following methodology uses the previous formalization:

-Step 1: The starting point of the analysis is to measure the gap between the regenerated product expected and the original product (new). So, the first step consists in comparing both requirements sets, respectively A l,R t and A l,N t for each requirement type t.

-Step 2: Consists in identifying the requirement type t that could be regenerated by the CS activities. -Step 3: Consists in comparing the requirements sets of a product to regenerated A l,r t to the regenerated product expected A l,R t for each requirement type t.

To illustrate this methodology, remanufacturing and resynthesis processes are categorized:

Step 1: the requirements set of a remanufactured product A 1,R and a resynthesized product B 1,R are compared with an original product A 1,N .

-For remanufacturing, the F requirements are identical to the original product (new

) (A 1,R F ≡ A 1,N F )
and the Q requirements have different parameters (worse performance than the original product

) (A 1,R Q = A 1,N Q ).
-For resynthesis, the requirements number and definitions are different because the product finality has changed (For t = {F, Q}:

B 1,R t ̸ = A 1,N t ).
Step 2: Both CS regenerate components and sub-assemblies and are able to recover F and Q requirements because they have the same activities. The difference is that resynthesis regenerates sub-assemblies and components from several other different products.

Step 3: Both CS receive some components and sub-assemblies, which may have requirements not satisfied, but with the CS activities satisfaction will be recovered for F and Q requirements (For t = {F, Q}: A l,r t ̸ = A l,R t and A l,r t ̸ = B l,R t ).

The following section analyzes the CS categorization and positions the CS.

Discussion

The characterization made it possible to clarify the differences and complementarities between circular strategies (CS). Indeed, by comparing the sets of F and Q requirements of a CS output product, a more relevant positioning is proposed. In addition, the CS characterization confirms that all CS do not enable a complete regeneration of all the product levels in a sustainable way. The next subsection shows the positioning.

Gap between regenerated product compared to an original product

The CS characterization showed that no CS can achieve the equivalent of an original product but with inferior performance. So the more a regenerated product has different requirements from the original product, the more it is distant.

Therefore, the CS of this regenerated product is more distant from the manufacturing process of the original (new) product. In addition, the more a regenerated product is close to an original product, the higher its health state, and the more likely it would go through a regeneration cycle again. Thus, the shortest gap for a product between an original and regenerated product will be preferred when choosing a CS.

Reuse, reconditioning, remanufacturing and recycling allow to get closer to the original requirements with the difference that the Q requirements have parameters representing their performance intervals lower than the original ones

(A l R Q = A l N Q ).
Thus, to decide which of these four CS used, it is necessary to look at the regeneration activities. It is more advantageous to reuse a product because it requires fewer activities and the product level (l) is the highest (1). However, to be reused, the incoming product must be at product level and all its functional requirements must be satisfied.

For upgrading, the objective is to improve the product by adding, deleting or improving the requirements. Thus, an updated product has different requirements set than the original one, but with the initial functional requirements common to the original product (A

1 N F ⊑ A 1 R F ).
Other CS such as repurposing and resynthesis completely change the product's finality, which further differentiates the requirements of these regenerated products from the original product (B 1 R F ̸ = A 1 N F ). Finally, energy recovery and landfill are even further away, as the output is energy or waste.

An analysis of holistic approach

To implement a complete circular economy (CE) it is necessary to regenerate a product at all its levels. From a sustainable development point of view it is obvious that favoring short regeneration loops with few activities with the highest product level like reuse is more advantageous. On the contrary, recycling a product that still has functional and reusable sub-assemblies is a significant loss.

The analysis of all circular strategies (CS) input shows that it is possible that a product does not fulfill any condition to access a CS. For example, if there is a product with a requirement set that does not have the right requirements satisfied to access product-level CS, or sub-assembly-level CS then the product will be regenerated for its material whereas probably several sub-assemblies and components are still functional. A need for a holistic approach in the design phase becomes important in order to plan the different regeneration and avoid skipping regeneration levels.

Thanks to the CS characterization and the expected input requirements (image of the product health state to regenerate) it is possible to position CS by specifying supply chains for the product flow to be regenerated. For example, to avoid switching from reuse to recycling without skipping intermediate CS. Four groupings are proposed:

-Product from use phase: The product can be sent to reuse, upgrading and reconditioning. -Product, sub-assemblies and components from reconditioning: The product can be sent to repurposing and sub-assemblies/components to remanufacturing or resynthesis. -Sub-assemblies and components from remanufacturing: The subassemblies and components are either sent to other supplier regeneration cycles that can regenerate them or they are sent to recycling. -Material from recycling: The material considered as waste is used as an energy source (energetic valorization) or landfilled if this is not possible.

Fig. 3 illustrates these explanations by positioning CS in a holistic approach. To simplify the figure, external cycles of different products that supply some CS with elements to regenerate have not been added. In addition, fig. 3 could be instantiated for each element disassembled. Indeed, sub-assemblies are potentially the finished product of a sub-supplier. By defining the access conditions of each CS in adequacy with the CS regeneration capacities and the expected result, it is possible to constrain the regeneration paths to avoid losing value and preserve the regeneration potential of a product throughout its life cycle.

Conclusion

According to the need to adopt a circular economy (CE) and the problems highlighted in literature, circular strategies (CS) are implemented in a punctual/individual way and the processes are mostly artisanal, this paper proposes to use a holistic vision to define the regeneration process which enables to support the CE. However, in this assumption, it would be necessary to analyze CS to study their differences and complementarities. So technical CS features from review are identified in section 2 and section 3 proposes a formalization to complete the CS characterisation to specify the CS more precisely, to be able in section 4, to position CS according to their technical features. Finally, a possible technical regeneration path is proposed to avoid losing value and preserving the regeneration potential of a product throughout its life cycle. So, this first characterization work raised several questions and perspectives: This first technical and systematic characterization of CS is a beginning. Indeed, in order to get a CS holistic approach, complementary characterizations from an environmental, economic and social point of view should complete this work. By integrating these elements into the CS categorization it will be possible to choose the optimal CS for a product to be regenerated, with a multi-criteria decision-making system. This system will need to be fed with complementary data (product, market and CS features, ...) [START_REF] Vanson | End-of-Life Decision making in circular economy using generalized colored stochastic Petri nets[END_REF].

This paper promote the need of a holistic approach to define a regeneration process and implement multiple CS. We therefore propose in the design phase to develop, in addition to the product, a regeneration system that will support the product family throughout the product life cycle. Thus, a product, its manufacturing system and its regeneration system must be co-designed to consider their interactions. So, the CS characterization in Section 3 can be used to determine the outputs, activities, and input conditions of the CS to build the regeneration system. Through this co-engineering, it would therefore be possible to avoid skipping regeneration loops and implement a realistic CE.

Fig. 1 .

 1 Fig. 1. Origin of the baseline requirements and the formalization method illustration.

Fig. 2

 2 Fig. 2 illustrates the above explanations by positioning CS according to the comparison gap between a regenerated product and an equivalent new product. In addition, CS are positioned according to what the CS activities can regenerate.

Fig. 2 .

 2 Fig. 2. CS positioning according to the comparison gap between a regenerated product with an equivalent new product and the regeneration level process.

Fig. 3 .

 3 Fig. 3. CS positioning synthesis to avoid value loss and preserve the regeneration potential of a product throughout its life cycle.

Table 1 .

 1 CS technical features in the literature

			new product composed	diagnostic,	cleaning,
			with different components	requalification, replace-
				ment,	disassembly,
				Re-Assembly	and
				reworking
	Resynthesis	Several sub-assemblies	A new product but now for				Sub-assemblies	/
	[8], [9]	and components from	another finality and com-				Components
		different product fami-	posed with different compo-
		lies	nents from different product
			families
	Recycling [5],	Several products mate-	Recycled material	diagnostic,	Sort	and	Material
	[6], [16], [3]	rial		Separate
	Energetic Val.		Energy	Combustion or Metha-	Wastes
	[17]			nization
	Landfill [24]		Wastes	Stock			No


analyze mathematically, therefore it is hard to guarantee a precise formation control.

In the leader following approach [START_REF] Sanchez | Sliding mode control for robot formations[END_REF], [START_REF] Li | Backstepping based multiple mobile robots formation control[END_REF], one of the robots is designated as the leader, with the rest being followers. The follower robots need to position themselves relative to the leader and to maintain a desired relative position with respect to the leader. In order, to prescribe a formation maneuver, we need only to specify the leader's motion and the desired relative positions between the leader and the followers.

When the motion of the leader is known, the desired positions (desired distance and orientation) of the followers relative to the leader can be achieved by local control law on each follower. Therefore, in a certain sense, the formation control problem can be seen as a natural extension of the traditional trajectory-tracking problem.

Among all the approaches to formation control reported in the literature, the leader-following method has been adopted by many researchers [START_REF] Ren | A Decentralized scheme for spacecraft formation flying via the virtual structure approach[END_REF], [START_REF] Egerstedt | Formation constrained multi-agent control[END_REF], [START_REF] Sugihara | Distributed algorithms for formation of geometric patterns with many mobile robots[END_REF], [START_REF] Li | Backstepping based multiple mobile robots formation control[END_REF], [START_REF] Luca | Control of wheeled mobile robots: An experimental overview[END_REF]. In this method, each robot takes another neighboring robot as a reference point to determine its motion. The referenced robot is called a leader, and the robot following it called a follower. Thus, there are many pairs of leaders and followers and complex formations can be achieved by controlling relative positions of these pairs of robots respectively. This approach is characterized by simplicity, reliability and no need for global knowledge and computation.

In this paper, we will develop a method based on the leaderfollowing approach to investigate formation control problem in a group of nonholonomic mobile robots. For this purpose, we design a new controller based on fuzzy logic to drive a fleet of mobile robots in a leader-follower configuration.

The rest of this paper is organized as follows. First motion modeling is revealed. Then, the method of path following used by the leader robot is exposed. After that, the architecture of the fuzzy controller is described. We conclude the paper by some simulation and results.

II. MOBILE ROBOT MODELING

The mobile robots considered in this study are the popular wheeled mobile robots of unicycle type, shown in Fig. 1. The configuration of the robot denoted by

π θ π ≺ ) (t ≤ -
its orientation relatively to the x-axis. The linear and angular velocities are respectively Abstract-In this article we address the problem of mobile robot formation control. Indeed, the most work, in this domain, have studied extensively classical control for keeping a formation of mobile robots. In this work, we design an FLC (Fuzzy logic Controller) controller for separation and bearing control (SBC). Indeed, the leader mobile robot is controlled to follow an arbitrary reference path, and the follower mobile robot use the FSBC (Fuzzy Separation and Bearing Control) to keep constant relative distance and constant angle to the leader robot. The efficiency and simplicity of this control law has been proven by simulation on different situation.

Keywords-Autonomous mobile robot, Formation control, Fuzzy logic control, Multiple robots, Leader-Follower.

I. INTRODUCTION

FORMATION control of multiple autonomous mobile robots and vehicles has been studied extensively over the last decade for both theoretic research and practical applications. Various approaches and strategies have been proposed for the formation control of multiple robots. Multi-robot coordination methods can be partitioned into three classes approaches: virtual structure approach, behavioral approach and leader follower approach. Each of them has several advantages and weaknesses.

The virtual structure approach treats the entire formation as a single virtual rigid structure [START_REF] Kar-Han Tan | Virtual structures for high precision cooperative control[END_REF]- [START_REF] Egerstedt | Formation constrained multi-agent control[END_REF]. Desired motion is assigned to the virtual structure as a whole, as a result which will trace out trajectories for each robot in the formation to follow. It is easy to prescribe the behavior of the whole group, and maintain the formation very well during the maneuvers. The main disadvantage of the current virtual structure implementation is the centralization, which leads a single point of failure for the whole system.

By behavior based approach, several desired behaviors are prescribed for each robot, and the final action of each robot is derived by weighting the relative importance of each behavior.

Possible behaviors include obstacle avoidance, collision avoidance, goal seeking and formation keeping [START_REF] Egerstedt | Formation constrained multi-agent control[END_REF]- [START_REF] Yamgachi | A Cooperative Hunting Behavior by Mobile Robot Troops[END_REF]. The limitation of behavior-based approach is that it is difficult to Abdelouahab Bazoula is with Military Polytechnic School. P.O. Box 17 EMP M1 Bordj-El-Bahri 16111 Algiers, Algeria (e-mail: abdelouaha.bazoula@gmail.com).

Hichem Maaref is with Evry Val D'essone University, IBISC LSC-LAMI CNRS-FRE 287340 rue du Pelvoux 91020 Evry Cedex (e-mail: hichem.maaref@iup.univ-evry.fr).

Fuzzy Separation Bearing Control for Mobile Robots Formation

A. Bazoula, and H. Maaref ) (t v and ) (t ω . The equation of motion of the mobile robot is given by: 1), the mobile robot behavior is subject to an additional nonholonomic constraint:

) ( ) ( ) ( sin ) ( ) ( ) ( cos ) ( ) ( t t t t v t y t t v t x ω = θ θ = θ = (1) ) (t v
0 ) ( cos ) ( ) ( sin ) ( = θ - θ t t y t t x (2)
This constraint means that the robot can not move in the direction of the wheel axis (i.e. y). )

) ( ), ( t y t x r r defined in a time interval [ ] T t , 0 ∈
, we can derive a control law. From the inverse kinematics the robot inputs are calculated which drive the robot on a desired path. The needed robot inputs, tangential velocity r v and angular velocity r ω are calculated from the reference path. The tangential velocity reads:

) ( ) ( ) ( 2 2 t y t x t v r r r + ± = (3)
Where "+" for the forward direction and "-" for inverse direction. The tangent angle of each point on the path can be determined as:

( ) π + = θ k t x t y t r r r ) ( ), ( 2 arctan ) ( (4)
Where 1 , 0 = k defines the desired drive direction (0 for forward and 1 for reverse). The reference angular velocity can be obtained by deriving previous equation [START_REF] Luca | Control of wheeled mobile robots: An experimental overview[END_REF], [START_REF] Oriolo | WMR control via dynamic feedback linearization: design, implementation, and experimental v validation[END_REF]:

) ( ) ( ) ( ) ( ) ( ) ( ) (

IV. CONTROL DESIGN FOR PATH FOLLOWING

For solving the tracking control problem, the following global change of co-ordinates was proposed by Kanayama et al. [START_REF] Kanayama | A stable tracking control scheme for an autonomous mobile robot[END_REF] (Fig. 2). In the frame of real robot, the error between controlled robot and reference path can be expressed as: Considering the robot kinematics (1), the error dynamics of the mobile robot can be derived from the time derivative of the above equation as [START_REF] Sanchez | Sliding mode control for robot formations[END_REF] where 1 r u is the feedforward tangential velocity and 2 r u is feedforward angular velocity. The robot inputs, regarding relation [START_REF] Sugihara | Distributed algorithms for formation of geometric patterns with many mobile robots[END_REF], can be expressed in the following form: By linearizing [START_REF] Luca | Control of wheeled mobile robots: An experimental overview[END_REF] around the operating point ( )

⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ θ - θ - - ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ θ θ - θ θ = ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡
⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ - - - + ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ 2 1 1
⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ + ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ + ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ - = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 2 1 1 3
2 1 3 2 1 , 0 v v e e e = = = =
we get the following linear system:

v e u u u e r r r Δ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ + Δ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ - = Δ 1 0 0 0 0 1 . 0 0 0 0 0 0 1 2 2 (10)
This system can be written under space state form as: . The resulting control can be schematized as indicated in Fig. 3. The control law, according to [START_REF] Klančar | Mobile robot control on a reference path[END_REF], can be written as:

u B q A q Δ + Δ = Δ . ( 11
⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ - - - = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡
This control can be verified as stable, and can make convergence of errors [START_REF] Klančar | Mobile robot control on a reference path[END_REF].

V. MODELING OF LEADER-FOLLOWER FORMATION

Let us consider the situation shown in Fig. 4. A leader and a follower robot are denoted as l R and f R , respectively.

According to the notation defined in Section II, the states and the inputs of l R and f R are newly denoted as ) , , (

l l l y x θ , ) , , ( f f f y x θ ) , ( l l v ω and ) , ( f f
v ω , where the subscript "l" and "f" mean leader and follower, respectively. The equations of motion of both robots are given by [START_REF] Kar-Han Tan | Virtual structures for high precision cooperative control[END_REF]. The relative distance between the leader and the follower robot is denoted as

fl lf d d =
and the relative angles from their heading are denoted as lf θ , They are given by: ( ) ( ) For translation velocity and angular velocity controls, two two-input-single-output FSBC are adopted, respectively. Let the input variables of the FSBC be defined as:

l f lf f l f l lf y y x x d θ θ θ - = - + - = 2 2 (14) l θ f θ f v Y X l v ) , , ( l l l l y x R θ lf d ) , , ( f f f f y x R θ
) ( ) ( ) ( k d k d k e act des - = ( 15
) ) 1 ( ) ( ) ( - - = Δ k e k e k e ( 16
) ) ( ) ( ) ( k k k l f θ θ θ - = ( 17
) ) 1 ( ) ( ) ( - - = Δ k k k θ θ θ (18)
where des d is the desired distance between leader and the follower robot. We want to design the FSBC for the follower mobile robot such that it can pursue the target mobile robot within a constant distance. The fuzzy control rules can be represented as a mapping from input linguistic variables e , e Δ , θ and θ Δ to output linguistic variables v and ω as follows:

)

) ( ), ( ), ( ), ( ( FSBC ) 1 ( k k k e k e k u θ θ Δ Δ = + ( 19
)
where u includes the translation and angular velocity.

Because translation and angular velocities of the mobile robot can be driven individually, thus we can decompose (19) as follows:

)

) ( ), ( ( FSBC ) 1 ( k e k e k v Δ = + (20) )) ( ), ( ( FSBC ) 1 ( k k k θ θ ω Δ = + (
v u = , e E = , e dE Δ = , case ω = u , θ = E , θ Δ = dE
) They all are decomposed into seven fuzzy partitions, such as: negative big (NB), negative medium (NM), negative small (NS), zero (ZE), positive small (PS), positive medium (PM), and positive big (PB).

Since each input is divided into seven fuzzy sets, 49 fuzzy rules for speed control and steering angle control must be determined, respectively. Following the FSMC concept [START_REF] Tzafestas | A simple robust sliding-mode fuzzy logic controller of the diagonal type[END_REF]- [START_REF] Li | Switching-type fuzzy sliding mode control of a cart-pole system[END_REF], a diagonal type rule table is adopted (see Table 1). The FSMC provides control action to drive state trajectories toward a sliding surface (in fact, the sliding line in this application) in the state-space, and to maintain the state trajectories sliding on the sliding surface until stable equilibrium state is reached. In this paper, we first have to choose the sliding surface that represents the control purpose.

Fig. 1

 1 Fig. 1 Coordinates system

Fig. 2

 2 Fig.2The new error coordinates

  inputs from the closed loop.

  ) and can be verified as controllable because Kalman controllability matrix is full rank 3

Fig. 3

 3 Fig. 3 Architecture of schematic control

Fig. 4

 4 Fig. 4 Leader-follower configuration

Fig. 5 (

 5 Fig. 5 (a) Membership function of e (b) Membership function of e Δ (c) Membership function ofθ (d) Membership function of θ Δ (e) Membership functions of v and ω

  The sliding surfaces for angular velocity control and angular velocity control are defined as e is implemented by the weighted average method.

Fig. 7

 7 Fig. 7 Leader Robot goes on reference path that has initially its curvature equal to -0.05 and change the curvature to 0.05 at time equal to 50s

The simulation results for several different cases are listed as below in Fig. 6 to Fig. 7. In each figure, the three plots are the simulation results of the robot team evolution, translation velocity of the leader, the angular velocity of the interdistance error, and angular error form the top to bottom respectively.

Fig. 6 shows the case when the reference path is a straight line with a slope of 0.2. The leader goes along a straight line with a constant linear speed (2m/s) and constant angular speed (0rad/s).

VIII. CONCLUSION

In this paper, we present a new controller based on fuzzy logic for the leader following formation of multiple nonholonomic mobile robots. For keeping the distance and bearing between two consecutive mobile robots in desired values, we design two controllers the first for translation velocity its inputs are distance and its derivative, the second one is for angular velocity its inputs are the difference between the mobile robots orientations and its derivative. Successful simulation have been conducted for various situations and showed the efficiency of the proposed approach.

Authors' future work will be focused on comparison with classical techniques, experimental verification of presented approach and the optimization of the fuzzy logic in real time.


Derrick Kondo

Bahman Javadi

Alexandru Iosup

Dick Epema

The Failure Trace Archive: Enabling Comparative Analysis of Failures in Diverse Distributed Systems

With the increasing functionality and complexity of distributed systems, resource failures are inevitable. While numerous models and algorithms for dealing with failures exist, the lack of public trace data sets and tools have prevented meaningful comparisons. To facilitate the design, validation, and comparison of fault-tolerant models and algorithms, we have created the Failure Trace Archive (FTA) as an online public repository of availability traces taken from diverse parallel and distributed systems. Our main contributions in this study are the following. First, we describe the design of the archive, in particular the rationale of the standard FTA format, and the design of a toolbox that facilitates automated analysis of trace data sets. Second, applying the toolbox, we present a uniform comparative analysis with statistics and models of failures in nine distributed systems. Third, we show how different interpretations of these data sets can result in different conclusions. This emphasizes the critical need for the public availability of trace data and methods for their analysis.

I. Introduction

With the increasing functionality, complexity, and scale of distributed systems, resource failures are inevitable. For scientific applications, failures can result in frequent performance degradation or in the worst case, premature termination of execution, or data corruption and loss. For commercial applications, failures can cause the violation of service-level agreements, and cause a devastating loss of customers and revenue [START_REF]Failure Rates at Google[END_REF].

A plethora of models and algorithm exist for analyzing, predicting, and resolving failures [START_REF] Bolosky | Feasibility of a Serverless Distributed file System Deployed on an Existing Set of Desktop PCs[END_REF], [START_REF] Schroeder | A large scale study of failures in high-performance-computing systems[END_REF], [START_REF] Kondo | Characterizing resource availability in enterprise desktop grids[END_REF], [START_REF] Iosup | On the dynamic resource availability in grids[END_REF], [START_REF] Rood | Multi-state grid resource availability characterization[END_REF], [START_REF] Andrzejak | Ensuring collective availability in volatile resource pools via forecasting[END_REF], [START_REF] Andrzejak | Predicting Machine Availabilities in Desktop Pools[END_REF]. At best, these models and algorithms are evaluated using failure traces of a single or limited number of systems. The trace data sets or methods or models based on them are rarely publicly available. Moreover, studies based on failure traces often use traces of different systems. The result is the fragmentation of failure models and faulttolerant algorithms, as their comparison or cross-validation on different types of systems is difficult if not impossible.

To remedy this situation, we have created the Failure Trace Archive (FTA), which comprises public availability traces of parallel and distributed systems, and public tools for their analysis. The community archive approach has been recognized as useful for sharing data in a common format, and has been employed by several communities in the computing domain. The parallel computing community has built the Parallel Workloads Archive [START_REF] Feitelson | Parallel Workloads Archive[END_REF], the grid computing community has created the Grid Workloads Archive [START_REF] Iosup | The grid workloads archive[END_REF], for instance. Efforts such as the Repository of Availability Traces [START_REF] Godfrey | Repository of Availability Traces[END_REF], the Computer Failure Data Repository [START_REF] Schroeder | The computer failure data repository[END_REF], and the Desktop Grid Failure Traces [START_REF] Kondo | Characterizing resource availability in enterprise desktop grids[END_REF] have led to making failure-related data public, but did not establish the premise of a community archive for distributed computing systems. In particular, they did not build a common format for storing failure-related data, and failed to obtain and publish a sufficient number of data sets. In contrast to these early efforts, our main contribution is threefold:

• We design a public failure trace archive, creating a standard format for failure traces, and a toolbox that facilitates comparative trace analysis (Section III).

• Using the toolbox, we present uniform statistical analyses and failure models for nine diverse distributed systems (Section IV);

• We show that differences in the interpretation of failures can change significantly the models and statistics derived from traces (Section V).

II. Background

Throughout this work, we follow the basic concepts and definitions associated with system dependability as summarized by Avizienis et al. [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF]. The basic threats to reliability are failures, errors, and faults occurring in the system. A failure is an event in which the system fails to operate according to its specifications. A failure is observed as a deviation from the correct state of the system. We term the continuous period of a service outage due to a failure as an unavailability interval. A continuous period of availability is called an availability interval.

An error is part of the system state that may lead to a failure. Some errors may not be visible from the outside of the system, that is, they may not reach the external state of the system and thus cause failures; such errors are said to be dormant. Errors that do cause failures are said to be active. The root cause of an error is a fault.

III. Overview of the Failure Trace Archive

The Failure Trace Archive (FTA) can be used in many ways. First, the FTA allows the comparison and crossvalidation of a fault-tolerant model or algorithm across identical trace data sets. Second, it allows the evaluation of the generality of a model or algorithm across different types of resources (in terms of reliability or user base, for example). Third, it allows for the evaluation of the generality of a failure trace, i.e., to determine whether measurements are biased to a particular platform or middleware. Fourth, it allows for the determination of which trace data set is most interesting or applicable for a given algorithm or model. Fifth, it allows for the analysis of the evolution of availability in different systems across long timescales. Sixth, it allows for the integration of failure models with other types of models (such as workloads). Seventh, it facilitates the incorporation of traces with a common format into fault simulators or emulators for model or algorithm evaluation.

A. Archive Format

In our experience, the majority of time in measurement and modeling studies is spent in parsing and interpreting the measurements. To accelerate this processing and analysis for others, we have parsed and interpreted 9 diverse distributed systems in a standard format. Here we describe the rationale of the format.

The majority of our collection of traces record times of failures for resources, and contain an alternating time series of availability and unavailability intervals. As such, our format is resource-centric (versus job-centric or usercentric) with respect to failures of individual nodes or components of nodes, such as memory, CPU, or hard disks. We believe the format is also applicable to failures of services deployed on top of resources. However, our format does not explicitly describe higher-level failures, such as job failures, though potentially the FTA format could be extended for this type of failure or perhaps combined with the Grid Workload Archive format. Measuring and understanding the relationship between lower-level failures (for example, of nodes or components) to higher-level failures (for example, jobs) is an area for future research. The trace format is organized hierarchically as follows: Platform → Node → Component → Event Trace. Figure 1 depicts the structure of the FTA, where boxes represent database tables. We summarize the meaning of each table below. Table names are shown in bold.

• A platform contains a set of nodes. Examples of a platform include desktop PC's at Microsoft, or nodes in the LANL clusters.

• A node contains a set of components, which is a software module or hardware resource of the node. Each node can have several components (e.g. CPU speed, available memory, client availability), each of which has a corresponding trace.

• The node_perf describes the node performance, as measured through benchmarks, for example.

• A component describes attributes of a software module or hardware resource of a node.

• A creator is the person responsible for the trace data set. This table stores details about data copyright, and about projects and published material that use the data.

• An event_trace is the trace of an event, with all of corresponding timing information (e.g. start and end times).

• The event_state is the state corresponding to an event_trace. For example, for CPU availability, the event_state could be the idleness of the CPU. For host availability, it could be the monitoring information associated with the event.

In addition, we have codes that correspond to different types of components (for example, memory, CPU, hard disk), events (for example, availability or unavailability), and event reason codes (for example, disk crash and CPU overheating).

The best test of a format is its application to real data sets for different types of systems with different types of failures measured in different ways. We applied this format to nine systems ranging from desktops on the Internet to supercomputing clusters. The types of failures included host, CPU, and even service failures. These failures were measured using a variety of methods, such as periodic probing, event notification, load measurement, and even human observation. Given that all of these data sets could be presented in this format with ease, we believe the format is good first step towards a standard. To anticipate future extensions of the format, we have several generic tables with double and string field that can contain additional new information should it arise.

B. FTA Toolbox

We implemented a FTA toolbox to facilitate the comparative analysis of failure traces (see Figure 2). The toolbox is implemented in Matlab, and uses several opensource Matlab packages, such as the Mysql and DataTable packages.

The toolbox takes as input four functions for initializing, querying, processing, and finalizing the data analysis. The initialization and query stages allow one to extract the necessary data from traces located in the MySQL database into Matlab in-memory data structures. By contrast to loading entire data sets into memory from large files, this method allows one to extract into memory only the data that is needed for processing.

Initialization and querying is separated from processing to allow expensive initialization queries to be conducted only once, after which any amount of processing can be done. Also this separation allows the same initialization and queries to be used for many different processing functions. This facilitates code reuse.

The results of initializing and querying are then passed to the processing function. This function is run across each of those results. The processing output is then fed into the finalize function, which can produce tables automatically in latex, HTML, text, and wiki formats using the DataTable module. All graphs and tables in Sections IV and V were produced using the FTA toolbox.

C. Trace Data Sets

The FTA currently has nine formatted data sets, which are listed in Table I, and seven others currently with raw data only. We describe each formatted data set and measurement method briefly. lanl05 is a data set of 22 HPC systems at Los Alamos National Laboratory. It contains a record for every failure that happened in these systems as well as the root cause [START_REF] Schroeder | A large scale study of failures in high-performance-computing systems[END_REF]. The g5k06 data set is a trace of a computational grid platform in France (i.e., Grid'5000) which consists of 9 sites, 15 clusters and more than 2,500 processors [START_REF] Iosup | On the dynamic resource availability in grids[END_REF]. The data was collected by periodic inspection and logging of each node's status through the grid middleware called OAR. The microsoft99 data set contains log files of 51,663 desktops PCs at Microsoft Corporation where their reachability was determined with a ping every hour [START_REF] Bolosky | Feasibility of a Serverless Distributed file System Deployed on an Existing Set of Desktop PCs[END_REF]. The data set of websites02 was derived from probe-based measurements where a single machine at Carnegie Mellon sent a HTTP file request to web servers periodically every 10 minutes [START_REF] Bakkaloglu | On correlated failures in survivable storage systems[END_REF]. pl05 consists of trace data measured between all pairs of PlanetLab nodes using pings every 15 minutes [START_REF] Stribling | Planetlab all paris ping[END_REF]. The ldns04 data set includes the probe results of 62,201 local DNS servers where the inter-arrival time of the probes followed an exponential distribution with mean of one hour [START_REF] Pang | Availability,usage, and deployment characteristics of the domain name system[END_REF]. The overnet03 data set is a probe-based measurement conducted over the Overnet peer-to-peer file-sharing system [START_REF] Bhagwan | Understanding Availability[END_REF]. In this data set, the availability of 3,000 hosts was checked every 20 minutes. The nd07cpu data set contains traces recorded by Condor from the desktop systems at the University of Notre Dame [START_REF] Rood | Multi-state grid resource availability characterization[END_REF]. The data set is comprised of timestamped CPU load and idle times of each system, recorded every 16 minutes. Finally, the skype06 data set is collected by application-level pings of nodes in the Skype superpeer network, every 30 minutes [START_REF] Guha | An experimental study of the skype peer-to-peer voip system[END_REF].

IV. Analysis of FTA Traces

In the following, we analyze data sets of FTA in two steps. First, we inspect the basic statistics of the traces. Second, we fit distributions for modeling failures in terms of probability distributions of availability and unavailability intervals.

A. Global Statistics

Statistics of availability and unavailability intervals for all data sets are listed in Tables II and III respectively, where the time unit is in hours. The statistics in the tables are mean, trimmed mean, median, standard deviation (std), These tables have three types of descriptive statistics. Statistics of the first type (mean, median, trimmed mean) reflect the central tendency of the distributions. Statistics of the second type (CV, IQR, minimum, maximum) measure the spread of the distribution. Statistics of the third type (kurtosis, skewness) reflect the shape of the distribution.

The results reveal that the ratios between the mean and the median for availability and unavailability intervals are quite different for each data set. This indicates that single parameter distributions might not be a good option for the failure model. This could be confirmed by the skewness and kurtosis values that show the availability distributions are right-skewed and long-tailed. Moreover, the unavailability distributions are highly right-skewed and longer tail than the availability distributions.

Additionally, the unavailability intervals have more variability than availability intervals due to higher values of coefficient of variance. Also, analysis of the trimmed mean (the mean value after discarding 10% of extreme values) confirmed that unavailability intervals have greater variability. So, we may need distributions with higher degrees of freedom, e.g., phase-type distributions, to model the unavailability for these data sets.

B. Failure Models

We refer to the distribution of availability and unavailability intervals as the failure model. The cumulative distribution functions (CDFs) of availability and unavailability intervals are plotted in Figure 3(a) and Figure 3(c), respectively. The difference of data sets in terms of distribution is shown in these figures.

We also conducted parameter fitting for various distributions, namely the Exponential, Weibull, Pareto, Lognormal and Gamma distributions. The fitting was done using maximum likelihood estimation (MLE). We adopted V for availability and unavailability distributions, respectively. The p-value shown is the average of 1000 p-values, each of which was computed by selecting 30 samples randomly from a data set. This is a standard method for computing p-values as described in [START_REF] Nurmi | Modeling Machine Availability in Enterprise and Wide-area Distributed Computing Environments[END_REF], [START_REF] Javadi | Mining for statistical availability models in large-scale distributed systems: An empirical study of seti@home[END_REF] when the number of samples is high. These results reveal that for availability/unavailability distribution we do not have a heavy-tail distribution as the p-values for Pareto are very low. The only exceptions are the distribution of unavailability of overnet03 and microsoft99, which are close to being a heavy-tail distribution. It is worth noting that the AD test is more sensitive to the tail than the KS test. This explains the difference between p-values of the two GOF tests, especially when we have a heavy-tailed data set.

The exponential function seems to be far from the underlying distributions. However, it could be a good fit for the availability distributions of microsoft99, overnet03 and skype06 and the unavailability distributions of microsoft99, ldns04, and skype06 as well. So, the skype06 data set with the exponential failure model is a good candidate to evaluate Markov models for prediction of host availability/unavailability. However, we observed that the resolution of the measurement method could have caused the exponential distribution to be a good fit. For example, the overnet03, skype06, and microsoft99 systems were measured using probes with periods of 20 minutes, 30 minutes, and 1 hour, respectively. As such, there are no (un)availability intervals less than this length, and in the CDF's shown in Figure 3, there are spikes at those period lengths.

Nevertheless, for all data sets, the Gamma distribution is a good fit for the failure model as the p-values are relatively high. This distribution is a very flexible distribution function and can be adopted for analytical Markov model as well [START_REF] Feitelson | Workload Modeling for Computer Systems Performance Evaluation[END_REF].

Additionally, the results of the GOF tests show that the best fit for all data sets are either the Weibull or Log-Normal distributions. As expected from our statistical analysis, the failure model tends to be a long-tailed distribution. However, a few data sets such as g5k06 and pl05 do not have a perfect fit for the unavailability distribution.

One possible answer would be the relation of the model with the system architecture. For instance, as the g5k06 platform has 15 clusters in 9 geographically distributed sites, each cluster could have its own separate model as proposed in [START_REF] Iosup | On the dynamic resource availability in grids[END_REF]. Moreover, as mentioned before, we need distributions with more degrees of freedom such as the hyper-exponential to model the unavailability distributions. Table VI reports the parameter values of different distributions for the availability and unavailability intervals of all data sets under study. For the availability distributions, we analyze the hazard rate, i.e., the probability of the next failure with respect to time from the last failure. For the data sets that Weibull or Gamma distributions are good fit, the hazard rate is decreasing. Recall that for such distributions if the shape parameter is less than one, i.e., k < 1, then we have a decreasing hazard rate. That means if the systems do not have any failure for long time (longer availability duration) the probability of a failure occurring in the near future decreases. In other words, a decreasing hazard rate could be interpreted as more stability of resources over time [START_REF] Nadeem | Characterizing, Modeling and Predicting Dynamic Resource Availability in a Large Scale Multi-Purpose Grid[END_REF]. The only hazard rate that is alarming is with overnet03 where the shape parameter is close to one.

Finally, to have an overall view of the data set characteristics, we present a qualitative comparison of them in Table VIII. The first two parameters are at the node-level, and the other two parameters are at the system-level. The volatility (V ) is dependent on the failure rate of each node in the system. The availability (A) is the percentage of time that a node is working properly. The measurement (M ) and the scale (S) is the duration of measurement and scale of the system, respectively. The failure model is the tail behavior of availability and unavailability distributions. For each item we assign three different levels as described in Table VII.

For the failure model, we observed that all best fits are long-tailed distributions. However, for the qualitative table, we applied another classification based on the pvalues of the KS and AD tests with a significance level of 0.05. If a data set has acceptable p-values for Pareto or Exponential distribution, the failure model would be heavy-tailed or short-tailed, respectively. Otherwise, the failure model could be classified as long-tailed (for more details about tail behavior, see [START_REF] Feitelson | Workload Modeling for Computer Systems Performance Evaluation[END_REF]). Table VIII could provide a good overview of the data sets' characteristics for researchers that want to use real traces for their research.

V. Differences of Interpretation

To emphasize the critical need for public data and analysis methods, we give three examples of where differences of trace interpretation result in differences of the derived models. In particular, we show that differences of interpretation can change dramatically the distribution of failures in terms of passing statistical goodness-of-fit tests and the fitted distributions.

We choose three systems, namely lanl05, g5k06 and nd07cpu, where the time of failures can be interpreted differently. On close examination of the lanl05 trace, we found that there are overlapping unavailability intervals. This overlapping of intervals was especially evident in System 16. This system is a cluster of 16 NUMA-based nodes, each of which has 128 processors and 4 NICs.

In some cases, one failure interval completely subsumed another. In other cases, the start time of a failure interval A was greater than the start time of another interval B but less than the stop time of interval B. Moreover, the stop time of A was greater than the stop time B. We believe these intervals might be the result of human error, as the data was manually recorded.

The authors that first described this data set in [START_REF] Schroeder | A large scale study of failures in high-performance-computing systems[END_REF] did not detail the cause of these intervals nor how or why these intervals were interpreted in a certain way. Comparing our statistics of the failures with those in [START_REF] Schroeder | A large scale study of failures in high-performance-computing systems[END_REF], we "reversed engineered" the interpretation, and found that the authors used the union of failures intervals having ambiguity. For comparison, we interpret the failure intervals in System 16 differently and optimistically using their intersection, calling the resulting post-processed data set lanl0516B.

We also found different possible interpretations of the g5k06 trace. In the raw trace, the states of nodes are given as available, unavailable, suspected, or dead. Suspected is a state (given mostly automatically) when a node does not behave well according to OAR, the Grid'5000 node manager. The "bad" behavior is detected through many tools, such as the node monitor finaud, the jobs monitor sarko, and the internal OAR state manager NodeChangeState. Pessimistic trace processing would interpret the suspected state as a failure, and assume unavailability. An optimistic trace processing would interpret the suspected state as a fault but not a failure, and assume availability. The former interpretation is used in the g5k06 trace described in previous sections and in [START_REF] Iosup | On the dynamic resource availability in grids[END_REF]. We denote the latter interpretation as g5k06B.

The nd07cpu trace is the third data set for which there is room for interpretation. The trace is comprised of host idle times and CPU loads as well. Defined in [START_REF] Rood | Multi-state grid resource availability characterization[END_REF], the original definition of CPU availability is when the host is idle without any user for more than 15 minutes, and CPU load (which could be independent of the user) is less than 50%. We relaxed this condition to lengthen the CPU availability time by including the time when a user is present (which in turns would cause zero idle time) and CPU load is less than 10%. That is a reasonable definition of CPU availability as the guest job could still be run on the host without interfering significantly with local jobs. The data set with this latter interpretation is referred to as nd07cpuB.

In the following, we present the analysis of different failure interpretations for the aforementioned data sets. First, we compare the empirical distributions graphically. Second, we fit several distributions to each of the data sets, and compare the fitted distributions for each pair of data sets. We compare the fitted distributions statistically with p-values, and then graphically with qq-plots. The Grid Observatory [START_REF] Loomis | The grid observatory[END_REF] provides numerous data sets. However, the repository is currently limited to EGEE resources, and only raw data is provided without a common format nor scripts for parsing or analysis. The Computer Failure Data Repository [START_REF] Schroeder | The computer failure data repository[END_REF] provides traces to several supercomputers and clusters. However, no standard format is defined, and the trace data is in raw format only. The Repository of Availability Traces [START_REF] Godfrey | Repository of Availability Traces[END_REF] contains traces for 5 distributed systems in a common format, and scripts used for parsing the raw data. While a standard format is defined, we believe this format excludes critical information for capturing a range of failure types and systems. For example, the format does not contain causes of failures, the creator, or the component type. The Desktop Grid Trace Archive [START_REF] Kondo | Characterizing resource availability in enterprise desktop grids[END_REF] is focused specifically on desktop grids. A generic failure format was not provided, nor were traces of other types of distributed systems.

The Parallel Workloads Archive [START_REF] Feitelson | Parallel Workloads Archive[END_REF] and Grid Workloads Archive [START_REF] Iosup | The grid workloads archive[END_REF] provide traces of jobs submitted to clusters or Grids. However, this application-level information does not contain information about job, service, or resource failures.

In terms of statistical modeling, our work presents the first uniform statistical analysis and comparison of the nine distributed systems. Most studies, in particular [START_REF] Bhagwan | Understanding Availability[END_REF], [START_REF] Bolosky | Feasibility of a Serverless Distributed file System Deployed on an Existing Set of Desktop PCs[END_REF], [START_REF] Guha | An experimental study of the skype peer-to-peer voip system[END_REF], [START_REF] Pang | Availability,usage, and deployment characteristics of the domain name system[END_REF], [START_REF] Stribling | Planetlab all paris ping[END_REF], do not focus on modelling issues. A few other studies have also conducted modelling of the distribution of failures. However, the modelling work usually focuses on a particular data set and so the generality of the model was not confirmed. Moreover, the process of failures modeled was significantly different.

For instance, in [START_REF] Schroeder | A large scale study of failures in high-performance-computing systems[END_REF], the authors model the time between failures, and the repair time. They do not model availability interval lengths directly. Yet we believe this is essential for stochastic scheduling algorithms that conduct task assignment based on the probability of task completion.

Also, in [START_REF] Iosup | On the dynamic resource availability in grids[END_REF], the authors model the inter-arrival time between failures. Again, the temporal structure of availability intervals and unavailability intervals is not captured in this model but is needed for stochastic scheduling. Clearly, an inter-arrival time does specify the availability or unavailability length during that time frame.

Similarly, in [START_REF] Bakkaloglu | On correlated failures in survivable storage systems[END_REF] the entity being modeled is different. In that study, the authors model the number of machines available at some time point, considering correlated failures, in the context of a distributed storage system. By contrast, our study focuses on the the continuous durations of availability and failures.

VII. Conclusion

Despite the importance of failures in (large-scale) distributed computing environments, few traces collected from real environments are publicly available. To address this situation, which restricts the applicability of failure models and the development of failure-aware systems, our contribution in this work is threefold:

• We have created the Failure Trace Archive for facilitating the comparative analysis of failures in distributed and parallel systems. We defined a standard trace format, and showed its suitability by converting nine diverse distributed systems to this format. Given traces of this format, we implemented a toolbox that facilitates the comparison of failure statistics, models, and algorithms. Ultimately, we envision that scientists would use the toolbox as a repository of modeling and predictive methods.

• Using the toolbox, we gave a uniform and global statistical analysis of failure in 9 distributed systems.

One key finding was that the Weibull and Gamma are the often the best candidates for availability and unavailability distributions. Moreover, the hazard rate wrt to the Weibull was decreasing in all systems. In some cases, the measurement method (in particular the resolution of probing) seemed to cause bias in the distribution of availability, and we identified these data sets with potential bias.

• Finally, we showed how differences of interpretation of trace data sets can result in dramatically different failure models and statistics. This showed that it is critical to make both trace data and analytical methods publicly available.

Fig. 1 .

 1 Fig. 1. Overview of the FTA structure.

Fig. 2 .

 2 Fig. 2. FTA Toolbox Design.

Fig. 3 .

 3 Fig. 3. CDFs of Availability and Unavailability Intervals.

TABLE I . Summary of nine data sets in the Failure Trace Archive.

 I

	Trace	Mean	TrMean	Median	Std	CV	IQR	Max	Min	Skewness	Kurtosis	No.
	lanl05	1779.99	1208.09	280.28	3462.33	1.95	1593.37	34480.23	0.02	3.09	14.29	19874
	g5k06	32.41	18.41	7.09	94.24	2.91	24.07	10157.73	0	15.06	695.83	294318
	microsoft99	67.01	40.39	10	138.47	2.07	55	840	1.0	3.4	15.8	526078
	websites02	11.85	5.17	0.83	40.10	3.38	5.17	1196.55	0	9.02	135.89	47843
	pl05	159.48	71.42	1.71	475.61	2.98	35.60	6051.49	0	4.91	34.26	24928
	ldns04	140.93	125.79	28.29	193.39	1.37	213.47	559.27	0	1.24	2.97	223596
	overnet03	2.29	1.48	1.33	4.63	2.02	1.00	120.11	0	8.03	113.34	33443
	nd07cpu	13.73	5.46	1.07	60.05	4.37	7.11	3783.57	0	25.49	1228.74	134176
	skype06	16.27	10.12	5.11	34.57	2.12	11.87	465.95	0	4.81	34.38	29217

TABLE II . Statistics of availability intervals for different data sets. (Values given in hours.)

 II

	Trace	Mean	TrMean	Median	Std	CV	IQR	Max	Min	Skewness	Kurtosis	No.
	lanl05	5.88	1.67	0.97	78.39	13.32	1.98	5325.70	0	43.96	2289.91	23451
	g5k06	7.41	0.94	0.05	60.24	8.13	0.19	6314.95	0	26.26	1237.26	294145
	microsoft99	16.49	9.15	2	46.50	2.82	14	840	1.0	8.52	105.12	493687
	websites02	1.18	0.49	0.17	22.92	19.46	0.34	3311.51	0	111.03	14311.32	47714
	pl05	49.61	12.86	0.5	269.90	5.44	6.36	9329.47	0	15.10	340.33	24236
	ldns04	8.61	5.47	2.28	20.68	2.40	7.82	533.22	0	8.62	123.06	161395
	overnet03	11.98	4	0.33	36.82	3.07	1.67	167.83	0	3.66	15.11	35449
	nd07cpu	4.25	0.47	0.27	62.83	14.77	0.36	3616.70	0.04	33.72	1307.29	134026
	skype06	14.31	9.45	6.16	30.23	2.11	14.30	596.03	0.02	6.26	62.72	27136

TABLE III . Statistics of unavailability intervals for different data sets. (Values given in hours.) coefficient

 III

of variance (CV), interquartile range (IQR), maximum duration, minimum duration, skewness (the third moment), kurtosis (the forth moment) and number of intervals.

TABLE IV . P-values resulting from KS and AD tests for availability. A gray box denotes p-value above significance level of 0.05. TABLE V. P-values resulting from KS and AD tests for unavailability. A gray box denotes p-value above significance level of 0.05.

 IV

	Trace	Exp(µ)	Wbl(k, λ)	LogN(µ, σ)	Gam(k, λ)	Exp(µ)	Wbl(k, λ)	LogN(µ, σ)	Gam(k, λ)
	lanl05	1779.99	0.48 816.60	5.56 2.39	0.35 5102.71	5.92	0.58 2.18	0.05 1.42	0.38 15.44
	g5k06	32.41	0.48 14.37	1.51 2.42	0.34 94.35	7.41	0.35 0.47	-2.00 2.20	0.19 39.92
	microsoft99	67.01	0.55 35.30	2.62 1.84	0.41 162.19	16.49	0.60 9.34	1.42 1.54	0.46 35.52
	websites02	11.85	0.46 3.68	0.23 2.02	0.31 38.67	1.18	0.65 0.61	-1.12 1.13	0.50 2.37
	pl05	159.49	0.33 19.35	1.44 2.86	0.20 788.03	49.61	0.36 5.59	0.40 2.45	0.21 237.65
	ldns04	141.06	0.51 79.30	3.25 2.33	0.39 362.43	8.61	0.63 5.62	0.91 1.64	0.51 16.87
	overnet03	2.29	0.85 2.04	0.19 0.98	0.91 2.53	12.00	0.44 2.98	0.08 1.80	0.29 41.64
	nd07cpu	13.73	0.45 4.16	0.30 2.20	0.30 46.16	4.25	0.51 0.74	-1.02 1.27	0.28 15.07
	skype06	16.27	0.64 10.86	1.60 1.57	0.53 30.79	14.31	0.63 9.48	1.40 1.73	0.50 28.53

TABLE VI . Parameters of distributions for availability (left) an unavailability (right

 VI goodness of fit (GOF) tests, namely the Kolmogorov-Smirnov (KS) and Anderson-Darling (AD) tests, to evaluate the fitted distributions. The results of both tests are reported in terms of the p-values in TableIV and Table

). mean: µ, std: σ, shape: k, scale: λ. two

TABLE VII . Parameters in the qualitative com- parisons. The Medium level is between Low and High levels.

 VII

				Levels
	Parameter		Low		High	Unit
	V : Volatility		V < 50	V > 100	hour
	A: Availability		A < 60	A > 90	%
	M : Measurement		M < 6	M > 12	month
	S: Scale		S < 1	S > 2	10 3 nodes
	Trace	V	A	M	S	Failure model
	lanl05	L	H	H	H	Long-tailed/Long-tailed
	g5k06	M	M	H	M	Long-tailed/Long-tailed
	microsoft99	M	M	L	H	Short-tailed/Heavy-tailed
	websites02	H	H	M	L	Long-tailed/Long-tailed
	pl05	L	M	H	L	Long-tailed/Long-tailed
	ldns04	L	H	L	H	Long-tailed/Short-tailed
	overnet03	H	L	L	H	Short-tailed/Heavy-tailed
	nd07cpu	H	M	M	L	Heavy-tailed/Long-tailed
	skype06	H	L	L	H	Short-tailed/Short-tailed

TABLE VIII . Qualitative comparison of nine data sets in the FTA

 VIII

. H:High, M:Medium, L:Low. For V, A, M, and S, see Table VII.

TABLE IX . Parameters of distributions for availability (left) and unavailability (right) for ambiguous data sets. mean

 IX

: µ, std: σ, shape: k, scale: λ. A

grey box indicates significant a difference of parameters between data sets.

	10 years. Third, it provides a public toolbox for failure
	trace analysis.

Acknowledgements

We gratefully acknowledge the generous contributors to the Failure Trace Archive that made their trace data sets publicly available. We thank the INRIA ALEAE project directed by Emmanuel Jeannot for supporting this collaborative work. We thank Eric Heien for creating the initial hierarchical version of the Failure Trace Archive format. We thank Cecile Germain for useful discussions with respect to resource versus job versus userlevel failures.

Trace Exponential Weibull Pareto Log-Normal Gamma lanl05 0.000 0.004 0.196 0.346 0.000 0.001 0.481 0.607 0.042 0.095 g5k06 0.000 0.000 0.008 0.073 0.000 0.000 0.037 0.144 0.003 0.022 microsoft99 0.004 0.180 0.048 0.529 0.000 0.376 0.076 0.611 0.052 0.368 websites02 0.000 0.023 0.001 0.150 0.000 0.002 0.005 0.209 0.003 0.090 pl05 0.000 0.000 0.035 0.178 0.000 0.004 0.081 0.274 0.019 0.079 ldns04 0.035 0.112 0.404 0.538 0.000 0.001 0.464 0.607 0.277 0.411 overnet03 0.000 0.040 0.003 0.305 0.000 0.204 0.011 0.389 0.005 0.118 nd07cpu 0.000 0.004 0.028 0.219 0.000 0.031 0.126 0.559 0.003 0.032 skype06 0.071 0.191 0.288 0.478 0.002 0.015 0.182 0.449 0.267 0.408

VIII. Availability of FTA Data and Scripts

The Failure Trace Archive, including technical documentation on the data format, the toolbox. and the trace data sets are available online at: http://fta.inria.fr.

A. Differences of Empirical Distributions

Figure 4 shows the quantiles of the empirical distributions for each pair of data sets. (We only show qq-plots for g5k06's availability, lanl0516's unavailability, and nd07cpu's availability to save space.) If the two data sets have the same distribution, their qq-plot will match the line y = x, which is plotted in solid red as a reference.

For g5k06, in Figure 4(a), we see that g5k06B has longer availability intervals (and also shorter unavailability intervals). This is clearly due to the optimistic interpretation of the suspected state. The deviation is greatest at the quantile at 1000 hours of g5k06B, which corresponds to the the quantile of 600 hours of g5k06. Also, the mean availability in g5k06B was increased by a factor of 1.50 because the difference of interpretation. The mean unavailability in g5k06B was decreased by a factor of 1.13 due to the decrease in the number of failures.

For lanl0516, we see little differences of interpretation for availability. This is due to the fact that System 16 is highly available over a long time frame. So changes in unavailability periods do not affect availability periods visibly. However, there are clear differences in the distribution of unavailability as shown in Figure 4(b). The unavailability in lanl0516B is much shorter than that in lanl0516.

For nd07cpu, we find that nd07cpuB has longer availability and unavailability intervals than nd07cpu. In particular, the mean length of availability and unavailability increased by a factor of 1.47 and 1.35 respectively. While the total amount of unavailability decreased in nd07cpuB, the small unavailability intervals became availability intervals, after the optimistic processing of the traces. So both the mean lengths of availability and unavailability were increased.

B. Differences of Fitted Distributions

Here we show how the differences of interpretation affect the statistical goodness-of-fit tests of fitted distribution, and their fitted parameters.

Typically, a significance value of 0.05 or 0.10 is used as a threshold for p-values to determine whether to reject the NULL hypothesis that the fitted distribution represents the empirical. We found several cases where the p-values result in conflicting conclusions, i.e., p-values that indicate both rejection and failure of rejection.

For instance, the AD-test for the Weibull distribution fitted to g5k06's unavailability intervals resulted in a p-value of 0.07, whereas the p-value corresponding to g5k06B was 0.035. Similarly, for the AD test for the Log-Normal distribution, the p-value is 0.148 for g5k06 versus 0.057 for g5k06B.

Thus, if a threshold of 0.05 is used, we find that the Weibull distribution would not be rejected for g5k06's unavailability distribution, but would be rejected g5k06B's unavailability distribution. Similarly, if a threshold of 0.10 is used, the Log-Normal distribution would not be rejected for g5k06, but would be rejected for g6k06B's unavailability distribution.

We find similar cases for lanl0516 and lanl0516B, and nd07cpu and nd07cpuB. For lanl0516, the Gamma distribution is rejected for lanl0516's unavailability intervals but not rejected for lanl0516B according to the p-values resulting from the KS test (0.046 versus 0.056). For nd07cpu, the Log-Normal distribution is rejected for nd07cpuB's unavailability intervals, but not rejected for nd07cpu according to the p-value for the KS test (0.14 versus 0.01).

In addition to quantitative contradictions, we show contradictions graphically as well in Figure 5. There, we plot the quantiles for the fitted Gamma distributions of each pair of data sets. We choose the Gamma distribution as it is analytically easy to use and has a relatively high p-value. In particular, we do so for g5k06's availability distributions, lanl0516's unavailability distributions, and nd07cpu availability distributions.

We observe from the qq-plots that the distributions fitted to different interpretations of the same data set are dramatically different. For example, for lanl0516, we see that the quantile of 40 hours for lanl0516B corresponds to the quantile of 180 hours for lanl516.

Furthermore, the impact on the distribution parameters is significant and shown Table IX. Significant differences in parameters are highlighted in grey. For instance, the mean of the exponential distribution for g5k06B's availability is a factor of 1.50 times greater than g5k06. Also, different interpretations affect greatly the scale parameter of the Gamma. For instance, the scale parameter of the gamma distribution for g5k06B's availability is factor of 1.39 times greater than g5k06.

The fact that both the empirical distributions and fitted distribution mismatch emphasizes the need for public data sets and methods. Otherwise, one cannot determine how the data was exactly interpreted much less why.

VI. Related work

Here we compare our archive with other projects, and also previous works on statistical modeling. While several archives exist, the FTA differs in several respects. First, it defines a standard format that facilitates use and comparison of the traces. Second, the archive contains over 9 data sets provided in this format, and raw traces for over 16 systems. Raw data and the scripts to parse and analyze them are publicly available. The data sets are derived from diverse distributed systems over a long time-frame of over