Jorge Leira Iglesias

Alessandra Tassoni

Takuji Adachi

Michael Stich

Thomas M Hermans
email: hermans@unistra.fr

Jorge Leira-Iglesias

Oscillations, travelling fronts and patterns in a supramolecular system

come

We use a perylene diimide derivative PDI that forms supramolecular polymers in aqueous borate buffer (Figure 1a). Upon reduction by Na 2 S 2 O 4 the dianion PDI 2-is mostly monomeric, and at equilibrium with small ~100 nm PDI 2-assemblies (see below). [START_REF] Leira-Iglesias | Supramolecular pathway selection of perylenediimides mediated by chemical fuels[END_REF] Oxidation by atmospheric oxygen leads first to the radical anion PDI• -, before returning to the neutral PDI mon (see Methods). The latter undergoes a cooperative supramolecular polymerisation to form micron-sized colloidal assemblies PDI assem by side-to-side bundling of one-dimensional PDI fibers. [START_REF] Leira-Iglesias | Supramolecular pathway selection of perylenediimides mediated by chemical fuels[END_REF] The polymerisation process can be followed by UV-Vis spectroscopy where a characteristic band at 528 nm can be tracked, colour camera where pink / blue / purple corresponds to PDI / PDI• -/ PDI 2-respectively, or dynamic light scattering (Supplementary Figures 1 and2).

The cooperative nature of the assembly process is discerned from the sigmoidal time progression of the degree of polymerisation a vs. time (Figure 1c), where a = 0 corresponds to the disassembled state and a = 1 to the fully assembled state. Light scattering shows a similar sigmoidal increase from ~100 to 1500 nm in hydrodynamic radius R H during assembly (Supplementary Figure 3, black line). In addition, the fact that the half-time t scales as log(t) µ -0.48 log(C 0 ), where C 0 is the initial concentration of PDI, indicates that more processes are occurring than only nucleation and elongation (Supplementary Section 2 and Supplementary Figure 4). A detailed analysis including seeding experiment and global fitting by analytical models [START_REF] Meisl | Molecular mechanisms of protein aggregation from global fitting of kinetic models[END_REF] showed that fragmentation is also involved (Figure 1c, Supplementary Section 2). Fragmentation was further confirmed by performing experiments at different stirring / shear rates, where the fastest growth was observed at the highest rate (cf. Supplementary Figure 7). Others have shown that stirring can lead to fragmentation [START_REF] Carnall | Mechanosensitive Self-Replication Driven by Self-Organization[END_REF] or increased secondary nucleation [START_REF] Kondepudi | Secondary nucleation that leads to chiral symmetry breaking in stirred crystallization[END_REF] . The reduction rate of PDI assem was quantified using stopped-flow experiments, where a solution of reductant Na 2 S 2 O 4 was rapidly mixed with PDI mon solutions that had been aged for determined times. Solutions prepared from freshly synthesized PDI powder gave seemingly random reduction kinetic profiles, due to the broad distribution [START_REF] Leira-Iglesias | Supramolecular pathway selection of perylenediimides mediated by chemical fuels[END_REF] of particle sizes. Therefore, all solutions were first fully reduced to PDI 2-, and stirred in air until a bright pink colour of the neutral PDI mon was observed. The latter solution was rapidly transferred into the stopped-flow syringe and left to age. Figure 1d shows a typical reduction experiment tracked using the PDI 2-absorption band at 612 nm, which shows first a fast exponential increase up to ~1 s, followed by a slower sigmoidal increase. These complicated kinetics can be understood by a 2-step process: 1) a firstorder reaction where Na 2 S 2 O 4 reacts with the outer shell of the PDI assem colloidal assemblies leading to a rapid colour / absorption change (i in Fig. 1b), and 2) surface-erosion of the colloids leading to sigmoidal release [START_REF] Ulery | Biomedical applications of biodegradable polymers[END_REF] of PDI into solution followed by instantaneous reduction to PDI 2-(ii-iv in Fig. 1b). The time constants corresponding to these two processes (t 1 and t 2 , respectively) both increase by a factor 2-3 over the 90 min aging period (cf. insets in Figure 1d). In other words, during the PDI mon to PDI assem aging the assemblies are getting larger and larger (from ~100 nm to ~2 µm, cf. Supplementary Section 1), leading to ever slower apparent reduction rates.

So far, we have shown that there is significant non-linearity in both the assembly and disassembly kinetics of PDI structures. The nucleation-elongation-fragmentation process acts as a positive feedback mechanism, whereas the size-dependent reduction / disassembly of PDI can be seen as a negative feedback; both of which are thought to be required [START_REF] Scott | Waves, and Chaos in Chemical Kinetics[END_REF] to obtain emergent properties such as oscillations. With the basic elements to construct an oscillator in place we set out to find the oscillating window by pushing the system far from equilibrium in a stirred semibatch reactor.

Practically, we placed a stirred glass vial in a well-ventilated box with constant oxygen supply and illumination and used a syringe pump to inject the reductant (Na 2 S 2 O 4 ) solution continuously (Figure 2a). A fast diode-array UV/Vis detector, colour CCD camera, near infra-red static light scattering IR-SLS, and confocal microscopy were used for analysis (Supplementary Section 3 and 4). Conventional visible light scattering cannot be used, since 1) PDI 2-absorbs the 639 nm laser light, preventing quantitative static light scattering (cf. Supplementary Figure 3), and 2) stirring disrupts the correlation needed for dynamic light scattering. A home-built 905 nm IR-SLS setup was used instead (Supplementary Figure 9); to benchmark the setup we performed a step-wise redox cycle (Supplementary Figure 10), namely: i) a solution of PDI assem has significant IR-SLS intensity and a pink colour, ii) addition of reductant leads to PDI 2-and a fast drop of the colour intensity of the red and blue channel, iii) oxidation in air to PDI• -results in a local maximum in blue intensity, iv) further oxidation to PDI mon restores the initial pink solution colour while the IR-SLS intensity reaches a minimum, v) assembly into PDI assem leads to a sigmoidal increase in scattering and visual turbidity. The latter experiment shows that reduction leads to disassembly and low IR-SLS intensity, and that PDI mon is the least assembled state consisting of ~100 nm structures.

The phase space of the system was explored in the semi-batch reactor by varying the initial concentration of PDI vs. the flow rate of reductant (Figure 2b). In all cases, the initial solution was completely reduced to PDI 2-before starting the continuous inflow of reductant. The composition of the solution species PDI 2-/ PDI• -/ PDI mon / PDI assem was determined from colour analysis and UV/Vis spectra (see supplementary section 3). For low flow rates a steady state 'SS' was observed by following the red channel of the CCD camera (Figure 2b,c). The composition of the solution is close to fully neutral assembled PDI, apparent from the solution colour and UV-Vis spectrum. To confirm the latter, the reductant inflow was stopped, causing full oxidation and assembly into PDI assem , and leading only to a minor (< 5 %) increase in intensity (Supplementary Figure 11a). Increasing the flow rate further, leads to complex oscillations in a narrow window 'OSC' (Figure 2b,d, Supplementary Video 1). For the highest flow rates, precipitation 'PR' occurred after ~40 min, where a film of solids would accumulate at the solution/air interface (Figure 2b,e).

Oscillations were always damped and with seemingly period-2 characteristics. That is, oscillations occur in 'pairs', where one of the two peaks is lower than the other (cf. Figure 2d). The amplitude of the oscillations gradually decreases, whereas their frequency is ever increasing. The path to oscillations can be understood by looking at the colour space in two-dimensions (Figure 2f). To this end, the red / green / blue channels obtained from the camera are converted to CIE 1931 x and y colour coordinates. In Figure 2f the process is as follows: i) reduction of PDI solution to PDI 2-by addition of an aliquot of Na 2 S 2 O 4 solution; ii) atmospheric air oxidizes to PDI• until very small PDI mon structures are formed; iii) sigmoidal growth to large assemblies PDI assem ; iv) start of the continuous flow of reductant, followed shortly by oscillations; v) damping and decay of oscillations. To be sure that oscillations in the size of the assemblies occurred, we performed experiments combining IR-SLS with colour tracking (Figure 2g and Supplementary Figure 12). In Figure 2g one can see that during a large oscillation all the way to disassembled PDI 2-(index ii), the IR-SLS intensity drops to the baseline and the (red) colour intensity is low as well; shortly thereafter, neutral PDI mon is formed (index iii) leading to rapid increase in colour intensity, followed by a much slower sigmoidal increase in IR-SLS intensity and visual turbidity in the vial (index iv).

A subsequent oscillation shows a similar trend (cf. indices v-viii in Figure 2g). Further evidence comes from confocal microscopy, where aliquots were taken during oscillations showing nearly complete disappearance of colloidal assemblies during large oscillations (e.g., compare v and vi in Supplementary Figure 13).

