Jean Jacques Moreau
email: moreau@lmgc.univ-montp2.fr

Indetermination due to dry friction in multibody dynamics

Coulomb friction commonly generates problems with multiple solutions. After examining an elementary example, one proposes to include the values of contact forces in the description of each state of the investigated system. This turns out to be what popular time-stepping numerical techniques implicitely do. Specifically, the Contact Dynamics computational policy, whose principle is recalled, offers this as an option with the additional advantage of improving computation speed. Thanks to this option, the evolution of the considered systems is predicted with negligible ambiguity. Alternatively, Contact Dynamics techniques may be used to explore the plurality of the solutions to problems stated in the traditional way. In this line, two examples of the assessement of contact forces in granular assemblies are presented, with the set of solutions graphically displayed.

INTRODUCTION 1.Features of dry friction

Tribology teaches us the complexity of the phenomena which may take place when two bodies are in contact, should sliding occur or not. Anyway, the law of Coulomb provides an irreplaceable framework for the first approach to dry friction. In many industrial situations, the only quantitative information provided by technical documents about friction-based devices is communicated in terms of Coulomb friction coefficients, with possible distinction between sticking and sliding values.

That the motions calculated from such a description of dry friction frequently are mathematically nonsmooth only reflects everyday observation: in the absence of lubrication, mechanisms may exhibit chattering motions, while emitting creaking noise, or jam.

Discussions have taken place for a long time about the fact that, in the dynamics of systems involving Coulomb friction, the initial value problem, i.e. the prediction of the motion consequent to an instant at which the positions and the velocities of the system elements are given, may have several solution or no solution at all. In the eyes of a 19th. century scientist like Painlevé, fascinated by the then recent theory of differential equations and Laplace's "determinism", this was an unforgivable defect of the law of friction, even inducing him to reject more generally the very concept of a contact force. The disquieting expression of "Painlevé's paradox" caused great harm to mechanical science since engineers who had, from another part, some reasons to be unsatisfied with the moderate quantitative precision of the Coulomb law, tended to view this as a hint to some underlying logical defect. The irrelevance of Painlevé's standpoint was already pointed at in his time [START_REF] Lecornu | Sur la loi de Coulomb[END_REF].

In the author's wiew, a physical model is nothing but a format, in the sense of Computing Science, in which one decides to record the available information concerning a certain physical situation, to treat this information and finally to communicate conclusions. Fundamentally, the information one may collect about some investigated situation is always incomplete, so the model through which this information is coded cannot be expected to generate exhaustive predictions. Also, as the situation evolves, the validity limits of the model may come to be overrun.

An elementary example

Figure 1 shows, in a vertical plane, the following system. Two fixed walls slightly converge upward. A rigid rod, subject to gravity, is inserted between them, with Coulomb friction at the two contact points and abandoned at zero velocity. If the configuration angles have suitable values, compared with the friction angles at contact points, the problem of finding the consequent motion visibly has two solutions: either the rod loses contact and falls freely or it remains wedged.

The quadrilateral area filled with light hachure is the intersection of the Coulomb cones drawn from the two contact points. The triangular part above AB intersects the vertical of the center of gravity along a line segment. Any position of I on this segment corresponds to values of the contact forces R A and R B compatible with Coulomb condition for no-sliding and equilibrating the bar weight. In systems affected with dry friction, one should be ready to meet such uncertainties.

Intuitively, the outcome depends of the "degree of wedging" of the rod. The natural measure of such a degree precisely consists in the values of the contact forces and it will be seen in the sequel that the computational methods which include these values in the description of each state of the investigated systems allow for practically unambiguous predictions. A deeper insight into the situation may be expected from the use of a richer model than above. To this end, let us take into account a certain longitudinal elasticity of the rod. This involves the introduction of a "small" variable s, the total elongation counted from some reference state. As long as contacts are effective, the value of s is geometrically connected with the displacements of points A and B on the respective walls, still treated as indeformable. A law of longitudinal elasticity of the rod should be given. Combined with the longitudinal compo-nents of the distributed forces, in particular gravity forces, that the rod undergoes, this leads to determining the stress distribution along AB through a differential equation for which the longitudinal components of R A and R B provide the endpoint data. For simplicity, assume AB horizontal and all the distributed forces vertical. Then this elastic analysis simply results in a monotone relationship between the variable s and the (opposite to each other) longitudinal components of R A and R B .

This models allows one to understand the scenario of rod insertion. If, after the first contact, increasing upward forces are applied, the evolution assumed quasi-static consists in points A and B sliding upward. At every time, vectors R A and R B have directions imposed by Coulomb law in sliding regime. Thanks to the quasi-equilibrium equations of the rod, these contact forces are then known. Since the elastic relationship connects their longitudinal components to the positions of A and B, elasticity intervenes secondarily to connect the displacements of these points to the actual value of the resultant of weight and pushing forces.

If, at some instant, one decides to make the vertical pushing forces decrease and eventually take downward direction, a new episode of motion begins, still assumed quasi-static. Points A and B remain fixed so that the elastic relationship, whatever it is, makes the longitudinal components of R A and R B constant. At each time, the values of these vectors result from the quasi-equilibrium equations and the no-slide regime persists so long as both vectors lie in the respective Coulomb cones. This allows one to determine the value that the resultant of the downward applied forces should eventually reach to produce detachment.

This model has the merit of making understand the processes of insertion and detachment but, to the lay observer it conveys no tractable information in the absence of a measuring device for microdisplacements, commonly not at hand. Since the proper elasticity law of the rod turns out to be immaterial, one may expects that some model simply ignoring this elasticity could be able to reproduce the above scenario. In fact, the Contact Dynamics computation method, described in the sequel, has been found to yield numerically a response of contact forces to the pushing history which agrees with that precedes.

NUMERICAL TECHNIQUES

Computation in (unilateral) multibody dynamics

The numerical dynamics of collections of bodies treated as perfectly indeformable, subject to the constraints of non-interpenetrability, with friction taken into account in the event of contact, currently is an active domain of research. Applications include the dynamics of machines, in particular robots, the dynamics of masonry works submitted to transient actions (earthquakes, gusts of wind or impacts), animated computer graphics and numerical simulation in granular mechanics. In all these domains, assuming the perfect indeformability of each part of the system leads to efficient numerical procedures which, in many circumstances, satisfy the needs. Possibly also, some variables are added in order to also account for a certain deformability of these parts [START_REF] Jean | Computational Modeling of Contact and Friction, special issue of Computer Meth[END_REF], without essentially changing the computational strategies.

The techniques used in unilateral multibody dynamics may be classified into the three following categories.

Event-driven methods

The methods so qualified (abbr. ED) are practical mainly when the investigated time-interval equals the union of not too many subintervals, a priori unknown, over which the status of the various contacts remain unchanged, i.e. no collision which would create new contacts occurs, no contact either gets loose, nor any critical situation needing a change in the analytical expression of Coulomb law is met [START_REF] Ch | Set-valued force laws[END_REF]. On each of these subintervals, the same numerical techniques, resting on high performance integrators, as in the investigation of systems with classical bilateral, possibly frictional, constraints may be used. As integration proceeds, the program has only to watch the evolution of some indicators. In particular, the contact forces will be calculated. If, after a certain instant, some of the values computed for these forces are found to have directions incompatible with the unilaterality of the non-interpenetrability constraints (neglecting adhesive, i.e. gluing effects), the program decides that the motion has to be calculated otherwise. But one should keep in mind that the contacts which get loose after the critical instant are not necessarily those for which an unfeasible contact force has just been evaluated [START_REF] Delassus | Mémoire sur la théorie des liaisons finies unilatérales[END_REF]. A popular approach to such discussions consists of reducing them to complementarity problems, similar to what is commonly met in constrained optimization.

Other cases of changing status arise from Coulomb law. The most critical one is that of an episode during which a certain contact has been found not sliding. If after some instant, the continuation of such a motion would require a contact force not belonging to the Coulomb cone, the transition to an episode of different status needs to be computed. This transition may sometimes consist in contact breaking but, more usually, in the inception of sliding. The integrator has to start with a new assessement of contact forces and acceleration variables. The crucial observation is that the inceptive direction of the sliding velocity v (direction involved in Coulomb law) is that of the time-derivative v of this vector, since intially v = 0. Now v is analytically connected with the acceleration variables. The mathematical problem to be solved is similar to the "Problem(P)" met at each step of a Contact Dynamics computation, as it is sketched in the sequel [START_REF] Saux | Dynamique multi-contact d'un système de solides tridimensionnels rigides[END_REF]. Uniqueness of solution should not be expected in general.

Difficulties of different nature occur for calculating the new velocity in case the critical instant is that of a collision. Contact forces take very large values during a very short time-interval and only poor phenomenological information is usually available about such physical circumstances. Even in the simplest case, that of the collision of two otherwise free members of the system, the traditional coefficient of restitution is known to depend not only on the materials these bodies are made of, but also on their shapes and relative orientations at the collision locus [START_REF] Stoianovici | A critical study of the applicability of rigid body collisions theory[END_REF]; only the case of spherical beads appears relatively comfortable [START_REF] Foerster | Measurements of the collision properties of small spheres[END_REF]. Furthermore, if some of the colliding bodies belong to clusters of already contacting ones, percussional reactions should be expected at all existing contact points. Newton's restitution concept should at least be extended so as to handle all these contacts collectively [START_REF]An introduction to unilateral dynamics[END_REF].

Though rigid body collisions currently make an active domain of research [START_REF] Brogliato | Nonsmooth Mechanics[END_REF][5] [START_REF] Stronge | Impact mechanics[END_REF][9], computation has to rely on pragmatic rules whose validity should be checked in each type of application. Anyway, a theoretical framework may be found in [START_REF] Frémond | Rigid body collisions[END_REF] [START_REF]Non-smooth thermo-mechanics[END_REF] which secures the thermodynamic correctness of the empirical information one may introduce into calculation.

