Julien Duboisset
email: julien.duboisset@fresnel.fr

Dora Aït-Belkacem

Muriel Roche

Hervé Rigneault

Sophie Brasselet
email: sophie.brasselet@fresnel.fr

Generic model of the molecular orientational distribution probed by polarization-resolved Second Harmonic Generation

Keywords: numbers: 42.65.An, 78.20.-e, 87.14.em

come

Generic model of the molecular orientational distribution probed by polarization-resolved second-harmonic generation

I. INTRODUCTION

Second Harmonic Generation (SHG) microscopy, since its first development [START_REF] Gannaway | Second harmonic imaging in the scanning optical microscope[END_REF][START_REF] Flörsheimer | In-situ imaging of Langmuir monolayers by second-harmonic microscopy[END_REF][START_REF] Freund | Connective tissue polarity. Optical second-harmonic microscopy, crossed-beam summation, and small-angle scattering in rat-tail tendon[END_REF] and its introduction in bio-imaging [START_REF] Campagnola | 3-Dimesional High-Resolution Second Harmonic Generation Imaging of Endogenous Structural Proteins in Biological Tissues[END_REF][START_REF] Moreaux | Membrane Imaging by Second Harmonic Generation Microscopy[END_REF][START_REF] Dombeck | Uniform polarity microtubule assemblies imaged in native brain tissue by secondharmonic generation microscopy[END_REF], is now widely used to image ordered bio-molecular assemblies in complex samples. Coherent SHG occurring naturally in non-centrosymmetric structures such as collagen [START_REF] Freund | Connective tissue polarity. Optical second-harmonic microscopy, crossed-beam summation, and small-angle scattering in rat-tail tendon[END_REF], skeletal muscles [START_REF] Campagnola | 3-Dimesional High-Resolution Second Harmonic Generation Imaging of Endogenous Structural Proteins in Biological Tissues[END_REF] and microtubules [START_REF] Dombeck | Uniform polarity microtubule assemblies imaged in native brain tissue by secondharmonic generation microscopy[END_REF], is today exploited as a functional contrast [START_REF] Strupler | Second Harmonic Microscopy to Quantify Renal Interstitial Fibrosis and Arterial Remodeling[END_REF][START_REF] Nadiarnykh | Second Harmonic Generation Imaging Microscopy of Ovarian Cancer[END_REF], possibly in conjunction with other nonlinear optical signatures [START_REF] Ralston | Detection and imaging of non-contractile inclusions and sarcomeric anomalies in skeletal muscle by second harmonic generation combined with twophoton excited fluorescence[END_REF], with the ultimate goal of developing diagnostics of pathological effects related to tissues and cell architecture. In addition to their unique imaging capabilities, nonlinear contrasts are dependent on the incident light polarization state, providing an interesting way to probe molecular orientation and order. Structural information, from membrane architecture and proteins aggregates to biopolymers and tissue assemblies, is a key parameter in a large variety of biological phenomena. Polarization sensitive imaging has been exploited a long time ago in fluorescence [START_REF] Axelrod | Carbocyanine dye orientation in red cell membrane studied by mi-croscopic fluorescence polarization[END_REF][START_REF] Borejdo | Measuring Orientation of Actin Filaments within a Cell: orientation of Actin in Intestinal Microvilli[END_REF] and SHG [START_REF] Flörsheimer | Second-harmonic microscopy -a quantitative probe for molecular surface order[END_REF] in ordered molecular samples. SHG polarization resolved imaging has allowed retrieving molecular orientation and order information in molecular materials [START_REF] Floc'h | Monitoring of orientation in molecular ensembles by polarization sensitive nonlinear microscopy[END_REF][START_REF] Anceau | Local orientational distribution of molecular monolayers probed by nonlinear microscopy[END_REF] and crystals down to the nanometric size [START_REF] Brasselet | In situ diagnostics of the crystalline nature of single organic nanocrystals by nonlinear microscopy[END_REF], as well as collagen and muscle structural quantitative information in tissues [START_REF] Stoller | Polarizationdependent optical second harmonic imaging of a rat-tail tendon[END_REF][START_REF] Williams | Interpreting Second-Harmonic Generation Images of Collagen I Fibrils[END_REF][START_REF] Yen | Collagen Thermal denaturation study with high resolution second harmonic generation imaging and polarization optical microscopy[END_REF][START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF][START_REF] Odin | Orientation fields of nonlinear biological fibrils by second harmonic generation microscopy[END_REF][START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF].

Deducing a structural information (molecular orientational order) from SHG polarization resolved data in microscopy has been so far based on the use of a priori known models in the orientation distribution of the probed system. Polarized SHG applied to collagen type I has shown that its hexagonal crystalline structure can be reduced to an equivalent orientational distribution with a cone surface shape [START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF][START_REF] Odin | Orientation fields of nonlinear biological fibrils by second harmonic generation microscopy[END_REF][START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF], similar to what would be obtained from a collection of active molecules assembled along the triple helix structure of the collagen protein. Many works have developed analyzes in this direction, using as an unknown parameter the aperture of this cone to quantify molecular order in collagen assemblies. In complex environments however such as tissues or micrometric assemblies of fibrils, much more complex orientational behavior can be expected. It is delicate to infer a model in this case, although tentative analyzes have been performed in this direction introducing an additional disorder parameter in the surface cone aperture [START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF]. Adding unknown parameters which are possibly correlated can however lead to ambiguous determinations. In addition these parameters remain model-dependent and can lead to an over-interpretation of the retrieved information. At last, the estimation quality of the parameters strongly depends on the noise In the interpretation of SHG polarized responses, the use of an a priori model ultimately fails in giving a general picture of the measured molecular orientational distribution, primarily because there is no possibility to validate this model. In this work, we propose a generic approach capable of encompassing all available orientational information without the need to rely on a specific model for the orientational distribution in the sample. Along the same lines as what has been developed in the past for polarization analysis in poled polymers doped by SHG active molecules [START_REF] Kuzyk | Second-order nonlinear-optical tensor properties of poled films under stress[END_REF], we base our approach on order parameters related to symmetry properties of the molecular orientation distribution function in a sample. This general model includes possible geometries that are not of cylindrical symmetry, which was not accessible in the previously developed cone models for collagen. It also gives general information on the shape of the orientational distribution with estimated parameters which are model-independent. We develop this model in a 2D approach that is adapted for the SHG microscopy geometry, and apply it to the quantitative imaging of molecular order parameters in assemblies of isolated collagen fibrils. A numerical model based on Monte Carlo analysis is furthermore implemented to quantify empirically the estimation precision on these parameters, assuming signals limited by Poisson noise.

II. MOLECULAR DISTRIBUTION

A. Reduction of the molecular orientational 3D distribution to a 2D distribution A polarized Second Harmonic Generation signal from an ensemble of molecules excited in a focal volume originates from the radiation of a macroscopic nonlinear induced dipole P 2ω , resulting from the orientational average of molecular nonlinear induced dipoles p 2ω :

P 2ω = N ∫ Ω p 2ω f (Ω)dΩ (1)
with N the molecular density. f (Ω) defines the molecular angular distribution function with Ω = (θ, φ, ψ) the Euler angles set defining the molecular orientation. This function models the molecular scale organization of a sample in the macroscopic laboratory frame, and describes the probability to find a molecule oriented along Ω. It is normalized such as

∫ Ω f (Ω)dΩ = 1.
The nonlinear molecular induced dipole originates from the coupling between the molecular nonlinear susceptibility tensor β and the incoming fundamental field E ω at the ω frequency:

p 2ω i = ∑ jk β ijk E ω j E ω k (2)
with i, j, k in the molecular frame (x, y, z).

Writing this dipole in the macroscopic frame (X, Y, Z) and averaging over orientation angles (Eq. 1) results in a macroscopic dipole:

P 2ω I = ∑ JK χ (2
)

IJK E ω J E ω K ( 3
)
where χ

(2)

IJK are the tensorial components of the macroscopic nonlinear susceptibility χ (2) with I, J, K in the (X, Y, Z) frame (Fig. 1a), and:

χ (2) IJK = N ∫ Ω β IJK (Ω)f (Ω)dΩ (4)
where β IJK (Ω) are the molecular susceptibility components expressed in the (X, Y, Z) frame:

β IJK (Ω) = ∑ ijk β ijk (I • i)(J • j)(K • k)(Ω) (5)
with (I • i) the transformation matrix components between the (x, y, z) and the (X, Y, Z) frames.

Note that Eq. 4, which relates molecular scale to macroscopic scale properties, is based on a purely additive model. Accounting for molecule-molecule interactions and molecular packing in dense media [START_REF] Bersohn | Double-Quantum Light Scattering by Molecules[END_REF][START_REF] Kielich | Molecular interactions in optically induced nonlinearities[END_REF] is often accounted for by a phenomenological tensorial local field correction factor [START_REF] Zyss | Relations between microscopic and macroscopic lowest-order optical nonlinearities of molecular crystals with one-or two-dimensional units[END_REF], compatible with this additive approach. In what follows, we implicitly embed this correction factor inside the expression of χ