In general, many oscillators studied under semi-batch conditions show damped oscillations due to accumulation of waste products. Microtubules for example, suffer from increasing concentrations of guanosine diphosphate over their triphosphate analogue, which is thought to lead to amplitude loss in batch experiments. [START_REF] Sept | A Chemical Kinetics Model for Microtubule Oscillations[END_REF][START_REF] Lange | Tubulin oligomers and microtubule oscillations[END_REF] To test whether waste accumulation was of importance in our system, we added an equivalent of 5 hours of waste mid-way during oscillations (Supplementary Figure 14a). Only a very minor disturbance in the oscillations was observed. As a negative control, an aliquot of buffer of the same volume as in the 'waste addition experiments' was added, which did not disturb the oscillations (Supplementary Figure 14b). From the latter two series of experiments we conclude that waste accumulation or resulting changes in ionic strength are not responsible for the damping of the oscillations. Another salient detail is that oscillations can never be obtained when starting from aged PDI assem solutions, but only when starting from mostly disassembled PDI mon solutions (i.e., by fully reducing to PDI 2-, and then oxidizing to PDI before starting inflow of reductant). In other words, the oscillations are inherently transient and 'en route' to a non-oscillating state consisting of large PDI assem . The latter is also confirmed by the model we develop (see below).

To understand the oscillator behaviour, we expanded a recent nucleation-elongationfragmentation model [START_REF] Cohen | Nucleated polymerization with secondary pathways. I. Time evolution of the principal moments[END_REF] (used above, cf. Figure 1c) with chemically-fuelled reduction by Na 2 S 2 O 4 and oxidation by O 2 . Specifically, we consider reduction of a polymer Q j of length j (i.e., the removal of an end-capped monomer from a one-dimensional polymer and its instantaneous reduction), and oxidation of non-assembled reduced monomer R to monomer O. Since both PDI• and PDI 2-are mostly disassembled (cf. Supplementary Figure 2), we combine them both into reduced monomer R. Figure 3a shows the used equations, rate constants, and schematic representations of the model. Using the mathematical approach by Knowles and co-workers [START_REF] Cohen | Nucleated polymerization with secondary pathways. I. Time evolution of the principal moments[END_REF] we derived the following equations (cf. Supplementary section 5) for the number concentration of polymers [P], the mass concentration of polymers [M], and the concentrations [O] and [R] of the monomer species:

![#] !% = -3𝑘 *+,-[𝑃] + 𝑘 *+,-[𝑀] + 𝑘 123 [𝑂] 5 , (1)
![7] !% = -2 𝑘 *+,-+ 𝑘 +9! [𝑃] + 2𝑘 9: [𝑃] 𝑂 + 2𝑘 123 [𝑂] 5 , (2)
![<] !% = 𝑘 +9! [𝑃] -𝑘 => [𝑅], (3)
𝑂 = [𝑚] %=% -[𝑀] -[𝑅], (4)
where we have used nucleus size n = 2 and conserve the total mass [m] tot . A continuation analysis and simulations of the model were performed with MatCont (see Supplementary Section 5). The main finding is that damped oscillations can be observed in all variables (total number of polymers, total mass of polymers, and the monomer concentrations) for an extended range of parameters (cf. Figure 3b and Supplementary Figure 15). We classify the behaviour as oscillating if the amplitude within 3 consecutive oscillations is larger than 50% of the asymptotic steady state value of [M]. A number of aspects of the model are in qualitative agreement with the experiments. One can compare Figure 3b to 2b (see above), where in the former at low flow rate of reductant a steady-state SS is obtained, and in the latter analogously at low k red a SS is found (note: k ox in the experiments is always constant, and determined by influx of atmospheric oxygen). In other words, at low rates of reduction the molecules stay in the assembled PDI assem state, as one would expect. Increasing k red values leads to damped oscillations (OSC in Figure 3b), since there is a competition between assembled and disassembled PDI with non-linear kinetics. The top inset in Figure 3b shows time traces along a vertical phase line, where decreasing k ox leads to more oscillations (i.e., less damping), an increasing asymptotic value, and an increasing period. A similar trend is seen for the horizontal phase line (bottom inset Figure 3b) in the direction of increasing k red at constant k ox . For too large k red the oscillations become unstable and lead to unphysical (negative and extremely large) concentrations, shown in the 'US' region in Figure 3b. Surprisingly, this is where in experiments precipitation is observed (Figure 2b), though a direct comparison cannot be made at this point.

Other than the chemically fuelled rates constants k ox and k red , fragmentation k frag is a sensitive parameter; decreasing its value leads to a decrease in damping (Figure 3c), allowing hundreds of oscillations up to the point that experimentally it would be difficult to distinguish from sustained oscillations. More generally, we can vary the nucleation k nuc , and elongation k el rates and conserve the qualitative finding-that is, the oscillations are generic. If the initial condition contains enough polymers, the nucleation rate can even be set to zero, while maintaining the oscillations.

Beyond oscillations, we investigated the spatiotemporal behaviour of our supramolecular system. Firstly, we explored traveling fronts, where a PDI mon solution was seeded with preformed 1h old PDI assem polymers, leading to isothermal frontal supramolecular polymerisation in adjacent volumes (Figure 4a,b, and Supplementary Video 2). Temperature differences are not important in our system as they would quickly equalize due to fast thermal diffusion. [START_REF] Pojman | Convective effects on chemical waves. 1. Mechanisms and stability criteria[END_REF] In a rectangular chip with two parallel glass slides spaced by 1 mm, a traveling front with an initial velocity of 0.26 ± 0.01 mm min -1 -about ~20 times faster than ~100 nm PDI mon diffusion-can be seen that increases the area initially occupied by the seeds (cf. left panel of Figure 4b and Supplementary Video 2). Later on, a ring structure is formed that slows down progressively until it stops completely, as can be seen in the kymograph in Figure 4c. Upon closer inspection of the traveling front using confocal microscopy and analysis by particle image velocimetry, it was clear that large scale in-plane convection was present in the chip, shortly after seeds were added (Supplementary Video 3). As a control, we added PDI assem and buffer to the same PDI mon solution, and observed much more spreading of the seeded front vs. the non-seeded region (Supplementary Video 4). In other words, seeding triggers the convective front, similarly to (thermal) initiation in covalent frontal polymerisation.

23 PDI mon solutions have an ~0.2% higher density as compared to fully assembled PDI assem (Supplementary Figure 16). While this seems like a small difference, it is known that in a horizontal experiment, neighbouring volumes with different density always lead to convective instabilities. [START_REF] Pojman | Convective effects on chemical waves. 1. Mechanisms and stability criteria[END_REF] The traveling front progressively slows down (Figure 4c), since spontaneous nucleation and growth occurs in the unreacted zones over time as well, reducing the density difference with the front, and thus halting convection.

When replacing the top glass plate with mineral oil, convection is exacerbated and a single massive convection cell is formed (Figure 4d). In the latter experiment, PDI 2-is oxidized by atmospheric oxygen diffusing through the oil, leading to an outward moving propagating oxidation front (cf. dashed area, Figure 4d), while simultaneously turning the entire volume into a single convection cell leading to alignment of PDI assem structures along the flow lines (Supplementary Video 5). Small scale convection is observed in unseeded as well as seeded experiments (far from the front), where mosaic structures are formed (Figure 4e and Supplementary Figure 17). Similar structures have been observed in microtubule experiments [START_REF] Mandelkow | Spatial patterns from oscillating microtubules[END_REF] and in an inorganic system [START_REF] Nagypal | Gravity-induced anisotropies in chemical waves[END_REF] . Again, spontaneous nucleation and growth leads to small zones of different composition and density, inducing localized structures.

We have shown collective size oscillations in a supramolecular polymer system by combining cooperative self-assembly with chemically fuelled disassembly. Interestingly, our model shows that non-linear negative feedback like we have observed experimentally (i.e., sizedependent reduction / disassembly rates, see above) is not required; positive non-linear feedback from the supramolecular polymerisation combined with chemically-fuelled linear depolymerisation is sufficient to obtain oscillations. This provides an exciting outlook for other supramolecular polymers reported on so far, [START_REF] Tena-Solsona | Non-equilibrium dissipative supramolecular materials with a tunable lifetime[END_REF][START_REF] Maiti | Dissipative self-assembly of vesicular nanoreactors[END_REF][START_REF] Mishra | Biomimetic temporal self-assembly via fuel-driven controlled supramolecular polymerization[END_REF][START_REF] Jalani | Temporal switching of an amphiphilic self-assembly by a chemical fuel-driven conformational response[END_REF][START_REF] Boekhoven | Transient assembly of active materials fueled by a chemical reaction[END_REF] which use chemical fuels to drive (seemingly) cooperative polymerisation. The type of supramolecular oscillations we find here are always damped. This is because they are found close to a subcritical Hopf bifurcation, [START_REF] Scott | Chemical Chaos[END_REF] which leads to an unstable limit cycle and therefore does not support sustained oscillations. Similar observations have been made in microtubule systems, where inherent damping was suggested as well. [START_REF] Hammele | Modeling oscillatory microtubule polymerization[END_REF] Other than temporal order, we have shown spatiotemporal phenomena. In non-stirred experiments cm-scale polymerization fronts and polygonal convection patterns are formed due to density differences between assembled and non-assembled regions. The latter polygons are dissipative structures in the Prigogine-sense, meaning they are only observed beyond stability of the thermodynamic branch. [START_REF] Nicolis | Self-organization in nonequilibrium systems[END_REF] Recognizing dissipative structures in supramolecular systems is difficult, since order can already exists at equilibrium due to non-covalent interactions. Dissipative structures, however, occur at length-scales much larger than the molecules and their fundamental (intermolecular) interactions, and should disappear if the system were to be isolated. Our system has nm-µm scale order at the level of the supramolecular structures, as well as cm-scale order at the level of the dissipative (convective) structures. It will be interesting to further explore the interplay of out-of-equilibrium supramolecular polymerisation with convective instabilities, in addition to recent enzymatic convection patterns 33 and supramolecular-mechanical couplings [START_REF] Orlova | Revolving supramolecular chiral structures powered by light in nanomotor-doped liquid crystals[END_REF][START_REF] Gelebart | Making waves in a photoactive polymer film[END_REF] . This will allow large scale self-organization, transport, and communication driven by fuelled dissipative non-equilibrium self-assembly [START_REF] Sorrenti | Non-equilibrium supramolecular polymerization[END_REF] . In general, non-equilibrium supramolecular polymerization [START_REF] Sorrenti | Non-equilibrium supramolecular polymerization[END_REF][START_REF] Sorrenti | Non-equilibrium steady states in supramolecular polymerization[END_REF] only leads to large scale emergent properties such as oscillations when the system is pushed far from equilibrium beyond the first bifurcation.

Correspondence and requests for materials should be addressed to T.M.H. ). e, Transient formation of polygons (appearing after ~ 30 min) was observed while performing propagating front experiments with identical conditions to those as shown in panel a.

