We study the asymptotic behaviour of the distance to the first available parking slot in a recursive Manhattan street network endowed with a hyperfractal intensity structure, where slot-release events occur according to Poisson processes along the streets. We establish, by analysing the associated self-similar harmonic sums via Mellin-transform asymptotics [Flajolet et al., 1995], a power-law decay of the expected distance as the total intensity grows, with exponent equal to the inverse of the hyperfractal dimension. In particular, the scaling exponent depends only on the large-scale geometry of the network. We further prove that this exponent is robust under random multiplicative modulations of the street intensities: mild stochastic heterogeneity affects only the multiplicative constant. Similar scaling behaviour holds for the variance, the number of turns before parking, and for a jump-over variant of the search strategy.

In online learning, a learner receives data in rounds and, at each round, predicts a label that is then compared to the true label, incurring a loss. The total loss overTrounds, when compared to the loss of the best expert from a class of experts or forecasters, is called the regret. In this paper, we focus on logarithmic loss for logistic-like experts withunbounded d-dimensional weights, a scenario that has been largely unexplored. To address the irregularities introduced by the unbounded weight norm, we introduce aregularizedversion of the average (fixed design) minimax regret by imposing asoft constrainton the weight norm. We demonstrate that the regularized minimax regret is fully characterized by a complexity measure we term the regularized Shtarkov sum. We also show how the behavior of the standard regret can be inferred from the regularized regret. Our main results provide aprecisecharacterization of the regularized Shtarkov sum and, consequently, the regularized regret with unbounded weights up to second-order asymptotics. Notably, unlike thed/2 logTregret growth known for bounded weights, our results imply that the regularized regret grows as (1/2+α/4)dlogTwhen the regularization parameter is of order Θ(T−α) for α ≤ 1/2. We achieve this using tools from analytic combinatorics, including multidimensional Fourier analysis, the saddle point method, and the Mellin transform.

In online learning, a learner receives data in rounds 1$t T$and at each round predicts a label which is then compared to the true label resulting in a loss. The total loss over$T$rounds, when compared to a loss over the best expert from a class of experts, is called the regret. This paper focuses on logarithmic loss over a class of experts represented by a probability distribution$p$and parameterized by addimensional weight vector w. Unlike previous work that studied bounded weights, we assume that the norm of the weights can be unbounded. This unboundedness poses a challenging problem that leads to unexpected results. For such a class of weighted experts we analyze the (fixed design) minimax regret for the best predictor and worst label sequence. Such a minimax regret turns out to be a universal lower bound for most regrets analyzed in the literature. For bounded weights it is known that the minimax regret can grow like where$R$is an upper bound on the weight norm. In contrast, we show in this paper that for unbounded norm with$R$the minimax regret is asymptotically (d - 1) for a logistic-like expert class which we also extend to$R$We prove our findings by introducing the so called splittable label sequences that partition the weight space into regions with maximum sequence probability equal to 1. Finally, for a general class of monotone experts we present an upper bound 2d log$T$for the regret.

Delays in blockchain networks are mainly related to consensus protocols. Among these protocols, we focus on a specific family of protocols, where the mempool's role in the consensus mechanism is explicitly examined. A mempool is a temporary storage area for transactions waiting to be included in a block. This study investigates the round duration of two mempool-based protocols: one requiring a single quorum of messages and another demanding two. We perform the delay analysis with two approaches. First, we elaborate on a Markov chain to determine the distribution of the round durations. Second, we establish an analytical model of message delays while assuming an exponential distribution of message propagation delays. Finally, asymptotic analysis is conducted to estimate the time of quorum formation. We end the paper by comparing the simulation results with the theoretical ones. Results show that both results are very close. This research offers valuable insights into the performance characteristics of mempool-based consensus protocols, aiding in the design and optimization of blockchain systems.

This article investigates data dissemination delays in a Directed Acyclic Graph (DAG)-based Byzantine Fault Tolerant (BFT) blockchain. We focus particularly on the Narwhal protocol, a mempool-based approach for efficiently disseminating transactions and constructing a DAG. Narwhal is designed to work alongside a BFT consensus protocol like Tusk. Tusk then orders the transaction metadata based on the DAG information. Through an in-depth analysis of the protocol messages, we establish a mathematical model for message propagation delays. We start by considering a specific probability distribution for data network propagation delays: Gaussian Distribution. Then, we consider a general propagation delay distribution. Also, we assume large networks and apply some approximations, i.e., the Central Limit Theorem (CLT). Finally, we develop the Narwhal protocol and demonstrate that the simulated delaysarecompatible with the theoretical ones.

Blockchain applications continue to grow in popularity, but their energy costs are clearly becoming unsustainable. In most cases, the primary cost comes from the amount of energy required for proof-of-work (PoW). Here we study the application of blockchains to the IoT, where most devices are underpowered and would not support the energy cost of proof of work. PoW was originally intended for two main uses: block moderation and protecting the blockchain from tampering. For IoT we propose to replace the expensive moderation of PoW with the proposed energy-efficient green mining [6]. The blockchain will be protected by a fractal difficulty PoW. One of the results of this paper is the proof that the average mining time in fractal PoW actually depends only on the average difficulty. This crucial property will allow low-difficulty PoWs to be reserved for devices with low computational capacity, while higher difficulties will be reserved for devices with the highest computational power. The consequence is to give equal opportunity to objects with low computational power compared to objects with high computational power.

We present an analysis of the depth-first search algorithm in a random digraph model with geometric outdegree distribution. We give also some extensions to general outdegree distributions. This problem posed by Donald Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan.

We study online logistic regression with binary labels and general feature values in which a learner tries to predict an outcome/ label based on data/ features received in rounds. Our goal is to evaluate precisely the (maximal) minimax regret which we analyze using a unique and novel combination of information-theoretic and analytic combinatorics tools such as Fourier transform, saddle point method, and Mellin transform in the multi-dimensional settings. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over a constant comparator which is used for prediction. In the minimax scenario we seek the best learning distribution for the worst label sequence. For dimension d = o(T1/3) we show that the maximal minimax regret grows as $d/2 \cdot \log (2T/\pi ) + {C_d} + O\left({{d^{3/2}}/\sqrt T }\right)$ where T is the number of rounds of running a training algorithm and Cdis explicitly computable constant that depends on dimension d and feature values. We compute explicitly the constant Cdfor features uniformly distributed on a d-dimensional sphere or ball.

