Isabelle Dufour

Daniel Alquier

Johan Bertrand

Tayeb-Mohand Boudjiet

Dominique Certon

Luis Iglesias-Hernandez

Thierry Leïchlé

Maria Dolores Manrique-Juarez

Fabrice Mathieu

Laurent Mazenq

Jean-François Michaud

Liviu Nicu

Marc Portail

Shanmugam Priyadarshini

Examples of vibrating MEMS sensing physical parameters for chemical gas detection

Keywords: Resonant MEMS, microcantilever, CMUT, gas detection, viscosity, mass density, sound speed, time of flight, sound absorption

This chapter presents advantages and drawbacks to achieve chemical detection without the use of sensitive coating by measuring physical properties of gas. Example of such detections are presented using two kinds of vibrating MEMS: microcantilevers and capacitive micromachined ultrasonic transducers (CMUT). The main advantages of such sensors relying on their concept are their short response time, good reliability and no need for calibration during the sensor's life cycle. Their major drawback is that there is no selectivity if only one physical parameter measurement is done. To overcome this drawback, discrimination between different gas mixtures can been achieved by simultaneous measurements of multiple physical properties of the gas. This latter principle has been applied with either microcantilevers or CMUT with the simultaneous measurements of either viscosity and mass density or acoustic wave speed and attenuation of gas.

Context -general principle

Chemical microsensors have not had the same industrial development as physical microsensors, such as accelerometers or gyroscopes for example [START_REF]Gas and particle sensors-technology and market trends[END_REF]. There are many reasons for this, including the facts that:

• the markets are niche markets specific to the species to be detected (bottleneck a),

• for each of the species to be detected, an appropriate sensitive layer must be developed or chosen (bottleneck b), • chemical sensors are less reliable and have shorter life spans than physical sensors and they have greater drift (bottleneck c).

Classically, a chemical microsensor is composed of a transducer and a sensitive layer. The role of the sensitive coating is to interact with the targeted gas. This interaction causes changes in temperature, refractive index, electrical properties, mass or mechanical changes and the transducer transforms these changes into an electrical signal. The sensitive coatings are subjected to environmental effects including temperature, humidity and aging effects. Then, the long-term stability of the coatings and the resulting aging affect the reliability of the sensor more than the aging of the transducer itself.

An alternative method to detect and quantify chemical species is to use "physical sensors" which measure a physical property of the gas without need of chemical interaction with the sensor. Examples of physical properties of gas that can be measured are mass density, viscosity, thermal conductivity and sound speed. These physical properties for major industrial gases are presented in Table 1, and some are very different from one gas to another. For example, hydrogen (H2) has a sound speed 4 time greater than the one of air, its thermal conductivity is 7 times greater, its viscosity 2 times smaller and its mass density 14 times smaller. The detection of gas based on the measurement of gas physical properties do not need a sensitive layer. Then such sensors avoid having to choose or develop a new sensitive layer for each application depending on the species to be detected and the possible interferents [START_REF] Malik | Functional gas sensing nanomaterials: a panoramic view[END_REF] (bottleneck b). Moreover, such sensors become generic sensors and can address different niche markets without any long development process (bottleneck a). Finally, the absence of a sensitive coating, which is subjected to sorption or redox phenomena in classical chemical sensors, leads to a more reliable and reversible behavior (bottleneck c).

Examples of such physical sensors for gas detection are thermal conductivity sensors [START_REF] Jones | GaN-on-Si Calorimetric Thermal Conductivity Gas Sensor[END_REF][START_REF] Struk | Investigating time-resolved response of micro thermal conductivitysensor under various modes of operation[END_REF][START_REF] Berndt | MEMS-based thermal conductivity sensor for hydrogen gas detectionin automotive applications[END_REF], mass density and viscosity sensors [START_REF] Mehdaoui | Design, Simulation, fabrication and characterization of piezoelectric MEMS cantilever for gas density and viscosity sensors applications[END_REF][10], speed of sound sensors [START_REF] Zipser | Acoustic sensors for analyzing binary gas mixtures[END_REF]. Commercialized devices also exist based on mass density [12] or thermal conductivity [13] measurements. Due to their physical principle, such sensors achieve good reliability and almost no drift. Their major drawback is that there is no selectivity nor discrimination because there is only one physical parameter measurement. Consequently, they are limited to determination of the concentration of a known binary mixture.

In this chapter, examples of physical sensors for gas detection using vibrating MEMS are presented. The presented results have been recently (2019-2022) realized in the IMS laboratory in collaboration with other French laboratories (GREMAN, LAAS, CRHEA). Moreover, it is shown how combining multiple physical properties measurement it is possible to discriminate different gas mixtures and to determine the gas concentration. In section 2, the vibrating MEMS are silicon microcantilevers, whereas in section 3 they are silicon nitride capacitive micromachined ultrasonic transducers. Then, section 4 presents how using such sensors (microcantilevers or CMUT) it is possible to replace the selectivity, usually obtained with the use of a sensitive coating, by discrimination of different gas mixtures. Finally, section 5 presents some potential applications of such sensors.

Detection using microcantilevers without sensitive coating

The operational principle of an uncoated resonant microcantilever utilized as a chemical sensor relies on the influence exerted by the mass of the fluid displaced by the oscillating cantilever on its resonant frequency. Indeed, when the density of the surrounding fluid increases (decreases), the effective equivalent mass of the cantilever also increases (decreases), thus leading to a reduction (increase) in the resonant frequency. In the context of chemical detection in gaseous environments, variations in gas density can serve as an indicator of alterations in the concentration of specific chemical species within a gas mixture [START_REF] Tétin | Modeling and performance of uncoated microcantilever-based chemical sensors[END_REF][START_REF] Kramer | High-precision density sensor for concentration monitoring of binary gas mixtures[END_REF][START_REF] Sparks | A MEMS-based low pressure, light gas density and binary concentration sensor[END_REF].