Figure Captions

Methods

PDI system. PDI was synthesized according to our protocol described recently. [START_REF] Leira-Iglesias | Supramolecular pathway selection of perylenediimides mediated by chemical fuels[END_REF] In short, PDI was prepared by imidization of perylene-3,4,9,10-tetracarboxylic acid dianhydride with ethylenediamine. Afterwards, amide coupling between the perylene diimide derivative and oligoethyleneglycol derived from gallic acid was performed yielding the target compound PDI. 𝐼 𝑞, 0 𝐼 𝑞, 𝜏 𝐼 𝑞, 0 [START_REF] Mandelkow | Spatial patterns from oscillating microtubules[END_REF] were measured on a home-built light scattering setup with an ALV7002 digital correlator using a laser diode at λ = 639 nm at a wavevector q = 0.0185 nm -1 (90° scattering angle).

Preparation of

Measurements were performed on 100 µM PDI, PDI where 𝑔 H = 𝑔 5 -1. Hydrodynamic radii RH were then calculated using the Stokes-Einstein relation 𝑅 S = 𝑘 T 𝑇 6𝜋𝜂𝐷

where 𝐷 = 1 𝜏𝑞 5 and the root mean-squared deviation from the mean size of each state where determined fitting the hydrodynamic radius distribution with a Schultz distribution function. In order to perform the cooperative growth analysis of PDImon (cf. Supplementary Figure 3), the intensity autocorrelation functions were fitted with a monoexponential decay function 𝑔 H 𝑡 = 𝑒 M[% .

Kinetics of the cooperative

Fig. 1 .

 1 Fig. 1. Kinetics of redox fuelled PDI assembly and disassembly. a, PDI is reduced to PDI 2-upon addition of Na2S2O4. Spontaneous oxidation in air leads first to radical anion PDI •-and then to neutral PDI. b, After one redox cycle (i.e., reduction to PDI 2-and oxidation to PDImon, kred and kox, respectively), PDImon grows via a cooperative polymerisation mechanism with nucleation knuc, elongation kel, and fragmentation kfrag constants. The system is also characterized by a size-dependent reduction rate for PDIassem (kred,p, see data in panel d). c, The degree of polymerisation a as a function of time at different seeding per cent and PDI concentrations (see methods). Global fitting was used (solid lines) with a saturating elongation + fragmentation model 14,19 yielding: knuc = 0.069 ± 0.002 M -1 min -1 , kel = 4.5•10 6 ± 4•10 5 M -1 min -1 , kfrag = 2.38•10 -5 ± 2.8•10 -6 min -1 , Ke = 1.80•10 -5 ± 1.5•10 -6 M, nucleus size n = 2 and error MRE = 0.0015. d, Reduction kinetics followed by stopped-flow where 80 µL of a 100 µM PDImon solution and 80 µL of a 50 mM Na2S2O4 solution were loaded in syringes and quickly mixed at defined intervals. Over time PDImon grows to PDIassem in the syringe, leading to slower kinetics shown in the insets. Two processes are observed: one exponential with time constant t1 and one sigmoidal with constant t2, which increase over time (see main text and methods). The red dashed line indicates the transition between the two processes. The reduction kinetics were followed at the characteristic dianion bands of PDI 2-at 612 nm.

Fig. 2 .

 2 Fig. 2. Supramolecular oscillations. a, Three different states (steady state SS, oscillations OSC, and precipitation PR) were observed in a semi-batch reactor under continuous influx of chemical fuel (Na2S2O4).

Fig. 3

 3 Fig. 3 Supramolecular oscillator model. a, The nucleation-elongation-fragmentation model is expanded with chemical fuels, i.e., reduction to PDI •-or PDI 2-species R and the oxidation back to PDImon species (here O). b, Phase space plot as a function of the reduction and oxidation rates (kred and kox, respectively) shows three different states: steady-state 'SS', oscillations 'OSC' and unphysical solutions 'US'. The top inset corresponds to the vertical cut through the oscillating window 'OSC' (along the solid line). The bottom inset shows the horizontal cut (along the dashed line). Initial conditions: [P] = 1•10 -8 M, [M] = 1•10 -7 M, [R] = 5•10 -6 M, [m]tot = 1•10 -5 M; constants: kfrag = 3•10 -4 s -1 , knuc = 4•10 -4 M -1 s -1 , kel = 400 M -1 s -1 . c, Reduced damping for smaller values of kfrag up to the point of nearly sustained oscillations (black line).

Fig. 4 .

 4 Fig. 4. Supramolecular traveling fronts and patterns. a, A rectangular 3D printed chip (50 x 25 mm) with two parallel glass slides spaced by 1 mm was used. A PDImon solution was immediately injected into the chip. Then, PDIassem seeds (30 µL of a 1h old PDImon solution) were added from one side of the chip. b, A traveling front in adjacent volumes was observed using a colour CCD equipped stereoscope (cf. Supplementary Video 2). The brightness/contrast has been increased to better show the front. c, The kymograph shows the progressive decrease in velocity of the front (extracted from Supplementary Video 2). d, The top glass cover slide was replaced by mineral oil permitting diffusion of O2 and near-frictionless fluid transport. A PDI 2-solution (100 µM) was poured into the chip and covered by oil. An outward moving front (dashed area) was observed showing oxidation to PDImon. Simultaneously, a single massive convection cell is formed leading to an alignment of PDIassem structures in the direction of the flow (see Supplementary Video

5

 5

  PDImon. A 100 µM PDI mother solution was prepared by dissolving PDI (1 mg, 0.60 µmol) in 50 mM borate buffer, pH 8. PDI solution (2 mL) was reduced to mostly monomeric PDI 2-by adding 2 µL of a 400 mM Na2S2O4 solution (in borate buffer) under constant stirring (i.e., 1000 rpm). Spontaneous oxidation in air (O2) leads to PDI •-and then to PDImon. Afterwards, PDImon grows via a cooperative polymerisation mechanism yielding colloidal PDIassem.

	Dynamic	light	scattering	(DLS).	The	intensity	autocorrelation	functions	𝑔 5 𝑞, 𝜏 ≡

  •-and PDI 2-every 60 s for 10 min. The relaxation dynamics were analysed by the inverse Laplace transformation 𝑔 (H) 𝜏 = 𝐻 𝛤 𝑒 MN% 𝑑𝛤

P Q

Jorge Leira-Iglesias 1 , Alessandra Tassoni 1, Takuji Adachi 1 , Michael Stich 2 and Thomas M. Hermans 1 * 1 University of Strasbourg, CNRS, ISIS UMR 7006, F-67000 Strasbourg, France. 2 Non-linearity and Complexity Research Group, Systems Analytics Research Institute, Engineering and Applied Science, Aston Triangle, Birmingham B4 7ET, United Kingdom. * e-mail: hermans@unistra.fr

Acknowledgements

This work was financially supported by the Region Alsace, University of Strasbourg Institute for Advanced Study (USIAS), LabEx grant 'Suproscill' (CSC-THE-17), and ERC-2017-STG 'Life-Cycle' (757910). We acknowledge Thomas Ebbesen, Cyriaque Genet, and Marcus Seidel for help with the NIR static light scattering.

Data availability. The data that support the plots within this paper and other findings of this study are available from the corresponding authors upon reasonable request.

Competing interests

The authors declare no competing interests.

Additional Information

Supplementary information is available in the online version of the paper.

Reprints and permission information is available online at www.nature.com/reprints. in order to prepare PDIassem seeds. Seeding experiments were performed by adding different amounts of seeds (i.e., 15, 10 and 5 % in v/v) to a 100 µM PDImon solution (final volume of the solution was 2 mL).

Stirring experiments were performed on a 100 µM PDImon solution (2 mL) at different stirring rates (i.e., 1000, 750 and 500 rpm). Kinetics experiments were performed on a JASCO V-670 spectrophotometer equipped with a Peltier system as a temperature controller. Spectra (i.e., from 400 to 700 nm) were recorded in a 1 cm quartz cuvette at 25 ºC.

Reduction kinetics. The reduction kinetics of PDI to PDI 2-was monitored by stopped-flow (SFM-3, Bio-Logic). The OD intensity was followed at 612 nm (i.e., characteristic band of PDI 2-). A 100 µM solution was prepared by dissolving PDI (1 mg, 0.60 µmol) in 50 mM borate buffer, pH 8. Afterwards, 9 mL of a 100 µM PDI solution were reduced with 15 µL of a 400 mM Na2S2O4 solution (in borate buffer) under constant stirring rate (1000 rpm). Immediately after oxidation, the freshly oxidized PDImon solution and 9 mL of a 40 mM Na2S2O4 solution were added into the syringes. Then, 80 μL of freshly oxidized PDImon solution and 80 µL of Na2S2O4 solution were quickly mixed. The reduction kinetics was followed for 90 min by doing data intervals of one minute. The data recording frequency was 0.2 ms for the first 2 s and 10 ms for one minute.

The evolution of the time constant t1 was obtained from fitting the next expression I = A•exp(t1/t). The evolution of time constant t2 was obtained from fitting the next expression y = A2+(A1-A2)/(1 + exp((t-t0)/t2)).

A values are constants.

Supramolecular oscillations.

Oscillations were tracked with a Basler CCD camera and a diode-array spectrophotometer (Analytikjena, Specord S600). PDImon (2.25 mL) solutions (i.e., 100, 75, 50 and 25 µM)

were measured under continuous influx of a 400 mM Na2S2O4 solution at constant stirring rate (i.e., 1000 rpm) in a well-ventilated box (constant oxygen supply and light) for 12 hours. Different flow rates (from 0.45 to 0.9 µL/min) were studied in order to map the state space. Red, green and blue channels were recorded at 10 frames per second using a home-built matlab interface. UV-Vis spectra were recorded from 400 to 900 nm in 2 seconds, spectra were taken every 10 seconds. Waste and buffer experiment were performed by adding 250 µL of waste or buffer after defined times.

Near-IR light scattering experiments. The scattering intensity measurements during oscillations were performed by using a home-built setup (cf. Supplementary Figure 9). A 905 nm laser line was obtained from a CW tunable Ti:Sapphire laser (Spectra-Physics, Model 3900S) pumped by a Millennia eV (Spectra-Physics, 15W diode-pumped solid state laser). This wavelength was selected because none of the three species (PDI, PDI •-and PDI Confocal measurements. Confocal micrographs were taken by using Zeiss LSM 710 confocal microscope system with 10 x magnification. The samples were excited by continuous-wave laser at 488 nm. The emission was measured from 500 nm to 700 nm using a spectral detector. Measurements were performed by taking 10 µL aliquots during oscillations. Measurements were performed on a 75 µM PDI solution.

Supramolecular traveling

Supplementary Section 1. UV-Vis and light scattering experiments

UV-Vis experiments showing the growth of PDImon to PDIassem (i.e., black to red spectra in Supplementary Fig. 1). 1 A new band appears at 528 nm having a sigmoidal time progression indicating that PDI assembles via a cooperative polymerization mechanism (see section 2 below for a more detailed analysis). UV-Vis spectra are shown as optical density OD since there is contribution of scattering as well as absorption. We assume that the optical density is directly proportional to the degree of aggregation and is experimentally determined as: 2 Neutral PDIassem structures are ~2 µm in size, whereas reduced PDI •-and PDI 2-are only ~100 nm at 100 µM (Supplementary Fig. 2). Dynamic and static light scattering show the size and scattering progression of the PDImon cooperative growth (Supplementary Fig. 3). 1). PDI 2-absorbs at 639 nm, which decreases the total scattered intensity. When PDI 2-disappears due to oxidation, a large jump in static light scattering intensity can be seen (t ~ 50 min). Therefore, visible static light scattering cannot be used quantitatively. The intensity autocorrelation functions for dynamic light scattering were fitted with a monoexponential decay function 𝑔 1 (𝑡) = 𝑒 -𝛤𝑡 .

Supplementary

Supplementary Section 2. Cooperative polymerization mechanism

PDImon assembles via a cooperative polymerization mechanism into PDIassem structures. 1 We determined the half times (i.e., the time needed for half of the PDI molecules to be assembled) at different concentrations and used them to discriminate between various available models. 3 A scaling factor  can be obtained from the plot of the half times vs. concentration (Supplementary Fig. 4). The scaling factor  is 0.485 ± 0.036 which indicates that PDI polymerization involves more processes than simple nucleation and elongation steps. In addition, the value of  suggests that fragmentation is also involved in the polymerization mechanism. 3 The data were analysed using three different analytical models (using the AmyloFit platform) 3 : nucleation-elongation, nucleation-elongation including fragmentation, and saturating elongation + fragmentation (see Supplementary Fig. 5 and Fig. 1c in the main text). The fitting improves when the fragmentation step is included into the model judged from the mean residual error (MRE), when compared to simple nucleation-elongation. The saturating elongation and fragmentation model gives the best fitting (i.e., lowest mean residual error, Supplementary Fig. 6) which indicates that the elongation involves multiple steps and thus, PDI polymerization is more complex than simple nucleationelongation. In addition, nucleus size 2 gives the best fitting for all models (Supplementary Fig. 6).

Supplementary

Supplementary Section 3. One redox cycle

A colour CCD camera permits to track separately red, blue and green colour channels of a PDI solution. Combined with a fast diode-array spectrophotometer, it can be used to determine the relative concentration of the different species present in solution. Prior to reducing the system, the starting values of red and blue channel and the diode-array (i.e., black line in the inset, Supplementary Fig. 8) confirm the presence of as prepared PDI assemblies. The intensity of the red channel drops quickly (i.e., intensity goes from ~80 to ~40) upon addition of reductant Na2S2O4. The diode-array (i.e., purple dash-dot line in the inset, Supplementary Figure 8) confirms the formation of PDI 2-. PDImon is reached after spontaneous oxidation in the air. The blue channel intensity increases and the red channel decreases indicating the transient formation of PDI •-(the spectrum shows the characteristic bands of PDI •-at 727 and 813 nm, blue dashed spectrum in the inset of Supplementary Fig. 8). Afterwards, the red channel intensity quickly increases and the blue channel intensity decreases showing the presence of PDImon (pink dotted spectrum in the inset). In addition, a slow sigmoidal increase in both channels indicates the cooperative growth of PDImon to PDIassem. Diode-array measurements (performed simultaneously) confirmed the presence of PDIassem (green dotted spectrum in the inset). In short, the colour camera and diode-array UV-Vis detector permit to track all the species present in a full redox cycle PDI  PDI 2- PDI •- PDImon  PDIassem. Supplementary Figure 8. One redox cycle. The system was measured in a semi-batch reactor at 1000 rpm with a CCD camera and diode-array UV-Vis detector. 2.25 mL of a 25 M PDI borate buffer solution is reduced to PDI 2-upon the addition of 2 L of 400 mM Na2S2O4 solution. Afterwards, PDI 2-was oxidized back to PDImon via PDI •-formation. PDImon grows via a cooperative polymerization mechanism leading to PDIassem. The inset shows the spectra of all different species present in solution along 1 redox cycle (i.e. PDI  PDI 2- PDI •- PDImon  PDIassem). Supplementary Figure 9. Scheme of the near-infra red light scattering setup using a 905 nm laser. The scattering intensity was recorded using a home-built setup (photo shown on the right). This wavelength was selected because none of the three species (PDI, PDI •-or PDI 2-) have light absorption at 905 nm (cf. Supplementary Figure 8). Supplementary Figure 10. Near-infra red light scattering intensity and colour tracking of PDI species during one redox cycle. The system was measured in a semi-batch reactor at 1000 rpm using a 905 nm laser (cf. Supplementary Figure 9) and a camera. PDI (i at t = 0 min, 2.25 mL of a 25 M solution) is reduced to PDI 2-upon the addition of the reductant (ii, t = 1.2 min) inducing a decrease in the scattering intensity (black curve, left axis) and in the red and blue channel intensity (red and blue curves on the right axis, respectively). Afterwards, PDI 2-was oxidized back to PDImon (iv, t = 4 min) via PDI •-formation (iii, t = 2.75 min), while reaching a minimum in the scattering intensity and a maximum in the blue channel. PDImon grows via a cooperative polymerization mechanism leading to PDIassem (v, t = 9 min) where an increase of the scattering intensity and the red/blue channel can be observed. Supplementary Figure 13. Confocal micrographs during supramolecular oscillations. Aliquots from a 75 M PDI solution during oscillations (followed with a CCD colour camera, black line shows red channel intensity) were measured using a Zeiss LSM 710 confocal microscopy (see methods). Red emissive assemblies can be observed in a freshly prepared PDI solution (i, t = 0 min). PDI 2-is formed after addition of Na2S2O4 inducing complete disassembly at the resolution of the microscope (ii, t = 2 min). Oxidation leads to PDImon which grows via cooperative polymerization. Red emissive assemblies can be observed when PDIassem are present in solution (iii, t = 10 min). The assemblies mostly disappear during oscillations (iv, t = 13 min, v, t = 23.3 min, and vii, t = 35.6 min). Micrograph viii (t = 120 min) shows that the number of PDIassem stays consistently high in the damped region (after t ~60 min). In general, only during the first 3-5 large scale oscillations do all of the PDIassem disappear. Supplementary Figure 14. Waste and buffer addition experiments during supramolecular oscillations. 2.25 mL of a 100 M PDI borate buffer solution was reduced to PDI 2-by adding 2 L of a 400 mM Na2S2O4 solution. Constant inflow of reductant (0.7 L/min) was set once PDImon was in solution. a, 250 L of a 400 mM old dithionate solution (prepared the day before) was added after 250min, b, 250 L of buffer solution was added after 225 min. These experiments show that neither waste accumulation nor volume changes significantly change the oscillations.

Supplementary Section 4. Supramolecular oscillator

Supplementary Section 5. Supramolecular oscillator model

The model can be derived using basic nucleation-elongation-fragmentation kinetics. 4 Continuation analysis and simulations of the model were performed with MatCont (downloadable from https://sourceforge.net/projects/matcont/). Simulations were done with the ODE45 routine provided by MatCont 5.1 within Matlab 8.4.0. The master equation for an ensemble of polymers is given by the time evolution of the concentrations 𝑓 (𝑡, 𝑗), where j indicates the length of the polymer and where we suppress the time dependence in the notation in the following:

Depolymerisation is assumed to occur only in the reduction step to the R type of monomers (vs monomers that are oxidised O, which can polymerize). No fusion (inverse of fragmentation) or secondary nucleation is considered here. The condition 𝑓(𝑗) = 0 for all 𝑗 < 𝑛 𝑐 , where 𝑛 𝑐 ≥ 2 is the critical nucleus size for the filament growth. From Eq. ( 1) we derive the kinetic equations for the number P and mass concentrations M:

By taking the sum over 𝑗 on both sides of Eq. (1). We obtain

where the contribution 𝑘 𝑟𝑒𝑑 𝑓(𝑛 𝑐 ) has been neglected to obtain a closed expression. The contribution of the dissociation of the nucleus to the overall dynamics is assumed to be small. The mathematical structure of the kinetic equations depends on the value of the critical nucleus size 𝑛 𝑐 . For simplicity, we fix 𝑛 𝑐 = 2 for the remainder of this article (simulations not displayed here show that oscillations can also be found for 𝑛 𝑐 = 3,4) and we obtain:

The reduced type of monomers R obeys the following mass-action expression

Supplementary video 2. Propagating front of supramolecular assemblies. A freshly oxidized

PDImon solution (1.5 mL of a 100 M PDI solution) was immediately injected into the 3D printed chip (50 x 25 x 1 mm). A propagating front in adjacent volumes was observed immediately after addition of PDIassem seeds (30 L of a 1h old PDImon solution) from one side of the chip. Images were acquired using a stereoscope (Nikon SMZ7457) equipped with a CCD camera, frames were recorded every 10 seconds for 60 min. The data shown in Fig. 4b,c corresponds to the video.

Supplementary video 3. The propagating front induces large scale in-plane convection.

Large-scale in plane convection was observed in a propagating front experiment. Images were acquired using a ZEISS LSM 710 confocal microscope, frames were recorded every 2 seconds for 30 min. The arrows indicate the direction of the flow and the length is proportional to the speed. The direction and velocity of the flow was tracked using PIVlab tool from Matlab.

Supplementary video 4. Control experiment. Seeded front vs. non-seeded region. A 3D printed chip (45 x 30 mm) was used, which was covered by mineral oil. Buffer solution was added on the left and PDIassem seeds on the right of the chip into a freshly oxidized PDImon solution (100 M, see methods for preparation). Images were acquired using a stereoscope (Nikon SMZ7457) equipped with a CCD camera, frames were recorded every 10 seconds for 50 min.

Supplementary video 5. An outward propagating oxidation front induces flow-alignment of

PDIassem. A 3D printed chip (45 x 30 mm) was used, which was covered by mineral oil. PDI solution (1.5 mL, filling 3 mm height in the chip) was reduced to PDI 2-by adding 4 L of 400 mM Na2S2O4 solution. PDI 2-solution was poured into the chip and carefully covered with mineral oil. An outward moving propagating oxidation front and convection through the entire cell was observed. In addition, PDIassem structures aligned along the flow lines. Images were acquired using a stereoscope (Nikon SMZ7457) equipped with a CCD camera, frames were recorded every 10 seconds for 100 min. The data shown in Fig. 4d corresponds to the video.

Supplementary References


Arif Ahmed

Guillaume Pierre

Docker Image Sharing in Distributed Fog Infrastructures

Keywords: Fog computing, Docker, containers

Fog computing platforms offer virtualized resources located in the vicinity of their end users. Their broad geographical distribution force them to split physical resources in large numbers of relatively weak machines. The limited available disk space per fog node however creates problems for Docker-based systems which locally cache a copy of every container image they execute: first, caches may fill very quickly, whereas standard Docker never automatically evicts any image from its cache. This motivates us to implement automatic cache replacement in Docker. Second, splitting cache space in multiple disjoint partitions negatively impacts the hit rates. This motivates us to propose allowing multiple co-located Docker servers to share their caches. Our trace-based evaluations show that the proposed design achieves significant cache hit improvements, leading to reductions of average container deployment times between 37% and 78% depending on the scenarios.

I. INTRODUCTION

Fog computing aims to extend traditional cloud data centers with additional compute, storage and networking resources located at the edge of the Internet. By bringing the server-side applications in the immediate vicinity of their end users, fog computing promises to deliver very low end-to-end network latencies for highly-interactive applications such as augmented reality gaming, and to drastically reduce the usage of longdistance data transfers for applications such as IoT analytics where large volumes of transient data can be processed locally.

Fog computing architectures are fundamentally different from traditional clouds: to maintain proximity with a large number of users, fog resources must be dispersed across a large geographical area such as a city or an entire country. As a consequence, fog resources are often organized in a large number of Points-of-Presence (PoPs) dispersed across the covered area. Each PoP may not be composed of datacentergrade servers but rather of a small number of weak machines such as single-board computers connected with each other and with the rest of the Internet using commodity networks [START_REF] Basford | Performance analysis of single board computer clusters[END_REF], [START_REF] Van Kempen | MEC-ConPaaS: An experimental single-board based mobile edge cloud[END_REF]. Fog platforms typically automate application deployment across the different PoPs using container orchestration systems such as Docker and Kubernetes [START_REF] Hoque | Towards container orchestration in fog computing infrastructures[END_REF], [START_REF] Nardelli | Multi-level elastic deployment of containerized applications in geo-distributed environments[END_REF].

Fog users are usually mobile, which implies that the applications running in the fog may need to be frequently redeployed in different PoPs to maintain proximity, low latency, and reduce long-distance traffic [START_REF] Bittencourt | Mobility-aware application scheduling in Fog computing[END_REF]. However, software deployment can be painfully slow when the fog node needs to download a full container image of the deployed application before starting the container itself [START_REF] Ahmed | Docker container deployment in fog computing infrastructures[END_REF]. Having their fog-hosted application freeze frequently while new containers get started would clearly be a source of frustration for most end users. Reducing the probability of such image cache misses, and the performance impact of their occurrence when they cannot be avoided, is therefore of crucial importance for providing the end users with a satisfactory quality of experience.

Docker was originally designed for powerful server machines [START_REF] Ahmed | Docker container deployment in fog computing infrastructures[END_REF]. It therefore keeps a copy of every container image in each server's local cache so it does not need to be downloaded again in case the same image is deployed in the future. Docker also never removes content from its caches unless explicitly requested by their user to do so [START_REF] Inc | Prune unused Docker objects[END_REF]. Although this strategy makes perfect sense in powerful server machines where disk space is rarely an issue, it creates important storage capacity problems in an environment composed of many weak machines with limited storage space and where containers are frequently started and stopped. If the working set of frequently-deployed images is larger than the storage capacity of a fog computing node, then the same image may need to be repeatedly downloaded, utilized and deleted, creating unnecessary delays and network transfers when re-deploying a container after its image had to be removed from the local node. Another effect of keeping separate image caches in each node is that these caches are likely to contain highly redundant content due to the fact that the same popular images may have been deployed multiple times in different nodes.

We propose to transform these issues in opportunities by allowing multiple fog nodes within a PoP to share the content of their Docker image caches. Instead of using the fog nodes' storage capacity as a set of limited and isolated caches, we propose to aggregate the storage capacity of clusters of colocated fog nodes using a distributed file system. The end result is a single sizable Docker image cache per PoP where large numbers of images can be stored, thereby significantly reducing the probability that images need to be downloaded over a long-distance network upon container deployment.

Our contributions in this paper can be unfolded in four parts: [START_REF] Basford | Performance analysis of single board computer clusters[END_REF] we analyze a large Docker registry workload and demonstrate the potential for deployment time improvements of Docker image sharing; (2) we survey distributed file systems (which were typically designed for high-performance computing environments) and discuss their suitability in fog computing environments; (3) we present the design of our Docker image sharing framework which supports image cache sharing among multiple co-located fog nodes; and finally (4) our tracebased evaluations show that sharing caches among multiple fog nodes delivers significant cache hit rate improvements, and leads to reductions of the average container deployment times between 37% and 78% depending on the scenario.

The paper is organized as follow. Section II presents the background and related work. Section III analyses the workload of large docker registries and demonstrates the potential of image sharing in fog infrastructures. Then, Section IV presents our cooperative Docker framework and Section V evaluates its performance. Finally Section VI concludes.

II. BACKGROUND AND RELATED WORK

A. Background 1) Fog computing architectures: A typical distributed fog architecture is depicted in Figure 1. In fog computing context, the servers which belong to the same PoP may easily be connected to each other using a fast local-area network. They can therefore be configured to use a shared file system to aggregate their respective storage capacity. On the other hand, the heterogeneous and potentially slow nature of connections between PoPs means that sharing storage between PoPs is unlikely to deliver reasonable performance.

2) Docker: Docker is an open source tool to manage applications inside containers [START_REF]Docker: Build, Ship, and Run Any App, Anywhere[END_REF]. Applications are packaged in the form of an image which usually contains multiple layers. Every layer is a full file system with application packages, libraries, binaries, configuration files, etc. Layers are stacked over each other such that every new layer may add, subtract or modify files present in the lower layers. Layers remain physically separated on disk, but a virtual file system such as AUFS and OverlayFS exposes a single "merged" file system view to the container applications [START_REF] Wikipedia | aufs[END_REF]. Docker encourages layer reusability so different images often share the same bottomlevel layers and differ only by their top-level layers [START_REF] Harter | Slacker: Fast distribution with lazy Docker containers[END_REF].

In Docker, container image layers are always read-only. To allow the running containers to modify their file system, a final read-write layer is dynamically created and stacked on top of the other layers at the starting time of a container. All file system modifications issued within the container are stored in this top-level layer using a copy-on-write (CoW) policy.

When it is instructed to deploy a container, if the requested image is not present in the cache, Docker first downloads manifest of the image from the central registry. This manifest contains the list of layers identified by a hash of their content. Docker then downloads the necessary layers which are not already present locally, and finally can start the container itself.

Figure 2 shows how Docker stores the layers as well as metadata about images and layers in persistent files inside docker storage directory. (e.g., /var/lib/docker). The metadata has three basic structures: (1) the reference store contains the manifests of all the images present in the local image cache; (2) the layer store contains the list of all locallyavailable layers, identified by their sha256 ID as well as metadata such as the layer's size, parent layer etc. and finally (3) the image store contains image configuration information such as the CPU architecture it relies on, the default exposed ports, attached volumes, and image history with a list of layers identified by their sha256 ID. As the metadata information are frequently accessed, Docker keeps a copy of the metadata files in memory to speed-up container operations.

The standard mechanism to share Docker images between servers is based on a centralized registry where all available images and layers are stored [START_REF] Inc | Docker hub[END_REF]. A registry supports two main operations: docker push and docker pull. A push operation uploads a new set of image layers and their manifest file to the registry server, whereas a pull downloads a container image from the registry to the docker daemon.

Although this mechanism provides image sharing, in a fog computing environment it presents three drawbacks. Firstly, downloading an image from the repository must therefore be considered as an expensive operation in terms of download time as well as quantity of data to be transferred long-distance. Secondly, the total size of all downloaded layers would quickly exceed the storage capacity of a resource-limited fog node. Finally, the content of different server caches is likely to be highly redundant with the same highly popular images.

We aim to resolve these issues by allowing multiple colocated fog nodes to share their Docker cache with each other. This provides every node with a larger cache than it could locally support, and thereby increases the probability upon container launch that the necessary image layers have been previously downloaded by one of the servers of the PoP.

B. Related work

Container-based virtualization has been widely adopted to handle application deployment in Fog computing infrastructures [START_REF] Hoque | Towards container orchestration in fog computing infrastructures[END_REF], [START_REF] Nardelli | Multi-level elastic deployment of containerized applications in geo-distributed environments[END_REF]. These platforms are often built using single-board computers such as Raspberry Pis which offer excellent performance/cost/energy ratios and are well-suited to scenarios where the device's physical size and energy consumption are important enablers for actual deployment [START_REF] Van Kempen | MEC-ConPaaS: An experimental single-board based mobile edge cloud[END_REF], [START_REF] Hajji | Understanding the performance of low power Raspberry Pi cloud for big data[END_REF]. However, the performance of Docker in such environments is often poor, which justifies the need for improved solutions.

One option to improve the performance of container orchestration systems is to redesign the image registry. CoMICon proposes a distributed registry which distributes the image layers across multiple nodes to speed-up deployment time and increase availability [START_REF] Nathan | CoMICon: A co-operative management system for Docker container images[END_REF]. Similarly, Nitro uses deduplication and network-aware data transfer strategies to reduce the transfer time of images over wide-area networks [START_REF] Darrous | Nitro: Network-aware virtual machine image management in geo-distributed clouds[END_REF]. These systems aim to reduce the performance impact of a Docker cache miss, but they do not change the cache hit rate. They are therefore complementary to our approach which aims at improving the cache hit rate thanks to shared image caches.

Docker-pi reorganizes the download and extraction of image layers in the Docker server to better exploit hardwarelevel parallelism [START_REF] Ahmed | Docker container deployment in fog computing infrastructures[END_REF]. It reduces the performance impact of a Docker cache miss, but it does not influence the frequency of occurrence of these cache misses. In contrast, we rather focus on the management of the Docker cache and its sharing between multiple Docker servers.

We are not the first ones to propose sharing the Docker images across multiple servers. Slacker proposes to store the Docker images in a shared NFS file server [START_REF] Harter | Slacker: Fast distribution with lazy Docker containers[END_REF]. With the use of a specialized storage driver in every Docker server, only the relevant parts of each image need to be downloaded from the NFS server to the Docker server upon every container start operation. However, this assumes that all relevant images are already stored in the NFS file server. This organization would be extremely difficult to manage in a fog computing server as it would require sufficient capacity in every PoP to store the entire set of images that may potentially need to be deployed there one day. Also, Slacker requires every image to be flattened into a single layer, which deviates from the Docker philosophy of image layer reusability.

The closest work to ours is Wharf, which proposes to share the caches of multiple Docker servers in a distributed file system to reduce storage utilization and the number of redundant image retrievals [START_REF] Zheng | Wharf: Sharing docker images in a distributed file system[END_REF]. This work differs from ours in a number of ways. First, it focuses on powerful server clusters where network bandwidth and data storage are cheap. In consequence it mostly discusses container startup times and does not address the issues related to limited cache size in fog computing servers. It also relies on the ability of Docker servers to download multiple image layers simultaneously, which was shown to perform poorly in the context of singleboard fog servers [START_REF] Ahmed | Docker container deployment in fog computing infrastructures[END_REF]. On the other hand, our study focuses on sharing Docker images in Fog infrastructures that are made of large numbers of strongly resource-constrained nodes.

III. POTENTIAL BENEFITS OF CACHE SHARING

To evaluate the potential benefits of sharing Docker caches among fog servers, and in the absence of publicly-available fog computing workloads, we analyze a container deployment workload in a cloud computing context. As previously discussed, we expect fog computing platforms to experience more frequent re-deployments of the same images than in a normal cloud platform. The results presented here therefore represent a worst-case analysis in terms of cache hit rates.

A. Simulation setup

We simulate the behavior of Docker image caches under a registry workload composed of a collection of HTTP-logs generated from 36 IBM Docker registry servers [START_REF] Anwar | Improving Docker registry design based on production workload analysis[END_REF]. These registries are classified in 7 Availability Zones (AZ) based on their geographical location and the type of workload they serve. Four AZs (fra, syd, dal and lon) are dedicated to serve production workloads: fra and syd are relatively new and have fairly small workloads (86GB and 92GB respectively) whereas dal and lon serve a much larger working set of images (1718 and 6789 GB respectively). Two AZs (prs and stg) are used for staging (pre-production) purpose, both are having sizable workload (213GB and 1181GB respectively) and finally dev is dedicated for development purpose (283GB).

Each entry in this trace contains the signature of an HTTP request made by a Docker server to the registry for operations such as docker pull and docker push. The signature provides information about the request such as name of the image, the type of request, and timestamp. However, the trace does not contain sufficient information to reliably detect container deployments which resulted in a cache hit in the Docker servers. Due to the fact that Docker never deletes cached image layers unless explicitly requested to do so [START_REF] Inc | Prune unused Docker objects[END_REF], we can see this trace as the residual cache miss traffic from a large set of isolated, infinite-sized image caches. Any temporal locality found in this trace therefore highlights an opportunity for cache sharing between multiple servers.

The simulator replays the container deployment logs and reproduces the behavior of a Docker image cache: when deploying a new container, the server checks if the image is available in the cache storage and, if found, immediately starts the container. Otherwise, it downloads the missing layer(s) in the image cache before starting the container. simulation we use the well-known Least-Recently Used (LRU) policy to decide which layer should be removed when the cache does not have sufficient available capacity to store a newly-requested image.

B. Cache hit ratio analysis

We can see in Figure 3(a) that, even with very small shared cache sizes, several AZs exhibit significant cache hit ratios. Most of the AZs (except prs and dev AZs) exhibit in-between 31% and 89% hit rates with a shared cache size of 32GB. This indicates that a small number of highly popular container images is repeatedly deployed in different servers from the same zone. For these scenarios, sharing even an extremely small cache delivers significant performance improvement compared with no sharing. On the other hand, prs and dev observe almost no cache hits with a very small cache size. This is probably due to the fact that, during development and pre-staging phases, each container image is deployed only a small number of times before either being replaced with an updated version (in case a bug was detected) or being moved to staging or production.

Figure 3(b) extends these curves until cache sizes of several TBs. When looking at slightly larger shared cache sizes, we observe that shared cache sizes in the order of a few hundred GBs are usually sufficient to exploit the temporal locality and reach hit rates of 50-95%. We can observe that such cache sizes do not deliver additional benefits compared to much smaller sizes. The only exception is dal here every cache size increase (up to the size of its total working set) delivers performance improvement.

We conclude the cache sharing between multiple Docker servers would clearly deliver significant benefits in almost all considered scenarios, even with limited size for the shared caches. This is a good news for us considering that in a fog computing platform each PoP would probably have limited storage capacity. The only exceptions where the benefits of sharing caches are limited derive from scenarios where each image is deployed only a couple of times (e.g., during the development phase) or the overall image working set if extremely large.

IV. SYSTEM DESIGN

The general framework for image cache sharing among a group of Docker servers is depicted in Figure 4. In this design, multiple Docker servers use a shared file system to store the (immutable) image metadata and layer files. On the other hand, each Docker server keeps in their local storage the containers' read-write layers, plugins, configuration files etc. However, realizing this design forces us to address a number of difficult challenges which are addressed in the following sub-sections.

A. Choice of distributed file system

A distributed file system (DFS) is defined as any file system that allows access to files from multiple hosts sharing via a computer network [START_REF] Wikipedia | Comparison of Distributed File Systems[END_REF]. Distributed file systems were mostly designed for high-performance computing environments where the servers are computationally powerful and connected by a high-speed network. In contrast, we aim to use them in severely resource-constrained fog computing environments. Our choice of DFS is therefore largely guided by an analysis of the resource requirements of different DFS.

The design of the Metadata Server (MDS) is an important differentiating factor between the many available distributed file systems. Depending on the DFS implementations the DFS may be centralized in a single machine or decentralized. In the centralized case, the machine which holds the MDS may incur a significant extra load and potentially become a performance bottleneck. A distributed MDS would share this load among the available servers and arguably exhibit better scalability and fault-tolerance properties.

Distributed file systems also differ in the storage medium used to keep the metadata during its operation. Some file systems load the metadata in memory (which promises fast metadata access) while others keep them on disk. In a resourcelimited environment such as a fog computing PoP, memory must be considered as a scarce resource. Although keeping metadata in memory may remain affordable if the number of shared files was small, any container image would contain a large number of (usually small) files, and therefore require significant memory resources to maintain their metadata.

Table I presents a comparison of six popular file systems: HDFS [START_REF]Apache Hadoop[END_REF], CephFS [START_REF] Hat | Ceph[END_REF], MooseFS [START_REF]MooseFS distributed file system[END_REF], GlusterFS [START_REF] Hat | Gluster | Storage for your Cloud[END_REF], iRods [START_REF]iRODS[END_REF] and Lustre [START_REF] Opensfs | Lustre[END_REF] based on information found on the respective file systems' web sites as well as a survey on distributed file systems [START_REF] Depardon | Analysis of six distributed file systems[END_REF]. CephFS and GlusterFS stand out because they rely on a distributed metadata server.

CephFS is a fully scalable distributed file system. A CephFS cluster must include one monitor (which maintains a master copy of the cluster map), one manager daemon (in charge of monitoring the file system cluster), at least three Object Storage Daemons (OSD) and at least one MetaData Server (MDS). The monitor and manager are lightweight processes which can easily run in a specific node from a fog computing PoP. The OSDs are in charge of storing all objects from the file system. Finally, the metadata servers share the metadata workload with one another. Since CephFS stores metadata in disk instead of main memory, it can easily be deployed in resource-constrained compute nodes. GlusterFS is a fully decentralized file system which does make use of any metadata server. Instead, it uses an Elastic Hash Algorithm to deterministically choose in which location each file must be stored [START_REF] Gluster | Cloud storage for the modern data center -an introduction to gluster architecture[END_REF]. Similar to CephFS, GlusterFS is sufficiently lightweight (especially thanks to its absence of metadata servers) to be deployed in a fog computing PoP.

CephFS and GlusterFS are the best two contenders for being used in a fog computing scenario. We experimentally compare their performance in Section V-A.

B. Sharing Docker images

Docker uses a single local directory (e.g., /var/lib/ docker) to keep all cached data such as image manifests, layer metadata, and the layers themselves(see Figure 2). To implement image sharing between multiple docker servers it is important to distinguish the cached content which should be shared from the one which should not.

Shareable content consists of image layers data and the metadata files. To allow multiple Docker servers to access the same layers we mount the distributed file system over the directories which contain these files. Non-shareable content consists of other content such as container read-write layers, server-specific configurations and plugins.Although Docker stores container read-write layers in the same directory as the read-only layers, we configured Docker to create the read-write layers in a separate directory out of the mounted distributed file system. Sharing the image metadata and layer files across multiple Docker servers is necessary for our approach, it is by no means sufficient. Docker keeps a copy of the cache metadata in memory, and it does not systematically check the consistency of the in-memory data with the persistent ones before using them. We therefore need to design additional mechanisms to maintain these data consistent, as we discuss next.

C. Consistency maintenance of in-memory metadata

Sharing Docker images through a distributed file system is not sufficient to guarantee the in-memory metadata of the image cache remains consistent with the shared content over time. For instance, when a Docker server executes an image operation such as adding an image in the shared image cache, the updates in the image cache are reflected in the shared file system and the in-memory metadata present in the concerned machine itself, but they are not propagated to the other Docker servers. As a result, in case another Docker server wants to deploy the same image, it will not find it and download it unnecessarily.

To maintain the consistency of the in-memory metadata across all servers within a PoP, we use the popular Redis system and create a publish-subscribe channel to disseminate any update to the in-memory metadata [START_REF]Redis pub/sub[END_REF]. When one server incurs an update in its in-memory metadata after adding or removing an image, it sends a message in this dissemination channel. When a server receives this message from the above channel, it discards its in-memory metadata and re-reads the image metadata from the shared file system. With this simple mechanism, the in-memory metadata remain consistent across all the servers of the PoP.

D. Preventing concurrent deployments of the same image

In a Docker cluster it is frequent to start multiple instances of the same image simultaneously, for instance to aggregate the processing capacity of multiple servers. In our case, if multiple servers from the same PoP attempted to concurrently deploy the same image, they may all notice that the image is not present in cache and redundantly download the same image. We must therefore allow multiple servers to coordinate with each other and download each image layer only once.

We propose to let a single Docker server downloads all the required layers. Other servers simply block when they discover the image they want to deploy is being downloaded, and resume the normal deployment process after the image download has completed. To allow each Docker server to reliably detect if an image is already being downloaded by another server we store locks in the Redis key-value store: each image is controlled by a separate lock identified by the sha256 ID of the image.

Figure 5 illustrates the updated workflow of the docker pull operation. When pulling an image, the Docker server first checks in the Redis database whether a lock for the same image has been created by another server. If the image is not already being downloaded, the server creates a lock in the Redis database under the ID of the image, then pulls the image normally. When the download is completed, it removes the lock and sends a notification to a Redis channel with the same ID. The lock test and set operations are executed within a transaction [START_REF]Redis transactions[END_REF] to ensure atomicity and avoid race conditions.

If a server discovers that the image it needs to pull is already being downloaded by another server, it simply subscribes to the Redis channel (again within a transaction) and waits for a notification that the image download has completed. It can then Input: S = size of the new image, available_space = available capacity of the shared cache, {I} = list of unused images, i = image to be deleted 1 while (available_space < S) do

{ 2 i = least_recently_used(I) 3 docker rmi i 4 Redis_Publish(Update_Metadata) 5 {I} = {I} -i 6 }
update its in-memory metadata as discussed in the previous section and terminate the deployment normally.

E. Cache replacement

In a fog computing platform where we expect a large variety of applications to be deployed over time, it is important to ensure that only the most relevant container images are kept in cache, and that the less frequently-deployed ones get discarded to save space. This significantly deviates from the standard Docker policy of never removing any image automatically and of rather relying on human administrators to remove unnecessary images manually [START_REF] Inc | Prune unused Docker objects[END_REF].

To automatically handle the removal of unused container images, we implemented a cache replacement mechanism within Docker [START_REF] Wikipedia | Cache replacement policies[END_REF]. This mechanism get triggered when the available shared disk space is not sufficient to store a new image which is being downloaded. While deploying an image, if the storage capacity is insufficient then Docker pauses the deployment process and calls the Image Replacement Interface to remove one or more unused images.

It would obviously be incorrect to remove an image from the cache while it is being used by any of the PoP's Docker servers. To inform other servers about the images they are currently using, Docker servers register the image name and current number of instances in the Redis database. Algorithm 1 depicts the replacement mechanism. When the available storage capacity is too small to store a new image, the Docker server builds a list of the currently unused images and the date they were last accessed. We use the popular Least Recently Used policy which evicts the image that was unused for the longest period of time. The in-memory metadata of all Docker servers is then updated using the same mechanism as discussed in Section IV-C. This removal process is repeated until the system has sufficient storage to store the new image.

V. EVALUATION We evaluate our system using micro-and macrobenchmarks. Micro-benchmarks show the performance of a single container deployment using various file system configurations, whereas macro-benchmarks show the system's performance under an actual scenario with multiple deployments.

We use a set of 10 VMs representing the nodes of a PoP. These VMs are created using KVM on a Dell PowerEdge R430 server with two Intel Xeon E5-2620 v4 processors running at 2.10GHz, with 8 hyperthreaded cores each, and 64 GB of RAM. Each VM has 2 vCPUs, 1 GB RAM and 32 GB disk and runs Ubuntu 18.04 server with Linux kernel 4.15.0-47-generic. We based ourselves on Docker-pi 18.04, which already contains a number of optimizations designed for Fog computing infrastructures [START_REF] Ahmed | Docker container deployment in fog computing infrastructures[END_REF]. To avoid interferences from the long-distance network or the Docker hub server, we deployed a private Docker registry within the testbed.

A. Micro-benchmarks

We first evaluate the performance of our system with different distributed file system configurations. Table II depicts the three experimental scenarios used in this study. Scenarios 1 and 2 rely on CephFS (Ceph version 13.2.4) with either its user-level FUSE client [START_REF] Kerrisk | fuse(4) -linux manual page[END_REF] of the kernel-based one. Conversely, Scenario 3 relies on Gluster (Glusterfs 4.0.2) with its native FUSE client (GlusterFS does not provide a kernellevel client). All configurations are using three nodes and a replication degree of 1, in order to maximize file system write performance while downloading a new image.

1) Deployment time: We deploy the popular Ubuntu:latest image using either regular Docker with no shared image cache, or one of the three shared cache scenarios listed in Table II. All machines are kept otherwise idle while deploying the image.

