Barrat

Lydéric Bocquet

Jean-Louis Barrat

Flow boundary conditions from nano-to micro-scales

Flow boundary conditions from nano-to micro-scales

I. INTRODUCTION

The nature of boundary conditions of fluid at solid surfaces has been revisited over the recent years. Beyond the fondamental understanding of the fluid-solid dynamics, the reason for such a strong interest lies in its potential applications in microfluidics. The driving of liquids in ever tiny channels raises a number of difficulties, one being the huge increase in hydrodynamic resistance when the channel size decreases. Releasing the no-slip boundary condition at the surfaces, and thereby allowing for boundary slippage, would allow to bypass this stringent conditions by decreasing wall friction. There is therefore a big hope to take benefit of slippage for microfluidic applications.

Many experiments have been performed on the subject, with sometimes contradicting results. We refer to the review of Lauga, Brenner and Stone for an exhaustive discussion of the experimental approaches to investigate slippage [START_REF] Lauga | Handbook of Experimental Fluid Dynamics[END_REF]. While experimental investigations focused first on slippage on bare (atomically smooth) surfaces, more recent works have turned towards structured surfaces, in particular superhydrophobic surfaces, characterized by patterns at the micro-or nano-scales.

In this review we concentrate on the theoretical understanding and expectations for the fluid-solid boundary condition. In particular, we will discuss the relevant theoretical framework for mechanisms that take place at different scales, and lead to slippage at solid-fluid interfaces.

II. FLOW PAST IDEAL INTERFACES/

From a conceptual standpoint, the simplest situation that can be considered is that of a semi infinite solid, bounded by an atomically smooth surface, in contact with a liquid that occupies the second half space. By atomically smooth, we mean for example a dense plane of a perfect crystalline lattice. The location of this lattice plane defines the xOy plane. The theoretical question becomes then simply to describe momentum transfer from the fluid to the solid (assumed here to be at rest) in terms of the velocity field existing in the fluid. Let us consider the case, where the fluid is undergoing a laminar, planar Couette flow in the x direction, e.g. driven by a second flat boundary far away in the z direction. In a stationary state, the stress component σ xz is uniform, and the velocity profile of a Newtonian fluid reads, far away from the solid wall

v x (z) = γz + v s (1)
The shear stress is η γ, where η is the shear viscosity of the bulk fluid and γ the shear rate. By definition, v s is the slip velocity. To achieve a complete hydrodynamic description of the system, a constitutive equation involving the interface has to be introduced. Such a constitutive equation is generally described as a "boundary condition". Although we will also use this traditional vocabulary, we emphasize that it is somewhat misleading. In many cases, "boundary conditions" are seen as auxiliary mathematical constraints that allow to solve partial differential equations. In our mind, the status of the constitutive equation relative to the interface is in every respect comparable to the one of the bulk equations, e.g.

• it is a material property, involving the chemical nature of the two phases that create the ideal interface.

• it should be amenable to the same type of microscopic justifications and statistical mechanical treatments as bulk properties.

• it can be extracted unambiguously from transport measurements.

As for any constitutive equation, the writing of the interfacial constitutive equation involves a first step of

σ xz = κv s (2)
Combining ( 2) with the constitutive equation for the bulk Newtonian fluid, σ xz = η∂ z v x , one arrives at the so called Navier boundary condition

v s = η κ ∂ z v x = b∂ z v x (3)
which can be used as a boundary condition (in the mathematical sense) that complements the Navier-Stokes equation inside the fluid. This boundary condition is applied within one atomic distance of the first solid plane [START_REF] Bocquet | [END_REF], where the stress (3) acts on the solid. By construction, the "hydrodynamic" flow that results from using this boundary condition will be identical to the actual, macroscopic flow far away from the boundaries. At the microscopic level, a thin interfacial region exists in which the flow may differ from the hydrodynamic calculation. We insist that this region, in which the velocity field can be obtained only from molecular scale studies, is not our main concern here. Studies at the molecular scales may result into velocity profiles that are not solution of the Stokes equation, or need to artificially introduce a position dependent viscosity.

The second equality in (3) introduces the slip length b = η/κ. The significance of this length is illustrated in figure 1, as the distance inside the solid to which the velocity profile has to be extrapolated to reach zero. The standard "no slip" boundary condition corresponds to b = 0, i.e. κ → ∞. Conventionally a positive slip length is associated with a positive slip velocity, while a (less common) negative length would indicate an apparent change in the sign of the velocity field near the solid. We emphasize that b is not an interfacial property in the usual sense, rather it is the ratio of a truly interfacial property, the friction κ, to a bulk property, the viscosity η. In particular, b is, in principle, completely unrelated to the width of the interfacial region alluded to above. All our knowledge of interfaces between solids and simple liquids indicates that -if critical phenomena are excluded-the width of the interfacial region is at most of a few atomic diameters. The slip length, on the other hand, can (theoretically) be made to diverge by going to the limit of a perfectly flat (in the mathematical sense) solid wall. Such a procedure, on the other hand, would not significantly alter the width of the interfacial region.

The determination of the interfacial constitutive relation, often described as "measurement of the slip length", has been the subject of numerous experimental [START_REF] Lauga | Handbook of Experimental Fluid Dynamics[END_REF]3,4,5,6,7] and theoretical [START_REF] Bocquet | [END_REF]8,9,10,11,12,13] investigations in the past 20 years . In spite of the experimental difficulties associated with the definition of "ideal" surfaces in experiments, the combination of increasingly accurate measurement methods and of insights from simulation and theory has produced a rather complete understanding of the "ideal" situation discussed here. The results can be summarized as follows.

(i) The linear relation (3) can be used to describe results for simple liquids, within the range of experimentally accessible shear rates [7]. Numerically, non linear behavior has been reported for shear rates of order 10 8 s -1 for simple liquids [14].

(ii) The friction coefficient κ, and hence the slip length b, depend strongly on the strength of the solid liquid interactions. Early measurements [3,4] were performed on fluid/solid interfaces that correspond to a "wetting" situation, with a low contact angle. These measurements clearly reported a "no slip" boundary condition, with a slip length smaller than the molecular dimensions.

(iii) When the interaction between liquid and solid becomes weaker, so that the contact angle of the liquid on the substrates increases, larger values of b can be measured, typically in the range 10-50 nanometers.

(iv) Points (ii) and (iii) correspond to a general trend, but there is not a unique correlation between contact angle and friction. Other factors, such as the crystallinity of the solid, do influence the friction κ [8,15]. These findings can be rationalized within the context of a linear response theory [START_REF] Bocquet | [END_REF]9] (see also [16]), which has been successfully compared to molecular simulations [9,12]. A possible starting point is the Kubo like formula, which relates the interfacial transport coefficient for momentum (i.e. the friction κ) to the integral of the autocorrelation function of the momentum flux (i.e. the force exerted by the liquid on the solid):

κ = S k B T ∞ 0 dt f x (t)f x (0) ( 4
)
where S is the surface area, and f x (t) is the tangential stress (force per unit area) exerted by the fluid on the solid at time t in the x direction [START_REF]A matrix generalization of 4 is easily obtained for anisotropic surfaces[END_REF]. Note that this formula can obviously be generalized to the case where κ would be anisotropic, represented by a 2 × 2 matrix, as would be the case for a surface of low symmetry. We will limit ourselves to the standard case of isotropic friction. Kubo formula such as (4) cannot in general be evaluated analytically. The correlation function can be computed in direct numerical simulations, or approximated using the standard methods of liquid state theory.

A simple approximation of the result of equation ( 4) was derived in [9], and allows one to quantify the main ingredients that enter the friction. The approximate expression reads

κ ⋍ S (q 0 ) D k B T ∞ 0 dzρ(z)V F S (z) 2 (5)
Here q 0 is the first wave-vector of the reciprocical lattice of the crystalline substrate; S (q 0 ) is the structure factor of the fluid evaluated for this wave-vector, in the interfacial region; D is a collective diffusion coefficient computed at the wave-vector q 0 ; ρ(z) is the density profile of the fluid perpendicular to the interface, and V F S (z) is the interaction potential between a molecule in the fluid and the solid wall. The physical content of the various factors entering ( 5) is clear. The structure factor describes the response of the fluid to the fixed atomic corrugation of the solid wall. A large S (q 0 ) indicates "commensurability" of some sort between the liquid and the solid, which will increase momentum transfer. The diffusion constant sets, roughly, the time scale for the decay of stress-stress correlations.

Note that when κ is divided by η to obtain 1/b, the product D η will be formed. For simple liquids, this ratio is typically equal to k B T divided by a molecular size σ, so that any explicit reference to the microscopic dynamics disappears from the resulting expression for the slip length.

b ⋍ (k B T ) 2 S (q 0 )σ ∞ 0 dzρ(z)V F S (z) 2 (6)
It is therefore expected to be independent of the fluid viscosity for simple liquids.

