LabEx PERSYVAL-Lab

Bike-sharing systems are becoming important for urban transportation. In these systems, users arrive at a station, pick up a bike, use it for a while, and then return it to another station of their choice. Each station has a finite capacity: it cannot host more bikes than its capacity. We propose a stochastic model of an homogeneous bike-sharing system and study the effect of the randomness of user choices on the number of problematic stations, i.e., stations that, at a given time, have no bikes available or no available spots for bikes to be returned to. We quantify the influence of the station capacities, and we compute the fleet size that is optimal in terms of minimizing the proportion of problematic stations. Even in a homogeneous city, the system exhibits a poor performance: the minimal proportion of problematic stations is of the order of the inverse of the capacity. We show that simple incentives, such as suggesting users to return to the least loaded station among two stations, improve the situation by an exponential factor. We also compute the rate at which bikes have to be redistributed by trucks for a given quality of service. This rate is of the order of the inverse of the station capacity. For all cases considered, the fleet size that corresponds to the best performance is half of the total number of spots plus a few more, the value of the few more can be computed in closed-form as a function of the system parameters. It corresponds to the average number of bikes in circulation.

Consider the minimum spanning tree (MST) of the complete graph with $n$ vertices, when edges are assigned independent random weights. Endow this tree with the graph distance renormalized by $n^{1/3}$ and with the uniform measure on its vertices. We show that the resulting space converges in distribution as $n\to\infty$ to a random compact measured metric space in the Gromov–Hausdorff–Prokhorov topology. We additionally show that the limit is a random binary $\mathbb{R}$-tree and has Minkowski dimension $3$ almost surely. In particular, its law is mutually singular with that of the Brownian continuum random tree or any rescaled version thereof. Our approach relies on a coupling between the MST problem and the Erdős–Rényi random graph. We exploit the explicit description of the scaling limit of the Erdős–Rényi random graph in the so-called critical window, established in [Probab. Theory Related Fields 152 (2012) 367–406], and provide a similar description of the scaling limit for a “critical minimum spanning forest” contained within the MST. In order to accomplish this, we introduce the notion of $\mathbb{R}$-graphs, which generalise $\mathbb{R}$-trees, and are of independent interest.

We present a Lax--Friedrichs-type algorithm to numerically integrate a class of nonlocal and nonlinear systems of conservation laws in several space dimensions. The convergence of the approximate solutions is proved, also providing the existence of a solution in a slightly more general setting than in other results in the current literature. An application to a crowd dynamics model is considered.

Massive graph data sets are pervasive in contemporary application domains. Hence, graph database systems are becoming increasingly important. In the experimental study of these systems, it is vital that the research community has shared solutions for the generation of database instances and query workloads having predictable and controllable properties. We present the design and engineering principles of gMark, a domain- and query language-independent graph instance and query workload generator. A core contribution of gMark is its ability to target and control the diversity of properties of both the generated instances and the generated workloads coupled to these instances. Further novelties include support for regular path queries, a fundamental graph query paradigm, and schema-driven selectivity estimation of queries, a key feature in controlling workload chokepoints. We illustrate the flexibility and practical usability of gMark by showcasing the framework's capabilities in generating high quality graphs and workloads, and its ability to encode user-defined schemas across a variety of application domains.

In the context of fog computing, we consider a simple case where data centers are installed at the edge of the network and assume that if a request arrives at an overloaded data center, then it is forwarded to a neighboring data center with some probability. Data centers are assumed to have a large number of servers, and traffic at some of them is assumed to cause saturation. In this case, the other data centers may help to cope with this saturation regime by accepting some of the rejected requests. Our aim is to qualitatively estimate the gain achieved via cooperation between neighboring data centers. After proving some convergence results related to the scaling limits of loss systems for the process describing the number of free servers at both data centers, we show that the performance of the system can be expressed in terms of the invariant distribution of a random walk in the quarter plane. By using and developing existing results in the technical literature, explicit formulas for the blocking rates of such a system are derived.

Sensitivity analysis (SA) of a numerical model, for instance simulating physical phenomena, is useful to quantify the influence of the inputs on the model responses. This paper proposes a new sensitivity index, based upon the modification of the probability density function (pdf) of the random inputs, when the quantity of interest is a failure probability (probability that a model output exceeds a given threshold). An input is considered influential if the input pdf modification leads to a broad change in the failure probability. These sensitivity indices can be computed using the sole set of simulations that has already been used to estimate the failure probability, thus limiting the number of calls to the numerical model. In the case of a Monte Carlo sample, asymptotical properties of the indices are derived. Based on Kullback–Leibler divergence, several types of input perturbations are introduced. The relevance of this new SA method is analysed through three case studies.

Besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for graph pattern matching (GPM) in the context of big data. As a result, relaxed GPM models have emerged as they yield interesting results in a polynomial time. However, massive graphs generated by mostly social networks require a distributed storing and processing of the data over multiple machines, thus, requiring GPM to be revised by adopting new paradigms of big graphs processing, e.g., Think-Like-A-Vertex and its derivatives. This article discusses and proposes a classification of distributed GPM approaches with a narrow focus on the relaxed models.

We extend the results on conservation laws with local flux constraint obtained in [2, 12] to general (non-concave) flux functions and non-classical solutions arising in pedestrian flow modeling [15]. We first provide a well-posedness result based on wave-front tracking approximations and the Kružhkov doubling of variable technique for a general conservation law with constrained flux. This provides a sound basis for dealing with non-classical solutions accounting for panic states in the pedestrian flow model introduced by Colombo and Rosini [15]. In particular, flux constraints are used here to model the presence of doors and obstacles. We propose a 'front-tracking' finite volume scheme allowing to sharply capture classical and non-classical discontinuities. Numerical simulations illustrating the Braess paradox are presented as validation of the method.

In this paper we introduce a class of Markov models, termed best-effort\nnetworks, designed to capture performance indices such as mean transfer times\nin data networks with best-effort service. We introduce the so-called min\nbandwidth sharing policy as a conservative approximation to the classical\nmax-min policy. We establish necessary and sufficient ergodicity conditions for\nbest-effort networks under the min policy. We then resort to the mean field\ntechnique of statistical physics to analyze network performance deriving fixed\npoint equations for the stationary distribution of large symmetrical\nbest-effort networks. A specific instance of such net- works is the star-shaped\nnetwork which constitutes a plausible model of a network with an\noverprovisioned backbone. Numerical and analytical study of the equations\nallows us to state a number of qualitative conclusions on the impact of traffic\nparameters (link loads) and topology parameters (route lengths) on mean\ndocument transfer time.\n

A wide array of random graph models have been postulated to understand\nproperties of observed networks. Typically these models have a parameter $t$\nand a critical time $t_c$ when a giant component emerges. It is conjectured\nthat for a large class of models, the nature of this emergence is similar to\nthat of the Erd\\H{o}s-R\\'enyi random graph, in the sense that (a) the sizes of\nthe maximal components in the critical regime scale like $n^{2/3}$, and (b) the\nstructure of the maximal components at criticality (rescaled by $n^{-1/3}$)\nconverges to random fractals. To date, (a) has been proven for a number of\nmodels using different techniques. This paper develops a general program for\nproving (b) that requires three ingredients: (i) in the critical scaling\nwindow, components merge approximately like the multiplicative coalescent, (ii)\nscaling exponents of susceptibility functions are the same as that of the\nErd\\H{o}s-R\\'enyi random graph, and (iii) macroscopic averaging of distances\nbetween vertices in the barely subcritical regime. We show that these apply to\ntwo fundamental random graph models: the configuration model and inhomogeneous\nrandom graphs with a finite ground space. For these models, we also obtain new\nresults for component sizes at criticality and structural properties in the\nbarely subcritical regime.\n

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class $\mathcal{C}$, that is, the maximum VC-dimension over the hypergraphs formed by the closed neighborhoods of elements of $\mathcal{C}$. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class $\mathcal{C}$) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on $C_4$-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of $c \log(|V|)$ for some $c>0$.

International audience

In this paper we seek to characterize the behavior of the Internet in the absence of congestion control. More specifically, we assume all sources transmit at their maximum rate and recover from packet loss by the use of some ideal erasure coding scheme. We estimate the efficiency of resource utilization in terms of the maximum load the network can sustain, accounting for the random nature of traffic. Contrary to common belief, there is generally no congestion collapse. Efficiency remains higher than 90% for most network topologies as long as maximum source rates are less than link capacity by one or two orders of magnitude. Moreover, a simple fair drop policy enforcing fair sharing at flow level is sufficient to guarantee 100% efficiency in all cases.

Networks are essential for analyzing complex systems. However, their growing size necessitates backbone extraction techniques aimed at reducing their size while retaining critical features. In practice, selecting, implementing, and evaluating the most suitable backbone extraction method may be challenging. This paper introduces netbone, a Python package designed for assessing the performance of backbone extraction techniques in weighted networks. Its comparison framework is the standout feature of netbone. Indeed, the tool incorporates state-of-the-art backbone extraction techniques. Furthermore, it provides a comprehensive suite of evaluation metrics allowing users to evaluate different backbones techniques. We illustrate the flexibility and effectiveness of netbone through the US air transportation network analysis. We compare the performance of different backbone extraction techniques using the evaluation metrics. We also show how users can integrate a new backbone extraction method into the comparison framework. netbone is publicly available as an open-source tool, ensuring its accessibility to researchers and practitioners. Promoting standardized evaluation practices contributes to the advancement of backbone extraction techniques and fosters reproducibility and comparability in research efforts. We anticipate that netbone will serve as a valuable resource for researchers and practitioners enabling them to make informed decisions when selecting backbone extraction techniques to gain insights into the structural and functional properties of complex systems.