We study logistic regression with binary labels and categorical (discrete) feature values. Our goal is to evaluate precisely the (maximal) minimax regret. We express it as the so called Shtarkov sum known in information theory. To the best of our knowledge such a sum was never computed in the context of logistic regression. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over some value of a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm. In the maximal minimax scenario we seek the best weights for the worst label sequence over all possible learning algorithms/ distributions, therefore it constitutes a lower bound for the pointwise regret. For finite dimension $d$ and $N$ distinct feature vectors we show that the maximal minimax regret grows as $$ \frac{d}{2} \log (T/2\pi)+C_d + O(N/\sqrt{T}) $$ where $T$ is the number of rounds of running a training algorithm and $C_d$ is explicitly computable constant that depends on the feature values and dimension $d$. We also extend these results to non-binary labels. The {\it precise} maximal minimax regret presented here is the first result of this kind. Our findings are obtained using tools of analytic combinatorics and information theory.

Lempel-Ziv'78 is one of the most popular data compression algorithms. Over the last few decades fascinating properties of LZ78 were uncovered. Among others, in 1995 we settled the Ziv conjecture by proving that for a memoryless source the number of LZ78 phrases satisfies the Central Limit Theorem (CLT). Since then the quest commenced to extend it to Markov sources. However, despite several attempts this problem is still open. The 1995 proof of the Ziv conjecture was based on two models: In the DST-model, the associated digital search tree (DST) is built over m independent strings. In the LZ-model a single string of length n is partitioned into variable length phrases such that the next phrase is not seen in the past as a phrase. The Ziv conjecture for memoryless source was settled by proving that both DST-model and the LZ-model are asymptotically equivalent. The main result of this paper shows that this is not the case for the LZ78 algorithm over Markov sources. In addition, we develop here a large deviation for the number of phrases in the LZ78 and give a precise asymptotic expression for the redundancy which is the excess of LZ78 code over the entropy of the source. We establish these findings using a combination of combinatorial and analytic tools. In particular, to handle the strong dependency between Markov phrases, we introduce and precisely analyze the so called tail symbol which is the first symbol of the next phrase in the LZ78 parsing.

We study the partial duplication dynamic graph model, introduced by Bhan et al. in [Bhan et al., 2002] in which a newly arrived node selects randomly an existing node and connects with probability p to its neighbors. Such a dynamic network is widely considered to be a good model for various biological networks such as protein-protein interaction networks. This model is discussed in numerous publications with only a few recent rigorous results, especially for the degree distribution. Recently Jordan [Jordan, 2018] proved that for 0 < p < 1/e the degree distribution of the connected component is stationary with approximately a power law. In this paper we rigorously prove that the tail is indeed a true power law, that is, we show that the degree of a randomly selected node in the connected component decays like C/k^β where C an explicit constant and β ≠ 2 is a non-trivial solution of p^(β-2) + β - 3 = 0. This holds regardless of the structure of the initial graph, as long as it is connected and has at least two vertices. To establish this finding we apply analytic combinatorics tools, in particular Mellin transform and singularity analysis.

The gradient descent to a local minimum is the key ingredient of deep neural networks learning techniques. We consider a function Lm(.) in dimension n with a random set of m absolute minima. When log m = o(n), we show that a gradient descent from an initial random point quasi always ends on a unique local minimum approximately at the centroid of the absolute minima. This fake minimum acts like an absorbing node, but its value by function Lm(.) can be far above the values obtained by Lm(.) on the absolute minima and sometimes gives very bad coefficients for the neural network. Fortunately in most cases the fake minimum leads to a neural network with not so bad prediction, with an error rate of order n-1/4. The only way to escape the fake minimum is to start a new gradient descent from a new random point and we show that finding a good initial point takes in average time which is at least proportional to ebn/mn2for some b > 0.

Dirichlet distribution and multinomial distribution play important role in information theory and statistics. They find applications in estimation, average minimax redundancy in source coding, Pólya urn model, and graph compression. Dirichlet-multinomial distribution is a multinomial distribution in which parameters are distributed according to the Dirichlet distribution. In this paper, we present some characteristics of the Dirichlet-multinomial distribution, including a precise asymptotic for the entropy. It should be point out that such a characterization turns out to be technically quite challenging requiring analytic tools including analytic continuation of hypergeometric series.

This paper studies the fundamental communication properties of urban vehicle networks by exploiting the selfsimilarity and hierarchical organization of modern cities. We use an innovative model called “hyperfractal” that captures the selfsimilarities of both the traffic and vehicle locations but avoids the extremes of regularity and randomness. We use analytical tools to derive theoretical upper and lower bounds for the information propagation speed in an urban delay tolerant network (i.e., a network that is disconnected at all time, and thus uses a store-carryand-forward routing model). We prove that the average broadcast time behaves as n1-δtimes a slowly varying function, where δ depends on the precise fractal dimension. Furthermore, we show that the broadcast speedup is due in part to an interesting selfsimilar phenomenon, that we denote as information teleportation. This phenomenon arises as a consequence of the topology of the vehicle traffic, and triggers an acceleration of the broadcast time. We show that our model fits real cities where open traffic data sets are available. We present simulations confirming the validity of the bounds in multiple realistic settings, including scenarios with variable speed, using both QualNet and a discrete-event simulator in Matlab.

The goal of this paper is to increase our understanding of the fundamental communication properties in urban vehicle-to-vehicle mobile networks by exploiting the self-similarity and hierarchical organization of modern cities. We use an innovative model called “hyperfractal” that captures the self-similarities of both the traffic and vehicle locations, and yet avoids the extremes of regularity and randomness. We use analytical tools to derive matching theoretical upper and lower bounds for the information propagation speed in an urban delay tolerant network (i.e., a network that is disconnected at all time, and thus uses a store-carry-and-forward routing model). We prove that the average broadcast time behaves as n1-δ(times a slowly varying function), where δ depends on the precise fractal dimension. Furthermore, we show that the broadcast speedup is due in part to an interesting self-similar phenomenon, that we denote as information teleportation. This phenomenon arises as a consequence of the topology of the vehicle traffic, and triggers an acceleration of the broadcast time. We show that our model fits real cities where open traffic data sets are available. The study presents simulations that confirm the validity of the bounds in multiple realistic settings, including scenarios with variable speed.