IJK , meaning that all molecular order interpretations need to be modulated by the existence of possible local interactions in the medium.

In what follows we consider the case of molecules of one-dimensional symmetry, therefore only (θ, φ) are required to define its orientation (Fig. 1a), and f (Ω) can be rewritten f (θ, φ). This assumption on the molecular structure is generally made for the investigation of SHG polarized signals from biomolecular assemblies has been shown to be appropriate in collagen [START_REF] Deniset-Besseau | Measurement of the second order hyperpolarizability of the collagen triple helix and determination of its physical origin[END_REF]. It can be nevertheless generalized to more complex symmetries by introducing the appropriate β tensor structure. The consequence of multipolar molecular symmetries on the determination of molecular order information is discussed in Section V.

Polarization-resolved SHG consists in rotating the incident fundamental polarization in the sample plane (X, Y ), the Z axis defining the propagation direction. Assuming a negligible nonlinear coupling in the Z direction, which is generally the case in samples investigated by nonlinear microscopy imaging [START_REF] Schön | Polarization distortion effects in polarimetric two-photon microscopy[END_REF][START_REF] Schön | Polarization and Phase Pulse Shaping applied to Structural Contrast in Nonlinear Microscopy Imaging[END_REF], the only accessible information is restricted to a projection in the (X, Y ) 2D plane. The projectors (I • i) with I = X, Y thus only contain terms such as sin θ cos φ or sin θ sin φ and Eq. 4 can be rewritten in a general form which demonstration is detailed in Appendix A:

χ (2) IJK = N ∫ 2π 0 ∫ π 0 β * IJK (φ)f (θ, φ) sin 4 θdθdφ (6)
with β * IJK (φ), defined in Appendix A, encompassing the sum over the microscopic coefficients β ijk and the φ dependence of its macroscopic projection. Due to the 2D constraint of the problem in the plane of polarization, we introduce a new distribution function P (φ) which only depends on φ, orientation of the molecule projection in the (X, Y ) plane (Fig. 1b):

P (φ) = ∫ π 0 f (θ, φ) sin 4 θdθ (7)
Eq. 7 shows that the relevant distribution function which is effectively read-out in a polarized SHG process is of the form f (θ, φ) sin 4 θ, a function which emphasizes the role of molecules close to the (X, Y ) plane compared to out-of plane ones, as depicted in Fig. 1c. In addition, the 2D distribution P (φ) can be used to define the effect of molecular orientation on the polarization resolved SHG signals, using only the molecules orientation information φ in the (X, Y ) sample plane. P (φ) is not a geometrical projection of the 3D distribution function f (θ, φ) in the (X, Y ) frame, but is rather a horizontal sectioning of the 3D molecular distribution imposed by the SHG contrast (Fig. 1c). The macroscopic SHG tensor components in the (X, Y ) plane can finally be written:

χ (2) IJK = N ∫ 2π 0 β * IJK (φ)P (φ)dφ (8)
Thereafter we develop the polarization resolved SHG response of the 2D molecular distribution P (φ). In the sample plane, this function can be decomposed on basis of circular functions, appropriate to its 2D geometry:

P (φ) = p 0 + p 1 cos(φ -φ 0 ) + ∑ n≥2 p n cos(n(φ -φ 0 )) + ∑ n≥2 q n sin(n(φ -φ 0 )) (9)
The (p n , q n ) order terms in Eq. 9 are the signature of different orders of symmetry of the P (φ) function, n=0 being representative of its isotropic contribution, and even/odd n orders terms being representative of its even/odd orders of symmetry. Moreover, high symmetry orders are representative of more defined angular details. φ 0 is the mean orientation, in the sample plane, of the first order term n=1 (Fig. 1b), introduced as a reference orientation angle of the 2D distribution function. Therefore there is no need to introduce a q 1 parameter.

The q n≥2 terms quantify the orientation of the n order terms with respect to the X axis.

Therefore q n≥2 are also signatures of the absence of a symmetry axis in the distribution function.

Since SHG, in the dipolar approximation used here, is only sensitive to non-centrosymmetric contributions of a distribution function up to the third order of symmetry [START_REF] Zyss | Molecular engineering implications of rotational invariance in quadratic nonlinear optics: From dipolar to octupolar molecules and materials[END_REF][START_REF] Brasselet | Polarization resolved nonlinear microscopy: application to structural molecular and biological imaging[END_REF], only the orders 1 and 3 of the distribution function P (φ) in Eq. 9 contribute to the SHG response. For this reason, the 2D orientational distribution function P (φ) can be reduced to a truncated P (φ) function, which is no longer considered as a probability function:

P (φ) = p 1 cos(φ -φ 0 ) +p 3 cos(3(φ -φ 0 )) +q 3 sin(3(φ -φ 0 )) (10)
The information present in P (φ) is therefore the relative non-centrosymmetric contribution, of first and third orders, to the complete molecular angular distribution P (φ).

B. Single molecule polarized SHG response

Assuming molecules of one-dimensional symmetry along a z direction in the sample plane (Fig. 1b), β ijk possesses a single non vanishing component β zzz in the molecular frame, denoted β in what follows. In the 2D molecular distribution, the z axis is oriented with an angle φ relative to the macroscopic axis X. Denoting α the angle of the incident linear polarization E relative to X, the amplitudes of the molecular nonlinear induced dipole along the X and Y axes are therefore proportional to:

p 2ω X = E 2 0 β cos φ cos 2 (α -φ) p 2ω Y = E 2 0 β sin φ cos 2 (α -φ) (11)
with E 0 the amplitude of incoming fundamental field.

The polarization dependence of the total SHG intensity I(α), measured without the use of any analyzer, can be written, in the plane wave approximation, as:

I = I X + I Y = |p 2ω X | 2 + |p 2ω Y | 2 (12)
Therefore:

I(α) = E 4 0 β 2 cos 4 (α -φ) (13)
The cos 4 (α -φ) function can be decomposed on the basis circular functions cos(n(α -φ))

with n = 0, 2, 4, which leads to:

I(α) = a 0 + a 1 cos(2(α -φ)) + a 2 cos(4(α -φ)) (14)
with

a 0 = 3E 4 0 β 2 /8 a 1 = E 4 0 β 2 /2 a 2 = E 4 0 β 2 /8 (15)
C. Polarized SHG response in a 2D angular distribution

The nonlinear response from an ensemble of molecules requires calculating the orientational averaged of single molecule's nonlinear induced dipoles (Eq. 1). The polarization dependence of the total SHG intensity can then be written, in the plane wave approximation, as a quantity proportional to the macroscopic expression

|P 2ω X | 2 + |P 2ω Y | 2 .
Introducing P (φ) in Eq. 8, and using the methodology developed in Appendix B, it can be shown that similarly as the single molecule case, this function is decomposed on the basis circular functions cos(n(α -φ 0 )) and sin(n(α -φ 0 )) with n = 0, 2, 4:

I(α) = a 0 + a 1 cos(2(α -φ 0 )) + a 2 cos(4(α -φ 0 )) +b 1 sin(2(α -φ 0 )) + b 2 sin(4(α -φ 0 )) (16)
with

a 0 = A 16 (5p 2 1 + p 2 3 + q 2 3 ) a 1 = A 4 (p 2 1 + p 1 p 3 ) a 2 = A 8 p 1 p 3 b 1 = A 4 p 1 q 3 b 2 = A 8 p 1 q 3 ( 17
)
where

A = N 2 E 4 0 π 2 β 2 .
This development shows that the total SHG intensity can be decomposed in a simple Fourier decomposition, in a similar manner as already introduced in previous works [START_REF] Refregier | Precision analysis in polarization-resolved second harmonic generation microscopy[END_REF][START_REF] Amat-Roldan | Fast image analysis in polarization SHG microscopy[END_REF],

with coefficients depending on the orders of the P (φ) function. Due to the coherent nature of the SHG process, this dependence is however not a pure linear combination of the p 1 , p 3 , q 3

orders, but rather a nonlinear mixing which prevents the simple resolution of an inverse problem. In the most general situation, all the orders can be however determined as a unique solution, as long as the first order p 1 does not vanish. Indeed in the case of a pure third order distribution (p 1 = 0), only a 0 does not vanish and the total intensity will be a constant function of α, the distribution function exhibiting in this case a 2π/3 invariant rotation while the fundamental electromagnetic field exhibits a π invariant rotation, making impossible any signal modulation. This property has been previously exploited in octupolar molecular media to obtain polarization-independent nonlinear responses [START_REF] Zyss | Molecular engineering implications of rotational invariance in quadratic nonlinear optics: From dipolar to octupolar molecules and materials[END_REF][START_REF] Brasselet | Control of the polarization dependence of optically poled nonlinear polymer films[END_REF].