The last important factor is the integral, which involves the wall fluid interaction and the density profile. It is through this integral, that the wetting properties of the fluid with respect to the solid enter the friction κ. As a crude approximation, let us assume that the density profile consists of a layer of density ρ c (the "contact density") within a molecular thickness σ, followed by a bulk density ρ B . We moreover assume van der Waals interactions with Hamaker constant A H . Then the integral can be crudely approximated by (A 2 H /ρ B σ 2 ) × (ρ c /ρ B ). Gathering the different ingredients that enter equation (5), it is easily seen that the only one that can display large variations is the "contact density", i.e. the average density of the liquid very close to the solid surface, typically within one molecular size, and, to some extent, the ratio A H /k B T . Both factors go into the same direction, namely large slip lengths are favored by a small liquid solid interaction. However, it is clear that, from a dimensional viewpoint, the integral ∞ 0 dzρ(z)V F S (z) 2 will always remain a "molecular" quantity, so that the length scale that emerges from equation ( 6) is not expected to become very large unless very special state points are considered. In fact, our simulations show that the slip lengths that are achieved for simple Lennard-Jones models vary between a few molecular diameters and 50 to 60 molecular diameters, depending on the value of the interaction parameter that defines the solid liquid attraction (Hamaker constant). This is in very reasonable agreement, at a qualitative level, with the most recent experimental results [7].

The same framework may be applied to melts of short polymers. In this case, the substrate wave-vector q 0 is much larger than the inverse radius of gyration of the polymer, so that the collective diffusion is measured at the monomer scale : D is accordingly expected to be independent of the molecular weight N . This predicts that the ratio D η scales like η and increases with the polymer length, similar the predictions of de Gennes for longer chains [17]. This prediction and the validity of Eq. ( 5) has been exhaustively verified for short polymers (up to 16 monomers) using Molecular Dynamics simulations by Priezjev and Troian [12]. The experimental situation may be more complex since slippage will be strongly dependent on the polymer adsorption at the surface. Polymers also display strong nonlinear effects at moderate shear rates, which are not accounted for in our description, and have been extensively studied experimentally [18,19] and theoretically [20].

Another interesting example of the use of equation ( 4) is the recent study of the influence of electrostatic effects on the solid-liquid friction in ionic solutions [START_REF] Joly | Houille Blanche-revue Internationale De L Eau[END_REF][START_REF] Joly | [END_REF]. A simple estimate of these effects based on Eq. ( 4) leads to an electrostatic friction contribution to the friction factor, varying as κ ′ ∝ ηΣ 2 ℓ B , with Σ the surface charge (in units of the elementary charge e), and ℓ B = e 2 /4πǫk B T the Bjerrum length (with ǫ the dielectric constant). Interestingly this contribution is independent of the Debye length.

While the theoretical and numerical descriptions converge unambiguously, a number of experimental reports have appeared over the years, that would appear to contradict either (i) or (ii) above, or both [5,11,23,24]. In some cases, these discrepancies can be attributed to experimental artefacts associated with the measurement apparatus [7,25]. However, another possible source of misunderstandings and errors lies in the structuration effects described below. The intrinsic constitutive boundary condition discussed in this section may be rather different from what is probed in flow experiments at larger length scales.

We conclude with a brief discussion of a view of the solid liquid interface which is sometimes proposed, in which the interfacial region is described as a "film" of thickness w i , formed by some interfacial fluid (or vapor) of viscosity η i . Standard "no slip" boundary conditions are applied at the film boundary. A straightforward calculation shows that, within this description, the friction κ that enters the constitutive equation for the interface is given by

1 κ = 1 η i - 1 η w i (7)
and the equivalent slip length is

b = w i η η i -1 (8)
Such a description does not have a clear microscopic funding. In general, it is impossible to identify a "phase" with distinct properties at the interface. However, it gives a useful insight into the sensitivity of interfacial transport parameters to the structure of the interface. For example, assuming that the viscosity η i is that of a vapor layer, it is easily shown that a slip length of 20nm corresponds to an interface thickness of just 0.25 nm (for water), hardly the size of a single molecule. Clearly this "layer" cannot correspond to a real phase, but is merely a very schematic representation of the depletion close to hydrophobic solid walls.

III. CLIMBING THE STRUCTURATION SCALE A. Effective slippage on patterned surfaces

The situation of an atomically smooth surface, as described in the previous paragraph, involves basically two lengths scales : the microscopic scale, ℓ, characterizing the liquid-solid interface, typically of the order of the atomic size; and the macroscopic size L, corresponding to the flow scale, e.g. the size of the channel in which the flow is conducted.

Intermediate scales may however be present, for example when the surface exhibits large scale structuration, associated with roughness or chemical patterns on a scale L. Assuming a scale separation between the different lengths, ℓ ≪ L < L, the microscopic information associated with the liquid-solid dynamics may be integrated out and summarized in the local slip length on the patterned surface. In this case, the hydrodynamic quantities, velocity profile and pressure, do obey the Stokes equation, complemented by the local Navier condition with local slip lengths {b} (of order ℓ) at the interface.

Once the solution of this set of equations has been calculated, it is possible to define an effective boundary condition, by integrating out the intermediate scale L. This introduces an effective slip length b eff , which may be defined in terms of the friction force F f on the solid interface and an averaged slip velocity V s , as :

F f = -A η V s b eff (9)
The averaged slip velocity V s is computed in a given plane parallel to the interface and the effective slip length will thus depend on the specific choice for the location of this plane (e.g., top, bottom or mean of the roughness). This definition of b eff integrates out the modulation of the surface at the scale L. The effective slip length, b eff , thus defines the effective boundary condition for the velocity profile v, at scales larger than L :

v s = b eff ∂ z v x (10)
The friction force on the surface can be obtained from the pressure P and viscous stress tensor σ at the solid interface ∂Σ :

F f = ∂Σ -P I + σ • dS (11)
with I the unit tensor. From the previous definition, the calculation of the effective slip length therefore reduces to the resolution of the initial (pure) hydrodynamic problem, involving the evaluation of the hydrodynamic velocity field and pressure fields. These fields are obtained from Stokes equation, complemented by the local boundary condition on the interface, with local slip lengths {b}.

As a first example of such a procedure we consider the simple case of flow past a wavy solid surface. For simplicity we consider a flow velocity perpendicular to the modulation of the surface, so that the situation is effectively two dimensional. The effective slip length is obtained in terms of the geometrical parameters of the interface, the period λ = 2π/q and amplitude u (≪ λ) of the roughness : b eff = λ 2π f (qu). In the case where a perfect slip boundary condition applies locally on the surface, one obtains f (qu) ∝ (qu) -2 [26], while for a local no-slip boundary condition on the surface, f (qu) ∝ (qu) 2 [27]. In both cases, the effective boundary condition applies at the averaged position of the surface. Though simple, these results provide some interesting insights into the nature of effective boundary condition :

• The result for the perfectly slipping interface shows that roughness inevitably decrease slippage. The friction originates accordingly in the viscous dissipation as the fluid flows past the roughness pattern. This result was first pointed out by Richardson [28], who showed that the no-slip boundary condition measured at the macroscopic scale follows from the roughness of surfaces. Recent MD simulations confirm this result [6,29].

• On the other hand the result for a wavy surface with a local no-slip boundary condition suggests an effective slip on a wavy no-slip surface, while an increased dissipation is expected on a modulated surface. This is a direct consequence of the choice for the position of the boundary plane, where the effective boundary condition applies : for the above results the averaged position has been chosen. For a boundary plane position at the bottom of the interface, the effective slip length is shifted by -u and thus negative, in agreement with the increased dissipation on the modulated surface. This shows that the effective BC applies at some position between the bottom and top of the roughness.

• The above results applies for a single surface. If the flow is conducted in a channel with two confining surfaces separated by a distance H, the above expressions for the effective slip lengths are modified, and do depend on H ! (see eg [27]). Such a dependence is exhibited when the gap size compares with the roughness period H λ. This points to the fact that effective boundary condition is not a characteristic of the liquid-solid interface solely, but may depend on the flow configuration when the surface modulation scale L ≡ λ becomes comparable (or larger) than the flow scale L ≡ H.

B. Slippage on superhydrophobic surfaces

Another situation which has been the object of a strong interest over the recent years is that of superhydrophobic surfaces. These surfaces combine hydrophobicity at the molecular scale with roughness at intermediate scales, leading to the so-called "Lotus leaf effect" [30]. The roughness amplifies the natural non-wetting caracter of the surface, leading to very large contact angles -up to 175 • for a liquid drop on the surface. We consider here the situation where the liquid surface remains at the top of the roughness (Cassie state). The liquid surface is in contact with the solid only through a small fraction φ s of the surface, while the remaining is free-standing. At the hydrodynamic level, this composite surface leads to a spatially dependent boundary condition with a noslip boundary condition on the real solid-liquid interface (with fraction φ s ), while the remaining surface is characterized by a perfect slip boundary condition (b = ∞) on the liquid-vapor interface.

Although the hydrophobicity of the surface at the molecular scale tends (according to the discussion of section II) to increase the slip length at small scale, the essential role of hydrophobicity is here a structural rather than dynamical one. The rough hydrophobic surface replaces part of the liquid solid interface with a stress free liquid vapour interface.

