Explore the vast range of titles available.

Infectious diseases are still a major global burden for modern society causing 13 million deaths annually. One way to reduce the morbidity and mortality rates from infectious diseases is through pre-emptive or targeted vaccinations. Current theoretical vaccination strategies based on contact networks, however, rely on highly specific individual contact information which is difficult and costly to obtain, in order to identify influential spreading individuals. Current approaches also focus only on direct contacts between individuals for spreading, and disregard indirect transmission where a pathogen can spread between one infected individual and one susceptible individual who visit the same location within a short time-frame without meeting. This paper presents a novel vaccination strategy which relies on coarse-grained contact information, both direct and indirect, that can be easily and efficiently collected. Rather than tracking exact contact degrees of individuals, our strategy uses the types of places people visit to estimate a range of contact degrees for individuals, considering both direct and indirect contacts. We conduct extensive computer simulations to evaluate the performance of our strategy in comparison to state-of-the-art vaccination strategies. Results show that, when considering indirect links, our lower cost vaccination strategy achieves comparable performance to the contact-degree based approach and outperforms other existing strategies without requiring over-detailed information.

While cryptocurrencies and blockchain applications continue to gain popularity, their energy cost is evidently becoming unsustainable. In most instances, the main cost comes from the required amount of energy for the Proof-of-Work, and this cost is inherent to the design. In addition, useless costs from discarded work (e.g., the so-called Forks) and lack of scalability (in number of users and in rapid transactions) limit their practical effectiveness. In this paper, we present an innovative scheme which eliminates the nonce and thus the burden of the Proof-of-Work which is the main cause of the energy waste in cryptocurrencies such as Bitcoin. We prove that our scheme guarantees a tunable and bounded average number of simultaneous mining whatever the size of the population in competition, thus by making the use of nonce-based techniques unnecessary, achieves scalability without the cost of consuming a large volume of energy. The technique used in the proof of our scheme is based on the analogy of the analysis of a green leader election. The additional difference with Proof-of-Work schemes (beyond the suppression of the nonce field that is triggering most of the waste), is the introduction of (what we denote as) \"empty blocks\" which aim are to call regular blocks following a staircase set of values. Our scheme reduces the risk of Forks and provides tunable scalability for the number of users and the speed of block generation. We also prove using game theoretical analysis that our scheme is resilient to unfair competitive investments (e.g., \"51 percent\" attack) and block nursing.

Dynamic systems are becoming steadily more important with the profusion of mobile and distributed computing devices. Coincidentally incremental computation is a natural approach to deal with ongoing changes. We explore incremental computation in the parameterized complexity setting and show that incrementalization leads to non-trivial complexity classifications. Interestingly, some incremental versions of hard problems become tractable, while others remain hard. Moreover tractability or intractability is not a simple function of the problem’s static complexity, every level of the W-hierarchy exhibits complete problems with both tractable and intractable incrementalizations. For problems that are already tractable in their static form, we also show that incrementalization can lead to interesting algorithms, improving upon the trivial approach of using the static algorithm at each step.

We characterise trade-offs between the end-to-end communication delay and the energy in urban vehicular communications with infrastructure assistance. Our study exploits the self-similarity of the location of communication entities in cities by modelling them with a hyperfractal model which characterises the distribution of mobile nodes and relay nodes by a fractal dimension d F and d r , both larger than the dimension of the embedded map. We compute theoretical bounds for the end-to-end communication hop count considering two different energy-minimising goals: either total accumulated energy or maximum energy per node. Let δ > 1 be the attenuation factor in the street, we prove that when we aim to a total energy cost of order n (1− δ )(1− α ) , the hop count for an end-to-end transmission is of order n 1 − α / ( d F − 1 ) , with α < 1 is a tunable parameter. This proves that for both goals, the energy decreases as we allow choosing routing paths of higher length. The asymptotic limit of the energy becomes significantly small when the number of nodes becomes asymptotically large. A lower bound on the network throughput capacity with constraints on path energy is also given. We show that our model fits real deployments where open data sets are available. The results are confirmed through simulations using different fractal dimensions in a Matlab simulator.