The outcomes presented herein were achieved using silicon microcantilevers featuring electromagnetic actuation and piezoresistive read-out (Figure 1):

• The process of generating vibrations entails passing alternating current (AC) through the conductive wire situated along the cantilever's periphery. When a magnetic field aligned with the longitudinal axis of the beam is present, it generates an AC Lorenz force at the microcantilever's free end, subsequently inducing vibrations out of the plane. • To effectively capture these vibrations, the process incorporates the creation of two semiconductor strain gauges (boron-doped piezoresistors). They are organized in a semi Wheatstone bridge setup: one gauge is positioned at the point of maximum strain (on the surface of the clamped-end of the microcantilever), while the second gauge is positioned on the rigid substrate. To assess the impact of cantilever geometries (including rectangular, U-, and T-shaped microstructures) and dimensions, a series of microcantilevers were manufactured at LAAS (Toulouse, France) and subjected to testing at IMS (Bordeaux, France) [START_REF] Boudjiet | Geometry optimization of uncoated silicon microcantilever-based gas density sensors[END_REF]. The results demonstrated that for mass density measurement, uniform rectangular cantilevers exhibited superior performance compared to their T-and U-shaped counterparts. Additionally, the investigation revealed that broader and shorter beams manifested heightened sensitivity toward changes in mass density. The sensitivity of rectangular beams was found to follow a proportional relationship with b/L^2 (where b and L represent width and length, respectively), in accordance with the analytical model developed by IMS [START_REF] Tétin | Modeling and performance of uncoated microcantilever-based chemical sensors[END_REF]. Interestingly, the thickness of the rectangular cantilevers didn't influence their sensitivity to mass density changes, despite its effect on the resonant frequency. Nevertheless, the noise on the resonant frequency is dependent on the microcantilever's thickness, underscoring the need for careful consideration when selecting the most suitable thickness for a given structural size (length and width). This consideration becomes especially relevant for optimizing the limit of detection.

Owing to the minor shifts in resonant frequency that require detection, novel characterization techniques have been developed to monitor these subtle frequency variations. The traditional approach to track changes in resonant frequency involves the identification of the resonant peak within the amplitude spectrum and tracing alterations in the associated frequency. However, the relative frequency variation for scenarios involving low hydrogen (H 2) concentration in nitrogen (N2) is exceedingly small. For example, when utilizing a silicon microcantilever featuring dimensions of 1 mm length, 1 mm width, 10 µm thickness, and an approximate resonant frequency of 23kHz, a concentration as low as 0.2% of H2 in N2 yields a resonant frequency shift of about 0.25 Hz (equivalent to a 10 ppm resonant frequency variation). As a result, the conventional technique proves inadequate in capturing such minute frequency shifts accurately. Primarily, this is attributed to the challenge of accurately pinpointing the exact location of the resonant peak due to inherent measurement noise. Consequently, alternative characterization methods involving the analysis of gain and phase spectra have been experimented using measurement data [START_REF] Boudjiet | New characterization methods for monitoring small resonant frequency variation: Experimental tests in the case of hydrogen detection with uncoated silicon microcantilever-based sensors[END_REF]. Derived from the same dataset, the diverse methodologies used to extract resonant frequency yielded different signal-to-noise ratios, spanning from 1.2 for the conventional technique to 190 for the most effective strategy (which involved linearizing the phase around the resonant frequency). The results presented in this section predominantly rely on the application of phase linearization, often employing a silicon cantilever measuring 1 mm x 1 mm x 10 µm (with a resonant frequency of around 23 kHz and a quality factor of approximately 500 in atmospheric pressure).

To conduct gas detection, the microcantilever is positioned within a tightly sealed gas chamber, with a volume of 500 µl, and subjected to controlled gas flow conditions. Gas compositions containing binary mixtures featuring the desired elements (such as hydrogen, helium, carbon dioxide, or methane) and nitrogen are introduced into the chamber, employing gas bottles and a suite of massflow controllers (Brooks 5850S). Each binary mixture is systematically introduced at three distinct concentrations-namely, 5%, 4%, and 3%-for a time span of 400 seconds each. Between the introduction of each gas mixture, nitrogen is introduced for a 400-second interval, serving to assess potential drift and to underscore the sensor's reversibility. The resonant frequency shifts observed throughout this experiment are depicted in Figure 2.

Figure 2. Example of resonant frequency shifts measured with a 1 mm x 1 mm x 10 µm silicon cantilever with different concentrations (5%, 4%, 3%) of H 2 in N2 (blue curve), He in N2 (red curve), C02

in N2 (green curve) and CH4 in N2 (black curve) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

Based on the physical principles governing these sensors, the presence of gases lighter than nitrogen (such as H2, He, and CH4) results in an increase in the resonant frequency, while the presence of heavier gases (like CO2) than nitrogen leads to a decrease in the resonant frequency. Furthermore, the trends match the full reversibility and quick response time (under 1 minute). In our experiment, the primary factor influencing response time is the duration required for the flow feedback loop to stabilize concentration levels (a swifter control system could potentially achieve sub-1-minute response times). Additionally, almost no drift is observed over the experiment's duration (a mere 0.15 Hz over 3 hours without room temperature control). Of notable significance is the consistent shift in resonant frequency, surpassing 2 Hz for the tested concentrations (5%, 4%, and 3%) across all four gases (equivalent to 100 ppm of the resonant frequency). Moreover, the capability to measure even lower concentrations is facilitated by the minimal noise associated with measurements based on phase linearization (an exemplar of detecting 100 ppm of H2 in N2 is depicted in Figure 3). As proved with the measurements presented in Figure 2, the resonant frequency measurement allows to discriminate if the gas becomes heavier or lighter but there is no selectivity between the different gas mixtures (He, H2 and CH4 can be confused with each other). Concerning this point, the measurement of another parameter (the quality factor) allows to discriminate between the different gas mixture (section 4).