Smoothing methods

"Nonsmoothness" is the salient feature of the problems in view. In fact, after the set of the possible positions of the investigated system has been parametrized through an element q of R n , the geometric restriction that the non-interpenetrability constraints impose on q are expressed by a set of inequalities. Hence, instead of running in a smooth submanifold as in traditional analytical dynamics, the point q is confined in a region of R n whose boundary consists of a lot of pieces of hypersurfaces (millions or billions of them in current applications to granular materials) joined along multidimensional edges: this is nonsmoothness in space. Furthermore, possible collisions are expected to induce velocity jumps: this is nonsmoothness in time. To end, the contact forces associated with the non-interpenetrability constraints are governed by highly irregular laws. These forces vanish as soon as the corresponding contacts break while, if contact holds, the commonly stipulated mechanical conditions do not express them as functions of q. If, in addition, Coulomb friction is taken into account this introduces some irregular relationships between contact forces and the sliding velocities. All this may be called nonsmoothness in law.

In such a state of the affairs, a natural move is to replace, approximately, the nonsmooth governing relationships by some regularized ones, a technique also used in the mathematical study of these problems [START_REF] Paoli | Penalty approximation for dynamical systems submitted to multiple non-smooth constraints[END_REF] . First the non-interpenetrability constraints will be replaced by some stiff repulsion laws which take effect as soon as two members of the system come close to each other. This automatically handles the possible collisions, as far as one considers them as "elastic", while the dissipativity of collisions may be accounted for by adding some damping actions or also by using different repulsion laws in the episodes of approach and of separation. Similarly, frictional contact may be somewhat regularized through the introduction of local elastic microdeformation and of viscosity-like effects. The dynamics of the approximate system is then governed by differential equations with sufficient regularity to be handled through standard numerical techniques. The drawback is that the need of precision requires the use of very stiff appproximating laws. Hence the time-stepping procedures applied, usually of the explicit type, must resort to very small step-length and possibly also have to enforce numerical stability by introducing artificial damping or artificially increasing inertia. When treating dynamical applications, the effect of such an artificial alteration of the mechanical data may blur the picture. Significant simulations of loose (collisional) flows of granular materials have been obtained in that way, but when compact collections of bodies are concerned (pieces of masonry or dense granulates) the method is mainly applied to quasi-static evolutions in which only a succession of equilibrium states is looked for. Dynamical computation is then used only as a way of attaining each of these equilibrium states, a strategy referred to as "Dynamic Relaxation".

The pioneering work of P. Cundall [START_REF] Cundall | A computer model for simulating progressive large scale movements of blocky rock systems[END_REF] was precisely based on the regularization strategy, today implemented in the majority of commercial pieces of software intended to handle noninterpenetrability. Because such computation techniques are close to those applied in molecular simulations, they are commonly referred to as "Molecular Dynamics" methods (abbr. MD), specially in the domain of granular mechanics [START_REF] Walton | Numerical simulation of inelastic, frictional particle-particle interactions[END_REF].

Anyway our point is that this approach rests on the introduction of local microdisplacements, to which the normal and tangential components of contact forces are connected. At the beginning of each time-step, these quantities are involved in computation, as the result of the antecedent one.

In this way, MD methods implicitely comply with our recommendation of treating contact forces as part of the description of each state.

Contact Dynamics

This is the technique (abbr. CD) used in preparing the examples shown in this communication. It originated from [START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF], where the unilateral contact, possibly frictional and/or collisional, between rigid bodies received a formulation in terms of elementary convex analysis which proves suitable for elaborating computational approaches. Mathematically, the resulting evolution problems are governed in smooth cases by differential inclusions. General information on the latter concept may be found in [3][7], but the need of treating also non-smooth evolutions calls for its extension to that of a measure differential inclusion [START_REF] Monteiro Marques | Differential Inclusions in Nonsmooth Mechanical Problems: Shocks and Dry Friction[END_REF].

A directing idea of the Contact Dynamics approach is that the main object of computation is the velocity function t → u ∈ R n . Time-stepping algorithms essentially have to determine the evolution of this function; the position function t → q is only to be updated at each step through adequate integration. Possibly, some members of u are "pseudo-parameters" such as the components of the spin vector of a solid, instead of the time-derivatives of position parameters. From the geometrical standpoint, one should observe that, in analytical dynamics, the position q ranges in some differential manifold, while for each q the possible velocities are elements of the tangent space to the manifold at this point. The latter is a vector space relatively to which such concepts as linearity, convexity, etc. make sense, while no algebraic concept of this sort is generally available in the position manifold.

The inequalities that the non-interpenetrability of bodies imposes on the q parameters are handled through velocity conditions.

Contact Dynamics procedures rest on drawing the balance of momentum of the investigated mechanical system over each time-step. No estimation of the acceleration is needed and the burden of calculating mathematically the curvatures of the involved surfaces is avoided. These curvatures are simply accounted for by the fact that, from one step to the other, the normal directions to the detected contacts vary.

At each time-step, there is to solve a highly nonlinear nonsmooth problem -call it Problem (P) -whose simultaneous unknowns are the update of the velocity variables (in the timediscretization setting, the increase of these variables reflects acceleration) and the values of the contact impulsions at the detected contact points. In smooth motions, the latter equal the integrals of contact forces over the time-step, so that an estimation of contact forces is obtained by dividing impulsions by the step length. These elements are required to satisfy, in discretized form, the equations of the dynamics of the whole system and the laws of frictional contact, including the non-interpenetrability conditions.

Several numerical techniques are available to solve Problem (P) (see e.g. [START_REF] Alart | Un nouvel algorithme de quasi-optimisation pour la résolution des problèmes multicontacts et application aux milieux granulaires[END_REF]). The most ancient one, an iterative procedure à la Gauss-Seidel [START_REF]An introduction to unilateral dynamics[END_REF], serves the best the purpose of the present study. It consists in reviewing contacts cyclically, solving at each "pass" a single contact problem for which all other contact impulsions are treated as known, after what the involved velocities and contact impulsions in memory are updated. The cyclic review is continued until a chosen degree of approximation is attained.

The method results in time-stepping schemes which, at least in what concerns the velocity function, are of the implicit type. Numerical stability is thus secured, allowing one to use much larger time-steps than in MD methods. The price to pay is the computational cost of Problem (P). The nonlinear Gauss-Seidel iterative procedure needs to start from an initial guess of the contact impulsions. In the numerical simulation of the motion of dense granulates, one considerably accelerates convergence by introducing as initial guess the contact impulsions found at the antecedent time-step, for the contacts which were already in effect.

If this is done, CD computation happens to comply with the policy of treating contact forces as part of the description of each state of the system.

Apart from this special initialisation, the CD method presents the considerable interest of generating at will all the solutions to Problem (P), simply by changing the way the nonlinear Gauss-Seidel iterations are conducted. This is illustrated in Section 3 below.

A single computation step is needed to decide whether equilibrium in a given position is a possible motion and to obtain the possible values of contact forces.

Contact Dynamics algorithms are ready at each step to treat collisions on the same footing as persistent contacts and to handle collectively the impulsional responses of all contacts in presence. The paroxysms in contact forces improperly called "Painlevé's paradox" [START_REF] Génot | New results on Painlevé paradoxes[END_REF] are also handled. But, of course, the same need of phenomenological information about collisional processes arises as in other computation methods.

INDETERMINATION IN THE EVALUATION OF CON-TACT FORCES

Equilibrium of a granular sample under gravity

A two-dimensional computation has been conducted in order to build a collection of 28 circular grains contained in a fixed container and in equilibrium under gravity. This configuration happens to involve 56 contact points of the grains between each other or with the container.

Friction coefficient was fixed at 0.3. The set of the components of contact forces makes a point r of R 2×56 . Coulomb law requires of this point to belong to a polyhedral cone C, the product of the 56 local friction cones, angular regions in each of the 56 corresponding copies of R 2 , while the 84 equilibrium conditions of the 28 grains (three degrees of freedom each), with account of gravity, define an affine manifold A of dimension 28 in R 2×56 . For each contact, the contact force is an element of the corresponding copy of R 2 , namely the Cartesian projection of r onto this factor space. The set of its possible values thus equals the projection of C ∩ A, a polyhedral subset of R 2×56 . As observed before, calculating the values of contact forces in such an equilibrium configuration is the matter of a single step of the CD algorithm. The plurality of solutions is reflected in the plurality of ways of conducting the Gauss-Seidel iterations. The latter need to start from an initial guess of the contact forces (actually appearing in computation through impulsive terms). If this initial guess is provided by random drawing from a domain estimated to contain all possible values, every solution has a chance to be reached since, as an extreme case, it could itself be the result of the random drawing. Another way of varying the Gauss-Seidel procedure is to fix the initial guess (for instance zero values at all contacts) but to change at random the ordering according to which the contacts are cyclically reviewed. If κ is the number of contacts, this method can yield at most (κ -1)! different solutions, but the following graphical display shows that this limitation does not prevent it from yielding a valid survey of the possibilities.

Figure 2 shows a detail of the piling. The calculation of contact forces is repeated as explained above and each result is represented by a dot.

Grain 1, on top, takes its bearing on two underlying ones. Its equilibrium under gravity is a standard problem, analogous to that of parag.1.2: in view of the contact points A and B lying on each side of the vertical drawn from the mass center, there exist an infinity of values of the contact forces R A and R B agreeing with equilibrium. In fact equilibrium conditions are preserved when opposite forces with direction AB are added to R A and R B , so long as the latter remain in the respective friction cones. In this case, the projections of C ∩ A onto the respective copies of R 2 reduce to line segments visible on the figure. The case of grain 2 is similar.