III. ESTIMATION OF ORDER PARAMETERS

A. Principle of the estimation of the order parameters

As mentioned above, the non linear expression of the Fourier coefficients a 0 , a 1 , a 2 , b 1 , b 2 as functions of the unknown parameters A, p 1 , p 3 , q 3 makes impossible an analytical resolution of the inverse problem. In a polarization resolved measurement, A is not relevant since it is a pure magnitude factor. The measurement being not absolute, a normalization is necessary and for this reason we chose to estimate three remaining parameters: the ratios p = p 3 /p 1 , q = q 3 /p 1 (called "order parameters" in what follows), and φ 0 . The distribution function becomes therefore a more simple expression:

P (φ) = cos(φ -φ 0 ) + p cos(3(φ -φ 0 )) +q sin(3(φ -φ 0 )) (18)
The SHG intensity I(α), which depends on the mean orientation φ 0 and the (p, q) parameters, will be written I(w(p, q), φ 0 , α) with w(p, q) = (a 0 , a 1 , a 2 , b 1 , b 2 ), the measured Fourier coefficients of Eq. 16, which depend only on p and q. A typical experimental measurement leads to intensity values I exp (α i ) for m regularly spaced measurement angles α i with i = 1..m, with m high enough to allow the unambiguous determination of the Fourier coefficients of Eq. 16. To retrieve the φ 0 and (p, q) information, a minimization can be performed of the mean square error between the measured intensity I exp (α i ) and the model intensity

I(w(p, q), φ 0 , α i ).
In practice, we implement a minimization procedure on the Fourier coefficients of the intensities. A minimization is separately performed on the φ 0 parameter since it appears as a pure phase parameter in Eq. 16. For each φ 0 , the estimation operation consists in finding the couple (p, q) which minimizes the error function:

E(w(p, q), φ 0 ) = ||w exp (φ 0 ) -w(p, q)|| 2 (19)
where w exp (φ 0 ) is the set of Fourier coefficients measured on the experimental SHG intensity artificially rotated by a φ 0 angle.

The nonlinear polarimetric microscope used in this work has been described in previous works [START_REF] Schön | Polarization distortion effects in polarimetric two-photon microscopy[END_REF]. The excitation light source is a tunable Ti:Sapphire laser that delivers 150 fs pulses at a repetition rate 80 MHz. The incident wavelength is set at 800nm for SHG with a typical averaged power of a few mWs at the sample plane. The laser beam is reflected by a dichroic mirror and focused on the sample by a high Numerical Aperture (NA) objective (× 40, NA 1.15). The backward emitted signal is collected by the same objective and directed to an avalanche photodiode. The total intensity is collected without any analyzer. Previous works have shown that using no analyzer can lead to misleading interpretation in case of polarization distortions by the sample [START_REF] Aït-Belkacem | Influence of birefringence on polarization resolved nonlinear microscopy and collagen SHG structural imaging[END_REF], therefore in the present case we preliminary verify that the sample does not exhibit such distortions following the methodology developed in [START_REF] Aït-Belkacem | Influence of birefringence on polarization resolved nonlinear microscopy and collagen SHG structural imaging[END_REF]. Images are performed by scanning the sample with two galvanometric mirrors. The linear polarization of the incident laser beam is continuously rotated in the sample plane by an achromatic half wave plate mounted on a step rotation motor at the entrance of the microscope. For each value α i of the polarization angle relative to X (in total 32 angles between 0 • and 180 • ), a SHG image is recorded. At last, polarization distortions (dichroism and ellipticity) originating from the mirrors reflection are preliminarily characterized following a calibration procedure described previously [START_REF] Schön | Polarization distortion effects in polarimetric two-photon microscopy[END_REF]. The ellipticity is found to be close to 20 • (with a dichroism factor close to 0), which is seen to induce a negligible bias in the estimation of the p and q parameters. At last, the polarization mixing effects induced by the high numerical aperture at both excitation and collection steps can be ignored in a first approximation for nonlinear dipoles principally lying close to the sample plane [START_REF] Schön | Polarization distortion effects in polarimetric two-photon microscopy[END_REF][START_REF] Schön | Polarization and Phase Pulse Shaping applied to Structural Contrast in Nonlinear Microscopy Imaging[END_REF], therefore the planar approximation used above to calculate the SHG intensity radiation can be considered as valid.

C. Results

As an illustration of the technique, polarization resolved SHG experiments have been performed on fibrils of collagen type I of submicrometric diameters, coated on a glass substrate following a procedure already established [START_REF] Fourre | Extracellular matrix proteins protect human HT1080 cells against the antimigratory effect of doxorubicin[END_REF]. The choice of this biological model is motivated by the fact that the fibrils are quite isolated from each other and not embed-ded in a dense tissue, which might distort polarization properties by scattering or birefringence [START_REF] Aït-Belkacem | Influence of birefringence on polarization resolved nonlinear microscopy and collagen SHG structural imaging[END_REF][START_REF] Gusachenko | Polarization-resolved Second Harmonic microscopy in anisotropic thick tissues[END_REF]. The structure of collagen type I fibrils is furthermore well known and has been studied previously by polarization resolved SHG imaging [START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF][START_REF] Odin | Orientation fields of nonlinear biological fibrils by second harmonic generation microscopy[END_REF][START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF].

The usually proposed model supposes that collagen fibrils or larger fibrils are made of SHG active one-dimensional molecules oriented along a triple helix structure of given pitch angle and period [START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF], which confers to them an averaged orientation distribution function lying along a cone surface. In this work we only assume that molecules are of one-dimensional geometry, without any further hypothesis on the orientational model. This allows in particular to address the question of distribution functions distortions in fibrils assemblies which are not necessary of cylindrical symmetry. At last, the macroscopic orientation of single fibrils can be directly visualized from the SHG image, which allows direct comparison with the obtained estimated orientation parameter for φ 0 .

A typical SHG image from collagen fibrils depicted in Fig. 2a shows elongated fibrils of various diameters and lengths, averaged intensities and orientations. For each pixel of this image, the mean orientation of the molecular distribution φ 0 , as well as the p and q order parameters are estimated by minimization of the E(w(p, q), φ 0 ) estimator introduced in Eq. 19, using sampling values of 10 • between 0 • and 180 • for φ 0 , and 0.02 between -3 and 3 for (p, q). The chosen range values for (p, q) is specific to collagen (see section V), and can be adapted for other type of samples. As can be observed in Fig. 2b, the obtained φ 0 values are in good agreement with the macroscopic orientation of the fibrils in the sample plane, supporting the fact that molecules orient on average along a main fibril direction (note that φ 0 = 0 • and φ 0 = 180 • are equivalent angles, therefore leading to a mixture of these two values in the image of horizontal fibrils). The p and q order parameters images are represented in Fig. 2c,d, and also as histograms in Fig. 2e,f. Note that we chose to represent the images (Fig. 2a-d) with a threshold of 60 photons/pixel (SHG signal summed over all 32 incident polarizations) in order to depict the large population of fibrils and intensities available in this sample. The threshold intensity chosen to represent the histograms (150 photons/pixel) is higher since a high signal to noise ratio is required to analyze the data with sufficient precision (see Section IV).

The averaged value of p obtained over the whole image is -0.47, which means that the first and third order contributions to the angular distribution function P (φ) are pointing towards opposite directions. This value leads to a depression in the truncated distribution in its center, represented in Fig. 2g, meaning that there are more SHG-active molecules on the side of the distribution than in its center. The two-lobes of this distribution are separated by an angular aperture of about 50 • , which is also close to the cone half aperture angle found in previous works on dense collagen structures, assuming a cone surface shape [START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF][START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF]. This result provides a direct evidence that the traditionally assumed distribution shape of cone surface can be considered as valid in ordered collagen structures, which would be otherwise impossible to verify. Third, the averaged value of q close to 0 means that the first and third order contributions functions exhibit the same averaged orientation, supporting the fact that the global angular distribution function exhibits an axis of symmetry (in 3D, this would correspond to a cylindrical symmetry).

In order to visualize the distribution function obtained locally in collagen fibrils, a small image section is selected and represented in Fig. 3a. This image contains different populations : isolated collagen fibrils of different orientations, and an overlap between fibrils. In the regions where collagen fibrils are clearly isolated, the truncated distribution function P (φ) is globally oriented in the direction of the fibrils, with a two-lobes shape resembling the averaged distribution function (Fig. 3c). In a region where the two fibrils intersect, the distribution function shows more pronounced fine lobes at a larger aperture angle. This distribution could be interpreted as the result of a higher disorder, although it is not possible to discriminate between a molecular origin for this disorder (change of chemical composition and helix structures in collagen) and a microscopic scale disorder made of a different fibrils orientations. Nevertheless this example illustrates the potential of this method to provide a direct visualization of the local disorder in a collagen fibrils sample. Using a pure cone surface model as usually inferred would not be able to provide this level of information, since it is not sensitive to pure distribution shape changes.