This problem has been first tackled theoretically by Philip [31] and more recently by Lauga and Stone [32] and Cottin-Bizonne et al. [33]. Several numerical approaches have also been proposed either at the molecular scale, using molecular dynamics [START_REF] Cottin-Bizonne | Houille Blanche-revue Internationale De L Eau[END_REF], or at larger mesoscopic scales using finite element methods, Lattice Boltzmann or phase field models [START_REF] Priezjev | [END_REF]36,37]. For a pattern composed of stripes, the expression for the effective slip length b eff depends on the direction of the flow. For a flow parallel to the stripes, b eff reads :

b eff = L π log( 1 cos[ π 2 (1 -φ s )] ) (12)
For a flow in the direction perpendicular to the flow, the result is given by the above expression divided by a factor 2. These expressions exhibit a weak (logarithmic) dependency on φ s . In practice, the logarithmic term only varies in the interval [0.4; 1.0] for φ s between 0.1 and 5%, i.e. for feasible surfaces. At a qualitative level, the theoretical results for the stripes can be summarized by stating that the effective slip length b eff essentially saturates at the value fixed by the lateral scale of the roughness L, with an unfavorable prefactor (1/(2π) in Eq. ( 12)). For example Eq. (12) shows that a slip length larger than the period of the pattern, b eff = L, is obtained only when φ s ≤ 10 -3 . A large slippage is therefore difficult to obtain within the stripe geometry.

Another, more 'natural', geometry is that of a pattern of posts (see figure 2). In this case the hydrodynamic model consists in assuming a flat interface with a no-slip BC on the top of the posts, while the remaining of the surfaces obeys a shear-free BC.

No analytical resolution of Stokes equation with this set of boundary conditions has been performed up to now. However a simple 'scaling' argument accounts for the effective slip length in the limit of a small fraction φ s of solid zones [38]. The friction force on the surface reduces to the force on the solid zones F f = Aφ s η γs , with γs the averaged shear rate on the solid patch. To estimate γs , one may note that the velocity profile in the liquid is influenced by the solid zones only in a region of their size, a, in all directions : this behavior is due to the Laplacian character of the Stokes equation obeyed by the fluid velocity. One therefore expects γs ∼ U/a, where U is the slip velocity of the fluid on the free slip zones. Therefore F ≃ Aφ s ηU/a. Now the effective slip length is defined by F f = AV /b eff , with V ≈ U the slip velocity. One therefore deduces, in the limit φ s → 0,

b eff ∝ a φ s . ( 13
)
For a pattern made of individual posts, φ s = (a/L) 2 , and b eff ∼ L 2 /a ∼ L/ √ φ s . A numerical resolution of the Stokes equation with a pattern of no-slip square dots confirms the validity of the heuristic argument above in the limit of small φ s (basically φ s < 40%) [38]. It moreover gives the prefactor of the predicted relationship, which is very close to 1/π, so that [38] (in the limit φ s → 0):

b eff ≃ 1 π L √ φ s (14)
This simple prediction would deserve an analytical justification, which has not been performed up to now. We note that the above argument is independent of the geometry of the pattern -posts or stripes -and one should recover the expression in Eq. ( 12) for stripes. For solid zones made of stripes, we have φ s = a/L, so that b eff ∼ L : up to slowly varying logarithmic terms, this is in good agreement with the Philip-Lauga-Stone prediction, b eff ∼ L/ log(1/φ s ). As we emphasized above, in this geometry, the effective slip length is mainly fixed by the roughness period, L.

From the experimental point of view, several experimental studies have been conducted to measure slippage effects on superhydrophobic surfaces. Using pressure drop experiments, Rothstein and coworkers have reported slip lengths in the micron range on patterns of stripes [39,40], with periodicity of the stripe in the tens of microns range (up to 150µm). Experiments are in good agreement with the prediction of hydrodynamic model of Philip [31]. More recently Choi et al. performed slip measurements on the same geometry but with nanoscale patterns [41], showing a slip length of a few hundred of nanometers, again in agreement with theoretical hydrodynamic predictions.

On surfaces made of a pattern of pillars and using rheological measurements, Choi and Kim [42] reported slip lengths in the tens of micron range on a surface made of nanoposts, b eff ≃ 20µm for water. The expression for the slip length on dilute posts derived above, b eff ≃ 1 π L/ √ φ s , requires a very small solid fraction in their case to reach a 20µm slip length (with L ∼ 1µm) : φ s ∼ 0.03%. The contact angle on such surfaces with ultra-low solid fractions is expected to be very close to 180•: with this solid fraction a contact angle of 179 • i sexpected, on the basis of the Cassie relationship [43], and assuming a contact angle of θ 0 = 110 • on the solid posts. Contact angles ∼ 180 • are indeed reported by Choi and Kim for their 'nanoturf' surface [42]. Note that the slip length is strongly dependent on the solid fraction in this regime : for example a slip length of 4.5µm is predicted for a solid fraction of φ s = 0.5%, corresponding to a contact angle of 175 • . More recently, and using also rheological measurements, Truesdell et al. report huge slippage (in the millimeter range) for surfaces with a strip geometry [44], while φ s ∼ 50% in their case. This result is at odds with theoretical expectations and would require further verifications. This points to the experimental difficulties to measure slippage effects inherent to rheological measurements, see Ref. [45]. Eventually, we mention the results of Joseph et al. who measured slip length on superhydrophobic carbon nanotube carpets using microparticle velocimetry (µ-PIV)measurements. Slip lengths in the micron range are found and measured to be proportional to the underlying pattern period L (with fixed surface fraction of solid φ s ∼ 0.15 in their case) [46]. This results is in full agreement, both qualitative and quantitative, with theoretical predictions of Eq. ( 14).

As an overall conclusion, these results and predictions do show that very large slip lengths may be obtained only at the expense of important efforts to obtain nanoengineered surfaces with very small solid fraction. Typically, slip length larger than tens of microns are expected only with micro-patterned surfaces for which the measured contact angle is larger than 178 • . This is a very stringent condition.

C. Effective boundary condition on porous surfaces

In this context, it is interesting to point out the differences and similarities between our approach of ideal or structured interfaces and the approach used in the field of porous media. Effective slip boundary conditions at the interface between a bulk liquid and a porous media have been introduced empirically by Beavers and Joseph [47,48,49], and strongly resemble equation [START_REF] Bocquet | [END_REF]. They can be justified on the basis of matching a Brinkman description of the flow field in the porous media

η e f f ∇ 2 v -∇P = η K v ( 15
)
with the standard Stokes flow in the fluid. The resulting boundary condition is

∂ z v x (0) = η ef f /η K (v x (0) -U ) ( 16
)
where K is the permeability of the porous medium, and U = -K∇P is the drainage velocity deep inside the porous wall. This condition is often empirically modified to account for variations in the local permeability or viscosity near the interface [49]. From a conceptual viewpoint, this approach is different from the one described in section II, as it does not attribute physical properties to the interface. Rather, the usual hydrodynamic approach is used everywhere, with particular approximations relevant to porous media. The approach described in the present section is somewhat closer in spirit, with the difference that it uses essentially exact results to describe the flow in the interfacial region.

IV. ANALOGY WITH THERMAL BOUNDARY CONDITIONS

An interesting analogy can be established between the flow of a fluid past a solid interface [50], and the flow of heat (or energy) transport across an interface. Let us consider two media (1 and 2) separated by an ideal planar interface perpendicular to the z axis, and a steady heat flux J = Je z perpendicular to the interface. Each medium is assumed to be described by Fourier's law, with conductivity κ i . The temperature profile in medium i is linear

T i (z) = J κ i z + T i (0) (17)
The temperature jump at the interface, T 1 (0) -T 2 (0), is the exact analog of the slip velocity. Again, note that T i (0) can be defined unambiguously as extrapolations of the bulk temperature field in the interface region, without any reference to a local temperature at the interface. A constitutive equation for the interfacial region is written in analogy with equation ( 2)

T i (0) -T 2 (0) = 1 R K J ṅ12 (18)
Equation ( 18) defines the Kapitsa resistance R K (also known as thermal boundary resistance), as the transport coefficient describing the thermal effect of the interface.

In order to complete the analogy with the slip length, a "Kapitsa length" ℓ K can be defined using a suitable thermal conductivity, e.g. κ 1 . ℓ K = R K κ 1 is then the the thickness of material 1 which is thermally equivalent to the interface. This transport coefficient has been extensively studied in the context of semiconductor physics, where the resistance can be interpreted in terms of phonon scattering at the interface [51]. It is also well known in the field of superfluid liquid helium [51] (where Kapitsa originally introduced the notion), where the very large conductivity of Helium II makes the effect particularly important. A Kubo formula similar to (4) can be formulated and reads [50,52] 1