We introduce a model of Poisson patterns of fixed and mobile nodes on lines designed for urban wireless networks. The pattern obeys to "Hyperfractal" rules of dimension larger than 2. The hyperfractal pattern is best suitable for capturing the traffic over the streets and highways in a city. We show that the network capacity under ad hoc routing algorithms scales much better than with the classic uniform Poisson shot model. The scaling effect depends on the hyperfractal dimensions. We show this results in two different routing models: nearest neighbor routing with no collision, minimum delay routing model assuming slotted Aloha and signal to interference ratio (SIR) capture condition, power-path loss and Rayleigh fading. The novelty of the model is that, in addition to capturing the irregularity and variability of the node configuration, it exploits self-similarity, a characteristic of urban wireless networks.

In this paper we address the problem of finding top k eigenvalues and corresponding eigenvectors of symmetric graph matrices in networks in a distributed way. We propose a novel idea called complex power iterations in order to decompose the eigenvalues and eigenvectors at node level, analogous to time-frequency analysis in signal processing. At each node, eigenvalues correspond to the frequencies of spectral peaks and respective eigenvector components are the amplitudes at those points. Based on complex power iterations and motivated from fluid diffusion processes in networks, we devise distributed algorithms with different orders of approximation. We also introduce a Monte Carlo technique with gossiping which substantially reduces the computational overhead. An equivalent parallel random walk algorithm is also presented. We validate the algorithms with simulations on real-world networks. Our formulation of the spectral decomposition can be easily adapted to a simple algorithm based on quantum random walks. With the advent of quantum computing, the proposed quantum algorithm will be extremely useful.

Mankind has never been connected as it is now and as it will be tomorrow. Nowadays thanks to the rise of social networks such as Tweeter and Facebook, we can follow in real time the thought of millions of people. In fact we can almost feel the thoughts of a whole humanity and maybe project ourselves in a position where we could predict the major trends in the collective behavior of this humanity. However such an ambitious aim would require considerable resources in processing and networking which may be far from affordable. Indeed trends and topics are carried in a multiple of small texts written in various language and vocabularies like an hologram carries information in a dispersed way. Their capture and classification pose serious problems of data mining and analytics. Processes based on pure semantic analysis would require too much processing power and memory. We will present alternative methods based on string complexity also inspired on geolocalization in wireless networks which saves processing power by several order of magnitude. The ultimate goal is to detect when people are thinking about the very same topics before they become aware.

We study the scaling properties of a georouting scheme in a wireless multi-hop network of n mobile nodes. Our aim is to increase the network capacity quasi-linearly with n, while keeping the average delay bounded. In our model, we consider mobile nodes moving according to an independent identically distributed random walk with velocity v and transmitting packets to randomly chosen fixed and known destinations. The average packet delivery delay of our scheme is of order 1/v, and it achieves network capacity of order (n/log n log logn). This shows a practical throughput-delay tradeoff, in particular when compared with the seminal result of Gupta and Kumar, which shows network capacity of order (n/log n)1/2and negligible delay and the groundbreaking result of Grossglauser and Tse, which achieves network capacity of order n but with an average delay of order √n/v. The foundation of our improved capacity and delay tradeoff relies on the fact that we use a mobility model that contains straight-line segments, a model that we consider more realistic than classic Brownian motions. We confirm the generality of our analytical results using simulations under various interference models.

We want to estimate the capacity of wireless networks under several models and several geometric assumptions. We consider that all nodes transmit to a single fixed access point. The nodes are randomly distributed in an infinite fractal Cantor map embedded in a space of dimension D, a model which is more realistic than the classic piecemeal uniform map model. We consider three capacity models, one is a theoretical upper bound, the two other are variations on outage capacities.

We study the Lempel-Ziv'78 algorithm and show that its (normalized) redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper, in particular, by presenting a new simplified proof of the central limit theorem (CLT) for the number of phrases in the LZ'78 algorithm. We first analyze the asymptotic behavior of the total path length in the associated digital search tree built from independent sequences. Then, a renewal theory type argument yields CLT for LZ'78 scheme. Here, we extend our analysis of LZ'78 algorithm to present new results on the convergence of moments, moderate and large deviations, and CLT for the (normalized) redundancy. In particular, we confirm that the average redundancy rate decays as 1/log n, and we find that the variance is of order 1/n, where n is the length of the text.

We study the information propagation speed in multi-lane vehicle-to-vehicle networks such as roads or highways. We focus on the impact of time-varying radio ranges and of multiple lanes of vehicles, varying in speed and in density. We assess the existence of a vehicle density threshold under which information propagates on average at the fastest vehicle speed and above which information propagates dramatically faster. We first prove that no such phase transition occurs if there is only one lane, regardless of the density of vehicles, when one takes into account real-time radio communication range variations at the MAC layer. We then prove that, on the other hand, a phase transition exists as soon as there are multiple lanes with different vehicle speeds and appropriate densities. We characterize conditions under which the phase transition occurs and we derive bounds on the corresponding threshold as a simple relationship between the vehicle density on the fastest lane and the sum of densities on the other lanes. Our results intrinsically encompass a wide range of vehicular network scenarios, including one-way and two-way roads, as well as special cases such as road side units and/or parked cars being used as relays. We confirm our analytical results using simulations.

We propose a classification test to discriminate Markov sources based on the joint string complexity. String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define the joint string complexity as the cardinality of the set of words which both strings have in common. In this paper we analyze the average joint complexity when both strings are generated by two Markov sources. We provide fast converging asymptotic expansions and present some experimental results showing usefulness of the joint complexity to text discrimination.

We want to estimate the average capacity of MISO networks when several simultaneous emitters and a single access point are randomly distributed in an infinite fractal map embedded in a space of dimension D. We first show that the average capacity is a constant when the nodes are uniformly distributed in the space. This constant is function of the space dimension and of the signal attenuation factor, it holds even in presence of non i.i.d. fading effects. We second extend the analysis to fractal maps with a non integer dimension. In this case the constant still holds with the fractal dimension replacing D but the capacity shows small periodic oscillation around this constant when the node density varies. The practical consequence of this result is that the capacity increases significantly when the network map has a small fractal dimension.