Detection using CMUT without sensitive coating

Another type of MEMS has been used to achieved chemical detection using gas physical properties measurement: silicon-based capacitive micromachined ultrasonic transducers (CMUT), which consist of small membranes that can be electrostatically actuated and the vibration can be measured with capacitive read-out.

The presented results have been achieved using silicon nitride CMUT microcantilevers fabricated at GREMAN (Tours, France) using the surface machining process described in [START_REF] Heller | Performance evaluation of CMUT-based ultrasonic transformers for galvanic isolation[END_REF]. Each CMUT sensor (8 mm x 0.8 mm) is composed of thousands of single CMUT in parallel (Figure 4). Each membrane is a square (32 µm x 32 µm) of 450 nm thickness. The resonant frequency is around 8 MHz. The same principle of gas detection as the one presented using microcantilever (section 2) based on the spectrum measurement around resonant frequency has been used. In this case, the measurement is based on the measurement of the spectrum of the CMUT admittance. It has been proved that the more sensitive measurement is obtained with the measurement of the minimum of the admittance [START_REF] Iglesias | Proof of concept and preliminary results of gas detection by measuring the admittance at the resonance and anti-resonance of an uncoated CMUT[END_REF]. Examples of detection of H2 or CO2 in N2 are presented in Figure 5. Similar conclusions can be drawn from those in section 2.

Figure 5.

Examples of gas detection using the measurement of the relative variation of the admittance of a silicon nitride CMUT composed of squared membranes (32 µm x 32 µm) on a 8 mm x 0.8 mm chip. The measurements have been made at different concentrations (4%, 3%, 2%, 1%) of H2 in N2 (blue curve) or C02 in N2 (green curve) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

Besides, two other innovative uses of CMUT for the gas detection have been also demonstrated: the first one consists in measuring the propagation time between two CMUTs and the second one consists in measuring the attenuation of the acoustic wave between two CMUT [START_REF] Shanmugam | Broad Bandwidth air-coupled micromachined ultrasonic transducers for gas sensing[END_REF][START_REF] Iglesias | Cmut Time of Flight Gas Sensor By Phase Shift Measurement[END_REF][START_REF] Iglesias | Hydrogen selective gas sensor based on attenuation measurement of acoustic wave using uncoated CMUT[END_REF].

The basic way to measure the time of flight between two CMUT consists in measuring the time that an ultrasound takes to propagate from a CMUT in emission mode to a CMUT in reception mode, both placed in front of each other. An ultrasonic pulse is sent through the gas mixture by a CMUT in emission mode. After travelling a distance of few millimeters, it is then received at the other end by another CMUT in reception mode (Figure 6). Both the emission and the reception signals were acquired via a Picoscope2000 Series acquisition card and then analyzed through a basic peak detection algorithm.

. Schematics illustrating the principle of a time of flight measurement for gas detection with 2 CMUT and example of measurements of echoes in nitrogen gas

Examples of detection of H2 (sound velocity higher than the one of N2) or CO2 (sound velocity lower than the one of N2) in N2 are presented in Figure 7. The measurements are in good agreement with analytical modeling [START_REF] Shanmugam | Broad Bandwidth air-coupled micromachined ultrasonic transducers for gas sensing[END_REF]. As for the other measurements presented in this chapter, they are reversible, with almost no drift and response time below 1 min. Although intuitive and effective, the measurement of the time of flight in the time domain presents some drawbacks. One of them being the need for a robust peak detection algorithm which usually is hard to integrate in a sensor and also required computational cost. Another issue is that a pulse generator is usually more expensive than a simple sine wave generator. An alternative method to measure the time of flight is to use the same setup (2 CMUT facing each other) but, instead of generating pulse, sinusoidal wave is emitted and received. In this case, the time of flight is the slope of the phase between emitted and received signals as a function of the radial frequency. A data processing was set up in order to suppress the influence of the multiple echoes [START_REF] Iglesias | Gas discrimination by simultaneous sound velocity and attenuation measurements using uncoated capacitive micromachined ultrasonic transducers[END_REF].

Examples of the same detection as those of Figure 7 are presented in Figure 8 with the time of flight measurement based on the spectrum of the phase. It can we easily seen that this method of measurement is less noisy. Another physical property of the gas that can be measured with the same setup is the sound attenuation of the gas. Indeed, instead of measuring the delay that the acoustic wave takes to travel the cell, the amplitude of the sinusoidal signal amplitude can be measured: an increase in the gas attenuation decreases the amplitude of the signal. The advantage of the attenuation is that it is a frequency dependent property and its dependence varies from one gas to another. For example, the attenuation at 4 MHz is much higher for H2 than for CO2 or CH4. As shown in Figure 9, an appropriate choice of the frequency measurement can achieve a kind of selectivity: MHz range is appropriate to detect hydrogen with small interference with other gases. Examples of gas detection using the frequency domain measurement of the attenuation shift between two CMUT at 4MHz. The CMUT are silicon nitride CMUT composed of squared membranes (32 µm x 32 µm) on a 8 mm x 0.8 mm chip. The measurements have been made at different concentrations (4%, 3%, 2%, 1%) of H2 in N2 (blue curve) or C02 in N2 (green curve) or CH4 in N2 (black curve) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