Table III compares the container's deployment time with shared and non-shared storage, measured from the time the docker run command is issued to the moment the container has started. In the case of a cache miss we observe that the configuration with no cache sharing requires 5.2 s to deploy the image, whereas in the distributed file system cases deployment times range from 7.01 s to 32.1 s. This may be as writing the image on a distributed file system creates additional tasks for the Docker server compared to simply writing it on the local drive. We however notice large performance variations depending on the client being used to access the distributed file system: although the kernel-based Ceph driver delivers similar performance to a native local drive, the FUSE-based clients suffer from considerable overhead.

In the case of a cache hit, results are similar although the difference between kernel-based and FUSE clients is less important. This is due to the fact that it is not necessary to read the entire image to start a container so the impact of file system performance is lower compared to the other operations that must be conveyed upon container creation.

2) Resource utilization: We instrumented the testbed machines to trace the overall deployment time as well as the node's resource consumption, especially network throughput which is measured using the nethogs utility [START_REF] Engelen | raboof/nethogs: Linux 'net top' tool[END_REF].

Figures 6(a) and 6(b) depict the download and upload bandwidth of the Docker server machine while the container image is being deployed upon a cache miss. For obvious reasons the native Docker server does not upload any significant amount of data during the image pull operation, whereas the distributed file systems scenarios see both download (from the image registry to the Docker server) and upload (from the Docker server to the other nodes which participate in the distributed file system). We can also see that the Ceph+kernel configuration can upload data to the distributed file server at a similar rate as the image is being fetched from the registry, whereas the FUSE-based Ceph and Gluster configurations achieve a much lower transfer rate. This is probably due to the fact that FUSE works in user space, which generate large numbers of context switches upon any I/O operation.