Grain 3 possesses four contacts with grains which themselves are in situations of force indetermination. Contact forces in each of the points E and F are indetermined in polygonal regions whose grey rendering results from the exploration procedure described above. The computation program is repeatedly applied to the calculation of equilibrium forces, each time with different choices in the completion of the Gauss-Seidel algorithm. At each time, the values found for the contact forces in E and F are represented by dots. A surprise is to see in these grey areas which are two-dimensional projections of the multi-dimensional polyhedron C ∩ A, the ghosts of some edges of the latter. For reasons unexplained so far, the limit points of Gauss-Seidel iterations are a little denser in the neighbourhood of some faces of C ∩ A, hence in the neighbourhood of the edges which are their intersections. The framed enlargements on Figure 2 correspond to two different modalities in Gauss-Seidel algorithm. On the right, the initial guess of iterations is chosen at random, so that the possibility is open of attaining every solution of the problem. On the left, the initial guess is always zero, but from one computation to the others, it is the order of the cyclic review of contacts which is changed at random. Both procedures yield the same polygonal areas, but with different visions of ghost edges.

Granular flow on a slope

On Figure 3 are shown some results from a two-dimensional model of dense gravity-driven granular flow.

The ground, presented horizontal on the drawing, actually is inclined 26.5 • down to the right and made rugous by glued grains created by the same random generator of polygonal shapes as the flowing ones. In order to imitate in some way a layer of infinite extent, the standard trick of periodic boundary conditions is used: only grains with mass-center located in some rectangular cell are the object of calculation. Grains close to the upstream and downstream edges of the cell can have contact interaction with virtual grains, images by translation of grains belonging to the cell. When a grain exits the cell by crossing one of these edges, it is replaced in computation by one of its images, with conservation of the velocity variables.

A division into 12 strips is superimposed to the drawing. Over each of them the average of the corresponding component of velocities is calculated, hence the velocity profile shown on the left part of the figure.

The calculation of contact forces in such a case of flowing grains involves less indetermination than in equilibrium situations. In fact when sliding occurs at a contact point, Coulomb's law connects the direction of the contact force with that of the sliding velocity and this makes a richer information than merely stipulating that the force belongs to the friction cone. But the presence of sticking contacts should also be expected.

The procedure of varying the Gauss-Seidel iterations has been applied in order to estimate the amplitude of the indeterminations. On the right part of the figure are shown the grains F1 and F2, glued to ground, and a few grains of the flow.

When two polygonal grains touch each other along a line segment, the program retains only two contact points, at the extremities of this segment (this amounts to imagine that polygones exhibit on each of their edges some infinitesimal concavity). From each contact point, the program draws a line segment representing, with a fixed graphical unit, the calculated contact force.

Grains F1 and F2 constitute a single fixed rigid body that grain A, whose velocity is found zero, touches in three points. The fans observed at each contact point give some idea of the indetermination.

On the contrary, the two contact points declared between grains A and B show no force dispersion. These grains have a nonzero sliding velocity and the two contact forces have the same direction corresponding to the value 0.3 of the friction coefficient. Also at some vertex-toedge sliding contacts no force dispersion is visible.

Figure 1 :

 1 Figure 1: Rod inserted between two converging walls

Figure 2 :

 2 Figure 2: Indetermination of intergranular forces

Figure 3 :

 3 Figure 3: Flow of polygonal grains on a rugous slope


Jean-Michel Le Bot

The Subjective Experience of "Nature": Methodological Reflections

It is not particularly easy to get modern city-dwellers to talk about their knowledge and experience of the species and habitats ¹ present in their environment (whether urban, suburban or rural ²). When asked about this in the parks and public gardens of three large cities in the West of France, many of those interviewed had little to say (even though the extent of the responses differed from person to person) ³. That they were present in these spaces and that we were able to question them there was, in most cases, due to the fact that they enjoyed being there in contact with what they spontaneously referred to as "nature". However, their pleasant experience of this "nature" seemed to take the form of something self-evident which it was difficult for them to express. This is in some ways similar to what is observed in the field of pain. Indeed, as a subjective biological experience, pain also seems to be difficult to express. Sometimes all that people suffering from chronic pain are able to say is "it hurts". However, the patient's description of the pain that he or she feels is a very important piece of diagnostic information for carers. It is this observation that has led one clinical practitioner amongst our colleagues to work together with a doctor specializing in the evalu-* Univ Rennes, LiRIS (Laboratoire interdisciplinaire de Recherche en Innovations Sociétales) EA 7481, F -35000 Rennes. Email: jean-michel.lebot@univ-rennes2.fr. This is a translation of an article first published in french by Natures Sciences Sociétés (DOI: https://doi.org/10. 1051/nss/2013059). Translated from french by Tim Pownall (Tinos Translations).

¹The concept of habitat here is understood in the ecological sense (see for instance the EUNIS habitat types classification: http://eunis.eea.europa.eu/ [accessed 27 Jun 2018]).

²For a definition of these concepts, see [START_REF] Clergeau | Une écologie du paysage urbain[END_REF]. In most cities, the exact boundary between the urban, the suburban and the rural (or peri-urban) is clearly difficult to define.

³This article is based primarily on the results of semi-directed interviews performed as part of a research project funded by the PIRVE (call for proposals 2008: "What is the place of wooded areas in city development?") and the ANR (call for proposals 2008, Sustainable Cities: "Trame verte urbaine, Assessment of urban green spaces and development of a reference document: combining aesthetics and ecology within a new urban infrastructure" -see Clergeau and Blanc 2013.) 1 ation of pain treatment in order to examine how patients suffering from pain not only succeed in expressing their pain but also work to take control of it, enter into a relation with it and tolerate it [START_REF] Guyard | Descriptions de la douleur quatre fois contraintes[END_REF]. It might seem surprising to want to compare individuals' relations with "nature" with the experience of pain because the former, according to the interviewees themselves, is mostly pleasant whereas the latter, by definition, is particularly unpleasant. However, it seems to us that there are a number of methodological and phenomenological lessons that can be drawn from this comparison. This is firstly because both cases relate to the subjective experience of something biological (situated within us in the case of pain or outside of us in the case of species and habitats). Secondly, though, this is because both cases relate to an experience that is difficult to express while the methods most commonly employed in sociological studies (interviews, focus groups, questionnaires) are based on the need for verbalization. It therefore seemed to us that an examination of the ways in which patients construct their relation with pain might be of use to sociologists, ethnologists and anthropologists who are interested in the way in which humans construct their relations with species and habitats or, more broadly, human or non-human living entities [START_REF] Descola | Beyond Nature and Culture[END_REF].

Just as our colleagues have investigated the "common" experience of pain compared to the expert knowledge of it assembled by doctors, we are interested here in the "common" experience that non-specialists might have of their environment. Our standpoint is therefore different from that of the sociology of science which is more interested in the definition of habitat and species by biologists and ecologists. Instead, the starting point for the ideas developed here took the form of semi-directed interviews conducted among users of public parks and gardens in Angers, Nantes and Rennes ⁴. However, the present article also draws on material relating to other surveys that we have performed in the past (Le [START_REF] Bot | Les habitants et la biodiversité[END_REF][START_REF] Bot | Analyse des critères de vulnérabilité de la biodiversité d'espaces anthropisés en zone rurale, littorale et urbaine. Le cas des landes du Cragou, des marais côtiers de Séné et de l'agglomération de Rennes[END_REF] and we have extended the scope of the included data to other sociological reports and even works of literature. The types of environment covered by our survey consisted of habitats (urban parks and gardens) which distinguish themselves from the adjoining built areas by the massive presence of vegetation. They were nonetheless "Regularly or recently cultivated agricultural, horticultural and domestic habitats" as defined by the European Nature Information System (EUNIS) habitat classification (code I, 2007). We will therefore designate them as "seemingly natural spaces" ⁵ (SNS below). Without wishing to enter into any extensive discussion on this point, it should, however, be noted that the persons interviewed spontaneously spoke in terms ⁴These interviews were conducted and transcribed by Françoise Philip during a postdoctoral fellowship. We should like to thank her very much for her work.

⁵See, for instance, [START_REF] Carr | Wilderness by Design: Landscape Architecture and the National Park Service[END_REF]Niemann 2000, p. 70;Wrobel 2002, p. 196. In the original French version of this article we used the locution "espaces à caractère naturel" [START_REF] Clergeau | Une écologie du paysage urbain[END_REF]).

of "nature" when referring to these spaces due, in particular, to the high level of vegetation which contrasts with the surrounding built environment. The term "nature" was also the one that most easily permitted the establishment of a contact during the conduct of these interviews (more precise terms such as "biodiversity", "species", "habitat" are not sufficiently well known and were not necessarily meaningful for the interviewed persons). The fact that we speak of the subjective experience of "nature" in the title of this article consequently reflects the utterances of the persons interviewed during the survey. From a theoretical perspective, our point of reference is the same as that used by the authors of the above-mentioned article on the experience of pain: it is the theory of mediation, or clinical anthropology, which, based on clinical experience, attempts to identify the various rational principles through which humans construct their relations with the world [START_REF] Gagnepain | Du vouloir dire[END_REF]Gagnepain 1991;Le Bot 2010;Le Bot 2013;Le Bot 2014). Starting from a differential approach to pathologies, it has been able to subdivide human reason into four "planes" of mediation, namely grammatical abstraction (sign model), technical artifice (tool model), ethnic absence (person model) and ethical abstinence (norm model). Following the four main sections of the article on pain, albeit in a slightly different order, we shall therefore examine in turn how the park and garden environment is conceptualized, fabricated, personalized and incorporated, as well as appreciated by its users for the pleasure it gives them.

Perception and conceptualization