As the microcantilever-based measurements presented in section 2, the CMUT-based measurements of this section are not selective: the time of flight measurement allows to discriminate if sound velocity of the gas increases or decreases and the attenuation measurement allows to achieve a partial selectivity by appropriate choice of frequency. Combining time of flight measurement with attenuation measurement allows to discriminate between the different gas mixture (section 4).

Discrimination of gases with multiple physical property measurements

As presented in section 2 and 3, resonant MEMS can be used to measure multiple physical properties of gas. One physical property measurement is not sufficient to achieve discrimination between different gases. Using the resonant MEMS spectrum, it is possible to measure simultaneously two gas physical properties and then to achieve discrimination between different gas mixtures and to measure their concentration. This will be shown in this section with both the microcantilevers and the CMUT of previous sections.

Using the spectrum measurement not far from the microcantilever resonant frequency, it is possible to measure both the resonant frequency and the quality factor of the microcantilever. Using a simple model [START_REF] Iglesias | Discrimination and concentration measurement of different binary gas mixtures with a simple resonator through viscosity and mass density measurements[END_REF] it is then possible to extract the relative variation of both the mass density and viscosity of the gas. In the plane (mass density, viscosity), the measurement points are not far from the one expected by theory (Figure 10). Then, depending where the point is in this plane the discrimination between different gas mixtures can easily be made and after that the mass density measurement, which is less noisy than the viscosity measurement, can be used to estimate the gas concentration. Figure 10. Simultaneous measurements of both the mass density and the viscosity of the gas using the simultaneous measurement of both the resonant frequency and quality factor of a silicon cantilever (1 mm x 1 mm x 10 µm) with different concentrations (5%, 4%, 3%) of H2 in N2 (blue), He in N2 (red), C02 in N2 (green) and CH4 in N2 (black) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm). The theoretical points are also reported.

On the same principle using the spectrum measurement of the signal of the receiver CMUT, it is possible to measure both the time of flight and the attenuation at each frequency (Figures 8 and9). As in the latter case (Figure 10), depending where the point is in the plane (attenuation, time of flight) the discrimination between different gas mixtures can easily be made and the gas concentration can be deduced (Figure 11).

-2.

. Simultaneous measurements of both the time of flight and the sound attenuation of the gas using the simultaneous measurement of both amplitude and phase of the signal of the CMUT receiver with different concentrations (5%, 4%, 3%) of H2 in N2 (blue), He in N2 (red), C02 in N2 (green) and CH4 in N2 (black) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

Potential applications

The presented sensors do not target a particular application, but, as the developed devices are generic, it is possible to use this kind of devices for different applications where quantitative determination of non-reactive gas compositions in gas mixtures requires particular attention. Such sensors could be of useful interest for a wide range of industries for the continuous monitoring of gases. Important markets include gas production, hydrocarbon fuel distribution, biogas production and distribution. Few possible applications are listed in more detail below:

• With the global population consistently on the rise, there is an exponential surge in the demand for diverse goods and services. This unfolding scenario of industrial expansion, coupled with the rapid growth of the populace, amplifies the need for energy, necessitating its provision through both traditional and renewable energy sources. Sustainable energy solutions have undoubtedly become the cornerstone of many contemporary scientific and technological advancements. Scientists are tirelessly seeking solutions that won't contribute to the prevailing carbon emissions. Within this context, it's noteworthy to highlight the widespread adoption of hydrogen-based energy generation as a means of securing clean energy. Hydrogen gas possesses an exceptional energy density. However, given the highly explosive nature of hydrogen-air mixtures within the 4%-75% hydrogen concentration range, continuous monitoring of hydrogen concentration becomes paramount. This is especially crucial due to the potential risks associated with the production, storage, and transport of hydrogen gas. Consequently, vigilant monitoring of hydrogen gas concentration remains indispensable to avert potentially hazardous situations. • The forthcoming French repository for radioactive waste is planned to encompass underground structures designed to house tens of thousands of cubic meters of high-level and intermediate-level long-lived radioactive waste, predominantly originating from French nuclear power plants. The CIGEO project aims to confine these waste products for an extended period, with the overarching objective of ensuring sustainable, secure, and reversible storage [26]. Central to the comprehensive monitoring strategy for geological disposal is the continuous observation and assessment of subsurface installations. The monitoring apparatus within such an environment must withstand the harsh conditions prevalent in a repository, particularly the radiation levels that could accelerate the deterioration of sensor materials. The adaptation of existing sensors or the creation of new ones becomes imperative to align with the technical demands of this application. This significance is especially pronounced in the domain of chemical sensors, where enhancing durability and minimizing maintenance requirements are paramount. In this context, the release of hydrogen is anticipated within the radioactive waste disposal facility, arising from both (i) the release of radioactive waste and (ii) the anoxic corrosion of metallic components. Consequently, as in the previous scenario, it becomes imperative to actively monitor the concentration of hydrogen gas within this radioactive repository, thereby averting any potential hazardous circumstances. • Serving as a premium-grade industrial raw material, hydrogen finds extensive applications not only in industries such as nuclear, aerospace, and metallurgy, but also beyond. The molecular structure of hydrogen is incredibly compact, endowing it with exceptional permeability. Consequently, the minute gas molecules of H 2 are inclined to escape through even the most minuscule openings and fissures. As a result, the detection of hydrogen leakage emerges as a critical concern within a multitude of industrial domains.

• The same problem of leakage in small holes or permeable materials could happen with helium gas which is also composed of very small molecules. As described in [27] it is important to avoid exposing smartphones or smartwatches to helium, because the small gaseous molecules can bleed into the MEMS devices and stop them from functioning. It is then important to control the concentration level of helium if helium is present not far. • Since the liberation of the French gas market, the importance of fuel gases (i.e. natural gas) in industrial applications has increased significantly. Non-traditional sources result in a gas composition that can vary greatly. Sources of gas can be traditional dry gas from natural gas wells, wet shale gas, biogas and synthetic natural gas made from a blend of propane and air. Significant variation of gas composition and energy content (combustion potential) creates added complexities in the design of burner control systems. The percentage of noncombustible gas (CO2 and N2) in fuel gas can vary from 1% to 20% depending on the source.