IV. ESTIMATION ACCURACY A. Monte-Carlo simulations

The accuracy of the estimation of the order parameters is studied assuming that measurements are limited by Poisson noise, which is verified in the present case. To quantify the accuracy of the method, Monte-Carlo experiments have been performed. A polarization resolved signal is created using Eqs. 16 and 17, for a chosen set of parameters φ 0 , p 1 , p 3 and q 3 , and furthermore introducing Poisson noise to the signal. The values of the parameters have been chosen to be close to the averaged ones found experimentally. From this signal, the parameters φ 0 and (p, q) are then estimated following the same methodology as previously described on experimental data. 2000 realizations are executed for several levels of noise (varying the SHG total intensity from 10 photons to 160 photons, summed over all 32 incident polarization angles). For each level of noise the mean value and the variance of the parameters on three regions of interest represented as white rectangles in the SHG image. These functions are obtained using the average of the retrieved parameter within the region of interest (only active pixels are used): 1 (p = -0.4, q = 0.04, ϕ 0 = 8 • ); 2 (p = -0.98, q = 0.04, ϕ 0 = 42 • ); and 3 (p = -0.38, q = 0.01, ϕ 0 = 80 • ). The error of estimation on the parameters produces an error bar on the angular distribution which is smaller than the thickness of the line used to draw the distribution function, therefore it is not represented here.

φ 0 and (p, q) parameters are calculated. These results are reported in Fig. 4. As expected, the variances of the estimated parameters are seen to decrease linearly with the number of photons. Moreover, stronger variances values are observed for the q parameter. This can be due to the fact that the determination of q relies on a set of equations (Eq. 17) which contains some redundancies, contrary to p. Overall this result provides indication on the level of signal to reach in order to estimate the order parameters with a reasonable quality.

It is for instance visible that the total number of photon should be above 150 to reach a good estimation precision with variances below 0.05, for all parameters in the situation considered here.

B. Experimental accuracy

To give a quantitative picture of the experimental accuracy and compare it to predictions from Monte Carlo simulations, seven experiments were performed on a same region of the collagen type I fibrils sample, using identical experimental conditions. A fibril with orientation φ 0 ∼ 45 • , lying in the middle of Fig. 2, is chosen to evaluate the (φ 0 , p, q) parameters for each of its pixels (in total 78 pixels are analyzed) and for each experiment.

The variance of these parameters is calculated for each pixel based on their seven estimated values. This procedure allows a direct calculation of the parameters' variance, avoiding any dependence on possible sample heterogeneities within the same collagen fiber. For each pixel, the variance of the φ 0 and (p, q) parameters is determined as well as the corresponding total number of photons, defined as the average of the total number of photons measured over the seven experiments. Although this procedure does not permit to explore a large range of total number of photons and is based on a small number of measurements, it gives a rough idea of the experimental accuracy of the parameters. To represent the global behavior of a given parameter in Fig. 4 It is possible to relate the obtained p and q parameters to the models used previously in the literature, using their definition in terms of Fourier decomposition coefficients of the molecular distribution.

A. Relation between order parameters and an explicit molecular distribution function

In a 2D molecular orientational distribution model where P (φ) is a priori assumed, the p n and q n parameters of the Fourier decomposition of P (φ) are defined as:

p n = ∫ 2π 0 P (φ) cos(nφ)dφ q n = ∫ 2π 0 P (φ) sin(nφ)dφ (20)
We first consider the case of a f (θ, φ) distribution made of a 3D cone filled with molecules with a total angular aperture 2ψ 0 , lying in the (X, Y ) plane along the X axis (we choose here φ 0 = 0 for simplification). In this situation, the corresponding 2D function P (φ) can be approximated by:

P (φ) = 1 2ψ 0 Rect[φ, -ψ 0 , ψ 0 ] (21)
with the Rect function defines as 1 for -ψ 0 ≤ φ ≤ ψ 0 and 0 elsewhere. This leads to:

p n = sin(nψ 0 ) πnψ 0 ; q n = 0 (22)
When ψ 0 → 0 (small cone apertures) then p n → 1/π, and when ψ 0 → π/2 (large apertures) then p 2n+1 → (-1) n (2n+1)π 2 /2 , therefore p = p 3 /p 1 → -1/3, which fixes a lower limit of the measurable p parameter in this case.

We then consider the case of a cone surface distribution where the molecules only lie on the surface of a cone of angular aperture 2ψ 0 . This situation is specifically used to explore molecular order in collagen based samples. In this case:

P (φ) ≃ 1 2 (δ[φ -ψ 0 ] + δ[φ + ψ 0 ]) (23)
which leads to:

p n = 1 π cos(nψ 0 ); q n = 0 (24)
ψ 0 = π/2 -ϵ, then p 2n+1 ≃ 1 π (-1) n (2n + 1)ϵ and thus p = p 3 /p 1 ≃ -3. In this case, the minimum expected value for p is therefore lower than for a filled cone distribution.

The dependencies of p as a function of the cone half aperture ψ 0 are represented in Fig. 5a for the two models, filled cone and cone surface. From this figure one can draw several observations. First, using p to determine ψ 0 can lead to different solutions depending on the model used, since the interpretation of ψ 0 is model-dependent. In the present approach, a cylindrical symmetry distribution is defined by one unique order parameter p, which is not model-dependent and is representative of the accessible quantity from polarization dependent SHG. Second, one can draw additional conclusions on the shape of the distribution, based on the measurement of p and q. Indeed in the case where p takes large negative values (typically p < -1/3), the 2D distribution function exhibits angularly a depression in its center, which makes it resemble more a surface cone distribution than a filled cone. This is illustrated in the polar representation of the P (φ) distribution (Fig. 5b). Note that any kind of hollow distribution in its center would lead to a similar behavior as observed for the cone surface.

In the case of investigations on collagen, models of cone surfaces have been extensively used and typical values found in the literature lie close to ψ 0 ∼ 45 -60 • [START_REF] Williams | Interpreting Second-Harmonic Generation Images of Collagen I Fibrils[END_REF][START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF], leading to p ranging from -0.3 to -1.4, which is the range found in single isolated fibrils in our measurements. The determination of p and q provides however here extra information which is not accessible in approaches based on a priori supposed models, in particular by revealing explicitly the hollow shape distribution and possible deviations from a cylindrical symmetry.

Finally, note that this whole derivation is based on the initial assumption that the angular distribution is made of pure 1D molecules exhibiting a unique diagonal β zzz coefficient, which has been shown to be robust in the case of collagen studies. Introducing a more complex molecular symmetry in Eq. 5 would lead to a deviation of the p values deduced here, which can be strong if significant off-diagonal molecular nonlinear coefficients arise. Along the same line as previously developed approaches [START_REF] Stoller | Polarizationdependent optical second harmonic imaging of a rat-tail tendon[END_REF][START_REF] Williams | Interpreting Second-Harmonic Generation Images of Collagen I Fibrils[END_REF][START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF][START_REF] Odin | Orientation fields of nonlinear biological fibrils by second harmonic generation microscopy[END_REF][START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF], the estimation of p therefore relies on either an assumed or an a priori known molecular structure.

B. Relation between order parameters and microscopic tensorial coefficients

The structural parameters of molecular assemblies are often expressed in terms of their microscopic tensorial nonlinear coefficients, which relate the molecular order information to a crystallographic point of view. In the case of collagen, a C 6 symmetry is assumed from the known crystalline structure of this macromolecule [START_REF] Freund | Connective tissue polarity. Optical second-harmonic microscopy, crossed-beam summation, and small-angle scattering in rat-tail tendon[END_REF]. Denoting 3 the high symmetry axis of the C 6 symmetry cylinder and (1, 2) its perpendicular plane, the collagen symmetry is therefore reduced to two microscopic tensorial coefficients under non-resonant excitation conditions: χ 311 , often used to characterize molecular order in collagen, has been found to range between 0.8 and 2.6 [START_REF] Freund | Connective tissue polarity. Optical second-harmonic microscopy, crossed-beam summation, and small-angle scattering in rat-tail tendon[END_REF][START_REF] Stoller | Polarizationdependent optical second harmonic imaging of a rat-tail tendon[END_REF][START_REF] Williams | Interpreting Second-Harmonic Generation Images of Collagen I Fibrils[END_REF][START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF][START_REF] Odin | Orientation fields of nonlinear biological fibrils by second harmonic generation microscopy[END_REF][START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF]. A relation between χ

In the present analysis, the value found for p = -0.4 in isolated fibrils leads to χ