Figure 6(c) and 6(d) respectively show the download and upload bandwidth of the Docker server while a container is being deployed from an already cached image. The upload speed is negligible because no content needs to be written to disk. We however observe some download traffic which corresponds to the read operation from the distributed file system. We observe the same phenomenon as in the cache miss scenario, where Ceph+kernel is the only configuration capable of reaching significant throughput in this operation.

We conclude that the Ceph+kernel configuration is the only one which can deliver deployment performance similar to that of the native Docker, both in the cache hit and cache miss scenarios. Based on these findings, in the next sections we focus on the CephFS+kernel configuration only.

B. Macro-benchmarks

The purpose of sharing Docker image caches is to allow multiple resource-limited PoP servers to increase their cache hit rate by gaining access to a large image cache with a good probability that an image is already present at the time it must be deployed. We therefore evaluate the respective performance of non-shared and shared caches under the same container deployment workload as discussed in Section III.

We created a PoP composed of 5 machines with the same configuration as in the previous sections. When using the shared cache configuration, every machine from the PoP dedicates 10 GB of its disk space to the Ceph distributed file system, and keeps the rest for its local usage. Ceph reserves 1.5 GB space of each disk to store the underlying file system journal, so the total shared storage capacity is 43 GB.

We replayed two traces of container deployments: • The fra availability zone has a total working set of 31 GB.