R K = S k B T ∞ 0 dt q(t)q(0) (19)
where q(t) is the heat flux (per unit area) across the interface at time t, and S is the interfacial area. For simple fluid/solid interfaces, the effect of the Kapitsa resistance has attracted much less attention. In the recent years a number of numerical and experimental studies have appeared, motivated in particular by the interest in thermal properties of "nanofluids" (colloidal solution of oxide or metallic particles). The general trend from simulation results [50,53] is that the Kapitsa length will depend on the interfacial or wetting properties in a way that is comparable to the slip length. A weaker affinity between the solid and the liquid, will result in higher resistances. Other ingredients, that are irrelevant for the slip length, include the difference in acoustic impedance between the liquid ans the solid [54]. Experimental studies involve transient absorption or transient reflectivity experiments [55,56]. Typical values found for G = 1/R K are in the range 50 -300GW.m -2 .K -1 , with the smallest values obtained for hydrophobic interfaces in contact with water [53,56]. This corresponds to a Kapitsa length (using the heat conductivity of water) of order 12nm, indeed comparable to the slip length at similar interfaces. If an attempt to model such a resistance through an "equivalent vapor layer" is made, a thickness of the order of one molecular size is found. This shows again that such transport coefficients are intrinsically interfacial properties, that cannot be assigned to the existence of a different "phase" at the interface.

We are not aware of any theoretical or experimental studies of heat transport across structured interfaces similar to those studied above for the slip properties. Obviously, strong effects, involving thermally driven dewetting, could be expected in the case of structured hydrophobic surfaces.

V. THE EXPECTED BENEFITS OF SLIPPAGE A. permeability and hydrodynamic dispersion

One of the reason for the recent interest in slippage is that it may facilitate flows in micrometric chanel, e.g. for microfluidic purposes. A simple calculation shows that for a pressure drop flow in a slit with thickness h and slip length b on the surfaces, the mean velocity is increased by a factor 1 + 6b/h as compared to the no-slip surfaces [63]. Slippage thus increases the permeability of channels and porous materials. A second interesting property of slip flows is the reduction of hydrodynamic dispersion of a probe transported in the channel using a pressure drop flow. This dispersion originates in the vanishing velocity at the surface, while it is maximum in the middle of the channel. For slipping surfaces, the velocity does not vanish at the surface, thereby reducing the difference between the maximum and minimum velocities. A criterium for dispersion may be defined as ∆v = (v max -v min )/v max , which for a slipping channel equals ∆v = (1 + 4b/h) -1 .

For both phenomena, the efficiency of slippage is determined by the ratio b/h. This shows that micrometric slip lengths have to be reached for the slippage effects to be relevant for microfluidic purposes. As discussed above, this requires a specific engineering of the surfaces since slip lengths on bare surfaces are well below the micron (b ∼ 20nm for water on hydrophobic surfaces). For example, for a channel with size H ∼ 10µm and a slip length b ∼ 20nm, the increase of permeability is of order of one percent ! For a slip length b ∼ 2µm as measured e.g. in [46], this permeability is more than twice its value for no-slip surfaces.

B. Interfacial transport phenomena

The above discussion relies on the fact that the flow is driven on the scale of the channel h. However alternative methods do generate flows within the interfacial structure at the solid-liquid interface. Electro-osmosis, i.e. flow generation by an electric field, is one such example which is commonly used in microfluidics. As discussed in references [57,58,59] these interfacially driven transport phenomena are considerably amplified by surface slippage, even for nanometric slip length. The reason for this amplification is that slip length b now compares with the thickness of the interfacial structure λ, and one expects a amplification ratio for the transport of order b/λ. For typical conditions, this ratio is larger than one even for nanometric slip lengths and slippage strongly increase the efficiency of interfacial transport phenomena.

Let us precise the underlying mechanisms on the example of electro-osmosis. Under the application of an electric field E, the solvent acquires a plug flow like velocity profile, with a velocity v EO proportional to E and given by the Smoluchowski formula :

v EO = - ǫζ η E (20)
with ǫ the dielectric permittivity of the solvent, η its viscosity; ζ is the Zeta potential of the surface, which is traditionally assumed to match the electrostatic potential at the position where the velocity profile vanishes (the shear-plane position) [START_REF] Hunter | Foundations of colloid science[END_REF]. Electro-osmosis originates within the Debye layer at the interface [START_REF] Hunter | Foundations of colloid science[END_REF]. The Debye layer quantifies the width of the interfacial regions at a charged surface and results from the competition between the attraction of ions at the charged surface and entropic effects. Its typical size λ D depends on the salt concentration in the liquid, and is of the order of a few nanometers : λ D ∼ 3nm for a concentration of salt of 10 -2 molar. The interfacial Debye layer is electrically charged, while the remaining bulk solvent is electrically neutral. Therefore, when applying an electric field, the electric driving force is located within the Debye layer only. The driving force per unit surface acting on the liquid thus writes f e = σE with σ the charge of the Debye layer, which is exactly opposite to the surface charge σ ≃ ǫV 0 /λ D , for weak surface potentials V 0 . This leads to f e ≃ -ǫ V0 λD E. Now the electro-osmotic velocity results from the balance between this electric driving force in the Debye layer and the viscous stress at the surface. For a no-slip boundary condition, the latter is f η ∼ ηv EO /λ D , since the velocity varies on a scale given by the Debye length. If slippage is exhibited at the surface, the velocity varies on the size λ D + b and the viscous stress becomes accordingly f η = ηv EO /(λ D + b), lower than for the no-slip BC. Gathering these results we get

η v EO λ D + b ∼ -ǫ V 0 λ D E (21)
This simple argument leads to the Smoluchowski formula, Eq. ( 20), and provides an expression of the zeta potential in the form

ζ = V 0 1 + b λ D (22)
This expression can be obtained using more rigourous description, see [START_REF] Joly | Houille Blanche-revue Internationale De L Eau[END_REF]57,59]. Molecular dynamics simulations of charge transport confirm fully this relationship [START_REF] Joly | Houille Blanche-revue Internationale De L Eau[END_REF]57]. They show, furthermore, that for a non-slipping surface V 0 can be identified with the potential at the plane of shear V 0 = V (z s ), with z s of the order of one liquid layer. As expected a strong amplification of charge transport is therefore demonstrated on slipping surfaces. This behaviour can be generalized to all interfacial transport phenomena. As practical examples, one may cite diffusio-osmosis and thermo-osmosis. These two phenomena correspond to the induction of a flow by the gradient of a solute concentration for the former and by a gradient of temperature for the latter [START_REF] Anderson | [END_REF]. The flow velocity for these phenomena is found to be proportional to the applied gradient of the observable O under consideration (electric potential, concentration, temperature) :

v s = - 1 η ΓL.[1 + b/L]. dO dx (23)
Γ and L defined in terms of the (equilibrium) interfacial stress anisotropy, Σ eq (x, y) = σ n -σ t : Γ = ∞ 0 dy. ∂Σeq ∂O (y), and L = Γ -1 ∞ 0 dy.y.

∂Σeq ∂O (y). These quantities are length scales of the order of the range of interaction of the solute with the solid surface [58] The origin of the phenomena thus lies in the thin interface layer of size L where the solute interacts specifically with the surface. For the diffusio-osmosis phenomena, the driving force is an osmotic pressure gradient within the interface layer. For thermo-osmosis, this is surface energy gradient induced by the temperature dependence of the stress anisotropy.

For all these phenomena, slippage again amplifies the transport phenomena with a ratio b/L. Slippage, even nanometric, is therefore relevant to amplify interfacial transport in microfluidic systems.

VI. PERSPECTIVES

In this short review, we have tried to establish a clear picture of our present understanding of slippage at different scales. At the molecular scale, we consider surfaces as ideal and introduce an "intrinsic" constitutive relation for the interface. The corresponding slip length depends strongly on the nature of intermolecular interactions (hydrophobicity effect), but stays within "molecular" orders of magnitude, a few ten nanometers at most.

A different picture is obtained by considering surfaces structured on an intermediate scale. To describe such situations, we adopt a mesoscopic view of the interface, in which the molecular details are hidden in a local, position dependent slip length. Such a view can be validated through molecular simulations. Hydrophobicity effects are essential to reduce the contact area between solid and liquid, so that a significant reduction of the solid-liquid friction is obtained. When this reduction is achieved, much larger slip lengths can be observed. The slip length is essentially determined by the scale of the surface pattern and the surface area of the "dewetted" part, on which a perfect slip boundary condition applies at the local level.

This description at two different levels is necessary to describe the full complexity of surfaces that can now be engineered at a submicrometer scale, with a combination of local hydrophobic properties and of a complex geometric pattern. For patterns whose typical scale is much larger than the intrinsic slip length, the separation of lengths scales allows a complete decoupling between the molecular and the hydrodynamic descriptions. Molecular simulations indicate that the same type of approach is possible, even when the length scale of the pattern and the intrinsic slip length are similar.

From this complete theoretical description, it is clear that the control of actual flow properties through surface engineering necessitates a control of the surface state at each different scale. When such a control is achieved, the flow of simple liquids appear to be relatively well understood, both experimentally and theoretically. More complex situations, such as the amplification of interface driven flows by molecular slippage described in section V B, have not been studied experimentally in detail yet, but are promising for the design of microfluidic devices.

In section IV we discussed the analogy between "temperature slip" and "velocity slip". Experiments and simulations have already shown that this analogy can be made quantitative, at least when ideal surfaces are concerned. The role of nano-structuration of the surfaces for thermal transport has not been explored up to now. Nonlinear effects may be expected for strong heat fluxes, while cross effects between heat and momentum transport are expected to be negligible, based on symmetry arguments.