We introduce a new algorithm to achieve a distributed leader election in a broadcast channel that is more efficient than the classic Part-and-Try algorithm. The algorithm has the advantage of having a reduced overhead log logN rather than log N. More importantly, the algorithm has a greatly reduced energy consumption since it requires O(N1=k) burst transmissions instead of O(N=k), per election, k being a parameter depending on the physical properties of the medium of communication. The algorithm has interesting potential applications in cognitive wireless networking.

Jitter is used in wireless ad hoc networks to reduce the number of packet collisions and the number of transmissions. This is done by scheduling random back-off for each packet to be transmitted and by piggybacking multiple packets in a single transmission. This technique has been standardized by the IETF in RFC 5148. This paper investigates on the impact of the standardized jitter mechanism on network-wide packet dissemination - i.e. flooding, an important component for many protocols used today. A novel analytical model is introduced, capturing standard jitter traits. From this model is derived accurate characterization of the effects of jittering on flooding performance, including the additional delay for flooded packets on each traversed network interface, the reduction of the number of transmissions over each network interface, and the increased length of transmissions, depending on jitter parameters. This paper also presents an analysis of the use of jitter in practice, over an 802.11 wireless link layer based on CSMA. The analytical results are then validated via statistical discrete event simulations. The paper thus provides a comprehensive overview of the impact of jittering in wireless ad hoc networks.

We study the scaling properties of a georouting scheme in a wireless multi-hop network of n mobile nodes. Our aim is to increase the network capacity quasi linearly with n while keeping the average delay bounded. In our model, mobile nodes move according to an i.i.d. random walk with velocity v and transmit packets to randomly chosen destinations. The average packet delivery delay of our scheme is of order 1/v and it achieves the network capacity of order n/(log n log log n). This shows a practical throughput-delay trade-off, in particular when compared with the seminal result of Gupta and Kumar which shows network capacity of order √(n/log n) and negligible delay and the groundbreaking result of Grossglauser and Tse which achieves network capacity of order n but with an average delay of order √n/v. The foundation of our improved capacity and delay trade-off relies on the fact that we use a mobility model that contains free space motion, a model that we consider more realistic than classic brownian motions. We confirm the generality of our analytical results using simulations under various interference models.

In this paper, we provide a full analysis of the information propagation speed in bidirectional vehicular delay tolerant networks such as roads or highways. The provided analysis shows that a phase transition occurs concerning the information propagation speed, with respect to the vehicle densities in each direction of the highway. We prove that under a certain threshold, information propagates on average at vehicle speed, while above this threshold, information propagates dramatically faster at a speed that increases quasi-exponentially when the vehicle density increases. We provide the exact expressions of the threshold and of the average information propagation speed near the threshold, in case of finite or infinite radio propagation speed. Furthermore, we investigate in detail the way information propagates under the threshold, and we prove that delay tolerant routing using cars moving on both directions provides a gain in propagation distance, which is bounded by a sublinear power law with respect to the elapsed time, in the referential of the moving cars. Combining these results, we thus obtain a complete picture of the way information propagates in vehicular networks on roads and highways, which may help designing and evaluating appropriate vehicular ad hoc networks routing protocols. We confirm our analytical results using simulations carried out in several environments (The One and Maple).

The method of types is one of the most popular techniques in information theory and combinatorics. Two sequences of equal length have the same type if they have identical empirical distributions. In this paper, we focus on Markov types, that is, sequences generated by a Markov source (of order one). We note that sequences having the same Markov type share the same so-called balanced frequency matrix that counts the number of distinct pairs of symbols. We enumerate the number of Markov types for sequences of length over an alphabet of size . This turns out to be asymptotically equivalent to estimating the number of the balanced frequency matrices, the number of integer solutions of a system of linear Diophantine equations, and the number of connected Eulerian multigraphs. For fixed , we prove that the number of Markov types is asymptotically equal to d(m) nm2-m/(m2-m)! where we give an integral representation for d(m). For m →∞, we conclude that asymptotically the number of types is equivalent to √2m3m/2em2/m2m22mπm/2nm2-m provided that m = o(n1/4). These findings are derived by analytical techniques ranging from analytic combinatorics, to multidimensional generating functions, to the saddle point method.

In this paper, we provide an analysis of the information propagation speed in bidirectional vehicular delay tolerant networks on highways. We show that a phase transition occurs concerning the information propagation speed, with respect to the vehicle densities in each direction of the highway. We prove that under a certain threshold, information propagates on average at vehicle speed, while above this threshold, information propagates dramatically faster at a speed that increase exponentially when vehicle density increases. We provide the exact expressions of the threshold and of the average propagation speed near the threshold. We show that under the threshold, the information propagates on a distance which is bounded by a sub-linear power law with respect to the elapsed time, in the referential of the moving cars. On the other hand, we show that information propagation speed grows quasi-exponentially with respect to vehicle densities in each direction of the highway, when the densities become large, above the threshold. We confirm our analytical results using simulations carried out in several environments.

We show that the Lempel Ziv'78 redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper [3]. We present a new simplified proof of the Central Limit Theorem for the number of phrases in the LZ'78 algorithm. As in our 1995 paper, here we first analyze the asymptotic behavior of the total path length in a digital search tree (a DST) built from independent sequences. Then we present simplified proofs and extend our analysis of LZ'78 algorithm to include new results on the convergence of moments, moderate and large deviations, and redundancy analysis.

We investigate the fundamental capacity limits of space-time journeys of information in mobile and Delay Tolerant Networks (DTNs), where information is either transmitted or carried by mobile nodes, using store-carry-forward routing. We define the capacity of a journey (i.e., a path in space and time, from a source to a destination) as the maximum amount of data that can be transferred from the source to the destination in the given journey. Combining a stochastic model (conveying all possible journeys) and an analysis of the durations of the nodes' encounters, we study the properties of journeys that maximize the space-time information propagation capacity, in bit-meters per second. More specifically, we provide theoretical lower and upper bounds on the information propagation speed, as a function of the journey capacity. In the particular case of random way-point-like models (i.e., when nodes move for a distance of the order of the network domain size before changing direction), we show that, for relatively large journey capacities, the information propagation speed is of the same order as the mobile node speed. This implies that, surprisingly, in sparse but large-scale mobile DTNs, the space-time information propagation capacity in bit-meters per second remains proportional to the mobile node speed and to the size of the transported data bundles, when the bundles are relatively large. We also verify that all our analytical bounds are accurate in several simulation scenarios.