This paper investigates moving networks of Unmanned Aerial Vehicles to extend connectivity and guarantee data rates in the 5G by analysing possible hovering locations based on limitations such as flight time and coverage. The authors provide analytic bounds on the requirements in terms of connectivity extension for vehicular networks served by fixed Enhanced Mobile BroadBand infrastructure, where both vehicular networks and infrastructures are modelled using stochastic and fractal geometry as a model for urban environment. The authors prove that assuming n mobile nodes (distributed according to a hyperfractal distribution of dimension dF) and an average of ρ Next Generation NodeB (gNBs), distributed like a hyperfractal of dimension dr if ρ = nθ with θ > dr/4 and letting n tending to infinity (to reflect megalopolis cities), then the average fraction of mobile nodes not covered by a gNB tends to zero like On−dF−2dr2θ−dr2$O\\left({n}^{-\\frac{\\left({d}_{F}-2\\right)}{{d}_{r}}\\left(2\\theta -\\frac{{d}_{r}}{2}\\right)}\\right)$ . Interestingly, the authors prove that the average number of drones, needed to connect each mobile node not covered by gNBs, is comparable to the number of isolated mobile nodes. The authors complete the characterisation by proving that when θ < dr/4 the proportion of covered mobile nodes tends to zero. The authors offer insights on the placement of the ‘garage of drones’, the home location of these nomadic infrastructure nodes, to minimise the ‘flight‐to‐coverage time’. The authors provide a fast procedure to select the relays that will be garages (and store drones) in order to minimise the number of garages and minimise the delay. The authors’ analytical results are confirmed using simulations in Matlab.

The asynchronous rumor algorithm spreading propagates a piece of information, the so-called rumor, in a network. Starting with a single informed node, each node is associated with an exponential time clock with rate \\(1\\) and calls a random neighbor in order to possibly exchange the rumor. Spread time is the first time when all nodes of a network are informed with high probability. We consider spread time of the algorithm in any dynamic evolving network, \\(G=\\G^(t)\\_t=0^ınfty\\), which is a sequence of graphs exposed at discrete time step \\(t=0,1\\). We observe that besides the expansion profile of a dynamic network, the degree distribution of nodes over time effect the spread time. We establish upper bounds for the spread time in terms of graph conductance and diligence. For a given connected simple graph \\(G=(V,E)\\), the diligence of cut set \\(E(S, S)\\) is defined as \\((S)=_\\u,v\\ın E(S,S)\\d/d_u, d/d_v\\\) where \\(d_u\\) is the degree of \\(u\\) and \\(d\\) is the average degree of nodes in the one side of the cut with smaller volume (i.e., \\(vol(S)=_uın Sd_u\\)). The diligence of \\(G\\) is also defined as \\((G)=_ S V(S)\\). We show that the spread time of the algorithm in \\(G\\) is bounded by \\(T\\), where \\(T\\) is the first time that \\(_t=0^T(G^(t))(G^(t))\\) exceeds \\(C n\\), where \\((G^(t))\\) denotes the conductance of \\(G^(t)\\) and \\(C\\) is a specified constant. We also define the absolute diligence as \\((G)=_\\u,v\\ın E\\1/d_u,1/d_v\\\) and establish upper bound \\(T\\) for the spread time in terms of absolute diligence, which is the first time when \\(_t=0^T(G^(t)) (G^(t)) 2n\\). We present dynamic networks where the given upper bounds are almost tight.

While cryptocurrencies and blockchain applications continue to gain popularity, their energy cost is evidently becoming unsustainable. In most instances, the main cost comes from the required amount of energy for the Proof-of-Work, and this cost is inherent to the design. In addition, useless costs from discarded work (e.g., the so-called Forks) and lack of scalability (in number of users and in rapid transactions) limit their practical effectiveness. In this paper, we present an innovative scheme which eliminates the nonce and thus the burden of the Proof-of-Work which is the main cause of the energy waste in cryptocurrencies such as Bitcoin. We prove that our scheme guarantees a tunable and bounded average number of simultaneous mining whatever the size of the population in competition, thus by making the use of nonce-based techniques unnecessary, achieves scalability without the cost of consuming a large volume of energy. The technique used in the proof of our scheme is based on the analogy of the analysis of a green leader election. The additional difference with Proof-of-Work schemes (beyond the suppression of the nonce field that is triggering most of the waste), is the introduction of (what we denote as) \"empty blocks\" which aim are to call regular blocks following a staircase set of values. Our scheme reduces the risk of Forks and provides tunable scalability for the number of users and the speed of block generation. We also prove using game theoretical analysis that our scheme is resilient to unfair competitive investments (e.g., \"51 percent\" attack) and block nursing.