The interview technique, in widespread use in sociology as well as in the medical field, albeit with different ends in mind in the case of medical interviews, collects people's utterances about what they think, do, feel, experience etc. [START_REF] Beaud | Alors ? Comment allez-vous ? Entrée en matière dans une consultation médicale[END_REF]. However, as soon as we speak about somethingwhether it be pain or the different elements of an environment -that thing is necessarily shaped by language. To understand what is said, it is therefore necessary to pay attention to the properties of language. Since there are many aspects of linguistic determinism and we do not intend to consider them all here, we shall consider only, and by way of example, the question of semantic differentiation. With reference to pain, one patient suffering from migraine described a pain which first of all "squeezed everywhere" and then "banged on one side only" (Guyard and Cahagne 2006, p. 16). She therefore used different words or expressions to distinguish between two pains which themselves were experienced differently and in different locations. The same approach can be found when we turn to the description of habitats and species. It is true that the ecological, zoological and botanical vocabulary of the city dwellers we interviewed was generally very lim-ited ⁶. Indeed, they distinguished far fewer taxa than a professional naturalist or informed amateur would have done, and nowhere near as many as the Hanunóo [START_REF] Conklin | Hanunóo Color Categories[END_REF], Breton fishermen [START_REF] Berr | Ichtyonymie bretonne[END_REF][START_REF] Berre | Ichtyonymie bretonne, DVD[END_REF] or the informants of the many other peoples referred to by [START_REF] Lévi-Strauss | The Savage Mind[END_REF] were able to do. Our surveys therefore confirm what N. Blanc said about the low level of knowledge of the plant or animal realms possessed by most city dwellers born in urban environments and the paucity of their vocabulary in this domain (Blanc 2000, p. 115). However, they nonetheless make a number of distinctions that are attested to by the observed lexical differences. When asked to give the names of various taxa very common in the area in which the survey was held after seeing the corresponding color pictures, they were able to develop hypotheses based on a range of perceptual cues:

[Picture of an oak tree with acorns] "It's a walnut. -No, no, it's an oak. -Yes, it's an oak, I didn't look carefully enough" (M, 16 years). "Acorns, but I don't know what the tree is" (F, 23 year).

[Picture of a yew] "It looks like a pine, you'd think it was a conifer" (M, 22 years).

[Picture of an elderberry] "Are they blueberries, something like that? They're red…" (M, 16 years). "My mother makes jam with those, are they morels? Oh yes, elderberries?" (F, 42 years).

Even though these people did not give the "right" name, they made a lot of distinctions and did not answer at random. Although in the last of the statements cited above there was a clear acknowledgment of the utility of the item (used to make jam), there was also perhaps a phonological derivation effect (in French, the words used were "morille/myrtille", corresponding to morel mushrooms/blueberries), since elderberries (french "sureau") were frequently referred to as blueberries (french "myrtilles"). Furthermore, when the respondents produced the term "bruyère" (heather) when asked to name ferns ("fougère"), it is very possible either that a phonological derivation (bruyère/fougère) occurred or that the interviews identified the shared semantic field (heathland plants). This identification of a common semantic field was also found when horse chestnut trees were referred to as sweet chestnuts, doves were called pigeons, and cyclamens were dubbed peonies or crocuses. Thus, in all these cases, although the interviewees did not give the "right" name, their answers were not without semantic relevance. However, the most important point to note is that the respondents made use of the polysemy of words (the absence of a bijective correspondence between words and things) when attempting to name what they had distinguished at the perceptual level. This naming involved a process of synonymy: "pine" and "confer" are not "yew" but they can act as quasi-synonyms in the right situation. The search for precision and a suitable designation for the item to be named then proceeded via a series of reformulations: "They look like redcurrants but they're not" (M, 22 years). The search for precision may also make use of periphrasis. For example, one interviewee recognized the picture of a dove but called it "a land gull" (F, 74 years). In the absence of any other lexeme, this expression acted here as a synonym of "dove". Another person was unable to give the name "cherry laurel" but nevertheless responded "it's what you find in garden hedges" (F, 71 years). Another recognized the picture of dandelions but said "They're marigolds. It's a wild plant but I can't remember the name" (F, 48 years). In a survey conducted by other sociologists, the interviewed walkers, without recognizing Prunus serotina as such, designated it using periphrases such as "the tree that's everywhere" or "the tree you find everywhere" (Dalla Bernardina 2010, p. 84 ;[START_REF] Javelle | Les aspects sociaux d'une invasion biologique en forêt domaniale de Compiègne : la construction sociale de Prunus serotina[END_REF]. If I might be permitted to recount my own experience, I long used a similar periphrasis ("the odd plant near the level crossing") to refer to Japanese knotweed (Reynoutria japonica). These few examples suffice to show that the paucity of the available vocabulary does not mean that everything is indistinct. It is possible to perceive and identify differences between taxa even in the absence of the lexemes that would permit an extremely precise designation and this perception may sometimes lead the speaker to search for more appropriate designations: "Number 4, I'd say it's a tree fern. I recognize it but I don't know the name" (F, 33 years), "We know these trees because we see them, but we don't know what they are" (F, 25 years). The paucity of the vocabulary does therefore not necessarily mean that perception of or attention paid to the living environment are equally impoverished ⁷. Guyard and Cahagne (2006, p. 16) observed the same phenomenon in connection with pain: verbal reasoning makes it possible to produce hypothetical names for the perceived feelings of pain. However, these hypotheses in turn make it possible to choose between various possible formulations, guide the search for the most appropriate formulations and lead individuals to enrich these. What therefore emerges is a dialectical relation between (non-verbal) perceptual distinctions and the more or less precise designation of these distinctions. As in the case of pain, this teaches us a methodological lesson: even if it is unclear what survey technique would make it possible to record perceptions directly without the need for naming, the restricted capacity to produce names should not be considered an obstacle. Instead, it is important to encourage the dialectical process of stating ⁷A clinical argument can be called on in support of this observation: aphasic patients with impaired grammatical capabilities who are no longer able to name objects are no less capable of distinguishing between them at the perceptual level. They sometimes say themselves that they know what the thing is but cannot give its name [START_REF] Laplane | La pensée d'outre-mot -La pensée sans langage et les relations pensée-langage[END_REF][START_REF] Brackelaire | Les mots se regardent. Initiation à un questionnement clinique sur le langage en sciences de l'homme[END_REF].

precisely what is perceived, without necessarily expecting the resulting descriptions to correspond precisely to the expert designations.

Equipment and the technical control level

Our colleagues, who are accustomed to the clinical experience of pain, have also emphasized the range of techniques, from personal habits through to the use of medication, with which patients attempt to manage their pain (Guyard and Cahagne 2006, pp. 18-19). This "technical" dimension is also found in the relation between individuals and the environment. In this regard, it is once again necessary to point out that the areas that were the object of our surveys were not wild, uncontrolled areas but spaces designed by and for humans. These habitats have been constructed over time though the deployment of various agricultural or horticultural techniques. Admittedly, as a result of greenspace differenciated management by the municipal parks and gardens department, the plant life in certain selected areas is now allowed to develop in a more spontaneous manner than in the past [START_REF] Menozzi | Mauvaises herbes', qualité de l'eau et entretien des espaces[END_REF]). However, this (relative) spontaneity can only be designated as such by comparison with other far more interventionist approaches in other areas or by comparison with the built environment. In all cases, these are examples of "composed" or "recomposed nature", as described by Mathevet (2004), which can be analyzed, at the technical level, in terms of an alternation of built spaces and green spaces, themselves distinguished by the application of different management practices. Many of the persons interviewed stressed this alternation: "There's a risk that the city of Rennes might turn into a park. There has to be a difference: a part that's park and a part that's city" (M, 16 years). In this "recomposed nature", users generally allow themselves to be guided by the technical installations provided by the managers -pathways, play areas, picnic tables, benches -and often want there to be more of them. Of course, they also bring their own technical equipment. Admittedly, this is often very simple: clothes, shoes, bike ⁸, etc. However, it has an influence on the way walkers may perceive their environment: it plays the role of (technical) mediator between them and the environment. Thus, one of the persons interviewed criticized the material previously used for the paths of a park in Rennes: "They'd put down stones on the paths and that hurt your feet when you walked. But now it's ⁸M. Mauss has emphasized the extent to which wearing shoes modifies the position of the feet while walking and consequently the human gait as well (Mauss 1979, p. 102). However, wearing shoes also modifies contact with the ground and consequently the feelings experienced when putting one's feet down. This was what one young woman, who came to the park to relax, told us: "I always come in flip-flops so I can walk barefoot. I feel the grass. I like the feeling; it tickles" (F, 19 years).

better, they've put down sand" (M, 45 years). The condition of these paths may encourage or discourage the presence of pushchairs and the absence of appropriate provisions may completely exclude wheelchair users. At the same time, the speed at which horse riders or cross-country cyclists travel means that they do not see what walkers see [START_REF] Javelle | Les aspects sociaux d'une invasion biologique en forêt domaniale de Compiègne : la construction sociale de Prunus serotina[END_REF]Dalla Bernardina 2010, p. 84). This phenomenon resembles what S. Chanvallon said about diving flippers. Although they clearly make it easier for people to move around in the underwater environment, the "modification to the mode of propulsion" they bring about also results in "new perceptions" (Chanvallon 2009, p. 120). The technical equipment therefore not only influence the sensations felt in contact with the environment but also our knowledge of this environment. It should also be added that the technical equipment does not just modify the sensations or contact that walkers may have with the environment. Just like patients experiencing pain who are able to engineer their own medication, walkers can engineer their environment and act on it in their own ways to gain a certain level of control. The environment thus becomes a reserve of food or materials while all types of artifice are used to modify it (Dalla Bernardina 2010, p. 85). And it is this reference to a technical utilization of the environment that may make it possible to designate a given taxon: "I don't know its name but my father called them firecrackers. You take off the small flower, squeeze it between your thumbs and it goes bang" (M, 41 years, talking about a foxglove).