(2) 333 /χ

(2) 311 = 1.85, which lies in the range of values previously found in tissues.

We have introduced a generic approach for the analysis of polarization dependent SHG microscopy measurement, applied to molecular and biological structural imaging. This approach is based on a 2D derivation of the problem, accounting for the fact that the read-out of the polarization information in the sample plane necessarily reduces the problem to the investigation of an angular distribution function lying in this plane. We derived a simple way to retrieve molecular order parameters from a Fourier decomposition of the SHG polarization responses, and showed their estimation precision as a function of the signal level, based on a Poisson noise statistics. The obtained parameters, based on a circular decomposition of the molecular distribution function, are shown to contain richer information than the traditional model-oriented estimations. We illustrated the application of this new approach for the imaging of molecular order in collagen type I fibrils, where order information can be obtained at the microscopic scale without the need to infer a specific orientational model.

Therefore:

⟨A 0 ⟩ = up 1 π cos φ 0 ⟨B 0 ⟩ = up 1 π sin φ 0 2 π ⟨A c ⟩ = u[p 1 cos φ 0 +p 3 cos(3φ 0 ) -q 3 sin(3φ 0 )] 2 π ⟨A s ⟩ = u[p 1 sin φ 0 +p 3 sin(3φ 0 ) + q 3 cos(3φ 0 )] 2 π ⟨B c ⟩ = u[-p 1 sin φ 0 +p 3 sin(3φ 0 ) + q 3 cos(3φ 0 )] 2 π ⟨B s ⟩ = u[p 1 cos φ 0 -p 3 cos(3φ 0 ) + q 3 sin(3φ 0 )] (B11)

The SHG intensity can finally be written as: where A = N 2 E 4 0 π 2 β 2 .

I(α) = a 0 +

FIG. 1

 1 FIG. 1. a) Geometry of the SHG polarized microscopy. (X, Y ) is the sample plane, Z is the direction of propagation of the fundamental beam. α is the angle of the incident polarization E relative to X. In one-dimensional symmetry molecules, (θ, ϕ) defines the orientation of the molecular axis m in the (X, Y, Z) frame. b) Orientation of the 2D distribution (ϕ 0 ) represented in a grey shape. ϕ is the orientation of the molecular axis m relative to X in the sample plane. c) Example of a 3D molecular distribution f (θ, ϕ) (left) and its modified shape when read by a SHG polarized contrast f (θ, ϕ) sin 4 θ (right).

FIG. 2

 2 FIG. 2. a) SHG Intensity image of isolated Collagen type I fibrils coated on the sample plane surface. The intensity scale is the sum of SHG signals over the 32 incident polarizations (threshold: 60 photons/pixel). b-d) Images of the parameters obtained from a Fourier decomposition of the intensity polarization dependence: b) ϕ 0 (degrees); c) p; d) q. e) histogram of p on the whole image; f) histogram of q on the whole image. For the histograms the threshold of the analyzed pixels is 150 photons/pixel. g) polar representation of the truncated distribution function P (ϕ) deduced from the averaged p and q values obtained over the whole image.

FIG. 3

 3 FIG. 3. a) SHG image of a selected region of Fig. 2. b) Corresponding image of p. c) Polar representation of the averaged distribution function P (ϕ) obtained from the retrieved (ϕ 0 , p, q)

  , the variances obtained for all 78 measured pixels are grouped by intensity ranges (of [0-10] photons, [10-20] photons, etc.) and averaged for each range. The obtained variances are seen to lie globally close to values expected from the Monte-Carlo simulation, which emphasizes the role of Poisson noise in our measurement.

FIG. 4 .

 4 FIG.4. Variances of the p, q and ϕ 0 parameters as functions of the total number of photon (summed over the 32 incident polarizations). Circles: p, squares: q, triangles: ϕ 0 . Dashed lines: Monte-Carlo simulations using the initial parameters p = -0.4, q = 0, ϕ 0 = 45 • . Continuous lines: experimental variances measured over seven experiments performed for a same region of interest, on a fibril of orientation ϕ 0 ∼ 45 • relative to X. Each point represents the average of the variances obtained in a range of photon number: [0-10] photons,[START_REF] Axelrod | Carbocyanine dye orientation in red cell membrane studied by mi-croscopic fluorescence polarization[END_REF][START_REF] Borejdo | Measuring Orientation of Actin Filaments within a Cell: orientation of Actin in Intestinal Microvilli[END_REF][START_REF] Flörsheimer | Second-harmonic microscopy -a quantitative probe for molecular surface order[END_REF][START_REF] Floc'h | Monitoring of orientation in molecular ensembles by polarization sensitive nonlinear microscopy[END_REF][START_REF] Anceau | Local orientational distribution of molecular monolayers probed by nonlinear microscopy[END_REF][START_REF] Brasselet | In situ diagnostics of the crystalline nature of single organic nanocrystals by nonlinear microscopy[END_REF][START_REF] Stoller | Polarizationdependent optical second harmonic imaging of a rat-tail tendon[END_REF][START_REF] Williams | Interpreting Second-Harmonic Generation Images of Collagen I Fibrils[END_REF][START_REF] Yen | Collagen Thermal denaturation study with high resolution second harmonic generation imaging and polarization optical microscopy[END_REF][START_REF] Tiaho | Estimation of helical angles of myosin and collagen by second harmonic generation imaging microscopy[END_REF][START_REF] Odin | Orientation fields of nonlinear biological fibrils by second harmonic generation microscopy[END_REF] photons, etc.

FIG. 5

 5 FIG. 5. a) Dependency of the p parameters as a function of the cone half aperture ψ 0 for two models of the molecular 2D distribution function P (ϕ): filled cone (continuous line), cone surface (dashed line). b) Different distributions P (ϕ) represented as polar plots in the sample plane, for p=0.5, 0, -1/3, -1, -3.

  all index permutation permitted in case of valid Kleinman symmetry conditions). The ratio χ

  aperture angle ψ 0 of the equivalent cone surface model mentioned above can be deduced from tensorial distribution expression similar to Eq. 4, leading to[START_REF] Psilodimitrakopoulos | In vivo, pixel-resolution mapping of thick filaments' orientation in nonfibrilar muscle using polarization-sensitive second harmonic generation microscopy[END_REF]:tan 2 (ψ 0 ) = 2 χ

1 + p 1 p 3 ) a 2 = A 8 p 1 p 3 b 1 = A 4 p 1 q 3 b 2 = A 8 p 1 q 3 (

 13313 a 1 cos(2(α -φ 0 )) + a 2 cos(4(α -φ 0 )) +b 1 sin(2(α -φ 0 )) + b 2 sin(4(α -φ 0 )) B13)

ACKNOWLEDGMENTS

We wish to acknowledge Philippe Réfrégier for his key contribution to the discussions. We also thank Marie Guilbert and Pierre Jeannesson (Université Reims Champagne Ardennes) for the preparation of the collagen type I fibrils sample. We thank the Provence Alpes Côte d'Azur (PACA) Region and CNRS for financial support.

Appendix A: From 3D to 2D expressions of the nonlinear SHG macroscopic response

The expression of the macroscopic nonlinear SHG response is based on calculation of the β IJK (Ω) molecular components expressed in the macroscopic frame (X, Y, Z). Assuming molecules of one-dimensional symmetry along a z direction in the sample plane, β ijk possesses a single non vanishing component β zzz (denoted β) in the molecular frame. We denote (θ, φ) the orientation of the z axis in the (X, Y, Z) frame. In the case the incident polarization lies in the (X, Y ) plane, only four macroscopic coefficients need to be considered (index permutation are allowed):

Therefore that the β IJK coefficients (with (I, J, K) = (X, Y )) can be written in a general way as:

with β * IJK (φ) encompassing all φ dependence sinusoidal functions. Finally the macroscopic nonlinear tensorial coefficients can be written:

Appendix B: SHG response from an ensemble of molecules

In this part we derive the expression of the Fourier coefficients of the SHG intensity polarization dependence for an ensemble of molecules. We consider a one-dimensional planar molecule lying in the sample plane, its main nonlinear coefficient β zzz being denoted β. The z axis is oriented with an angle φ relative to the macroscopic axis X. α the angle of the incident linear polarization E relative to X. The amplitudes of the molecular nonlinear induced dipole along the X and Y axes are proportional to:

with E 0 the amplitude of incoming fundamental field.

Using trigonometric formula, these expressions can be written as:

where

In the case of a distribution made of an ensemble of molecules, we introduce the expansion of the molecular distribution on the basis of circular functions:

The coherent SHG intensity from this molecular distribution is deduced from its macroscopic nonlinear induced dipole, defined as the orientational average of the molecular nonlinear induced dipole:

with N the molecular density and ⟨...⟩ the orientational averaging operation defined as:

This orientation averaging involves moments of the molecular distribution:

which can further be written as:

The same calculus is made for the sin moment: ⟨sin(mφ)⟩ = p m π sin(mφ 0 ) + q m π cos(mφ 0 ) (B9)

The different moments necessary for the calculation of the macroscopic nonlinear dipole are simply:

⟨cos(φ)⟩ = p 1 π cos(φ 0 ) ⟨sin(φ)⟩ = p 1 π sin(φ 0 ) ⟨cos(3φ)⟩ = p 3 π cos(3φ 0 ) -q 3 π sin(3φ 0 ) ⟨sin(3φ)⟩ = p 3 π sin(3φ 0 ) + q 3 π cos(3φ 0 ) (B10)


Héctor Fernández

Marko Obrovac

Cédric Tedeschi

Decentralised Multiple Workflow Scheduling via a Chemically-coordinated Shared Space

Keywords: Community Clouds, Workflow Scheduling, P2P, Unconventional Programming Models, Chemical Programming Model Community Clouds, Ordonnancement de workflows, P2P, Modèle de programmation non conventionnel, Modèle de programmation chimique

Community clouds have arisen as a promising infrastructure to face the ever-growing demand for computational power needed by applications. In such a community, different cloud providers federate their resources, allowing users to run applications across multiple sites through a global workflow scheduling system. However, current workflow scheduling approaches exhibit limited scalability, as they rely mostly on centralised scheduling mechanisms, and thus cannot fully leverage possible cooperation among cloud providers. To overcome these limitations, we propose a fully decentralised workflow scheduling system which uses a chemistry-inspired model to coordinate decision making in a community cloud platform. Our system implements a distributed shared space inside which resources are associated to tasks, enabling a decentralised decomposition of workflows into tasks. They are then independently mapped onto resources. In particular, in spite of decentralisation, the system is able to select the momentarily most appropriate resource for a given task, independently of the cloud provider the resource is located on. The framework's expectations in terms of scalability are captured through simulation experiments.

Ordonnancement décentralisé de workflows multiples à travers un espace partagé chimiquement coordoné 1 Introduction

Applications tend more and more to take the shape of compositions of independent, looselycoupled services bounded at run time. This is particularly true for scientific applications that are now commonly built as workflows of services, i.e. temporal compositions thereof. The success of the myExperiment platform1 for service and workflow sharing is a clear sign of the shift in application conception. Independently, over the last few years, the concept of cloud computing has emerged. Its elasticity property makes the cloud an appealing tool for large-scale scientific computations. Clouds have recently seen their usage extended and consolidated as computing environments for scientific research. For instance, the Magellan project [1] aims at providing a cloud-based platform for scientists. However, the computing power demanded by scientific applications can reach such proportions that some resource providers alone are not able to face them. This led to collaborations amongst different cloud providers, giving birth to an infrastructure called a community cloud. It allows different cloud providers to share their resources, making it possible for these workflows to be deployed and executed. The idea of sharing resources, however, carries with it new challenges such as the interoperability between different cloud providers, elasticity, security, as well as economical issues [START_REF] Dias De Assunção | Intergrid: a case for internetworking islands of grids[END_REF][START_REF] Caron | Cloud computing resource management through a grid middleware: A case study with diet and eucalyptus[END_REF].

In this paper, we focus on the crucial feature of scheduling, i.e., the process deciding on which resource which task of the workflow has to be run. Two primary concerns in such platforms are cooperation (between different resource/cloud providers) and decentralisation (in regards to the envisioned scale of community clouds). Traditional centralised schedulers ought not to be put in use, as they would inevitably suffer from significant reliability and scalability limitations.

It is thus essential to promote decentralised and autonomic solutions which embrace all the participants in a community in order to select the appropriate resource for a task. However, while decentralisation offers a robust solution, it is not able to handle the cooperation between different resource providers. The platform should be enhanced with coordination mechanisms enabling efficient task-to-resource mapping.

Lately, natural metaphors, and in particular chemistry-inspired analogies, have been identified as a promising source of inspiration for developing new approaches for autonomic service coordination [START_REF] Viroli | A biochemical approach to adaptive service ecosystems[END_REF]. More precisely, we consider the chemical programming paradigm -a highlevel execution model, where a computation is envisioned as a set of reactions taking place concurrently and autonomously between molecules of information moving and colliding nondeterministically. With such an execution model, the expression of coordination is done via a set of user-defined rules consuming molecules and producing new ones, freeing it of artificial sequentiality and structuring, making the paradigm a good candidate for specifying autonomic and decentralised coordination. Recently, it has been shown that this paradigm provides adequate abstractions to enact workflows [START_REF] Napoli | A Chemical Based Middleware for Workflow Instantiation and Execution[END_REF] and execute them in a decentralised way [START_REF] Fernández | A Chemistry-Inspired Workflow Management System for Scientific Applications in Clouds[END_REF]. Contribution. In this paper, we are proposing a fully decentralised workflow scheduling framework including two layers. The top layer is a chemically-coordinated shared space where workflows are decomposed into tasks, which are mapped to resources following simple chemical rules. The bottom layer implements this shared space in a fully decentralised way, based on a peerto-peer overlay network allowing the efficient storage and retrieval of molecules. Altogether, the system proposed here, and evaluated through different simulation experiments, is a decentralised framework allowing for an efficient dynamic multiple workflow scheduling. Outline. Section 2 introduces the chemical programming paradigm. Section 3 describes our decentralised workflow scheduling system and its chemistry-inspired coordination model. Section 4 evaluates the performance and network overhead of the framework. Section 5 presents the related works, and Section 6 draws some conclusions.

Chemical Programming Model

Natural analogies, and more specifically bio-chemical metaphors, have recently regained momentum in the construction of programming models coping with the requirements of the Internet of Services [START_REF] Viroli | A biochemical approach to adaptive service ecosystems[END_REF]. Initially proposed to adequately express highly parallel programs, the chemical programming paradigm exhibits properties required in emerging service platforms and naturally expresses autonomic coordination.

According to the chemical metaphor, molecules of data float in a chemical solution, and, on collision, react according to reaction rules (program) producing new molecules (resulting data). These reactions take place in an implicitly parallel, autonomous, and non-deterministic way until no more reactions are possible -a state referred to as inertia. The computation is carried out according to local conditions without any central coordination, ordering or serialisation. This programming style allows writing programs cleared of any artificial sequentiality and to concentrate on the functional aspects of the problem being solved. The simple presence of a molecule is enough to trigger a reaction requiring it. HOCL (Higher-Order Chemical Language) [START_REF] Banâtre | Generalised multisets for chemical programming[END_REF] is a language following such a paradigm. In HOCL, the solution is a multiset containing molecules, and rules define reactions between molecules which rewrite it. The multiset is the solely data structure provided. For the sake of illustration, let us consider the following chemical program which extracts the maximum value from a set of integers: replace x :: int, y :: int by x if x ≥ y in 2, 4, 5, 7, 9

Inria

The rule of the program specifies that any pair of integers inside the solution can react, consuming these two molecules and creating a new one with the highest value of the two, in case the condition holds. While the result of the computation is deterministic, the execution itself is not; HOCL simply ensures the mutual exclusion of reactions by the atomic capture of the reactants. In our example, a possible execution is the following: and4, and7 and9 (andproducing 4 and9) were carried out simultaneously and independently from each other. Once there is only one number left in the multiset (here, 9) the rule cannot be applied any more, and inertia is reached. Note that, even though in imperative programming languages this symbolises the end of the execution, the chemical programming paradigm does not have that notion -inertia is simply a stable state. This means that in case new molecules (here, integers) are dynamically inserted into the multiset, an imbalance arises. It is going to be detected and a new execution cycle triggered. Enabling persistent coordination amongst scheduling entities requests for such a concept.

Going even further, HOCL treats rules as regular molecules. This characteristic opens doors to autonomic computing: by consuming and producing rules, a program is able to modify its execution flow on-the-spot. The newly established expressiveness has been at the origin of new approaches to build autonomic service platforms [START_REF] Fernández | A Chemistry-Inspired Workflow Management System for Scientific Applications in Clouds[END_REF][START_REF] Napoli | A Chemical Based Middleware for Workflow Instantiation and Execution[END_REF][START_REF] Németh | Distributed workflow coordination: molecules and reactions[END_REF]. However, in these works, resources, on which the tasks of the workflows are run, are abstracted out, i.e. scheduling considerations were left aside.

Throughout the paper we are using the HOCL notation to express rules responsible for managing incoming workflows.

Decentralised Shared Space for Workflow Scheduling

We now present a fully decentralised just-in-time multiple workflow scheduler, of which the abstract organisation is shown on Figure 1: the scheduling process is shared by a set of chemical engines running on every resource machine, that constitute the entry points for the workflows which will be locally decomposed first into levels then into tasks for later execution. As illustrated by Figure 2, the proposed system is a two-layer architecture. It takes its roots in a generalised system for decentralised execution of chemical programs [START_REF] Obrovac | When Distributed Hash Tables Meet Chemical Programming for Autonomic Computing[END_REF], but is adapted here for scheduling purposes. We now detail these two layers.