It is too large to fit in a single local cache but it can entirely fit in the shared cache whose aggregate capacity is 43 GB. • The dal availability zone has a total working set of 54 GB.

In this case, even the shared image cache is too small to store all downloaded images. It therefore applies the cache replacement mechanisms described in Section IV-E to keep only the most recently used images. As discussed in Section III-B, this workload has limited temporal locality properties and is expected to deliver modest cache hit rates. Image deployments are issued to the different nodes of the PoP following a round-robin policy. Since we are only interested in the container deployment times, we stop every container immediately after the end of its deployment.

Figure 7(a) depicts the evolution of the cache hit ratio during the execution of the two traces, with and without shared cache, binned by groups of 50 consecutive deployments. For both workloads, the shared cache delivers a much greater hit rate than the non-shared caches. More precisely, during the first few hundred deployments, the shared cache's hit rate grows much faster than the non-shared caches. This is explained by the fact that the most popular images must be downloaded only once in the case of a shared cache whereas in the nonshared case the same image must be downloaded separately by multiple fog nodes. In the end of the curve we see the effect of increasing the cache size available to any Docker server: the cache hit rate of the fra zone stabilizes around 82% using the shared cache whereas the non-shared caches deliver only 52% hit rate. In the case of the dal zone the cache hit rates are more modest (as expected from the study in Section III-B) but there as well the shared cache delivers a significant cache hit rate improvement compared to non-shared caches.