There is then a need to measure the gas composition of fuel gas.

Figure 1 .

 1 Figure 1. Schematic representation and photo of the microcantilever with electromagnetic actuation and piezoresistive read-out.

Figure 3 .

 3 Figure 3. Example of resonant frequency shifts measured with a 1 mm x1 mm x 5 µm silicon cantileverwith small concentrations (500ppm, 250ppm and 100ppm) of H2 in N2 with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

Figure 4 .

 4 Figure 4. Schematic representation of the CMUT membrane and CMUT chip.

Figure 6

 6 Figure 6. Schematics illustrating the principle of a time of flight measurement for gas detection with 2 CMUT and example of measurements of echoes in nitrogen gas

Figure 7 .

 7 Figure 7. Examples of gas detection using the time domain measurement of the relative shift of the time of flight between two CMUT. The CMUT are silicon nitride CMUT composed of squared membranes (32 µm x 32 µm) on a 8 mm x 0.8 mm chip. The measurements have been made at different concentrations (4%, 3%, 2%, 1%) of H2 in N2 (blue curve) or C02 in N2 (green curve) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

Figure 8 .

 8 Figure 8. Examples of gas detection using the frequency domain measurement of the shift of the time of flight between two CMUT. The CMUT are silicon nitride CMUT composed of squared membranes (32 µm x 32 µm) on a 8 mm x 1 mm chip. The measurements have been made at different concentrations (4%, 3%, 2%, 1%) of H2 in N2 (blue curve) or C02 in N2 (green curve) or CH4 in N2 (black curve) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

Figure 9 .

 9 Figure 9. Examples of gas detection using the frequency domain measurement of the attenuationshift between two CMUT at 4MHz. The CMUT are silicon nitride CMUT composed of squared membranes (32 µm x 32 µm) on a 8 mm x 0.8 mm chip. The measurements have been made at different concentrations (4%, 3%, 2%, 1%) of H2 in N2 (blue curve) or C02 in N2 (green curve) or CH4 in N2 (black curve) with a gas flow of 100ml/min at room temperature conditions (temperature ≈ 20°C, pressure ≈ 1 atm).

Table 1 . Physical properties of common industrial gases [2-4]

 1

	Gas	Mass density	Viscosity	Thermal conductivity	Sound speed
		(kg/m 3 )	(µPa.s)	(mW.m -1 .K -1 )	(m.s -1 )
		1.015 bar, 15°C	1.015 bar, 0°C	1.015 bar, 0°C	1.015 bar, 20°C
	CO2	1.87	13.7	14.7	267
	O2	1.35	19.1	24.4	326
	Air	1.22	17.2	24.4	343
	N2	1.18	16.6	24.0	349
	CH4	0.68	10.1	30.6	446
	He	0.17	18.7	146.2	1007
	H2	0.09	8.4	172.6	1270

This research was conducted thanks to the contest Programme d'Investissements d'Avenir of the French Government under the supervision of the French National Radioactive Waste Management Agency (ANDRA).


Laurent Bulteau

Pierre-Yves David

Florian Horn

The Problem of Discovery in Version Control Systems

Keywords:

Version Control Systems, used by developers to keep track of the evolution of their code, model repositories as Merkle graphs of revisions. In order to synchronize efficiently between different instances of a repository, they need to determine the common knowledge that they share. This process is called discovery.

In this paper, we provide theoretical definitions for the problem of discovery, establish some universal upper and lower bounds on the amount of data that needs to be exchanged, as well as NP-hardness for a restricted variant (with only 2 round-trips). We also present and analyze some algorithms that are used in extant VCSs, such as Mercurial and Git, and propose an algorithm based on chain-decomposition.

Introduction

Version Control Systems (VCSs) are tools that help developers follow the evolution of code over the lifetime of a project. They allow multiple developers to interact concurrently with the source code and keep track of every version of the project.

The first VCSs, Source Code Control System [START_REF] Rochkind | The source code control system[END_REF] and Revision Control System [START_REF] Tichy | Design, implementation, and evaluation of a revision control system[END_REF], tracked files separately and locally: they allowed collaboration, but only on one site, and only one programmer at a time. Both systems allowed users to check out earlier versions of the code (SCCS through regular deltas, RCS through reverse-deltas), although the process could be painstakingly slow.

A second generation of VCSs, spanning from Concurrent Versioning System [START_REF] Grune | Concurrent versions system, a method for independent cooperation[END_REF] through Subversion [START_REF] Collins-Sussman | Version control with Subversion -next generation open source version control[END_REF] introduced a central repository containing all the versions of the files. This repository could be accessed remotely, allowing programmers in different locations to work on the same project. Locks were also removed and replaced by merging procedures, so multiple programmers could write code simultaneously.

The current generation of VCSs, represented by tools like Git [START_REF] Torvalds | Initial revision of "GIT", the information manager from hell[END_REF] and Mercurial [START_REF] Mackall | Towards a better SCM: Revlog and Mercurial[END_REF], does away with the notions of a central repository and current version. Instead, each developer has their own copy of a given repository, which is structured as a Merkle graph, i.e. an acyclic graph in which each node includes the hash(es) of its parent(s).

This allows anyone to add freely to their own copy, adding revisions, creating new branches or merging existing ones. They can also exchange nodes with another peer, pushing the revisions that they know and pulling those that they do not.