In practice, ad hoc networks are still too unreliable for standard mobile and vehicular communications. It is thus important to complement current protocols in this context, with schemes guaranteeing the exchange of critical data when needed. A promising approach in this realm is to use an overlay subgraph, over which critical messages are exchanged and acknowledged in a peer to peer fashion. Overlay nodes' local databases remain thus synchronized over time, at least concerning critical data. This paper elaborates on the problem of performance, related to the discovery and maintenance of such overlay networks in a mobile ad hoc context. We analyze SLOT, an overlay selected based on a Relative Neighbour Graph (RNG) scheme. We then apply SLOT to a standard IP protocol: OSPF, a popular routing protocol which has recently been extended, with RFC 5449 and RFC 5614, to work also on mobile ad hoc networks, and which makes use of a similar overlay synchronization subgraph. This paper compares the performance of these existing OSPF mechanisms with that of SLOT-OSPF, a novel OSPF extension for mobile ad hoc networks using SLOT. Simulations show that SLOT-OSPF produces drastically less control traffic than RFC 5449 or RFC 5614, allowing SLOT-OSPF to function correctly while the other existing approaches stall, when the number of routers in the domain is large.

Vehicular Ad hoc NETworks (VANETs) aim at increasing safety on our road networks as well as bringing road users new applications and entertainment. Ad hoc networks with a linear topology appear frequently in VANETs stimulating increased interest in the study of linear ad hoc networks. Access in VANETs is usually governed by Carrier Sense Multiple Access (CSMA) techniques. Thus studying the performance of CSMA in linear ad hoc networks can be very beneficial to optimize the design of these new networks: VANETs. In this paper we analyze the performance of CSMA in linear networks. Using a simplified model for the carrier sense where only the nearest interferer is taken into account, we derive an exact model to compute the number of simultaneous transmissions in a linear VANET. We assume that the density of nodes is infinite and that all the nodes have a pending packet to transmit. We are able to extend this model to a great but finite density of nodes. For a more realistic model of CSMA where the whole interference is taken into account, we derive a lower bound for the average number of transmitters whereas the average number of transmitters with only the nearest interferer previously computed is an upper bound. We validate the results predicted by the analytical model with those obtained through simulations. We show that both approaches provide coherent results.

The goal of this paper is to increase our understanding of the fundamental performance limits of mobile and Delay Tolerant Networks (DTNs), where end-to-end multihop paths may not exist and communication routes may only be available through time and mobility. We use analytical tools to derive generic theoretical upper bounds for the information propagation speed in large scale mobile and intermittently connected networks. In other words, we upper-bound the optimal performance, in terms of delay, that can be achieved using any routing algorithm. We then show how our analysis can be applied to specific mobility models to obtain specific analytical estimates. In particular, in 2-D networks, when nodes move at a maximum speed$v$and their density$\nu $is small (the network is sparse and asymptotically almost surely disconnected), we prove that the information propagation speed is upper bounded by$(1+O(\nu ^{2}))v$in random waypoint-like models, while it is upper bounded by$O(\sqrt {\nu v} v)$for other mobility models (random walk, Brownian motion). We also present simulations that confirm the validity of the bounds in these scenarios. Finally, we generalize our results to 1-D and 3-D networks.

We study the classical problem of noisy constrained capacity in the case of the binary symmetric channel (BSC), namely, the capacity of a BSC whose input is a sequence from a constrained set. As stated by Fan , “... while calculation of the noise-free capacity of constrained sequences is well known, the computation of the capacity of a constraint in the presence of noise ... has been an unsolved problem in the half-century since Shannon's landmark paper.” We first express the constrained capacity of a binary symmetric channel with (d,k)-constrained input as a limit of the top Lyapunov exponents of certain matrix random processes. Then, we compute asymptotic approximations of the noisy constrained capacity for cases where the noise parameter ε is small. In particular, we show that whenk≤ 2d, the error term (excess of capacity beyond the noise-free capacity) isO(ε) , whereas it isO(εlogε) whenk> 2d. In both cases, we compute the coefficient of the error term. In the course of establishing these findings, we also extend our previous results on the entropy of a hidden Markov process to higher-order finite memory processes. These conclusions are proved by a combination of analytic and combinatorial methods.

The goal of this paper is to increase our understanding of the fundamental performance limits of mobile and delay tolerant networks (DTNs), where end-to-end multi-hop paths may not exist and communication routes may only be available through time and mobility. We use analytical tools to derive generic theoretical upper bounds for the information propagation speed in large scale mobile and intermittently connected networks. In other words, we upper-bound the optimal performance, in terms of delay, that can be achieved using any routing algorithm. We then show how our analysis can be applied to specific mobility and graph models to obtain specific analytical estimates. In particular, when nodes move at speed v and their density v is small (the network is sparse and surely disconnected), we prove that the information propagation speed is upper bounded by (1 + O(v2))v in the random way-point model, while it is upper bounded by O(radic(vv)v) for other mobility models (random walk, Brownian motion). We also present simulations that confirm the validity of the bounds in these scenarios.

Motivated by the fact that neighbors are generally known in practical routing algorithms, we introduce the notion of remote-spanner. Given an unweighted graph G, a sub-graph H with vertex set V (H) = V (G) is an (alpha, beta)-remote-spanner if for each pair of points u and v the distance between u and v in Hu, the graph H augmented by all the edges between u and its neighbors in G, is at most alpha times the distance between u and v in G plus beta. We extend this definition to k-connected graphs by considering the minimum length sum over k disjoint paths as a distance. We then say that an (alpha, beta)-remote-spanner is k-connecting. In this paper, we give distributed algorithms for computing (1 + epsiv, 1 - 2epsiv)-remote-spanners for any epsiv > 0, k-connecting (1, 0)-remote-spanners for any k ges 1 (yielding (1, 0)-remote-spanners for k = 1) and 2-connecting (2, -1)-remote-spanners. All these algorithms run in constant time for any unweighted input graph. The number of edges obtained for k-connecting (1, 0)-remote-spanner is within a logarithmic factor from optimal (compared to the best k-connecting (1, 0)-remote-spanner of the input graph). Interestingly, sparse (1, 0)-remote-spanners (i.e. preserving exact distances) with O(n4/3) edges exist in random unit disk graphs. The number of edges obtained for (1 + epsiv, 1-2epsiv)-remote-spanners and 2-connecting (2, -1)-remote-spanners is linear if the input graph is the unit ball graph of a doubling metric (even if distances between nodes are unknown). Our methodology consists in characterizing remote-spanners as sub-graphs containing the union of small depth tree sub-graphs dominating nearby nodes. This leads to simple local distributed algorithms.