Finally, it could be interesting, at least from a formal point of view, to extend the above discussion of heat and momentum transport across an interface to diffusive mass transport. The standard description assumes a local partition equilibrium at the interface, or equivalently a continuity of the chemical potential. Following the approach outlined here, it would seem more consistent to introduce a discontinuity in chemical potential proportional to the diffusive flux across the interface. The magnitude of this discontinuity has not, to our knowledge, be explored at the molecular scale.

FIG. 1 :

 1 FIG. 1: Schematic representation of the definition of the slip length b

FIG. 2 :

 2 FIG. 2: Schematic representation of a surface patterned with nanoposts, and equivalent representation in terms of flow boundary conditions.

FIG. 3 :

 3 FIG. 3: Schematic representation of electro-osmotic flow past a slippery surface.

Acknowledgments

We thank A. Ajdari, C. Barentin, E. Charlaix, C. Cottin-Bizonne, P. Joseph, L. Léger, and C. Ybert for many stimulating discussions.


Seth Gilbert
email: seth.gilbert@comp.nus.edu.sg

Calvin Newport
email: cnewport@cs.georgetown.edu

The Computational Power of Beeps

We study the quantity of computational resources (state machine states and/or probabilistic transition precision) needed to solve specific problems in a single hop network where nodes communicate using only beeps. We begin by focusing on randomized leader election. We prove a lower bound on the states required to solve this problem with a given error bound, probability precision, and (when relevant) network size lower bound. We then show the bound tight with a matching upper bound. Noting that our optimal upper bound is slow, we describe two faster algorithms that trade some state optimality to gain efficiency. We then turn our attention to more general classes of problems by proving that once you have enough states to solve leader election with a given error bound, you have (within constant factors) enough states to simulate correctly, with this same error bound, a logspace TM with a constant number of unary input tapes: allowing you to solve a large and expressive set of problems. These results identify a key simplicity threshold beyond which useful distributed computation is possible in the beeping model.

Introduction

The beeping model of network communication [1-3, 10, 14, 20] assumes a collection of computational nodes, connected in a network, that interact by beeping in synchronous rounds. If a node decides to beep in a given round, it receives no feedback from the channel. On the other hand, if a node decides to listen, it is able to differentiate between the following two cases: [START_REF] Afek | Beeping a maximal independent set[END_REF] no neighbor in the network topology beeped in this round, and (2) one or more neighbors beeped.

Existing work on this model provide two motivations. The first concerns digital communication networks (e.g., [START_REF] Cornejo | Deploying wireless networks with beeps[END_REF][START_REF] Degesys | Desync: self-organizing desynchronization and tdma on wireless sensor networks[END_REF]). Standard network communication (in which nodes interact using error-corrected packets containing many bits of information) requires substantial time, energy, and computational overhead (at multiple stack layers) to handle the necessary packet encoding, modulation, demodulation, and decoding. Beeps, on the other hand, provide an abstraction capturing the simplest possible communication primitive: a detectable burst of energy. In theory, beep layers could be implemented using a fraction of the complexity required by standard packet communication, establishing the possibility of micro-network stacks for settings where high speed and low cost are crucial.

The second motivation for the beeping model concerns a connection to biological systems (e.g., [START_REF] Afek | A biological solution to a fundamental distributed computing problem[END_REF][START_REF] Navlakha | Distributed information processing in biological and computational systems[END_REF][START_REF] Scott | Feedback from nature: an optimal distributed algorithm for maximal independent set selection[END_REF]). Network communication in nature is often quite simple; e.g., noticing a flash of light from nearby fireflies or detecting a chemical marker diffused by nearby cells. Therefore, understanding how to achieve distributed coordination using such basic primitives can provide insight into how such coordination arises in nature (see [START_REF] Navlakha | Distributed information processing in biological and computational systems[END_REF] for a recent survey of this approach).