Personification and reminiscences

In their observations of the experience of pain, Guyard and Cahagne also showed how pain initially seems to be foreign to patients who feel themselves to be "invaded", "modified" and sometimes even "dominated" by it. They then need to reconstruct a story which encompasses this "strange, rapacious figure which gives them no respite and incessantly torments them" (Guyard and Cahagne 2006, p. 16). In this story, the patients are first of all the "victims" of the pain. However, they also "fight" it, enjoy "victories" and suffer "defeats" which might oblige them to "compromise", to agree on a sort of contract. That is to say that the experience of pain is almost always accompanied by a personification of it as an enemy that one can attempt to hold in check even if it is impossible to vanquish it. This type of personification also occurs very frequently in relation to the environment even without it being necessary to evoke any type of "savage mind" (Lévi-Strauss 1966) or any particular ontology whether "animistic" or "totemistic" [START_REF] Descola | Beyond Nature and Culture[END_REF]. To personify certain non-human beings seems to us to be part of a very commonplace experience, including in western urban societies in which a naturalistic ontology nevertheless predominates (ibid.). S. Dalla Bernardina thus refers to a study that shows how "voles are thought of as ingenious tacticians" or how Ulva armoricana algae are perceived as a presence that is waiting for its time to come (Dalla Bernardina 2010, p. 67). In a similar vein, we can cite the words used by this female respondent to our survey when talking about pollution: "It's everywhere. It moves around. It's even in the countryside" (F, 60 years). Invasive species are declared "public enemies" and are themselves personified (as in a brochure published by the Institut Klorane on the subject of invasive exotic plants ⁹). The vocabulary used by ecologists itself undoubtedly helps maintain and even promote this personification of an active "nature" that sometimes avenges itself. In the early 20th century, P. Sébillot reported that the inhabitants of Tréguier, in the north of Brittany, believed that the sea would punish those who dared to dirty it (ibid., p. 72). More than a century later, a lecturer at the Paris Institute of Political Studies writing about the accident at the Fukushima nuclear power station said that "the first visual impact is the irruption of a violent nature that is perhaps avenging itself" (Libération, 1st April 2011). However, the great difference between this and the experience of pain, in which the latter appears first and foremost as an enemy that persecutes its victim, is that in the experience that our interviewed city-dwellers have of SNS, these or certain of their components are more often represented as friends rather than as enemies: "I like trees a lot […]. That might be due to my background.

[…] I was born in the Ardennes forest. I'm particularly fond of woodland areas. Some people need the sea to feel at ease, other people need the mountains, for me the forest is where I feel at ease. I feel happy among the trees" (M, 57 years). Another man evoked "a need that we have as living beings. We can't detach ourselves from the living environment around us, from the Earth that feeds us". He went on to speak of "the presence of the water and the trees. I try to benefit from them as much as possible. When you take the time to stay among them and savor them, there are other things that appear: little secrets, other, deeper levels of communicating with nature and the location may reveal themselves. […] I've loved nature ever since I was small" (M, 36 years). Without exhibiting the same intense level of attachment, many people visit parks to "get close to nature" (F, 23 years). Another woman told us: "I like greenery, silence, peace and quiet. I can't give any other explanation. I love nature. I feel well when I'm in nature. It recharges my batteries. It makes me think of more positive things" (F, 65 years). This experienced presence of what the interviewees themselves call "nature" is a reason to relativise the "great divide" which is often considered to be one of the characteristics of western culture [START_REF] Descola | Beyond Nature and Culture[END_REF]. In spite of this "great di-⁹https://www.doc-developpement-durable.org/file/ programmes-de-sensibilisations/environnement-ecologie/ plantes-invasives/Guide_plantes_exotiques_envahissantes.pdf [accessed 27 Jun 2018].

vide", which is the result, in the western world, of a whole body of sophisticated thought from the ancient Greeks onwards, we can observe many examples, in the heart of that same western world and in different eras, of a very different relationship with the "existings" that form our environment. Our hypothesis is that there is nothing here that is specific to a "savage" or primitive mind but that it is instead due to the fact that, because of their human nature, people have a tendency to personify non-humans (Le Bot 2010; Le Bot 2013). It is therefore necessary to pay attention to the way in which the person, or Self, of the interviewees, which is not reducible to language effects ¹⁰, enter into relation with these non-human others. However, the interviews also show that the experience of a relationship of friendship with "nature" is very frequently associated with early contact with it and that the other, here, may form a part of the Self. In effect, many of the people interviewed in these parks and gardens were attempting to rediscover a rural environment that they had known in their childhoods and which, however remote in time that might have been, they still carried within them: "In my childhood, I grew up next to a pond and there was nature all around. And this reminds me of it, all this reminds me of my childhood" (F, 65 years). If it is true that the child is a dimension of the person [START_REF] Quentel | L'enfant. Problèmes de genèse et d'histoire[END_REF], if it is true that the habitus is an "embodied history, internalized as a second nature" which "gives disproportionate weight to early experience" (Bourdieu 1990, pp. 54-56), and if it is also true that "the world internalized in primary socialization is so much more firmly entrenched in consciousness than worlds internalized in secondary socializations" (Berger and Luckmann 1991, p. 78), then it is not surprising that these positive or negative childhood experiences of the environment, whether more or less urban or rural in nature, determine the relationship that individuals have with this same environment once they have become adults. What is more, these experiences of the environment during childhood, just like the experiences of the social world of childhood, are still within us even if we believe that we have forgotten them. Everyone carries within himself/herself landscapes, skies, smells and sounds that may reappear in the form of reminiscences. It is also this that makes it possible to go "in search of lost time" (Proust). Indeed, for this to be possible, for time to be "regained", it must still be present within us. The experiences of reminiscences that literature (from Chateaubriand to Proust) has made famous presuppose a memory which, as clinical neuropsychology has shown, is erased in certain amnesias: lost time is then definitively lost and can no longer be "regained" ¹¹. O. Sacks has provided a gripping description of this type of amnesia and its consequences for social life in an account of a patient suffering from Korsakoff's syndrome ("The Lost Mariner", Sacks 1995). In con-¹⁰For more information on this question, see also [START_REF] Bloch | La mémoire autobiographique et le Soi. Pour une alliance entre sciences sociales et sciences cognitives[END_REF]. ¹¹Patients suffering from episodic memory disorders definitively lose a part of their past.