We analyze the performance of epidemic routing in large-scale intermittently connected networks, under a random geometric graph model and for different mobility parameters (such as the random-waypoint, random walk and Brownian motion models). We derive a generic scaling law on the delay, which provides us with lower bounds: the average delay from a source to a destination and the average broadcast delay are both ¿ ((RN¿n)/vn), where n is the number of nodes in the network, vnthe maximum node speed, and Rnthe radio range.

Classical routing strategies for mobile ad hoc networks operate in a hop by hop "push mode" basis: packets are forwarded on pre-determined relay nodes, according to previously and independently established link performance metrics (e.g., using hellos or route discovery messages). Conversely, recent research has highlighted the interest in developing opportunistic routing schemes, operating in "pull mode": the next relay can be selected dynamically for each packet and each hop, on the basis of the actual network performance. This allows each packet to take advantage of the local pattern of transmissions at any time. The objective of such opportunistic routing schemes is to minimize the end-to-end delay required to carry a packet from the source to the destination. In this paper, we provide upper bounds on the packet propagation speed for opportunistic routing, in a realistic network model where link conditions are variable. We analyze the performance of various opportunistic routing strategies and we compare them with classical routing schemes. The analysis and the simulations show that opportunistic routing performs significantly better. We also investigate the effects of mobility and of random fading. Finally, we present numerical simulations that confirm the accuracy of our bounds.

Delay/disruption tolerant networks (DTNs) or intermittently connected mobile networks (ICNs) are mobile ad hoc networks where end-to-end multi-hop paths may not exist and communication routes may only be available through time and mobility. While most of the research is dedicated to the design of routing protocols, very few properties of such networks are known. In a recent paper [6], the authors provided analytical upper bounds for the information propagation speed in DTNs when they are modeled as two-dimensional Unit Disk Graphs. In this paper, we extend this study to other models by using analytical tools to derive theoretical upper-bounds of the information propagation speed. Firstly, we will present results for DTNs mapped in a space of dimension D, where D varies from 1 to 3. Secondly, we will depart from the Unit Disk Graph model to consider a more realistic model where a node captures a packet sent at distance r with probability p(r).

Classical routing strategies for mobile ad hoc networks forward packets on a pre-defined route (typically obtained by a shortest path routing protocol). Research has high-lighted the interest in developing opportunistic routing schemes, where the next relay is selected dynamically for each packet and each hop. This allows each packet to take advantage of the local pattern of transmissions at any time. The objective of such opportunistic routing schemes is to minimize the end-to-end delay required to carry a packet from the source to the destination. In this paper, we provide upper bounds on the packet propagation speed for opportunistic routing, in a realistic network model where link conditions are variable. We analyze the performance of various opportunistic routing strategies and we compare them with classical routing schemes. The analysis and simulations show that opportunistic routing performs significantly better. We also investigate the effects of mobility. Finally, we present numerical simulations that confirm the accuracy of our bounds.

We investigate the problem of enumerating the words that are common to two random strings. We show that when the source models are memoryless that the number of common words is sublinear in the length of the sequence, and linear when the source models are exactly the same. We draw the same conclusions for the number of common nodes in the associated respective suffix trees.

We study the classical problem of noisy constrained capacity in the case of the binary symmetric channel (BSC), namely, the capacity of a BSC whose input is a sequence from a constrained set. As stated in [4] "... while calculation of the noise-free capacity of constrained sequences is well known, the computation of the capacity of a constraint in the presence of noise ... has been an unsolved problem in the half-century since Shannon's landmark paper ...." We express the constrained capacity of a binary symmetric channel with (d, k)-constrained input as a limit of the top Lyapunov exponents of certain matrix random processes. We compute asymptotic approximations of the noisy constrained capacity for cases where the noise parameter epsiv is small. In particular, we show that when kles2d, the error term with respect to the constraint capacity is O(epsiv), whereas it is O(epsiv log epsiv) when k > 2d. In both cases, we compute the coefficient of the error term. We also extend previous results on the entropy of a hidden Markov process to higher-order finite memory processes.

A sequence of zeros and ones is called a (d,k)-sequence if it does not contain runs of zeros of length either less than d or greater than k, where d and k are arbitrary, but feed, positive integers and d < k. For a given pattern w, we enumerate exactly and asymptotically (d,k) sequences of length n that do not contain a given word w. We use techniques of analytic algorithms such as generating functions, combinatorial calculus, and complex asymptotics

We show that the per node overhead of traffic control in a mobile ad hoc network with N nodes with density ν moving at average speed ν can be made proportional to √νNν). In this case route between source and destination has a bounded strectch factor compared to optimal route. Since by Gupta and Kumar scaling property the per node traffic cannot be larger than some O(1/log N). Therefore there is a maximal network size which depends of speed ν and node density. We show that we moderate hypotheses (location aware nodes) this size can be significantly large.

In this paper, we investigate structural properties of multicast trees that give rise to the so-called multicast power law. The law asserts that the ratio R(n) of the average number of links in a multicast tree connecting the source to n destinations to the average number of links in a unicast path, satisfies asymptotically R(n)/spl ap/cn/sup /spl phi//, 0</spl phi/<1. In order to obtain a better insight, we first analyze some simple multicast tree topologies, which under appropriately chosen parameters give rise to the multicast power law. The asymptotic analysis of R(n) in this case indicates that it is very difficult to infer the validity of power law by observing graphs of R(n) alone. Next we introduce a new metric, "reachability degree," which is easy to measure and applicable to general networks where multicast trees are constructed as subtrees of a given spanning tree which we call Global Multicast Tree. The reachability degree is indicative of the structure of the Global Multicast Tree. We show that this metric provides a more reliable means for inferring the validity of the power law. Finally, we perform experiments on real and simulated networks to demonstrate the use of the new metric.