RR n°7925

Communication Layer. In order to abstract out the underlying network topology and to deal with the potential unlimited growth of resources, chemical engines are connected in a structured peer-to-peer overlay network [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF][START_REF] Stoica | Chord: a scalable peer-to-peer lookup protocol for internet applications[END_REF], illustrated in the lower part of Figure 2. Next, we assume that the chemical engines, referred to as nodes throughout the paper, communicate through a ring-shaped overlay network. However, indeed, a DHT with a different topology could be used. Coordination Layer. Due to the use of the DHT, chemical engines can share their local data -molecules -with other participants in a scalable fashion (DHTs provide a distribution and retrieval mechanism the complexity of which typically grows logarithmically with the number of nodes). This way, an actual shared multiset is created on top of the DHT, to which nodes expose their molecules -levels, tasks and resources, as shown in the upper side of Figure 2. Thus, nodes are able to retrieve and consume molecules they do not hold, giving birth to a decentralised scheduling space. Moreover, each chemical engine includes workflow-independent rules in charge of workflow decomposition and task scheduling, acting by consuming molecules within the shared multiset. These rules are named generic scheduling rules and are explained more in depth in Section 3.3.

In the remainder of the section we firstly describe the structure of the molecules of the scheduling space and their placement in the underlying DHT-layer. Then, we detail the decentralised scheduling process carried out as reactions take place in the upper layer.

Molecule Types

There are three types of molecules in our system: molecules representing workflow levels, task molecules and resource molecules. When a molecule is produced, it is assigned a unique identifier based on a cryptographic hash function (typically provided as part of the DHT, such as SHA1). The molecule is then placed in the shared multiset, i.e. in the DHT ring in the bottom layer, by routing it to the appropriate node based on its hash identifier. The molecules and their placement in the DHT are depicted in Figure 3. Upon its entry in the system, a workflow is decomposed into levels by the entry node, producing level molecules (white dots in Figure 3). A level of a workflow comprises all of the tasks at the same distance from the exit task of a workflow's graph. Level molecules take the form Level : idLevel : task 1 , . . . , task n , where idLevel identifies the level of the workflow, and task 1 , . . . , task n are the tasks located in it. Each level molecule is then sent to its appropriate destination node according to its hashed value.

Task Molecules.

Once it is the turn of a level to be processed, the node storing its molecule cuts it into a set of task molecules (black dots in Figure 3), one per task. A task molecule takes the form Task : idT ask : command : res_desc : Dest : destT askId, . . . , where idT ask is the task's identifier, command denotes the actual service to invoke, res_desc is the description of the resource requirements needed to execute the task, and the Dest : destT askId, . . . sub-solution specifies to which tasks (given their task identifiers as destT askId) the output of the task has to be sent. Upon a level's decomposition, task molecules are similarly stored in the DHT. where idRes is the identifier of the resource and f eature 1 , . . . , f eature n are its current characteristics, such as the number of processors, the CPU load, or the memory usage. Since the features of a resource variate in time, every so often nodes republish resource molecules that replace old ones. Determining the right interval of republishing falls out of the scope of this paper. However, unlike level and task molecules, resource molecules are not uniformly hashed Instead, they are kept on the originating node (as suggested in Figure 3). Doing so keeps the network cost of republishing at zero. Furthermore, it allows the system to be up-to-date, since when a resource machine crashes the respective molecule consequently disappears from the shared multiset, preventing other participants to try to schedule a task on this resource.

Meta-Molecules and Resource Retrieval

In order to implement efficient scheduling policies, resources have to be ranked to efficiently select a resource satisfying a task's constraints. For this purpose, we introduce a second, orderpreserving, DHT layer, physically matching the original one (node ids as well as the key space size are preserved), to store meta-moleculespointers to resource molecules, in an order-preserving manner, which means that a meta-molecule's hash identifier is no more cryptographically hashed but based on its molecule's value. When a node (re)publishes its resource molecule, it creates a meta-molecule and stores it in the second DHT layer. As an illustration, consider two resource molecules M 1 = Res : cpu(80%) and M 2 = Res : cpu(50%). Supposing the ordering criterion for resource molecules is processor utilisation, M 1 's meta-molecule's hash identifier would be greater than that of M 2 's meta-molecule, since the resource represented by M 1 is more utilised than M 2 's resource.

The second, order-preserving DHT layer is used when trying to map a task to a resource. When a node is searching for an appropriate resource to execute its task on, it simply consults the second DHT layer for resource meta-molecules. Moreover, the node is able to precisely locate specific matching resources in this layer, by issuing specialised queries such as cpu < 80%. The support for such range queries has been extensively studied in literature, and typically require O(log 2 (n)) messages to complete, as discussed for instance in [START_REF] Chen | On overlay schemes to support point-in-range queries for scalable grid resource discovery[END_REF]. A meta-molecule testifies to the existence of a particular resource molecule; when a node obtains a meta-molecule, it is able to consequently obtain the original resource molecule the meta-molecule derives from.

Workflow Scheduling Process

Despite the wide variety of existing scheduling heuristics, none of them have been shown to deliver an efficient scheduling algorithm for both types of scientific workflows: data intensive and computation intensive. The selection of an appropriate workflow scheduling algorithm depends of several parameters estimated by users, such as communication costs and task completion times, making the schedulers prone to judgement errors. To this respect, the framework proposed in this paper aims at providing a decentralised and just-in-time task-to-resource mapping, on top of which any workflow scheduling heuristic can be implemented.

Inter-layer Execution Model.

The execution of rules is event-driven: a rule is triggered when a node receives a molecule or a workflow. Three entities can provoke a rule's execution: a workflow, a level molecule and a task molecule. Upon the receipt of a workflow or a level molecule, a node locally triggers rules to decompose the workflow into levels or levels into tasks, respectively. Afterwards, the levels and tasks generated are hashed and stored in the DHT.

On the other hand, when a node receives a task molecule, it has to find a resource to map it to. Thus, the node constructs a range query in which it lists the requirements a resource has to satisfy and then lets the DHT's range search mechanism (second layer) find it a match. If a matching resource meta-molecule has been found, the node proceeds to the next step: retrieving the resource molecule itself containing information for the actual execution of the task. Finally, the node sends its task to the resource node for execution.

Workflow Structure.

Workflows received by nodes are described using the chemical workflow definition (Algorithm 1). The general shape of this workflow representation is as follows: the main solution is composed of Inria as many task molecules as there are tasks (or services) participating in the workflow. This chemical representation of workflows has been shown to be appropriate to express the decentralised execution of a wide variety of workflows patterns [START_REF] Fernández | A Chemistry-Inspired Workflow Management System for Scientific Applications in Clouds[END_REF].

Algorithm 1 Chemical workflow representation.

2.01

// Multiset (Solution)

2.02

Task : 1 : command1 : res_desc1 : Dest : 2, Dest : 3, . . . , // Task1 definition

2.03

Task : 2 : command2 : res_desc2 : Dest : 4, . . . ,

2.04

Task : 3 : command3 : res_desc3 : Dest : 4, . . . ,

2.05

Task : 4 : command4 : res_desc4 :

2.06

Workflow Scheduling Flow.

We now describe the workflow scheduling process, which is illustrated by Figure 4. Chemical rules used in the process are given in Algorithm 2. A workflow initially enters the platform by being sent to a given chemical node, its entry point, which receives the workflow and decomposes it in levels, producing level molecules. This step mimics the first phase of algorithms such LMT or HEFT [START_REF] Topcuoglu | Task scheduling algorithms for heterogeneous processors[END_REF]. Upon the receipt of a workflow, a node triggers the workflowDecomp rule which reorganises the tasks represented as sub-solutions of the workflow representation into levels. It consumes the molecules representing the different tasks in the workflow, and produces one molecule per level.

Algorithm 2 Generic rules.

-WORKFLOW DECOMPOSITION - Tasks have to be scheduled level by level, calling for coordination between nodes involved in scheduling a given workflow, in order to allow the system to pass from scheduling tasks of one level to the next one, and so on until reaching the last level and delivering the final result to the requesting user. More precisely, the system has to assure tasks from level i are not being scheduled for execution before or during the scheduling of tasks from level i -1. To distinguish between levels which can be scheduled and those which have to wait on scheduling we use two types of molecules: Level : num : READY and Level : num, respectively. The initial workflow decomposition through the activation of the rule workflowDecomp produces only Level : num molecules to indicate that none of the levels can be scheduled at that time. However, as the scheduling goes on, these molecules will, one by one, turn into Level : num : READY molecules, indicating that the tasks of the previous levels have been completed and that the tasks of the next level can be scheduled for execution.