trast, in other cases, which do not correspond to amnesias but can be provoked by a stimulation of a precise area of the cortex, patients experience extended "Proust-like" reminiscence. In one such case, the reminiscences provoked by an epileptic fit allowed an elderly woman to rediscover the happy times of her childhood and a renewed serenity ("Reminiscences", ibid.). Such cases both explain and justify the concept of "embodied history" used by Bourdieu to define the habitus. Indeed, the neuropsychology of amnesias and reminiscences shows that this "embodiment" of each individual's history does take place, while also providing information about its neurological determinants ¹². Our hypothesis therefore is that certain affinities with landscapes, habitats or species can be explained by this presence in us of an entire environment inherited from our primary socialization and that this may be manifested through experiences of reminiscence. Literature provides us with many examples. There is, of course, the famous "episode of the madeleine" in Marcel Proust's Search of Lost Time. But there is also the "romanticism" of Chateaubriand which owes much to the writer's childhood affinity with the countryside of Brittany, that "the song of a thrush perched on the topmost branch of a silver birch" allows him to remember many years later ¹³. And the "Frontenac Mystery", in Mauriac's novel, is in part the result of the same type of affinity between the Frontenacs and their land with, as life and the seasons move on, the smell of mignonette coming from the flowering vines, the oaks, the streams with their crayfish, the rains brought by storms, the wasps attracted in the summer by the fruit bowls laden with peaches, the murmuring of the westerly winds among the pines… In anthropology, it is well known that the attachment to a territory, to a "homeland", is essential in the definition of an ethnic group (see for instance [START_REF] Simon | Aspects de l'identité bretonne[END_REF]). Breton-ness, for instance, "is inconceivable […] without reference and intense attachment to this part of the world known as Brittany" (ibid.). However, Simon adds that "it is not enough to talk about a territory. It is important to understand that there is much more than that: a sky, a light, a climate, landscapes that have been profoundly influenced by man" (ibid.). And he also refers to the evidence of "the attachment of the working classes to their place of origin in the many songs sung by the conscripts" of the 19th century, evidence which -it goes without saying -can be found not only among Bretons with regard to Brittany but potentially among all other human beings with regard to their region of origin. It seems to us that we are in the presence here of a "rooting of identity" in the genius loci which is for Descola a characteristic of the totemistic ontology [START_REF] Descola | Beyond Nature and Culture[END_REF]. ¹²See also the works on brain plasticity and mental and synaptic traces [START_REF] Ansermet | À chacun son cerveau. Plasticité neuronale et inconscient[END_REF].

¹³Mémoires d'outre-tombe, book II, chap. 9 (Kline's translation:

Evaluating pleasure and avoiding displeasure

Unlike the experience of pain which consists of suffering and displeasure, the experience of nature, as our interviewees described it, is usually pleasant. In both cases, however, we are dealing with affects and it is again important to be attentive to what is said in this regard during an interview. Even if they do not necessarily say so quite as directly, visits to SNS are motivated first and foremost by the pleasure that users experience there. However, like suffering, pleasure can be evaluated. It has different degrees: some pleasures are more intense than others. Thus to examine people's relations with the habitats and species present in the environment is also to examine the pleasure they procure and how they measure this pleasure. Time spent in SNS therefore appears to be a sought-after good which is attributed a greater or lesser level of importance and obtained at the cost of certain efforts or precautions undertaken precisely in order to avoid the risk of this pleasure being spoiled. An analysis of the interviews confirms first of all that the pleasure of visiting SNS is associated with a certain cost in terms of physical effort or traveling time. While our interviewees did not express this cost in economic terms, in particular because the places where we conducted our surveys were freely accessible public spaces, they were sensitive to the issue of proximity which facilitates access by reducing traveling times. Thus, when asked why they preferred one of the parks in Rennes, two high school students replied "it's just because the Thabor [another park] is a long way from where we live and we go on foot. And when it's hot, we get lazy and stay here". When the opportunity for pleasure arises, people grab it. They "take advantage" of the good weather (F, 25 years) or the presence of a park near where they live or work: "This park is so relaxing. I'm lucky to work near a park like this. It's a piece of luck and I take advantage of. To tell the truth, I find it difficult to understand why my workmates don't do the same" (F, 33 years). They enjoy the spectacle: "The trees are superb at the moment.

[…] They're magnificent, full of flowers.

[…] At the moment everything's growing and looking lovely. And the weather's nice" (F, 60 years). This pleasure also consists in getting rid of anxiety or "stress", in "clearing your head", "chilling out", "getting some fresh air", "relaxing". After that, you "work better", "sleep better" and you are "more at ease". These expressions were frequently encountered in our interviews. Going to SNS seems to make it possible to release a tension that is felt to be something unpleasant: the experience of pleasure and well-being thus seems to correspond to its Freudian definition as a release of tension [START_REF] Freud | Three Essays on the Theory of Sexuality[END_REF]. However, beyond this sensation of feeling better or of immediate pleasure, the sought-after good can also take the form of one's health: "I walk for twenty minutes or half an hour. That's what's recommended for your health" (F, 33 years), "I just do the small circular walk. It's just to stay in shape" (F, 23 years). A few precautions, which may be more or less significant depending on the case in question, ensure that pleasure does not turn into displeasure, that something good does not become something bad. Thus one elderly woman (71 years), who was suffering from a pain in her hip, had decided to come less frequently to the park by foot, a walk of 20 minutes from her home, during the periods when she wanted to enjoy a stroll in the park. It is a question of not overdoing things: for walking to remain a pleasure, it is important not to do too much of it at once. Other precautions relate more to avoidance. Some people, who are looking for peace and quiet, avoid places where the sound of traffic is too pervasive or where there are too many people, or the days or times when the park is crowded. In effect, there is a danger that crowds or noise might spoil the pleasure: "up there, there's an area that's absolutely full of motor scooters and that spoils what I enjoy here: the silence" (M, 57 years). Other people (or sometimes the same people) avoid spots that are too isolated and represent a source of anxiety: "You'd have to ask them why they don't come. I think that in part it might be the fear of being alone. That worries people. The fear that you might be attacked" (F, 33 years). People also attempt to avoid pollution, such as this woman who was collecting dandelions to use in a salad but who was careful not to gather them from the roadside because "there's too much pollution" (F, 60 years). Variety and contrast also contribute to the experience of pleasure. People walk "where the mood takes them" and along "the paths that appear on the way": "it's pleasant, it's not the same thing all the time" (F, 45 years). This dimension of affects and pleasure is simply the dimension of the emotions which, as our interviews revealed, are mostly pleasant and which the various precautions that are taken attempt to preserve in this state. However, that amounts to saying that, in the absence of precautions or in certain circumstances that are difficult to control, these positive emotions could change into negative emotions that are synonymous with displeasure. In this regard, we can also point to certain observations made by F. [START_REF] Terrasson | La peur de la nature[END_REF] who considered the negative emotions ("the fear of nature") to be the cause of destructive behaviors and indeed, many frequent and easily observable behaviors would seem to support this theory: people tread on a spider, kick the mushrooms or an ant hill, kill a snake. However, we believe that what is at stake here is less the negative or positive character of the emotions as such but the inability to control them and the impulses they trigger. This is because the pleasure experienced in SNS may lead to behaviors that are just as destructive as those caused by fear unless they are controlled. Although we did not observe any such examples in our surveys, S. Dalla Bernardina rightly refers to those moments when people, whether as hunters or fishers, allow their behavior to be dictated by the "principle of pleasure" when it triumphs over the "principle of reality" (Dalla Bernardina 2010, p. 71). In brief, what makes behavior destructive is not so much the emotion or impulse itself, whether positive or negative, but rather the lack of ethical control over it which, in turn, makes it possible to justify and measure, with a certain critical distance, both pleasure and displeasure.

Conclusion

"Who can be in any doubt that the functioning of memory and self-awareness are phenomena that comprise a psychological dimension?" asks M. Bloch ¹⁴, who immediately adds that "when they deal with these issues, the social sciences cannot therefore act as if the cognitive sciences did not exist" [START_REF] Bloch | La mémoire autobiographique et le Soi. Pour une alliance entre sciences sociales et sciences cognitives[END_REF]. Similarly, can anyone doubt that feeling, perception and representation are phenomena which comprise a psychological dimension and, in the latter case at least, a linguistic dimension? When they turn their attention to the perception or representation of the environment, therefore, social anthropology and sociology cannot act as if psychology (and more specifically clinical neuropsychology) and linguistics did not exist. That is why, inspired by research into the experience of pain conducted within the framework of clinical anthropology, we wanted to show that the relation with the habitats and species that constitute the environments we refer to as SNS and, beyond this, the relation with the environment more generally, is just as complex as the relation with pain. The empirical material that we were able to use, taken from our own surveys or the works of other researchers in the fields of environmental sociology or anthropology, lend support to the hypothesis that the relation with the environment is "mediated" in ways similar to those observed in connection with the relation to pain by clinical practitioners. This constitutes an interesting methodological lesson that argues in favor of greater interdisciplinary collaboration in the field of environment-related research in the human and social sciences, between the field survey-oriented disciplines of social and cultural anthropology, on the one hand, and clinical anthropology on the other. It is not a question of attempting to find in what is said a confirmation of the researcher's hypotheses but instead of attending more precisely to what is said, done, experienced and felt -even when, once again, the experience seems almost impossible to express.

  http://www.poetryintranslation.com/PITBR/Chateaubriand/ ChateaubriandMemoirsBookII.htm [accessed 27 Jun 2018]).

⁶However, it does vary depending on a number of factors including, unsurprisingly, the rural or urban origin of the interviewee and academic level (Le Bot and Sauvage 2011).

¹⁴Autobiographical memory presupposes episodic memory, which has been clearly identified by clinical neuropsychology, which is not specific to humans and which makes the reminiscences we have discussed possible. It also permits semantic memory[START_REF] Warrington | The selective impairment of semantic memory[END_REF] which makes it possible to integrate it within a history.


Eddy Caron
email: eddy.caron@ens-lyon.fr

Marcos Dias De Assunção
email: marcos.dias.de.assuncao@ens-lyon.fr

Multi-Criteria Malleable Task Management for Hybrid-Cloud Platforms

The use of large distributed computing infrastructure is a means to address the ever increasing resource demands of scientific and commercial applications. The scale of current large-scale computing infrastructures and their heterogeneity make scheduling applications an increasingly complex task. Cloud computing minimises the heterogeneity by using virtualisation mechanisms, but poses new challenges to middleware developers, such as the management of virtualisation, elasticity and economic models. In this context, this work proposes algorithms for efficient scheduling and execution of malleable computing tasks with high granularity while taking into account multiple optimisation criteria such as resource cost and computation time. We focus on hybrid platforms that comprise both clusters and cloud providers. We define and formalise the main aspects of the problem, introduce the difference between local and global scheduling algorithms and evaluate their efficiency using discrete-event simulation.

I. INTRODUCTION

Managing and providing compute resources to user applications is one of the main challenges tackled by the distributed computing community. To manage available resources, existing solutions rely on abstractions where users submit application requests to a management system or middleware responsible for task scheduling and resource allocation. Over the years, with varying levels of heterogeneity and success, several types of distributed infrastructure have been established to provide users with the resources they need to execute their applications. Cloud computing, by making use of resource virtualisation, has enabled the provision of more standard resource units (i.e. virtual machines) that are allocated atop underlying physical infrastructure.

From the point of view of allocating cloud resources to be managed by a middleware for running application tasks, the allocation can be either static, where a fixed number of resources is allocated; or dynamic, a scenario in which resources are allocated or released on demand to match the applications workload. Among the possible types of deployment, one can identify centralised, where the middleware is deployed in a single cloud; a federation, in which the middleware manages resources obtained from multiple clouds; and hybrid, a case where cloud resources are used together with clusters, data centres and workstations.

For reasons of cost, availability, control, and avoidance of provider lock-in, many organisations prefer to maintain and manage local infrastructure (e.g., their own clusters and data centres) while using a cloud for certain workloads, and sometimes they exploit multiple cloud offerings simultaneously. Such hybrid deployment scenarios considered in the present work, are hereafter termed as hybrid-cloud platforms. Although the problem of scheduling requests onto available resources has been extensively investigated [START_REF] Agrawal | Energy-aware scheduling of distributed systems[END_REF], [START_REF] Tracy D Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF], [START_REF] Ramamritham | Dynamic task scheduling in hard real-time distributed systems[END_REF], the number of criteria taken into account when scheduling application tasks is generally limited. Moreover, cloud computing and the increasing availability of commercial offerings force middleware designers to deal with several additional issues related to managing virtualisation, exploiting elasticity, and multiple economical models.