This paper introduces lronMask, a new versatile verification tool for masking security. lronMask is the first to offer the verification of standard simulation-based security notions in the probing model as well as recent composition and expandability notions in the random probing model. It supports any masking gadgets with linear randomness (e.g. addition, copy and refresh gadgets) as well as quadratic gadgets (e.g. multiplication gadgets) that might include non-linear randomness (e.g. by refreshing their inputs), while providing complete verification results for both types of gadgets. We achieve this complete verifiability by introducing a new algebraic characterization for such quadratic gadgets and exhibiting a complete method to determine the sets of input shares which are necessary and sufficient to perform a perfect simulation of any set of probes. We report various benchmarks which show that lronMask is competitive with state-of-the-art verification tools in the probing model (maskVerif, scVerif, SILVEH, matverif). lronMask is also several orders of magnitude faster than VHAPS -the only previous tool verifying random probing composability and expandability- as well as SILVEH -the only previous tool providing complete verification for quadratic gadgets with nonlinear randomness. Thanks to this completeness and increased performance, we obtain better bounds for the tolerated leakage probability of state-of-the-art random probing secure compilers.

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minorclosed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad–Nagata dimension at most 2. Furthermore, our techniques allow us to determine the asymptotic dimension of graphs of bounded layered treewidth and graphs with any fixed growth rate, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours.

Although postquantum cryptography is of growing practical concern, not many works have been devoted to implementation security issues related to postquantum schemes. In this paper, we look in particular at fault attacks against implementations of lattice-based signatures and key exchange protocols. For signature schemes, we are interested both in Fiat-Shamir type constructions (particularly BLISS, but also GLP, PASSSign, and Ring-TESLA) and in hash-and-sign schemes (particularly the GPV-based scheme of Ducas-Prest-Lyubashevsky). For key exchange protocols, we study the implementations of NewHope, Frodo, and Kyber. These schemes form a representative sample of modern, practical lattice-based signatures and key exchange protocols, and achieve a high level of efficiency in both software and hardware. We present several fault attacks against those schemes that recover the entire key recovery with only a few faulty executions (sometimes only one), show that those attacks can be mounted in practice based on concrete experiments in hardware, and discuss possible countermeasures against them.

Massive graph data sets are pervasive in contemporary application domains. Hence, graph database systems are becoming increasingly important. In the experimental study of these systems, it is vital that the research community has shared solutions for the generation of database instances and query workloads having predictable and controllable properties. We present the design and engineering principles of gMark, a domain- and query language-independent graph instance and query workload generator. A core contribution of gMark is its ability to target and control the diversity of properties of both the generated instances and the generated workloads coupled to these instances. Further novelties include support for regular path queries, a fundamental graph query paradigm, and schema-driven selectivity estimation of queries, a key feature in controlling workload chokepoints. We illustrate the flexibility and practical usability of gMark by showcasing the framework’s capabilities in generating high quality graphs and workloads, and its ability to encode user-defined schemas across a variety of application domains.

Internet-of-Things (IoT) devices have grown in popularity over the past few years. The RSA public-key cryptographic primitive is time consuming for resource-constrained IoT. Recently, Zhang et al. proposed a two-party outsourcing protocol between a client and a server for RSA decryption in IoT. It relies on the Chinese remainder theorem as proposed by Quisquater and Couvreur in 1982 and is very efficient. We show that their protocol does not achieve the claimed security guarantees: 1) the (secret) decryption exponent, the plaintext, and the factorization of the RSA modulus are revealed to a passive adversary and 2) a malicious server can make the client accept an (invalid) value of its choice as the result of the delegated computation.

The dense nature of transportation networks expands the challenge of their visualization and processing. Several statistical backbone extraction techniques are proposed to reduce their size while keeping essential information. Here, we perform a comparative evaluation of seven prominent statistical backbone extraction techniques in the USA weighted air transportation network. One can classify the airports into hubs, spokes, and focus airports based on the business models used by the airlines. We compare the extracted backbones using various performance measures. We consider the number of components, sizes, the fraction of airport type, edge type, and weights preserved by each method. Results show that the Enhanced Configuration Model (ECM) Filter tends to preserve edges between spoke airports uncovering the infrastructure connecting the regional spoke airports. In contrast, the alternative filters (Disparity, Polya Urn, Marginal Likelihood, Noise Corrected, Global Statistical Significance (GLOSS), Locally Adaptive Network Sparsification (LANS)) highlight edges between the hub and spoke, focus and spoke, and spoke and spoke airports revealing more of the hub and spoke foundation used by airlines. Moreover, the Disparity Filter, Marginal Likelihood Filter, and Noise Corrected Filter preserve the highest proportion of weights while Polya Urn Filter and ECM Filter keep the lowest. The GLOSS and LANS Filters maintain a moderate fraction of weights between the two extremes.