In this paper the entropy rate of a binary hidden Markov process (HMP) defined by observing the output of a binary symmetric channel whose input is a first-order binary Markov process is studied. Despite the simplicity of the models involved, the characterization of this entropy is a long standing open problem. By presenting the probability of a sequence under the model as a product of random matrices, and show that the entropy rate sought is a top Lyapunov exponent of the product, which explains the difficulty in its explicit computation. The same product of random matrices to derive an explicit expression for a first order Taylor approximation of the entropy rate with respect to the parameter of the binary symmetric channel is applied. The accuracy of the approximation is validated against empirical simulation results and also extends the results to Renyi's entropy of any order.

In this paper, the entropy rate of a hidden Markov process (HMP) is computed. The HMP entropy is expressed in terms of a measure Q, which solves an integral equation dependent on the parameters of the process. The measure is hard to extract from the equation in any explicit way. The study focuses on the regime where the channel parameter (noise) /spl epsiv/ is small.

Gupta and Kumar (1999) have shown that density increases wireless capacity. Grossglauser and Tse (2001) have shown that mobility also increases capacity. We quantify more precisely these properties by setting up the general laws that the propagation path must satisfy in the presence of traffic flow density. Introducing the time constraint in packet delivery, we generalize to a space-time problem with mobile networks.

Using the fact that effective wireless range decreases in inverse function of local traffic density, we show that a variable traffic density impacts the curvature of paths in a dense wireless ad hoc network the same way a variable optical density bends light paths. We set up the general laws that paths must satisfy in presence of traffic flow density. We give some example of tractable network traffic topologies.

The optimized link-state routing protocol (OLSR) is a proactive link-state routing protocol. While similar to the well-known Internet routing protocol OSPF, OLSR is designed to be simple, and to maintain connectivity in face of highly dense and dynamic networks, while being resource-economic (battery, bandwidth etc.) These characteristics make OLSR suitable as an underlaying routing protocol in a wide range of ad-hoc sensor networks. In this paper, we introduce an extension to OLSR: OSPF-style database exchange and reliable synchronization. The goal of this extension is to provide a mechanism, through which nodes in an ad-hoc sensor network can detect and correct discrepancies in their link-state databases. We qualify why the mechanism, found in OSPF, is not directly applicable for ad-hoc sensor networks, describe an adopted mechanism, accomplishing the same goal, and evaluate the performance of this mechanism in comparison to the database exchange mechanism found in OSPF. We finally discuss some applications of database exchange and reliable synchronization in ad-hoc sensor networks.

Redundancy of universal codes for a class of sources determines by how much the actual code length exceeds the optimal code length. In the minimax scenario, one designs the best code for the worst source within the class. Such minimax redundancy comes in two flavors: average minimax or worst case minimax. We study the worst case minimax redundancy of universal block codes for Markovian sources of any order. We prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to 1/2m/sup r/(m-1)log/sub 2/n+log/sub 2/A/sub m//sup r/-(lnlnm/sup 1/(m-1)/)/lnm+o(1), where n is the length of a source sequence, m is the size of the alphabet, and A/sub m//sup r/ is an explicit constant (e.g., we find that for a binary alphabet m=2 and Markov of order r=1 the constant A/sub 2//sup 1/=16/spl middot/G/spl ap/14.655449504 where G is the Catalan number). Unlike previous attempts, we view the redundancy problem as an asymptotic evaluation of certain sums over a set of matrices representing Markov types. The enumeration of Markov types is accomplished by reducing it to counting Eulerian paths in a multigraph. In particular, we propose exact and asymptotic formulas for the number of strings of a given Markov type. All of these findings are obtained by analytic and combinatorial tools of analysis of algorithms.

We consider a universal predictor based on pattern matching. Given a sequence X/sub 1/, ..., X/sub n/ drawn from a stationary mixing source, it predicts the next symbol X/sub n+1/ based on selecting a context of X/sub n+1/. The predictor, called the sampled pattern matching (SPM), is a modification of the Ehrenfeucht-Mycielski (1992) pseudorandom generator algorithm. It predicts the value of the most frequent symbol appearing at the so-called sampled positions. These positions follow the occurrences of a fraction of the longest suffix of the original sequence that has another copy inside X/sub 1/X/sub 2//spl middot//spl middot//spl middot/X/sub n/; that is, in SPM, the context selection consists of taking certain fraction of the longest match. The study of the longest match for lossless data compression was initiated by Wyner and Ziv in their 1989 seminal paper. Here, we estimate the redundancy of the SPM universal predictor, that is, we prove that the probability the SPM predictor makes worse decisions than the optimal predictor is O(n/sup -/spl nu//) for some 0</spl nu/< 1/2 as n/spl rarr//spl infin/. As a matter of fact, we show that we can predict K=O(1) symbols with the same probability of error.

This paper proposes a simple but effective admission control algorithm for integrated services packet networks. The admission control scheme, based on stochastic control, aims at ensuring user discrimination, by enforcing different call blocking probabilities. The queueing behavior of reservations is analytically characterized in the absence of admission control. From this, call blocking probabilities and analytical estimates of the performance of admission control are derived, allowing proper tuning of the algorithm. Simulations illustrate the effectiveness of the algorithm.

We present different aspects of quality of service that should be adapted to the BRAIN architecture. Several parameters and policies of QoS are depicted. Also, the paper shows the dynamic adaptation of these parameters in the context of BRAIN.

We analyze the possibility to apply the tree random access protocol (also called the stack protocol) for the W-CDMA part in the UTRA radio interface proposition. We study also a priority system applied on the random access directly. The analytical model uses generating functions and an algebraic method in order to show the stack protocol performance. Also, numerical and simulation results are presented and show the predominance of this protocol compared with the slotted ALOHA mechanism.

We investigate the basic question of information theory, namely, evaluation of Shannon entropy, and a more general Renyi (1961) entropy, for some discrete distributions (e.g., binomial, negative binomial, etc.). We aim at establishing analytic methods (i.e., those in which complex analysis plays a pivotal role) for such computations which often yield estimates of unparalleled precision. The main analytic tool used here is that of analytic poissonization and depoissonization. We illustrate our approach on the entropy evaluation of the binomial distribution, that is, we prove that for binomial (n, p) distribution Shannon's h/sub n/ becomes h/sub n//spl ap/ 1/2 ln n+ 1/2 +ln/spl radic/(2/spl pi/p(1-p))+/spl Sigma//sub k/spl ges/1/a/sub k/n/sup -k/ where a/sub k/ are explicitly computable constants. Moreover, we argue that analytic methods (e.g., complex asymptotics such as Rice's method and singularity analysis, Mellin transforms, poissonization, and depoissonization) can offer new tools for information theory, especially for studying second-order asymptotics (e.g., redundancy). In fact, there has been a resurgence of interest and a few successful applications of analytic methods to a variety of problems of information theory, therefore, we propose to name such investigations as analytic information theory.