In this work we investigate the problem of multicriteria management and scheduling of malleable tasks [START_REF] Trystram | Scheduling parallel applications using malleable tasks on clusters[END_REF]. These tasks provide a high level of granularity and parallelisation and have numerous practical applications in scientific and real-life computations [START_REF] Kendall | High performance computational chemistry: An overview of nwchem a distributed parallel application[END_REF], [START_REF] Rampersaud | Computing nash equilibria in bimatrix games: Gpu-based parallel support enumeration[END_REF], [START_REF] Zenios | High-performance computing in finance: The last 10 years and the next[END_REF]. In contrast to previous work that restricted the optimisation criteria for scheduling, the present work investigates algorithms to schedule and efficiently execute malleable computing tasks with high granularity while taking into account multiple optimisation criteria such as resource cost and computation time.

The rest of this paper is organised as follows. Section II presents background on hybrid platforms with multiple types of resources. Section III defines and formalises the main aspects of the considered problem, introduces the difference between local and global scheduling, and describes the main steps of the scheduling algorithms. Detailed explanation of local scheduling algorithms and realisations for the different types of platforms are found in Section IV. Section V presents a global scheduling algorithm and discusses means to optimise it. Description of simulation settings and results on performance evaluation of the algorithms are presented in Section VI. A discussion of existing work is given in Section VII, whereas the last section concludes the paper.

II. PLATFORM FRAMEWORK

This work focuses on scheduling of malleable tasks onto heterogeneous resources, considering several types of computing infrastructures for middleware deployment. We use the terms job and task interchangeably. Our goal is to leverage the heterogeneity of underlying available resources to devise efficient scheduling strategies. The tasks are submitted to a hybrid-cloud platform through a single interface provided by the global scheduler and are scheduled on various types of systems detailed next. Each system has its local scheduler that strives to respect tasks requirements. The acceptance of a job by a local scheduler can trigger rescheduling activities that can in turn result in migration of previously scheduled tasks to other systems. The rest of this section describes the three types of resource infrastructures considered, whereas the next section details the (re)scheduling activities that schedulers perform.

A. Dedicated Cluster

A dedicated cluster is entirely available to a user or client. By default, it is highly available and is viewed by a user as a computing resource with negligible cost. Its performance, however, is bounded and static, a reason why many organisations also use clusters along with other types of on-demand infrastructure.

B. Computing Centre

A computing centre is a fee-based resource, where the computation price P i per hour of a job i can be estimated as:

P i = t i × n i × k
where t i is computation time, n i the number of used processors, and k is the cost of using a processor over an hour. Here k accounts for the fixed and variable costs incurred by providers when offering and managing infrastructure, such as energy consumption, management personnel and so forth. This formula can in fact be used for all fee-based resources whose price is taken into account during scheduling.

C. Cloud Infrastructure

A cloud is a more recent model of distributed computing infrastructure under which a resource provider acquires a certain number of servers that are in turn rented out to users. Considering Amazon EC2, a widely used Infrastructure as a Service (IaaS) provider, virtual machine instances can be leased by customers under various models: reserved instances, on-demand instances and spot instances. This work considers the use of spot instances as they are usually cheaper than their on-demand counterparts. Switching to on-demand instances is possible when Amazon EC2 cannot provide the required number of spot instances. The use of reserved instances may be more appealing when the cloud usage grows large and yearly reservation ends up justifying the pre-allocation of multiple reserved instances.

The choice of the platform types described above is motivated by the fact that they are frequently used by enterprises. Dedicated clusters correspond to computing resources owned by an enterprise. It should be used as much as possible to maximise return of investment. Cluster resources shared with or rented from partners are referred here as allocated clusters. Use of the cloud depends on the charge of the resources mentioned above as well as on cloud provider prices.

III. PROBLEM AND SCHEDULING STEPS

The problem of scheduling malleable tasks onto hybrid clouds is split into two levels, namely:

• Local scheduling: which handles tasks at a locally controlled resource.

• Global scheduling: responsible for selecting a resource to which a new task is assigned. Algorithms at this level schedule tasks considering the overall distributed infrastructure.

The optimisation criteria provided for task scheduling can be conflicting. The introduced algorithms consider three criteria: deadline, budget and task priority. The goal is to assign a task to a computing resource so that the price paid for its use and the task's makespan respect, respectively, the task's budget and deadline constraints. A local scheduler sorts tasks by decreasing order of priority when selecting a task to execute.

The task parameters are explained as follows. The input of scheduling consists of a tuple (T, R), where T comprises computing tasks and information about their computational complexity, priority, deadline, maximum budget for execution, or other parameters that a user might find relevant. An individual task is represented as T task_id :

T task_id = (task_id, size, priority, deadline, budget) R, on the other hand, describes a set of hosts with parameters such as type, performance (MFlops/CPU), usage cost (e.g. cost per CPU hour as P i previously introduced in Section II), and number of CPUs: R rsc_id = (rsc_id, type, perf ormance, cost, nbCP U ) While T task_id is information provided by a user, R rsc_id describes a computing resource managed by the middleware. The scheduling objective is to provide mappings of (T, R) such that a candidate resource R rsc_id is as closer a match to a task T task_id requirements as possible.

The scheduling Step 1 defines two parameter sets for a given tuple (T task_id , R rsc_id ) namely optimising cost and computation time (i.e. makespan):

{P cost , P perf } = create_schedules(T task_id , R rsc_id )
The building of such schedules depends on the type of resources considered for task execution -e.g. for a cloud we can vary the number and type of machines. Although task execution on a low-power machine will be cheaper, it may take longer than allocating several powerful instances. For clusters the balance of makespan and price depends on the reservation strategy in place. The speed-up of using multiple processor cores is rarely linear, so usually the more processors we use the smaller is the performance/price ratio. The number of reserved time slots also correlates with the ratio because of deployment and start-time overhead; i.e., an application needs time to start running. Although this execution time is usually paid for, it is not actually used for task execution. Specific optimisation schemes to handle this step are given in Section IV which describes the resource-specific local algorithms.

A submission strategy P strategy defines the actual execution cost, the list of processors used for computation, the intervals over which processors will be allocated as specified by start (st) and end time (et), and the list of tasks to be executed with these parameters. More formally, a P strategy can be viewed as:

P strategy = (cost, {(cpu_id 1 , st 1 , et 1 ), (cpu_id 2 , st 2 , et 2 ), . . . , (cpu_id n , st n , et n )}, {tasks_to_migrate})
where tasks_to_migrate refers to tasks that will be rescheduled if the new task is accepted. A candidatea tuple composed of task, resource, submission parameters and the candidate type -hence refers to a computing resource that can suit a given job execution scenario; i.e., the expected job makespan, execution cost, and list of tasks to be rescheduled. Let us define a good candidate as a resource respecting both the deadline and budget of a task, and a bad candidate as one that does not respect at least one of the two constraints.

For each possible set of submission parameters, there exists a type of candidate (good or bad) that is initially set to null:

∀ strategy ∀rsc_id ∀task_id ∃ C strategy,rsc_id,task_id | C strategy,rsc_id,task_id = (T task_id , R rsc_id , P strategy , null) At scheduling
Step 2, a candidate status is represented by boolean whose value is true if the candidate parameters respect all the task requirements and false otherwise. A job makespan, when choosing a given candidate, is represented by:

P.makespan = max i P.cpu_usage i .et
Moreover, a candidate is considered good when the following inequality is respected:

IsGood(C i ) = C i .T.deadline ≥ C i .P.makespan & C i .T.budget ≥ C i .P.cost & C i .T.size ≥ j C i .P.tasks_to_migrate j
Next, the null value used on the previous step is replaced by the actual type of the candidate, true for a good candidate or false for a bad one. Hence, we redefine the types of all candidates in the previously described list as it is shown in the equation: C strategy,rsc_id,task_id = (T task_id , R rsc_id , P strategy , IsGood(C strategy,rsc_id,task_id ))

Step 3 splits the candidate set into two subsets namely containing good and bad candidates as represented by:

C good = {C i | IsGood(C i ) = true} C bad = {C i | IsGood(C i ) = f alse}
After that, Step 4 picks a candidate among the set of all the potential candidates {C i } to which a task is then submitted. For simplicity, we use a Heaviside step function to take into account the budget or deadline overhead:

H(x) = 0 if x ≤ 0 1 if x > 0.
3 Using this function we define the operator (•) + as:

(x) + = H(x) • x
If there exist good candidates, we pick the cheapest one. Otherwise, two simple strategies are possible for selecting a candidate C f etch :

1) Pick the least expensive candidate among those with smallest delay, where: C i such that:

{C f etch } = C ∈ {C i } | (
C opt = argmin C f etch .cost C f etch
2) Select the fastest candidate among those with smallest spent budget, where: C i such that:

