Upcoming mobile network technologies developed in the context of 5G and DSRC are expected to finally legitimize direct data transfers among vehicles as a standard communication paradigm. We investigate fundamental properties of the topology of vehicular networks built on top of these emerging vehicle-to-vehicle communication technologies. Our study yields multiple elements of originality: ( i) it addresses temporal connectivity, which has been poorly investigated despite a high relevance for vehicular network operations; (ii) it introduces exact but computationally efficient models of the temporal connectivity of vehicular networks; (iii) it evaluates the proposed models in urban settings that exhibit an unprecedented combination of dependability, scale and generality of vehicular mobility. This approach lets us unveil an apparent scale-and city-invariant law of temporal reachability in vehicular networks. Finally, we open our original scenarios to the research community, so as to ensure reproducibility of our results and foster further investigations of vehicular network performance.

Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader . If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this article, we study deterministic leader election in anonymous trees. Our aim is to establish tradeoffs between the allocated time τ and the amount of information that has to be given a priori to the nodes to enable leader election in time τ in all trees for which leader election in this time is at all possible. Following the framework of algorithms with advice , this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the size of advice . For a given time τ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time τ. For most values of τ, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let T be an n -node tree of diameter diam ⩽ D . While leader election in time diam can be performed without any advice, for time diam − 1 we give tight upper and lower bounds of Θ(log D ). For time diam − 2 we give tight upper and lower bounds of Θ(log D ) for even values of diam , and tight upper and lower bounds of Θ(log n ) for odd values of diam . Moving to shorter time, in the interval [β · diam , diam − 3] for constant β > 1/2, we prove an upper bound of O ( n log n / D ) and a lower bound of Ω( n / D ), the latter being valid whenever diam is odd or when the time is at most diam − 4. Hence, with the exception of the special case when diam is even and time is exactly diam − 3, our bounds leave only a logarithmic gap in this time interval. Finally, for time α · diam for any constant α < 1/2 (except for the case of very small diameters), we again give tight upper and lower bounds, this time Θ( n ).

Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node means that all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in anonymous trees. Our aim is to establish tradeoffs between the allocated time τ and the amount of information that has to be given a priori to the nodes to enable leader election in time τ in all trees for which leader election in this time is at all possible. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the size of advice. For a given time τ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time τ. For most values of τ, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let T be an n-node tree of diameter diam ≤ D. While leader election in time diam can be performed without any advice, for time diam – 1 we give tight upper and lower bounds of ⊝(log D). For time diam – 2 we give tight upper and lower bounds of ⊝(log D) for even values of diam, and tight upper and lower bounds of ⊝(log n) for odd values of diam. Moving to shorter time, in the interval [β · diam, diam – 3] for constant β > 1/2, we prove an upper bound of and a lower bound of , the latter being valid whenever diam is odd or when the time is at most diam – 4. Hence, with the exception of the special case when diam is even and time is exactly diam–3, our bounds leave only a logarithmic gap in this time interval. Finally, for time α · diam for any constant α < 1/2 (except for the case of very small diameters), we again give tight upper and lower bounds, this time ⊝(n).

This paper investigates compact routing schemes that are very efficient with respect to the memory used to store routing tables in internet-like graphs. We propose a new compact name-independent routing scheme whose theoretically proven average memory per node is upper-bounded by nγ, with constant γ < 1/2, while the maximum memory of any node is bounded by √n and the maximum stretch of any route is bounded by 5. These bounds are given for the Random Power Low Graphs (RPLG) and hold with high probability. Moreover, we experimentally show that our scheme is very efficient in terms of stretch and memory in internet-like graphs (CAIDA and other maps). We complete this study by comparing our analytic and experimental results to several compact routing schemes. In particular, we show that the average memory requirements is better by at least one order of magnitude than previous schemes for CAIDA maps on 16K nodes.