Figures 7(b) and 7(c) compare the average and standard deviation of deployment times of Fra and Dal AZs during the same experiment. After deploying the first dozen deployments, in the fra trace the average shared-cache deployment time is approximately 4 s whereas the non-shared cache observes deployment times close to 6 s. This difference persists through the entire workload: the mean deployment time of shared caches stabilizes to a value 78% lower than non-shared caches. In the case of the dal trace we observe a similar behavior.

The lower cache hit rates of this difficult workload imply that the average deployment times remain above 2 s. However, here as well the shared cache delivers significantly lower deployment times than the non-shared scenario (37% reduction of the stabilized mean response time). We also observe smaller standard deviations of the deployment times in the sharedcache scenarios, which indicates that deployment times are more predictable than in the case of non-shared caches. These improvements in container deployment times may significantly impact the perception that fog applications' end users have about the performance of the overall system. VI. CONCLUSION Docker was implemented with the assumption that every server's local cache would be large enough to store all the relevant container images after they are first downloaded. This assumption is however not true in fog computing environment where the compute resources are split between a large number of relatively weak machines. In such environments we extended Docker with a cache replacement policy which evicts unused images and maintains an acceptable image cache size. Splitting the available cache size also negatively impacts the cache hit rates because the same popular images must be downloaded and stored separately in multiple disjoint caches. We therefore proposed sharing caches among multiple colocated fog nodes. Our trace-based evaluations show that the proposed design achieves significant cache hit improvements, leading to reductions of average container deployment times between 37% and 78% depending on the scenarios.