In larger projects such as Linux (Git) or Firefox (Mercurial), these operations can be very time-consuming: repositories can contain millions of revisions and grow daily by thousands of revisions, with peaks at several revisions per second. At this scale, it becomes necessary to optimize the exchange of information. This requires different agents to be able to determine efficiently which revisions they have in common. This is the problem of discovery, which we study in this paper from an abstract point of view. VCSs have been an object of academic interest in recent years [START_REF] De Rosso | What's wrong with GIT? A conceptual design analysis[END_REF][START_REF] Levenberg | Why Google stores billions of lines of code in a single repository[END_REF][START_REF] Babenhauserheide | Automatic coordinated rebase with changeset evolution and Mercurial[END_REF][START_REF] Courtiel | Theoretical analysis of GIT bisect[END_REF], although to the best of our knowledge, this article is the first to study this specific problem.

The remainder of this paper is organized as follows. In Section 2, we formally define our model for VCSs as well as the computation model that we use to analyse discovery algorithms. Then, in Section 3, we present several algorithms, including the ones used by Git and Mercurial. Section 4 studies the theoretical complexity of Graph Discovery, in terms of the number and volume of exchanges between the local and remote agents. In Section 5, we build test examples from large real-world repositories and analyze the performance of existing algorithms in terms of round-trips and total query size.

Definitions

Merkle graphs

A directed graph G is a pair (V, E) where V is a set of nodes and E ⊆ V 2 is a set of edges. It is a directed acyclic graph (DAG) if it does not contain any cycles. If u → v is an edge of a DAG, we call u a parent of v and v a child of u. The set of ancestors of u is the set recursively defined as the union of {u} with the ancestors of the parents of u (if any). Similarly, the descendants of u is the union of {u} with the descendants of its children, if any. We write u → + v if u is an ancestor of v with u v.

A node with two or more parents is a merge node and a node with no parents is a root. A node with two or more children is a branchpoint and a node with no children is a head. A node with a single parent and a single child is a linear node. A linear section is a (possibly empty) sequence of linear nodes where each node is the parent of its successor, preceded by a base and followed by a tip which are non-linear nodes.

A Merkle graph is a DAG where nodes contain the hash of their parents (assuming hashes to be collision-free), which must belong to the graph. A Merkle graph is therefore entirely determined by the set of its heads. Furthermore, if two Merkle graphs G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) have a common node, it has the same parents in both graphs.

Formally, if v ∈ V 1 ∩ V 2 , then for any u → v ∈ E 1 , then u → v ∈ E 2 .
In the remainder of this paper, whenever we use the term graph, we mean a Merkle graph. When discussing existing algorithms, we sometimes use the terms repository and revision instead of graph and node.

Discovery Problem

We study the problem of Graph Discovery, in which a local agent knows a graph G = (V , E ) and has to determine its intersection with another graph known by a remote agent G r = (V r , E r ). Formally, the common subgraph G c has vertex set The local agent, who runs the algorithm, does not have direct access to information about the remote graph. Instead, it has to send network requests (prefixed by remote in our pseudo-code algorithms). Each algorithm may implement a different set of requests, possibly involving non-trivial computations on the remote side. A commonly used request, remote.known(X) with X ⊆ V , returns the subset of remotely known nodes among X (i.e., X ∩ V r = X ∩ V c ).

V c = V ∩ V r . It is defined as G c = G [V c ] = G r [V c ]
In this article, we do not consider the classical complexity of Graph Discovery in terms of unit operations. We are only interested in network requests, specifically two quantities: the number of separate requests (round-trips) and the total size of the requests (queries), defined as the number of unique node identifiers sent in either direction.

Many algorithms start with a pre-processing step (e.g. an initial exchange of local and remote heads). We ignore this step in our pseudo-code algorithm, as they add a lot of complexity for little theoretical gain, but keep them for the experimental cases.

Although we focus on the theoretical study of the exact Discovery problem, an under-approximation, returning only a subset of the common vertices (or equivalently, an over-estimation return a super-set of the unknown vertices), is acceptable in practice. This case, which happens for example in Git, results in unnecessary node data being exchanged between peers, although the Discovery phase only exchanges node identifiers.

Discovery Algorithms in Git and Mercurial

Git: default discovery

In Git, discovery is done by default in breadth-first fashion, starting with the local heads (Algorithm 1). The local revisions are sorted in topological order1 as undecided, with children preceding their parents. Then local asks remote which revisions they know over a channel with capacity 32, using a request remote.known returning the subset of known nodes. When an answer is positive, the revision and all its ancestors are added to common and removed from undecided. Furthermore, Git has a timeout threshold: if 256 successive revision are unknown to remote, it considers that no other revisions are known to remote and returns the current common set (resulting in an under-approximation).

Git: skipping discovery

As timeouts occurred too often in larger projects, Git introduced a skipping variant of its discovery algorithm. Instead of checking each revision in order to find the exact border of common, this version jumps over an ever growing number of generations in order to find a known ancestor (this corresponds to the two-parameter ancestor function line 22). This means that the skipping discovery may return an under-approximation of the set of common revisions even if the timeout is not reached. We transcribe this algorithm in pseudo-code as Algorithm 2. Note that the candidates are represented as a heap, rather than a queue, to ensure that candidates are always queried in topological order, even if they may have been added in a different order.

Mercurial: tree discovery

We include in our analysis the Mercurial tree discovery algorithm in use until 2010. Informally, the local agent asks for remote heads, and successively asks for linear sections (i.e. separated by merge nodes) in the remote graph as long as both ends of the sections are unknown. Finally, it uses a binary search over the linear sections starting with a known node to compute the precise border of the common subgraph.