{C f etch } = C ∈ {C i } | (
C opt = argmin C f etch .deadline C f etch

IV. LOCAL SCHEDULING ALGORITHMS

As each type of platform has its own characteristics, we provide a specific local scheduling algorithm for each one. The proposed algorithms, however, provide the same interface and expect the same parameters in order to take a decision on task scheduling. The common task parameters required by all algorithms in order to determine the scheduling of new task are namely: size, priority, deadline and budget.

A local scheduling algorithm can offer more than one possible candidate; for example, it gives the options of either respecting deadline or budget constraints, when both cannot be simultaneously respected. Moreover, the algorithm may not return any candidates at all, such as when the sum of the sizes of tasks to be rescheduled exceeds the new task's size. Therefore, all described algorithms provide as output a list of candidates even if it contains only one element.

The algorithms described next compute the candidate parameters. When a task submission candidate is placed in the queue, the preempted jobs should be rescheduled by the submitter of the new job.

A. Dedicated Cluster

Algorithm 1 presents the placement of tasks on a dedicated cluster according to their priority while striving to respect users requirements. The higher a task's priority, the earlier it is executed. Once a task becomes the first in the queue, it is executed using all available processors, as we target applications with high parallelisation levels.

As described earlier, when a new task is admitted by the scheduler the deadlines of previously scheduled tasks may no longer be respected. The possible decisions under such a case are the following:

• Reschedule tasks whose deadlines are no longer respected;

• Do not schedule the new job on the current host.

As illustrated by Algorithm 1, when a new job is received, the scheduler computes two lists namely with jobs whose priorities are lower than that of the received job (line 2), and one with jobs whose priorities are higher than the incoming job's (line 3). Then the algorithm checks whether the new job's deadline is respected (lines 5 to 10). After that, it determines the jobs whose deadlines can still be respected if scheduled on the same host, and then builds a list with jobs whose deadlines can no longer be satisfied (lines 12 to 18). Jobs whose deadlines cannot be respected become candidates to be rescheduled (see the host data structure in lines 20 to 24). As the position of a job in a queue is determined by its priority, it is not worth rescheduling a job on the same resource because it will take the same place in the queue. The rescheduling of a job ends if it reaches a resource that does not support rescheduling (e.g. Cloud) or after postponing another job's deadline under lack of resources. To prevent excessive rescheduling, the total size of rescheduled jobs should not exceed the size of the new job being scheduled.

B. Allocated Cluster

Algorithm 2, which illustrates the scheduling for an allocated cluster, is similar to scheduling for a dedicated cluster, except for the fact that the local scheduler does not control all the underlying cluster resources.

In order to execute jobs, a reservation must be made through the local scheduler. A reservation consists in a set of processors which the scheduler can dispose of during a fixed time period. As we focus on malleable jobs, one job can be executed during several reservations Algorithm 1: Dedicated Cluster Algorithm (DCA) even if the number of reserved processors is not the same across reservations.

To make reservations correctly, we first simulate the placement of a new task and calculate the amount of processor time to reserve in order to fulfil the resource requirements of all jobs (lines 1 to 12 of the algorithm). Then, as done for the dedicated cluster, we sort jobs by decreasing order of priority and check whether deadlines of all tasks are respected. After that, the algorithm copies one for dedicated cluster only adding the budget sufficiency step.

C. Cloud Scheduler

For clouds, more detailed information is required to determine the type of allocated machines. The rationale of Algorithm 3 is to verify whether the cloud is able to execute a received job respecting its budget and deadline. If that is the case, the algorithm returns a good candidate. Otherwise, it returns a list of two candidates; the first minimising the budget overspend and calculating the execution time needed with this budget, and the second calculating the amount of money needed to finish the job in time.

However, clouds have their intricacies that demand a technique to optimise expenses slightly. Certain clouds (e.g. Amazon EC2) charge per-hour fees for resource usage. Hence, the same money is spent for 30 minutes and 59 minutes of use of a given computing resource. To exploit this particularity one should only shut down free machines at the end of their payment hour. All the jobs Algorithm 2: Allocated Cluster Algorithm (ACA)

V. GLOBAL SCHEDULING MODEL

The goal of the global scheduling algorithm is to optimise the overall money spent while respecting task deadlines and budgets. A basic global scheduler would broadcast job requirements to all computing resources and choose the best candidates. If good candidates exist, we pick one with the lowest price to which a job is submitted. This approach is efficient when the number of computing resources is small, but as the number grows the global scheduler may become a bottleneck. Hence, we propose a hierarchical approach for the global scheduler. The principle of this approach is to pass down the hierarchy details of a task execution, aggregate answers from local schedulers using a multi-level system and choose a convenient host. The approach considers a multi-level system comprising scheduling agents structured as a tree with computing hosts as leaves.

The rationale of Algorithm 4, used for global scheduling, is simple. Each scheduling agent requests from its children a list of candidates. If there exists a good candidate, the agent forwards it one level up in the hierarchy. Otherwise it returns a candidate with the best price with the least deadline violation and another and another with the earliest makespan among those that least exceed the budget. The top level node of the hierarchy then returns one good, or two bad, candidates to the caller which chooses one onto which the job is scheduled.

One can see that the simple approach is a particular case of hierarchical algorithm with just one root with all computation nodes connected directly to it. The hierarchical algorithm is distributed and its complexity can be expressed as O(mn), where m is maximum leaf depth, n is maximum number of children per scheduling agent.

VI. PERFORMANCE EVALUATION

A Python simulator was developed in order to validate and evaluate the efficiency of the proposed algorithms. We resorted to discrete-event simulation as it enables controlled and repeatable experiments, and because the use of real resources such as those allocated from a cloud, could make the cost of evaluation prohibitive. The choice was hence motivated by the need to test all the types of previously described resources, namely a dedicated cluster with negligible computing price, a paid allocated cluster, and cloud resources.

For the clusters the granularity at which resources can be allocated is one minute, and the performance of all processors is homogeneous. For the paid clusters, the cost per processor minute is taken as a cost unit. The price of an hour on an 8 processor machine on the cloud is equal to 960 units (2 units/minute per processor).

The jobs were generated randomly. The time between job arrivals was exponentially distributed whose random variable has a mean of 1 minute. The priority is an integer uniformly chosen from 1 to 20. The deadline for all tasks is uniformly distributed between minimal possible execution time (using maximal number of processors) and time of execution on a single processor. To evaluate the behaviour of the algorithms, three sets of jobs were generated: small jobs (60-120 processor minutes), big jobs (1000-2000 processor minutes) and mixed sets with equal number of tasks of both sizes.

We considered three evaluation metrics:

• Total job execution time, which is sum of the time between job arrival and end of execution for all jobs.

• Total execution cost.

• Delay of jobs against their initial deadlines.

A round-robin algorithm which submits a job to a uniformly chosen resource was taken as baseline and tested against the same job sets. Algorithms were run on sets of different sizes, gradually increasing the number of jobs. Each algorithm was run twice for all the job sets considering namely: the first run where in the absence of "good" candidates the algorithm chooses the least expensive "bad" candidate (money saving strategy, policy A); and the second run in which the fastest candidate is picked (time saving strategy, policy B). The rest of this section presents the simulation plots for all the described variations of parameters. The graphs in figures 2 to 4 demonstrate that in general the proposed algorithms outperform the roundrobin approach except under small tasks. However, even in this case the proposed algorithms give much better savings of budget (Figure 6) and significantly lower delay (Figure 7). In the case of big jobs, our algorithm shows better performance considering all metrics.

The difference between the policies of budget overspend and delay minimisation is also shown. It corre-

VII. RELATED WORK

There exists a vast literature on task scheduling on distributed systems, part of which considers scheduling onto heterogeneous resources [START_REF] Trystram | Scheduling parallel applications using malleable tasks on clusters[END_REF], [START_REF] Prabhakaran | A batch system with efficient adaptive scheduling for malleable and evolving applications[END_REF]. The use of clouds to augment the capabilities of local infrastructure has also been considered in previous work [START_REF] Dias De Assunção | Evaluating the cost-benefit of using Cloud computing to extend the capacity of clusters[END_REF].

The case of multi-criteria optimisation has also been considered [START_REF] Rehn-Sonigo | Multi-criteria mapping and scheduling of workflow applications onto heterogeneous platforms[END_REF], even though the proposed algorithms are often off-line, and require prior information about tasks in order to execute. On-line multi-criteria scheduling algorithms with no a-priori information about tasks has been considered in previous work, where computing resources are represented by clusters composed of ordinary computers of heterogeneous performance [START_REF] Baraglia | A multi-criteria job scheduling framework for large computing farms[END_REF], and where the choice of platforms is much richer and includes Internet desktop Grids, best effort Grids and Clouds [START_REF] Moca | Multi-criteria and satisfaction oriented scheduling for hybrid distributed computing infrastructures[END_REF]. Stating the same problem, this previous work offers absolutely different heuristic solutions tailored to desktop Grid environments and hence less efficient when considering hybrid clouds.

The algorithms proposed in our paper have advantages over the precited existing work, as it uses rescheduling mechanisms for moving tasks across resources. In order to maximise efficiency we focused on malleable tasks.

VIII. CONCLUSIONS

This paper presented algorithms that optimise resource consumption. Though the work considered a large list of target platforms, it can further be extended. The algorithms can also be customised to suit the needs of a user. Additional criteria (e.g. energy efficiency) could be included with minor modifications of local algorithms and the function IsGood.

The efficiency of algorithms was demonstrated by simulation and is being evaluated with real computa-tional tasks. The results may slightly differ because of different distributions of the task sizes and of periods between task arrivals.

  C.P.makespan -C.T.deadline) + = min (Ci.P.makespan-Ci.T.deadline)+

  C.P.budget -C.T.cost) + = min (Ci.P.budget-Ci.T.cost)+

Fig. 1 :

 1 Fig. 1: Example of distributed heterogeneous platform structure.

Algorithm 4 :

 4 Algorithm used by scheduling agent. 1 agent_on_job_receive(job) 2 children.broadcast(job) 3 hosts = children.gather() 4 good_candidates = {h : h ∈ hosts, h.good_candidate = true} 5 if good_candidates.length = 0 then 6 cost -j.budget)+ 10 list1 = {h : h ∈ hosts, (h.cost -j.budget)+ = min1} 11 end_time -j.deadline)+ 13 list2 = {h : h ∈ hosts, (h.end_time -j.deadline)+ = min2} 14 candidate2 = argmin h∈list2 (h.cost) 15 parent.send([candidate1, candidate2]) 16 end

Fig. 2 :

 2 Fig. 2: Total cost for mixed jobs.

Fig. 3 :

 3 Fig. 3: Total execution time of mixed jobs.

Fig. 4 :

 4 Fig. 4: Total delay of mixed jobs.

Fig. 5 :

 5 Fig. 5: Total execution time of small jobs.

Fig. 6 :

 6 Fig. 6: Total cost of small jobs.

Fig. 7 :

 7 Fig. 7: Total delay of small jobs.

IX. ACKNOWLEDGEMENT

We thank Semen Marchuk for his help in this work especially for his work on the simulator.