A Key Question. As detailed below, existing work on the beeping model seeks to solve useful problems as efficiently as possible in this primitive network setting. In this paper, by contrast, we focus on solving useful problems as simply as possible (e.g., as measured by factors such as the size of the algorithm's state machine representation), asking the key question: is it possible to solve problems with both simple communication and simple algorithms? Notice, the answer is not a priori obvious. It might be the case, for example, that complexity is conserved, so that simplifying the communication model requires more complex algorithms. Or it might be the case that simple algorithms coordinating with beeps are sufficient for even complex tasks. Given the above motivations for studying beeps, answering this question is crucial, as it will help us probe the feasibility of useful networked systems-whether constructed by engineers or evolution-that are truly simple in both their communication methods and control logic.

Our Answers. Consider a collection of n nodes connected in a single hop topology (i.e., the network graph is a clique). We model the randomized process executing on each node as a probabilistic state machine. The two parameters describing the complexity of these algorithms are: [START_REF] Afek | Beeping a maximal independent set[END_REF] an upper bound on the number of states (indicated by integer s ≥ 1); and (2) an upper bound on the precision of the probabilistic transitions (indicated by integer q ≥ 2, where we allow probabilistic transitions to be labeled with probability 0, 1, or any value in the interval [ 1 q , 1 -

1 q ]
). We ask how large these values must grow to solve specific problems. Our motivating premise is that smaller values imply simpler algorithms. (Notice, by considering both s and q, we can capture the trade-off between memory and probabilistic precision, a question of standalone interest; c.f., [START_REF] Lenzen | Trade-offs between selection complexity and performance when searching the plane without communication[END_REF]). We begin by considering leader election, a fundamental primitive in distributed systems. We prove that for a given error bound ∈ [0, 1/2] and probabilistic precision q, any algorithm that solves leader election with probability 1 -requires s = Ω(log q (1/ )) states. Given a lower bound N on the size of the network, this lower bound reduces to s = Ω(log q (1/ )/ N ) states. Thus, the more nodes in the network, the fewer states each node needs to solve the problem.

This lower bound leverages a reduction argument. We begin by defining and lower bounding a helper problem called (1, k)-loneliness detection, which requires an algorithm to differentiate between n = 1 and n ≥ k (but has no requirements for intermediate network sizes). This bound uses an indistinguishability argument regarding how nodes move through a specified state sequence. We then show how to transform a solution to leader election for size lower bound N , to solve (1, N )-loneliness detection-allowing our loneliness bound to carry over to leader election.

We then turn our attention to leader election upper bounds. We begin by proving our lower bound tight by showing, for every network size lower bound N ≥ 1, how to solve leader election with s = O(log q (1/ )/ N ) states. The key idea behind this algorithm is to have nodes work together to implement a distributed timer. The more nodes in the network, the longer the distributed timer runs, and the longer the distributed timer runs, the higher the probability that we succeed at leader election. In this way, increasing the network size reduces the states required to hit a specific error bound. A shortcoming of this new algorithm, however, is that its expected running time is exponential in the network size. With this mind, we then describe two faster algorithms (their time is polylogarithmic in the relevant parameters) that require only the minimum precision of q = 2. The cost for their efficiency, however, is a loss of state optimality in some circumstances.

The first algorithm requires s = O(log (1/ )) states and solves leader election with probability at least 1 -, for any network size n. It terminates in O(log (n + 1/ ) log (1/ )) rounds, with probability at least 1 -. The key idea behind this algorithm is to test a potentially successful election by having the potential leader(s) broadcast with probability 1/2 for log (1/ ) rounds, looking for evidence of company. It is straightforward to see that a single such test fails with probability no more than (1/2) log (1/ ) = . The problem, however, is that as the network size grows, the number of such tests performed also increases, making it more likely that one fails. We neutralize this problem in our analysis by showing that the test failure probabilities fall away as a geometric series in the test count-bounding the cumulative error sum as the network grows.

The second algorithm requires only s = O(1) states, and yet, for every network size n, it solves leader election with high probability in n when run in a network of that size. It requires only O(log 2 n) rounds, with high probability.

The key idea driving this algorithm is to harness the large amount of total states in the network to implement a distributed timer that requires Θ(log n) time to countdown to 0, when executed among n nodes. This duration is sufficient for the nodes to safely reduce contention down to a single leader.

After studying leader election, we turn our attention to more general classes of distributed decision problems. Leveraging our leader election algorithms as a key primitive, we show how to simulate a logspace decider Turing Machine (TM) with a constant number of unary inputs (all defined with respect to the network size n). Perhaps surprisingly, this algorithm requires only O(log (1/ )) states to complete the simulation with probability 1 -, and only O(1) states to achieve high probability in n. (Notice that this is not enough states for an individual node to store even a single pointer to the tape of the simulated machine.) Our simulation uses the same general strategy first highlighted in the study of population protocols [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF]: simulate a counter machine with a constant number of counters that hold values from 0 to O(n), and then apply a transformation due to Minsky [START_REF] Minsky | Computation: finite and infinite machines[END_REF] to simulate a logspace TM with this machine. Due to the differences between the beeping and population protocol models, however, our counter machine simulation strategies are distinct from [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF].

Implications. The results summarized above establish that the log (1/ ) state threshold for leader election with bounded error is (in some sense) a fundamental simplicity threshold for solving useful problems with beeps. It is striking that if you have slightly less than this much memory, even the basic symmetry breaking task of leader election is impossible, but if you instead have slightly more, then suddenly you can solve large classes of complicated problems (i.e., everything solvable by a logspace TM). If you are satisfied with high probability solutions (which is often the case), then this treshhold reduces even more all the way down to O(1). Given these results, we tentatively claim a positive answer to the key question posed above: complexity is not destiny; you can solve hard problems simply in simple network models.

Before proceeding into the technical details of our paper, we will first take the time to place both our model and our results in the context of the several different areas of relevant related work. Among other questions, we want to understand the relationship of our bounds to existing beep results, and how the beeping model compares and contrasts to similar settings.

Comparison to Existing Beep Results. The algorithmic study of beeping networks began with Degesys et al. [START_REF] Degesys | Desync: self-organizing desynchronization and tdma on wireless sensor networks[END_REF], who introduced a continuous variant of the beeping model, inspired by the pulse-coupled oscillator framework. They studied biologically inspired strategies for solving a desynchronization problem. Follow-up work generalized the results to multihop networks [START_REF] Degesys | Towards desynchronization of multi-hop topologies[END_REF][START_REF] Motskin | Lightweight coloring and desynchronization for networks[END_REF]. Cornejo and Kuhn [START_REF] Cornejo | Deploying wireless networks with beeps[END_REF] introduced the discrete (i.e., round-based) beeping model studied in this paper. They motivated this model by noting the continuous model in [START_REF] Degesys | Towards desynchronization of multi-hop topologies[END_REF][START_REF] Degesys | Desync: self-organizing desynchronization and tdma on wireless sensor networks[END_REF][START_REF] Motskin | Lightweight coloring and desynchronization for networks[END_REF] was unrealistic and yielded trivial solutions to desynchronization, they then demonstrated how to solve desynchronization without these assumptions. Around this same time, Afek et al. [START_REF] Afek | A biological solution to a fundamental distributed computing problem[END_REF] described a maximal independent set (MIS) algorithm in a strong version of the discrete beeping model. They argued that something like this algorithm might play a role in the proper distribution of sensory organ precursor cells in fruit fly nervous system development. Follow-up work [START_REF] Afek | Beeping a maximal independent set[END_REF][START_REF] Afek | Beeping a maximal independent set[END_REF][START_REF] Scott | Feedback from nature: an optimal distributed algorithm for maximal independent set selection[END_REF] removed some of the stronger assumptions of [START_REF] Afek | A biological solution to a fundamental distributed computing problem[END_REF] and improved the time complexity. In recent work, Förster et al. [START_REF] Förster | Deterministic leader election in multihop beeping networks[END_REF] considered deterministic leader election in a multihop beeping network.

To place this paper in this context of the existing work on the beeping model, it is important to note that the above-cited papers focus primarily on two goals: minimizing time complexity and minimizing information provided to nodes (e.g., network size, max degree, global round counter). They do not, however, place restrictions on the amount of states used by their algorithms. Accordingly, these existing results require either: the ability to store values as large as Θ(n) [1-3, 10,20], or uniques ids [START_REF] Förster | Deterministic leader election in multihop beeping networks[END_REF] (which in our framework would require a machine with n different initial states, or equivalently, n different machines). In this paper, we prove that the algorithmic complexity threshold for solving many useful problems is actually much lower: O(1) states are sufficient for high probability results and O(log (1/ )) states are sufficient for fixed error bound results. 3 We argue the direction pursued in this paper (how complex must algorithms become to solve useful problems with beeps) complements the direction pursued in existing papers (how fast can algorithms solve useful problems with beeps). Answers to both types of queries is necessary to continue to understand the important topic of coordination in constrained network environments.

Comparison to the Radio Network Model. The standard radio network model allows nodes to send large messages, but assumes concurrent transmissions lead to message loss (that may or may not be detectable). The key difference between the radio network model and the beeping model is that in the former you can recognize the case where exactly one node broadcast (e.g., because you receive a message). This capability, which the beeping model does not offer (a single beeper looks like multiple beepers), is powerful. It allows, for example, algorithms that can solve leader election with deterministic safety using only a constant amount of state, when run in network of size at least 2. If you assume receiver collision detection, these solutions require only polylogarithmic expected time. 4These results violate our lower bounds for leader election with beeps (where the state size grows toward infinity as you drive the error bound toward 0)indicating that the communication limitations in the beeping model matter from a computability perspective.

Comparison to the Stone Age Computing Model. It is also important to place our results in the context of other simplified communication/computation models. Consider, for example, the stone age distributed computing model introduced by Emek and Wattenhofer [START_REF] Emek | Stone age distributed computing[END_REF]. This model assumes state machines of constant size connected in a network and executing asynchronously. The machines communicate with a constant-size message alphabet and when transitioning can distinguish between having received 0, 1, or ≥ b messages of each type, for some constant parameter b ≥ 1. For b = 1, this model is essentially an asynchronous version of the beeping model. To this end, nodes in our model can simulate nodes in the stone age model with b = 1 indefinitely using a constant number of states. For b > 1, however, any such simulation likely becomes impossible in the beeping model with a constant number of states. As noted in our discussion of the radio network model, the ability to safely recognize the case of exactly one message being sent provides extra power beyond what is achievable (without error) using only beeps.

Comparison to the Population Protocol Model. Another relevant simplified communication/computation setting is the well-studied population protocol model [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF][START_REF] Angluin | Stably computable predicates are semilinear[END_REF][START_REF] Angluin | Fast computation by population protocols with a leader[END_REF][START_REF] Angluin | A simple population protocol for fast robust approximate majority[END_REF][START_REF] Angluin | The computational power of population protocols[END_REF][START_REF] Chatzigiannakis | The dynamics of probabilistic population protocols[END_REF] . This model describes nodes as state machines of constant size that interact in a pairwise manner-transforming both states asymmetrically. In the basic version of the model, a fair scheduler chooses pairs to interact. A version in which the scheduler is randomized adds more power. There are similarities in the goals pursued by the beeping and population protocol models: both seek (among other things) to understand the limits of limited state in distributed computation. The core difference between the two settings is the role of the algorithm in communication scheduling. In the beeping model, algorithms must reduce contention and schedule communication on their own. In the population protocol model the scheduler ensures fair and reliable interactions. Imagine, for example, a continuous leader election problem where every node has a leader bit, and the problem requires in an infinite execution that: (1) every node sets leader to 1 an infinite number of times; and (2) there is never a time at which two nodes both have leader set to 1. This problem is trivial in the population protocol: simply pass a leader token around the network. In the beeping model, by contrast, it is impossible as it essentially requires nodes to solve leader election correctly an infinite number of times-a feat which would require an unachievable error bound of 0. It follows that in some respects these two models are studying the impact of limited state on different aspects of distributed computation.

Model

We model a collection of n probabilistic computational agents (i.e., "nodes") that are connected in a single hop network and communicate using a unary primitive; i.e., beeps. They execute in synchronous rounds in which each node can either beep or receive. Receiving nodes can distinguish between the following two cases: (1) no node beeped; (2) one or more nodes beeped. We characterize these agents by s (a bound on the number of states in their state machine), and q (a bound on the precision allowed in probabilistic transitions, with larger values enabling more accurate transition probabilities). In more detail: Node Definition. We specify the algorithm executing on each node as a probabilistic state machine M = (Q r , Q b , q s , δ ⊥ , δ ), where: Q r and Q b are two disjoint sets of states corresponding to receiving and beeping, respectively; q s is the start state; and δ ⊥ and δ are the probabilistic transition functions 5 for the cases where the node detects silence and where the node beeps/detects a beep, respectively. Some problems have all nodes execute the same state machine, while others include multiple machine types, each corresponding to a different initial value.

Executions. Executions proceed in synchronous rounds with all nodes in their machine's start state. At the beginning of round r, for a node u running a machine (Q r , Q b , q s , δ ⊥ , δ ), if its current state q u is in Q b , then u emits a beep, otherwise it receives. If at least one node beeps in r, then all nodes either beep or detect a beep in this round. Therefore, each node u applies the transition function δ to its current state q u and selects its next state according to the distribution δ (q u ). If no node beeps in r, then each node u applies the transition function δ ⊥ , selecting its next state from the distribution, δ ⊥ (q u ).

Parameters. We parameterize state machines with two values. The first, indicated by s ≥ 1, is an upper bound on the number of states allowed (i.e., |Q r | + |Q b | ≤ s). The second, indicated by q ≥ 2, bounds the precision of the probabilistic transitions allowed by the δ functions. In more detail, for a given q, the probabilities assigned to states by distributions in the range of δ must either be 0, 1, or in the interval, [ 1 q , 1 -1 q ]. For the minimum value of q = 2, probabilistic transitions can occur only with probability 1/2. As q increases, smaller probabilities, as well as probabilities closer to 1, become possible. Finally, we parameterize an execution with n-the number of nodes in the network.

Leader Election

The first computational task we consider is leader election: eventually, one node designates itself leader. An algorithm state machine that solves leader election must include a final leader state q that is terminal (once a node enters the state, it never leaves). Entering this state indicates a node has elected itself leader. For a given error bound ∈ [0, 1/2], we say an algorithm solves leader election with respect to if when executed in a network of any size, it satisfies the following two properties: (1) liveness: with probability 1, at least one node eventually enters the leader state; and (2) safety: with probability at least 1 -, there is never more than 1 node in the leader state. We also consider algorithms for leader election that are designed for networks of some minimal size N . In this case, the algorithm must guarantee liveness in every execution, but it needs to guarantee safety only if the network size n is at least N . Our goal is to develop algorithms that use a minimum number of states to solve leader election for a given error bound , probability precision q, and, when relevant, network size minimum N .

Roadmap. In Section 3.1, we present a lower bound for leader election. In Section 3.2, we present a universal algorithm template, followed by three specific instantiations in Sections 3.3, 3.4, and 3.5. Due to space constraints, proofs are deferred to the full version of this extended abstract [START_REF] Gilbert | The computational power of beeps[END_REF].

Leader Election Lower Bound

Here we analyze the number of states required to solve leader election given a fixed , q, and network size lower bound N . Our main result establishes that the number of states, s, must be in Ω(

log q (1/ ) N ).
To prove this result, we begin by defining and bounding a helper problem called (1, k)-loneliness detection, which requires an algorithm to safely distinguish between n = 1 and n ≥ k. The bound leverages a probabilistic indistinguishability argument concerning a short execution of the state machine in both the n = 1 and n = k cases. We then show that loneliness detection captures a core challenge of leader election by demonstrating how to transform a leader election algorithm that works for n ≥ N into a solution to (1, N )-loneliness detection. The bound for the latter then carries over to leader election by reduction.

(1, k)-Loneliness Detection. The (1, k)-loneliness detection problem is defined for some integer k > 1 and error bound . It assumes all nodes run the same state machine with two special terminal final states that we label q a (indicating "I am alone") and q c (indicating "I am in a crowd"). The liveness property of this problem requires that with probability 1, every node eventually enters a final state. The safety property requires that with probability at least 1 -, the following holds: if n = 1, then the single node in the system eventually enters q a ; and if n ≥ k then all nodes eventually enter q c . Crucial to this problem definition is that we do not place any restrictions on the final states nodes enter for the case where 1 < n < k.

The following bound shows that it becomes easier to break symmetry, i.e., easier to solve loneliness detection, as the threshold for detecting a crowd grows. Put another way: a big crowd is easier to detect than a small crowd. Lemma 1. Fix some integer k > 1. Let L be an algorithm that solves (1, k)loneliness detection with error bound and probability precision q using s states. It follows that s = Ω( log q (1/ ) k

).

Reducing Loneliness Detection to Leader Election. We now leverage the above result on (1, k)-loneliness detection to prove a lower bound for leader election under the guarantee that the network size n ≥ N . The proof proceeds by reduction: we show how to transform such a leader election solution into a loneliness detection algorithm of similar state size.

Theorem 2. Fix some network size lower bound N ≥ 1. Let A be an algorithm that solves leader election with error bound and probability precision q using s states in any network where n ≥ N . It follows that s ∈ Ω(

log q (1/ ) N
).

The Universal Leader Election Algorithm

We now turn our attention to leader election upper bounds. The three results that follow adopt a template/subroutine approach. In more detail, Figure 3.1 describes what we call the universal leader election algorithm. This algorithm, in turn, makes calls to a "termination subroutine." Different versions of this subroutine can be plugged into the universal algorithm, yielding different guarantees. Notice, this universal algorithm is parameterized with probability precision q and error bound , which it uses to define the useful parameter q = min{q, (1/ )}.

This algorithm (as well as one of our termination subroutines) uses 1/q, not 1/q, as its smallest transition probability (intuitively, there is little advantage in using a probability too much smaller than the bound ).

Algorithm 1 Universal Leader Election Returns 0 with prob 1/q, else 1

1: active ← 1 2: ko ← 1 3: q ← min{q, ( 1

9:

participate ← random bit(1/q) 10:

chan ←

11:

Knock Out Logic

12:

if active ∧ participate then 13:

beep()

14:

else 15:

chan ← recv()

16:

end if

17:

if active ∧ not participate then

18:

if chan = then

19:

active ← 0

20:

ko ← 1

21:

end if

22:

end if

23:

Termination Detection Logic

24:

if chan = ⊥ then

25:

done The basic operation of the algorithm is simple. Every node is initially active. Until the termination subroutine determines that it is time to stop, nodes repeatedly execute the knockout loop (lines 7-25). In each iteration of the loop, each active node beeps with probability 1 -1/q and listens otherwise. If a node ever hears a beep, it is knocked out, setting ko = true and active = f alse. In any silent iteration where no node beeps, they execute the termination subroutine to decide whether to stop. Once termination is reached, any node that remains active becomes the leader.

Termination Subroutines. The goal of the termination subroutine is to decide whether leader election has been solved: it returns true if there is a leader and false otherwise. The termination subroutine is called simultaneously by all the nodes in the system, and it is passed two parameters: the value of active, which indicates whether or not the calling node is still contending to become leader, and ko, which indicates whether or not it has been knocked out in the main loop since the last call to the subroutine. We fix R = 4 log q (max(n, 1/ )): a parameter, which as we will later elaborate, captures a bound on the calls to the subroutine needed before likely termination. We consider the following properties of a termination detection routine, defined with respect to and R:

1. Agreement: Every node always returns the same value. 2. Safety: Over the first R invocations, the probability that it returns true in any invocation with more than 1 active node is at most /2. 3. Eventual Termination: If it is called infinitely often with only one active node, then eventually (with probability 1), it returns true.

Fast Termination:

If it is called with only one active node, and with at least one node where ko = true, then it returns true.

Universal Leader Election Analysis. We now observe that the universal leader election algorithm is correct when combined with a termination subroutine that satisfies the relevant properties from above. To do so, we first determine how many rounds it takes until there is only one active node, and hence one possible leader. We say that an iteration of the knockout loop (lines 7-25) is silent if no node beeps during it. (Notice that the termination routine is only executed in silent iterations of the knockout loop.) We first bound how long it takes to reduce the number of active nodes:

Lemma 3. Given probability ≤ 1/2 and parameter R = 4 log q (max(n, 1/ )): after R silent iterations of the knockout loop (lines 7-25), there remains exactly one active node, with probability at least 1 -/2.

Let T be a termination subroutine that satisfies Agreement and Eventual Termination. In addition, assume that T satisfies safety in networks of size at least N . We can now show that the universal leader election algorithm is correct with termination subroutine T : Theorem 4. If termination subroutine T uses s states and precision q, then the universal algorithm solves leader election with error , s + O(1) states, and q precision (guaranteeing safety only in networks of size n ≥ N ).

While the preceding theorem can be used to show the feasibility of solving leader election, it does not bound the performance. For that, we rely on termination subroutines that ensure fast termination: Theorem 5. If termination subroutine T satisfies Fast Termination instead of Eventual Termination, and if it uses s states and q precision, and if it runs in time t, then the universal algorithm solves leader election with error with s + O(1) states and q precision (guaranteeing safety only in networks of size ≥ N ). Furthermore, it terminates in O(t log q (n + 1/ )) rounds, with probability at least 1 -.

Optimal Leader Election

Here we define a termination subroutine that, when combined with the universal leader election algorithm, matches our lower bound from Theorem 2. In more detail, fix an error bound and probability precision q. Fix some lower bound N ≥ 1 on the network size. We describe a termination detection subroutine that we call StateOptimal( N ) that requires O( log q (1/ ) N ) states, and guarantees Agreement, Termination, and Safety in any network of size n ≥ N .

There are two important points relevant to this leader election strategy. First, for N = 1, it provides a general solution that works in every size network. Second, the state requirements for this algorithm are asymptotically optimal according to Theorem 2. As will be clear from its definition below, the cost of this optimality is inefficiency (its expected time increases exponentially with n). We will subsequently identify a pair of more efficient solutions that gain efficiency at the cost of some optimality under some conditions.

The StateOptimal( N ) Termination Detection Subroutine. The StateOptimal( N ) subroutine, unlike the other subroutines we will consider, ignores the active and ko parameters. Instead, it runs simple distributed coin flip logic among all nodes. In more detail, recall from the definition of the universal algorithm that q = min{q, (1/ )}. The subroutine consists of δ = c log q (1/ ) N rounds, defined for some constant c ≥ 1 we will bound in the analysis. In each round, each node beeps with probability 1 -1/q. At the end of the δ rounds, each node returns 1 if all δ rounds were silent, otherwise it returns 0.

Analysis. It is straightforward to determine that all nodes return the same value from this subroutine (i.e., if any node beeps or detects a beep, all nodes will return 0). It is also straightforward to verify that implementing this subroutine for a given δ requires Θ(δ) = Θ(

log q (1/ ) N ) = Θ( log q (1/ ) N
) states (we can replace the q with q in the final step because once q gets beyond size 1/ , the function stabilizes at 1). Eventual termination is also easy to verify, as every call to the subroutine has a probability strictly greater than 0 of terminating.

To show safety, we observe that the routine returns true only if all n nodes are silent for all δ rounds. The probability of this happening is exponentially small in (δn) and hence it is not hard to show that every R invocations, the probability that the subroutine returns true in any invocation with more than one active node is at most /2. Lemma 6 (Safety). Over the first R invocations, the probability that the subroutine returns true in any invocation with more than 1 active node is at most /2.

Combined with Theorem 4, this yields the following conclusion: Theorem 7. For any network size lower bound N , error parameter and precision q, the universal leader election algorithm combined with the StateOptimal( N ) subroutine, solves leader election with respect to these parameters when run in a network of size n ≥ N , and requires only s = Θ( log q (1/ ) N ) states.

Fast Leader Election with Sub-Optimal State

The leader election algorithm from Section 3.3 can solve the problem with the optimal number of states for any combination of system parameters. It achieves this feat, however, at the expense of time: it is straightforward to determine that this algorithm requires time exponential in the network size. Here we consider a termination subroutine that trades state optimality for a solution that is fast (polylogarthmic in 1/ rounds) and simple to define (it uses the minimal probabilistic precision of q = 2). Furthermore, its definition is independent of the network size n, yet it still works for every possible n. For the purpose of this section, we assume that q = q = 2. As we show below, this subroutine uses Θ(log (1/ )) states. This is suboptimal when high precision (i.e., larger q) is available, and when there is a lower bound N on the size of the network.

The Fixed Error Termination Detection Subroutine. This termination subroutine consists of a fixed schedule of log (2/ ) + 2 rounds. During the first round, any node that calls the subroutine with parameter ko equal to 1 beeps while all other nodes receive. If no node beeps, then the subroutine is aborted and all nodes return false.

Assume this does not occur, i.e., at least one node beeps in the first round. For each of the log (2/ ) rounds that follow, every node with parameter active = 1, will flip a fair two-sided coin. If it comes up heads, it will beep, otherwise it will receive. Each node with active = 1 will start these rounds with a flag solo initialized to 1. If such a node ever detects a beep during a round that it receives, it will reset solo to 0 (as it just gained evidence that it is not alone).

The final round is used to determine if anyone detected a non-solo execution. To do so, every node with active = 1 and solo = 0 beeps. If no node beeps in this final round, then all nodes return true. Otherwise, all nodes return false.

Analysis. We proceed as before, observing that all nodes return the same value from this subroutine since all observe the same channel activity in the first and last rounds. It is also straightforward to verify that implementing this subroutine requires O(log (1/ )) states to count the rounds and record solo. Fast termination follows directly from a case analysis of the algorithm.

Lemma 8 (Fast Termination). If the Fixed Error subroutine is called with only 1 active node and with at least 1 node where ko = true, then it returns true.

Safety requires a little more care, showing that the failure probabilities over R invocations can be bounded by /2, since the error probability depends on the number of active nodes. Lemma 9 (Safety). Over the first R invocations of the subroutine, the probability that it returns true in any invocation with more than one active node is at most /2.

Combined with Theorem 5, these properties yield the following conclusion: Theorem 10. For error parameter , the universal leader election algorithm combined with the Fixed Error subroutine, solves leader election with respect to in every size network, using only s = Θ(log (1/ )) states and q = 2. With probability at least 1 -, it terminates in O(log (n + 1/ ) log (1/ )) rounds.

Fast Leader Election with O(1) States and High Probability

The final termination detection subroutine we consider requires only a constant number of states, and when executed in a network of size n, for any n > 1, it solves leader election with high probability in n. At first glance, this result may seem to violate the lower bound from Section 3.1, which notes that the state requirement grows with a log (1/ ) factor as decreases. The question is why a constant number of states is sufficient here even though this term grows with n. The answer lies in the fact that is here a function of n, such that for any fixed n, it is true that N ≥ n, and therefore the N factor in the denominator of our lower bound swamps the growth of the log n factor in the numerator.

The Constant State Termination Detection Subroutine. The subroutine here is identical to the Fixed Error subroutine, except the length of subroutine is not fixed in advance (no node has enough states to count beyond a constant number of rounds-which is not enough for our purposes). Instead, we dynamically adapt the length of the subroutine to a sufficiently large function of n using a distributed counting strategy.

In more detail, during the first round, any node that called the subroutine with parameter ko equal to 1 beeps while all other nodes receive. If no node beeps, then subroutine is aborted and all nodes will return value false (as is true for Fixed Error). Assuming the subroutine has not aborted, the nodes then proceed as follows: We partition rounds into even and odd pairs. During the odd numbered rounds, we proceed as in Fixed Error: every node with parameter active = 1, flips a fair coin; if it comes up heads, it will beep, otherwise it will receive; each node with active = 1 will start these rounds with a flag solo initialized to 1; if such a node ever detects a beep during a round that it receives, it will reset solo to 0 (as it just gained evidence that it is not alone).

During the even rounds, the nodes run a repeated knockout protocol for O(1) iterations, for some fixed constant bounded in the analysis. In more detail, each node (regardless of whether or not it has active equal to true) begins the subroutine with a flag attack = 1 and a counter count = 0. In each even round, each node with attack = 1 flips a fair coin and beeps if it comes up heads; otherwise it listens. Any node that listens in an even round and hears a beep sets attack = 0. If there is an even round in which no node beeps, then all nodes increment count and reset attack = 1. This continues until count grows larger than the fixed constant mentioned above, When this occurs, all nodes move to the final round, which is identical to the final round in Fixed Error. That is: every node with active = 1 and solo = 0 beeps. If no node beeps in this final round, then all nodes return true. Otherwise, all nodes return false.

Analysis. The Liveness and Fast Termination properties follow from the same arguments used in our analysis of Fixed Error. The main difficulty in analyzing this subroutine is proving Safety. To do so, we first bound how long the subroutine is likely to run on any given invocation: Lemma 11. For any constant c, there exists a c > c and a constant bound for count, such that the main body of the subroutine runs for at least c log(n) rounds but no more than c log n rounds, with high probability.

Lemma 12 (Safety). Over the first R invocations of the subroutine, the probability that it returns true in any invocation with more than one active node is at most 1/n c , for a constant c we can grow with our constant bound on count.

We can then show that the subroutine guarantees safety. Combined with the Theorem 5, these properties yields the following conclusion: Theorem 13. For any network size n, the universal leader election algorithm combined with the Constant State termination detection subroutine, solves leader election with high probability in n using s = O(1) states and q = 2. Also with high probability in n, it terminates in O(log 2 n) rounds.

Solving General Distributed Decision Problems

In this section, we use a combination of our fast leader election algorithms as a key primitive in constructing an algorithm that simulates a logspace (in n) decider Turing Machine (TM) with a constant number of unary input tapes (of size O(n) each). The simulation has error probability at most , requires only the minimum probabilistic precision (q = 2), and uses s = O(log (1/ )) states. If high probability in n is sufficient, then the state size can be reduced to s = O(1). In other words, once you have enough states to solve leader election, you can also solve a large class of expressive problems. Formally: Theorem 14. For any problem solvable by a logspace TM with a constant number of unary input tapes, there exist constants c, d ≥ 1, such that for any error probability ∈ [0, 1/2] and network size n ≥ 1, we can solve the problem in the beeping model in a network of size n with probability at least 1 -using s = c log (1/ ) states, precision q = 2, and an expected running time of O(n d log 2 (n + 1/ )) rounds. For high probability correctness, s = O(1) states are sufficient.

Our strategy follows the outline originally identified in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], where it was used to simulate a TM using a population protocol in the randomized interaction model. We first simulate a simple counter machine with a constant number of counters that can take values of size O(n). We then apply a classical computability result due to Minsky [START_REF] Minsky | Computation: finite and infinite machines[END_REF] which shows how to simulate a logspace TM (with unary input tapes) using a counter machine of this type. The counter machine simulation in the beeping model, combined with Minsky's TM simulation, yields a TM simulation in the beeping model. See the full version of this extended abstract [START_REF] Gilbert | The computational power of beeps[END_REF] for the details of our simulation, its analysis, and a discussion of its implications.

Notice, direct comparisons between many of these results is complicated by the variety of possible assumptions; e.g., synchronous versus asynchronous starts, multihop versus single hop, small versus large probability precision.

[START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF] For example: divide rounds into pairs of even and odd rounds. In even rounds, nodes broadcast a simple message with constant probability. If a node ever succeeds in broadcasting alone, all other nodes become heralds. They stop competing in even rounds and begin competing in odd rounds. When the winner (who is now the only non-herald in the network) eventually hears a message in an odd round, it elects itself leader. If we assume collision detection, we can reduce contention fast in the even rounds with basic knockout protocols; e.g., if you choose to listen and detect a collision you are knocked out and just wait to become a herald.

Transition functions map the current state to a distribution over states to enter next.

Supported in part by NUS FRC T1-251RES1404 Supported in part by NSF grant CCF 1320279