In contrast with the gitaxian approach, tree discovery always answers the exact common set. It is also the only algorithm in this article that works from the structure of the remote graph, rather than the local one. The tree discovery algorithm performs well on cases with a small number of large linear section, but there were catastrophic cases where several thousands round-trips were necessary to complete discovery (see Section 5).

Mercurial: set discovery

In 2011, Mercurial replaced its tree discovery algorithm with a set-based discovery algorithm, which samples repeatedly the still undecided subset of the local repository (Algorithm 3).

It works by updating a partition of the local nodes in three sets: common, missing and undecided. In the beginning, all local nodes are undecided. In the end, they are all either common or missing. In each iteration of the while loop, the algorithm samples a non-empty subset of the undecided nodes, using the sample set method, and asks remote whether they know these nodes. All nodes in the sample are thus sorted in common or missing. Furthermore, thanks to the Merkle graph properties, the descendants of a missing node are also missing, and the ancestors of a common node are also common. The termination of the algorithm follows from the depletion of the undecided set. There are many possible variants of the Set-Discovery algorithm, depending on how one implements sample set.

Mercurial defines samplable nodes according to the following rules: all heads and roots of undecided are samplable, and any other node is samplable if its height or depth (i.e., distance to some head or root) is a power of 2. In each round, the set of samplable nodes is computed, and a random subset of size 200 is selected from it. If there are less than 200 samplable nodes, additional random nodes from undecided are added.

Complexity bounds and chain-based algorithm

In this section we study the worst-case complexity of the discovery problem. Note that we assume that algorithms must be name-agnostic: it is impossible to derive any non-topological information from an identifier. Remark 1. In Graph Discovery, for any local node v, any exact algorithm needs to exchange at least one node u such that either u is an ancestor of v in V \ V r , or u is a descendant of v in V ∩ V r .

First, we give a "classical" complexity analysis of the discovery problem restricted to only 2 round trips. We show that finding a first query that would guarantee a limited number of overall node queries is NP-hard.

Theorem 1. Given G and an integer q > 1, it is NP-hard to decide whether the discovery can be completed in two rounds with at most q node queries in total.

For worst-case pairs of local and remote graphs, the total query size in the problem of discovery is linear: Lemma 2. For any n, there exists a size-n local graph G ,n such that Graph Discovery needs a total query size of at least n nodes in the worst case over all graphs G r .

Proof. Let G ,n consist in n unrelated revisions. By Remark 1, since the nodes in V do not have any ancestor or descendent except themselves, they must all be part of the exchanged set.

We note that the above bound is tight, since it is always possible to solve the Discovery problem with the single sizen request remote.known(local.nodes). However, the graphs involved in this lower bound are not very interesting from a practical point of view. There is also a universal logarithmic lower bound for any local graph of size n: Lemma 3. For any fixed local graph G with n nodes, Graph Discovery needs a total query size of at least log 2 (n+1) nodes in the worst case over all graphs G r . This bound is tight.

Our main theorem for this section deals with a wider range of possible graphs, giving a tight bound for the total number of revisions queried in terms of height and width of the graph.

A chain of a graph G is a sequence of nodes (v 0 , v 1 , . . . , v m ) where each v i is an ancestor of v i+1 . An antichain is a set of nodes such that none of them is an ancestor of another. The maximal length of a chain in G is called the height of G. The maximal size of an antichain is its width. We recall Dilworth Theorem [START_REF] Dillworth | A decomposition theorem for partially ordered sets[END_REF], stating that the size of the largest antichain in a DAG is equal to the minimal number of chains required to cover the graph. Theorem 4. There is a family of graphs of arbitrary width w and height h for which any algorithm needs a total query size of at least w log 2 (h + 1) .

There is a protocol that realizes discovery in w log 2 (h + 1) total query size over log 2 (h + 1) round-trips for each graph of width w and height h.

Proof. We first give a construction of the set of graphs yielding this worst-case lower bound. Given w and h, G w,h is a graph containing w disjoint paths of length h. As each path has size h, it follows from Lemma 3 that there needs to be log 2 (h + 1) queries related to that path. As the paths are disjoint, no information from one path can be useful to solve the other paths. It follows that any protocol solving discovery for G w,h requires at least w log 2 (h + 1) total queries in the worst case.

We describe an algorithm realizing discovery in w log 2 (n + 1) total query size over log 2 (n + 1) round-trips as Algorithm 4 (see Figure 1 for an example). It consists in finding a minimal chain cover of the local nodes and then searching for the border in each chain by dichotomy. Note that a chain may skip over some revisions that are covered by other chains. It may even skip over the border, in which case one half of the chain will eventually belong to common while the other will eventually belong to missing. This chain discovery can be seen as an instance of set discovery, with a different way of sampling undecided nodes. In particular, there might be cross-chain inferences where a result on one chain gives information on another. However, the chain cover should not be computed anew in each loop, as the height of undecided may not be divided by two when we split the chains.

Computing a minimal chain covering is quadratic in time, which makes the Chain Discovery algorithm intractable in practice. However, Cáceres et al. [START_REF] Cáceres | Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time[END_REF] recently proposed a parameterized linear-time algorithm (i.e. linear for constant width) for the similar minimum path cover problem, which should be competitive for small width graphs. One may also maintain a chain cover problem through on-line insertions of the nodes. Since the nodes are inserted in topological order, each new node can be assigned a chain (without editing past nodes), using at most O(w 2 ) chains for width-w graphs [START_REF] Felsner | On-line chain partitions of orders[END_REF].

Experimental Results

We ran the Git, Mercurial and chain algorithms on large repositories to see how they behaved in practice. Our study cases were created from copies of pypy, netbeans, mozilla-unified, and mozilla-try repositories, to see account for different topologies. For each of them, we started from a specific repository state and then created 10 000 different Percentage of overestimation (log scale)