The collision detection (CD) is an interesting feature which provides optimal performance to radio LANs such to make the latter comparable to wired LANs (e.g. Ethernet). The European HIPERLAN 20 Mbps standard is the natural environment for this implementation, since this standard involves the most powerful physical base and the most multivalent architecture for radio LANs. We describe one possible way to detect collision in a radio LAN, based on the so-called Comb strategy which is very similar to collision detection. This technique is developed and implemented in LAURA Esprit project.

We consider a functional-differential equation of the form ah~(z, u)+,8h(z, u) = ~(zap, u).h(zuq, a)+ a(.z, u) with h(O, ti) = 1 where p + q = 1, cz,~are nonnegative constants, h~(.,.) denotes the partial derivative with respect to z, and a and z are complex numbers, This equation arises in numerous problems in combinatorics, computer science, data compression and molecular biology (e.g., complexity

Digital tries occur in a variety of computer and communication algorithms, including symbolic manipulations, compiling, comparison-based searching and sorting, digital retrieval techniques, algorithms on strings, file systems, codes, and communication protocols. The depth of the PATRICIA trie in a probabilistic framework is studied. The PATRICIA trie is a digital tree in which nodes that would otherwise have only one branch have been collapsed into nodes having more than one branch. Because of this characteristic, the depth of the PATRICIA trie provides a measure on the compression of the keys stored in the trie. Here, n independent keys that are random strings of symbols from a V-ary alphabet are considered. This model is known as the Bernoulli model. This paper shows that the depth in the asymmetric case (i.e., symbols from the alphabet do not occur with the same probability) is asymptotically normally distributed. In the symmetric case, which surprisingly proved to be more difficult, the limiting generating function and the limiting distribution are presented. In either case, the results point to the conclusion that the PATRICIA trie is with high probability a well-balanced tree.

An analytical evaluation is given of the behavior of the free access stack algorithm when the input load, a Poisson flow of lambda packet per slot, is above the maximum throughput achievable by the protocol (within 0.360177 packet per slot) under an infinite population model. In particular, the marginal output stream that the system sustains on the channel is analytically and quantitatively derived.>

Flow control algorithms specially designed for high speed networks are introduced. They are based on a new queuing model called the La Palice queue. An algorithm that is simply an extrapolation of the classic flow control algorithm with a request to the destination and an answer to the source is presented. It is shown that the overflow occurrence is lowered to a certain probability by the application of the algorithm. An intermediate algorithm is presented that cancels overflow occurrence, but allows repetition of requests with a certain probability per multipacket message.>

article Free Access Share on Subexponential tail distribution in LaPalice queues Author: Philippe Jacquet INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 Le Chesnay cedex, France INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 Le Chesnay cedex, FranceView Profile Authors Info & Claims ACM SIGMETRICS Performance Evaluation ReviewVolume 20Issue 1June 1992 pp 60–69https://doi.org/10.1145/149439.133087Online:01 June 1992Publication History 2citation155DownloadsMetricsTotal Citations2Total Downloads155Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A complete characterization of a digital tree, also called a trie, is presented from the depth viewpoint in a Markovian framework, that is, under the assumption that symbols in a key are Markov-dependent. The main findings show that asymptotically, as the number of keys n tends to infinity, the average depth becomes ED/sub n/ approximately (1/h/sub 1/) log N+c', and the variance is var D/sub n/ approximately alpha log n+c", where h/sub 1/ is the entropy of the (Markovian-dependent) alphabet, alpha is a parameter of the probabilistic model and c' and c" are constants. The symmetric independent model has alpha =0, hence in this case var D/sub n/=O(1). Limiting distribution is also derived for the depth D/sub n/, and in particular, it is shown that D/sub n/ tends to the normal distribution in all cases except the symmetric independent model. These results extend all previous analyses since most of them have been limited to independent models.>

In high-speed networks, the ratio of the end-to-end propagation delay to the transmission delay may exceed one. Under these conditions, neither token-passing nor conventional CSMA/CD schemes can work efficiently. Previous work on access protocols for high-speed networks is generally based on round-robin service and can only operate on unidirectional media. This paper introduces new high-speed access protocols which can work on various LAN's topologies (star, tree, unidirectional media) and also on satellite networks. Based on a tree algorithm with deferred collision detection, this protocol includes mechanisms which reduce collisions and increase throughput. The maximum channel utilization can reach 100% whatever the propagation delay and the total connected population may be.

An exact performance evaluation of the free-access stack collision resolution algorithm is given under the hypotheses of carrier-sense multiple access with collision detection (CSMA-CD) local area network communication with packets of different length. In particular, the packet delay moments (mean and variance) and the maximum throughput that the system achieves for any given packet length distribution are precisely described.>

The interval searching algorithm for broadcast communications of Gallager and Tsybakov and Mikhailov is analyzed. Ultimate characterizations of the burst response of the algorithm, that is, when the number of collided packets becomes large is presented. Three quantities are of interest: the conflict resolution interval (CRI); the fraction of the resolved interval (RI); and the number of resolved packets (RP). If n is the multiplicity of a conflict, then it is proved that the mth moments of CRI, RI, and RP are $O(\log ^m n)$, $O(n^{ - m} )$ and $O(1)$, respectively. In addition, for the first two moments of these parameters precise asymptotic approximations are presented. The methodology proposed in this paper is applicable to asymptotic analysis of any problem that can be reduced to a solution of the functional equation$f(x) = 2^s \cdot f({x / 2}) \cdot a(x) + b(x)$ , where s is an integer and $a(x),b(x)$ are given functions.

A precise asymptotic expansion of the variance of the size of a trie built on random binary strings is presented. This data structure appears in some hashing schemes and communications protocols. The variance is asymptotically linear, and numerical results are given. The reader is referred to an earlier work for formal proofs.>

An exact analysis is given of the main parameters that characterize the properties of the Capetanakis-Tsybakov-Mikhailov collision resolution algorithm with the free-access (continuous input) protocol. In particular, the distributions of the collision resolution interval, the delay experienced by a packet, and the state of the top level of the stack that is maintained by the algorithm are determined.