To extract tasks from level molecules, a node uses the levelDecomp rule. This rule consumes a level molecule with its state set to READY , and produces as many task molecules as there are tasks in the given level (Algorithm 2, line 3.03). The task molecules are then hashed and stored in the DHT.

Upon receipt of a task molecule, a node uses the mapTaskRes rule to map the task to the best suitable resource it can find (Algorithm 2, line 3.05). Using the resources' requirements indicated in the task molecule, the second DHT layer is scanned by a range query reflecting the if -clause of the mapTaskRes rule. If a matching resource molecule is found, the rule produces a molecule that deploys the given task onto the resource found during molecule capture (denoted by the special system.deploy() molecule in Algorithm 2). Note that the resource molecule is consumed in the reaction, preventing other tasks to be scheduled before it has been republished. Once a node receives the notification from the system that its task has been completed, it notifies the node holding the level molecule for this task, which, in turn, keeps track of completed tasks. When all of its tasks have been completed, the node holding the (currently active) level molecule retrieves the inactive molecule of the next level. It then deletes it and creates a new, active level molecule and stores it with the same hash identifier. This act allows the next level to be decomposed and its tasks to be scheduled. This process carries on until the tasks of the last level have finished their execution. At the end, its node collects all of the results and transfers them to the entry node, which delivers them to the client which submitted the workflow for execution.

Inria

Multiple Workflow Scheduling Example. Let us consider two workflows, A and B, where task molecules of level L1 (in both workflows) are awaiting scheduling, as illustrated on Figure 5. Task molecules A, B and C from workflowA and D and E from workflowB are ready to be executed. There are four available resources. This leads to a situation where not all of the tasks can be scheduled concurrently. Each of the five nodes holding task molecules tries to grab a matching resource molecule (due to the execution of the mapTaskRes rule). Supposing the nodes holding B, C, and D successfully grab their respective resource molecules, they execute a reaction following the mapTaskRes rule by deploying their tasks onto the matching resources. If the only available resource left does not meet the needs of neither A nor E, the nodes holding them wait for a small predefined amount of time and retry fetching a resource molecule.

Evaluation

Simulation Set-up

To better capture the behaviour and expected performance of the proposed system, a Pythonbased simulator was built. It simulates a two-layered, DHT-structured network of nodes offering storage and computing power. The nodes also store the meta-information about available resources (the meta-molecules). Workflows sent to this network are processed and scheduled following the decentralised coordination model described in Section 3. The simulator operates in discrete time steps.

Goals and Assumptions. Our goal is to generally show the overhead, in terms of latency and network load, of the scheduling process itself, as we do not intend to provide a new scheduling algorithm, but a framework for decentralised coordination for large-scale scheduling. Accordingly, some assumptions were made. A workflow's depth (the number of levels) was randomly chosen between 3 and 10, with each level containing an arbitrarily assigned number of tasks (between 1 and 15). Furthermore, a task's duration was voluntarily kept low (between 1 and 10 time steps) as it facilitates the evaluation of the framework's overhead. Finally, the computing power of nodes and the capacity of links in the network were virtually unbounded. While such an assumption could sound unrealistic, our simulation did not intend to provide real accuracy in actual settings, as only a real-world deployment could do that. Our validation is oriented towards providing insight into the scalability of the framework.

Results

Execution Time. We first tried to capture the scalability in terms of time overhead, when both the number of nodes and workflows increase. Results are depicted on Figure 6. The first conclusion is that increasing the number of nodes has an impact on the time taken to schedule workflows. However, this overhead is limited, since the cost of the routing process grows logarithmically with the number of nodes (except for resource retrieval which requires log 2 (n) messages to deal with range queries). Another conclusion that can be drawn by looking at all of the curves together is that when the number of workflows increases, the time to solve them does not increase much. This is a consequence of fully decentralising the scheduling process, which enables a high degree of parallelism. However, one can argue that, as Figure 6 suggests, having fewer nodes leads to better performance. This anomaly is inherent to the assumption that the network links and the computing power are unbounded. Hence, we need to have a look on the network overhead, which is depicted in Figures 7 and8. Network Overhead. The series of curves on Figure 7 shows the total number of messages generated in the same experiments as earlier. They first suggest that, due to the usage of logarithmic routing, increasing the number of nodes does not impact significantly the network. The curves also show that the number of messages increases with the number of workflows. In fact, the number of messages is directly proportional to the number of tasks to be scheduled, as the scheduling of a task relies on resource retrieval, which needs O(log 2 (n)) messages to complete. However, this is partly inevitable as each task must be scheduled independently of others. Finally, Figure 8 depicts the evolution of the traffic load perceived by each node in the same conditions. While the traffic costs per node increase with the number of workflows, it is also drastically reduced when more nodes take part in the scheduling process. This behaviour is a highly desirable one, as we target large-scale platforms. This reinforces the scalability of the whole platform, since the system is able to spread the network load evenly as it increases in size.

Related Works

We here briefly review the most recent approaches dealing with decentralised scheduling intended for large-scale platforms.

Works such as [START_REF] Dias De Assunção | Intergrid: a case for internetworking islands of grids[END_REF] and [START_REF] Leal | A decentralized model for scheduling independent tasks in federated grids[END_REF] motivate the need of interlinking Grid systems through peering arrangements in order to enable resource sharing. Local schedulers are connected through gateways which are used to serve unsatisfied local requests. Ranjan et al. [START_REF] Ranjan | A decentralized and cooperative workflow scheduling algorithm[END_REF] designed a fully decentralised scheduler which uses a DHT split in regions, where requests for resources are posted.

Inria

Since each region is managed by one grid peer, the system is still susceptible to single-point-offailure patterns. Finally, works presented in [START_REF] Fiscato | On the feasibility of decentralized grid scheduling[END_REF][START_REF] Vasilakos | Decentralized As-Soon-As-Possible grid scheduling: A feasibility study[END_REF] propose Gossip-based schemes to schedule computation-intensive jobs. Like in our system, there are no predefined schedulers -any entity can schedule a job.

In contrast to these approaches, our framework intends not only to decentralise the scheduling process, but also to maximise the efficiency of scheduling algorithms to be deployed, as the coordination layer, built upon a structured network globally ranking resources, enables a global knowledge of available resources in the platform, ensuring that each task will be run on an adequately and accurately chosen resource.

Conclusion

The evolution of clouds towards community clouds raises the need for large-scale, coordinated workflow mechanisms where the whole set of resources and jobs are associated in a transparent way. This calls for new mechanisms for large-scale coordination mechanisms. This paper proposes a fully decentralised coordination space relying on a chemical metaphor: workflows, jobs and resources are molecules to be consumed, i.e. matched. The underlying communication layer ensures a fully decentralised execution of this matching, by relying on a DHT. Moreover, the DHT-driven coordination enables a just-in-time scheduling technique capable of matching a task to its currently perfect resource candidate. Simulations were conducted, establishing further the feasibility and scalability of the approach.

A software prototype is being developed, interfacing the P2P-based layer with a chemical engine for coordination. It is planned to be deployed over actual platforms, and will constitute a platform for implementing different scheduling strategies in a fully decentralised fashion.

  Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.1.1 Level Molecules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.2 Task Molecules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.3 Resource Molecules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Meta-Molecules and Resource Retrieval . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Workflow Scheduling Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3.1 Inter-layer Execution Model. . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3.2 Workflow Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3.3 Workflow Scheduling Flow. . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4 Evaluation 11 4.1 Simulation Set-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2, 4 , 5 , 7 , 9 → 4 , 5 , 9 → 5 , 9 → 9

 4579459599 Because of the implicit parallelism of the execution model, reactions consuming 2

Figure 1 :

 1 Figure 1: Proposed architecture overview.

Figure 2 :

 2 Figure 2: Two-layer architecture.

Inria

  3.1.1 Level Molecules.

Figure 3 :

 3 Figure 3: Scheduling molecules.

Figure 4 :

 4 Figure 4: Workflow decomposition.

  workflowDecomp = replace Task1, Task2, ..., Taskn 3.02 by Level:1: Task1 , Level:2: Task2 , Level:N: Taskn -LEVEL DECOMPOSITION -3.03 let levelDecomp = replace-one Level:num:READY: Task1, ... ,Taskn 3.04 by Task1, ... ,Taskn -TASK TO RESOURCE MAPPING -3.05 let mapTaskRes = replace Taski, Resj 3.06 by system.deploy( Taski, Resj ) 3.07 if ( Taski.isCompatibleWith( Resj ) )

Figure 5 :

 5 Figure 5: Multiple workflow mapping.

Figure 6 :Figure 7 :Figure 8 :

 678 Figure 6: Execution time.

http://www.myexperiment.org/ RR n°7925

RR n°7925

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399