We consider a variation of balls-into-bins which randomly allocates \\(m\\) balls into \\(n\\) bins. Following Godfrey's model (SODA, 2008), we assume that each ball \\(t\\), \\(1\\le t\\le m\\), comes with a hypergraph \\(\\mathcal{H}^{(t)}=\\{B_1,B_2,\\ldots,B_{s_t}\\}\\), and each edge \\(B\\in\\mathcal{H}^{(t)}\\) contains at least a logarithmic number of bins. Given \\(d\\ge 2\\), our \\(d\\)-choice algorithm chooses an edge \\(B\\in \\mathcal{H}^{(t)}\\), uniformly at random, and then chooses a set \\(D\\) of \\(d\\) random bins from the selected edge \\(B\\). The ball is allocated to a least-loaded bin from \\(D\\), with ties are broken randomly. We prove that if the hypergraphs \\(\\mathcal{H}^{(1)},\\ldots, \\mathcal{H}^{(m)}\\) satisfy a \\emph{balancedness} condition and have low \\emph{pair visibility}, then after allocating \\(m=\\Theta(n)\\) balls, the maximum number of balls at any bin, called the \\emph{maximum load}, is at most \\(\\log_d\\log n+O(1)\\), with high probability. The balancedness condition enforces that bins appear almost uniformly within the hyperedges of \\(\\mathcal{H}^{(t)}\\), \\(1\\le t\\le m\\), while the pair visibility condition measures how frequently a pair of bins is chosen during the allocation of balls. Moreover, we establish a lower bound for the maximum load attained by the balanced allocation for a sequence of hypergraphs in terms of pair visibility, showing the relevance of the visibility parameter to the maximum load. In Godfrey's model, each ball is forced to probe all bins in a randomly selected hyperedge and the ball is then allocated in a least-loaded bin. Godfrey showed that if each \\(\\mathcal{H}^{(t)}\\), \\(1\\le t\\le m\\), is balanced and \\(m=O(n)\\), then the maximum load is at most one, with high probability. However, we apply the power of \\(d\\) choices paradigm, and only query the load information of \\(d\\) random bins per ball, while achieving very slow growth in the maximum load.

We study functional graphs generated by several quadratic polynomials, acting simultaneously on a finite field of odd characteristic. We obtain several results about the number of leaves in such graphs. In particular, in the case of graphs generated by three polynomials, we relate the distribution of leaves to the Sato-Tate distribution of Frobenius traces of elliptic curves. We also present extensive numerical results which we hope may shed some light on the distribution of leaves for larger families of polynomials.

This paper investigates moving networks of Unmanned Aerial Vehicles (UAVs), such as drones, as one of the innovative opportunities brought by the 5G. With a main purpose to extend connectivity and guarantee data rates, the drones require hovering locations due to limitations such as flight time and coverage surface. We provide analytic bounds on the requirements in terms of connectivity extension for vehicular networks served by fixed Enhanced Mobile BroadBand (eMBB) infrastructure, where both vehicular networks and infrastructures are modeled using stochastic and fractal geometry as a model for urban environment. We prove that assuming \\(n\\) mobile nodes (distributed according to a hyperfractal distribution of dimension \\(d_F\\)) and an average of \\(\\rho\\) Next Generation NodeB (gNBs), distributed like an hyperfractal of dimension \\(d_r\\) if \\(\\rho=n^\\theta\\) with \\(\\theta>d_r/4\\) and letting \\(n\\) tending to infinity (to reflect megalopolis cities), then the average fraction of mobile nodes not covered by a gNB tends to zero like \\(O\\left(n^{-\\frac{(d_F-2)}{d_r}(2\\theta-\\frac{d_r}{2})}\\right)\\). Interestingly, we then prove that the average number of drones, needed to connect each mobile node not covered by gNBs is comparable to the number of isolated mobile nodes. We complete the characterisation by proving that when \\(\\theta

Paper

Share this book

Add to My Shelf