Overestimation ratio for Git algorithms Fig. 2: Distributions of the number of round-trips, total query size, and over-estimation ratio (for Git algorithms) for each algorithm. Boxes delimit the second and third quartiles, and whiskers extend to the 5-95 percentiles. Overall, the current algorithms for Git and Mercurial (git skip and set discovery) have similar performances with typically 1-10 round trips and 1 000-10 000 queried nodes. Git yields an overestimation of typically 1-20%.

pairs of local subgraphs by choosing a revision at random and keeping only its ancestors. Our results are presented in Figure 2. We extended Git's sample size from 32 to 200 to get a fairer comparison with Mercurial's results. Git's algorithms make a trade-off between speed and accuracy, giving up when cases become complicated. This helps keep the number of round-trips under control (visible in the top plot of Figure 2), but comes at the cost of a potentially large number of missed common revisions (visible in the bottom plot of Figure 2). This can represent a very large excess network use if already known revisions are later sent to the remote server. The skipping variant alleviates some of these problems, reducing the overestimation ratio to less than 50% in most of the cases, but the issue remains significant.

Mercurial's set discovery also has very low number of round-trips while tree discovery regularly used thousands (tens of thousands in the case of mozilla-try).

However, set discovery uses more total queries than tree discovery for pypy and netbeans. This is a direct consequence of set discovery maximising the information fetched in each round-trip: most of the apparent advantage of tree-discovery comes from "wasted" capacity, as overhead costs mean that a request for a few revisions is not much less costly than a request for 200 revisions.

Finally, we tested a naive implementation of the chain discovery algorithm, using a heuristic for chain decomposition. This algorithm obtains very competitive results in terms of number of queries, but at the cost of additional round-trips, as well as a time-consuming chain decomposition in the first place. We expect that larger queries (sampling more nodes per chain) can give a better trade-off between round-trips and total queries.

As a final statistic, we tested former versions of Mercurial on hand-picked difficult cases. The current algorithm adjusts dynamically the size of of the sample based on the number of heads and roots. Compared to fixed-size samples, this policy yields a 92% round-trip gain, while a simple growing policy of +5% per round already gives a 71% gain. On the other hand, larger samples lead to more queries per round trips, and overall there is an increase in total query size in both cases (+1.5% with the simple version, +13% in the dynamic version).

Conclusion

With the third generation of VCSs, the problem of discovery has emerged as a significant issue for efficient handling of larger repositories.

Mercurial's latest algorithm, set discovery, has very good performances, with a number of round-trips in the single digits. However, it should be noted that one reason for its performance is that requests can be arbitrarily large. In pathological cases with many heads and a wide boundary, these requests can include several thousands revisions ids. This cannot always be done over http protocols, leading to a commensurate explosion on the number of round-trips.

It would be interesting to investigate new methods to reduce the cost of discovery for repositories with large width, especially when there are many heads. Towards this goal, the constraint that only nodes can be exchanged could be lifted: one can allow, for example, the agents to share hashes of larger sets of nodes, in order to check whether all nodes in some set are known without sending each node one by one. Such an approach would be particularly useful in cases with a large common subgraph between the local and remote agents.

  by definition of Merkle graphs. Graph Discovery Input: local graph G , remote graph G r Output: the common subgraph G c of G and G r .

8 for chain ∈ chains do 9 ifGFig. 1 :

 891 Fig.1:The chain discovery algorithm. Left: a Merkle graph with an unknown (dotted) border. Right: a chain partition is computed (non-adjacent vertices consecutive in the blue chain are linked by a dotted arc), and middle vertices of each chain are probed successively until the known and unknown vertex sets (bottom and top shaded areas, respectively) cover the whole graph.

  Data: local, remote 1 common ← ∅ 2 undecided ← sort(local.nodes)

			Data: local, remote
			1 common ← ∅
			2 undecided ← local.nodes
			3 candidates ← ∅
			4 for h in local.heads do
			5	candidates.heappush((h,0))
	3 while undecided ∅ do	6 while candidates ∅ do
	4	sample ← undecided[0:32]	7	sample ← ∅
	5	present ← remote.known(sample)	8	for i in range(32) do
			9	sample.add(candidates.heappop())
	6	for node ∈ sample do	10	present ← remote.known(sample)
	7	if node ∈ present then	11	for (node,i) ∈ sample do
	8	anc ← ancestors(node)	12	if node ∈ present then
	9	common.add(anc)	13	anc ← ancestors(node)
	10	undecided.remove(anc)	14	common.add(anc)
	11	timeout ← 0	15	undecided.remove(anc)
			16	candidates.remove(anc)
	12	else	17	timeout ← 0
	13	undecided.remove(node)	18	else
	14	timeout += 1	19	timeout += 1
	15	if timeout = 256 then	20	if timeout = 256 then
	16	return common	21	return common
	17 return common	22 23	for a ∈ ancestors(node, i 2 + 1 ) do candidates.heappush(a, 3i 2 + 1 ))
		Algorithm 1: Git: default discovery	24 return common
				Algorithm 2: Git: skipping discovery
		Data: local, remote
	1 common ← ∅
	2 missing ← ∅
	3 undecided ← local.nodes
	4 while undecided is not empty do
	5	sample ← sample set(undecided)
	6	present = remote.known(sample)
	7	for node ∈ sample do
	8	if node ∈ present then
	9	common.add(ancestors(node))
	10	undecided.remove(ancestors(node))
	11	else
	12	missing.add(descendants(node))
	13	undecided.remove(descendants(node))
	14 return common
		Algorithm 3: Mercurial set discovery

Git sorts by date, which may not be exactly topological, but their discovery algorithms ignore these cases and so shall we.