Fig. 1 .

 1 Fig. 1. Distributed fog architecture.

Fig. 2 .

 2 Fig. 2. Docker storage directory.

  (a) Small cache sizes. (b) Large cache sizes.

Fig. 3 .

 3 Fig. 3. Cache hit ratios of different AZs vs. shared cache size.

Figure 3

 3 Figure3depicts the cache hit ratio that a shared cache for each AZ would have with different storage capacity. In our

Fig. 4 .

 4 Fig. 4. Docker shared image cache architecture.

Fig. 5 .

 5 Fig. 5. Flowchart of the updated docker pull deployment command. Algorithm 1: Image replacement algorithm.

  (a) Download speed upon cache miss. (b) Upload speed upon cache miss. (c) Download speed upon cache hit. (d) Upload speed upon cache hit.

Fig. 6 .

 6 Fig. 6. Resource utilization upon a cache hit & cache miss.

Fig. 7 .

 7 Fig. 7. Hit ratio and deployment time of shared vs. non-shared image caches under a workload of 4000 container deployments.

TABLE I COMPARISON

 I OF POPULAR DISTRIBUTED FILE SYSTEMS.

		HDFS	CephFS	MooseFS	GlusterFS	iRods	Lustre
	Metadata Server	Centralized	Distributed	Centralized	Decentralized	Centralized Centralized
	Metadata storage	Memory	Disk	Memory	Algorithm	Disk	Disk
	Placement policy	Auto	User controlled [17]	No	Random	Admin	No
	Striping	Yes	Yes	Yes	Yes	No	Yes
	Replication	Yes	Yes	Yes	Yes	Yes	No
	Suitable For files	Big files	Big and small files	Big files	Big and small files	Big files	Big files
	Caching	Yes	Yes	Yes	No	Yes	Yes
	Memory usage (GB)	8	1	20	1	2	1
	API access	FUSE	FUSE, ceph, librados	FUSE	FUSE	FUSE	FUSE
	POSIX compliance	No	Yes	Yes	Yes	No	Yes

TABLE II DISTRIBUTED

 II FILE SYSTEM CONFIGURATIONS.

		File		Number of Replication
	Scenario	system	Client	nodes	degree
	1	CephFS	Kernel	3	1
	2	CephFS	FUSE	3	1
	3	GlusterFS	FUSE	3	1

TABLE III DEPLOYMENT

 III TIMES OF AN ubuntu:latest CONTAINER.

			File system configuration
		No cache	Ceph	Ceph	Gluster
		sharing	kernel	FUSE	FUSE
	Deployment time (Cache miss)	5.2 s	7.01 s	27.01 s	32.1 s
	Deployment time (Cache hit)	0.99 s	1.23 s	2.43 s	2.54 s