TY - GEN
T1 - Ephemeral networks with random availability of links
T2 - 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014
AU - Akrida, Eleni C.
AU - Mertzios, George B.
AU - Ga̧sieniec, Leszek
AU - Spirakis, Paul G.
PY - 2014
Y1 - 2014
N2 - In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are ephemeral: their links appear sporadically, only at certain times, within a given maximum time (lifetime of the net). More specifically, our temporal networks notion concerns networks, whose edges (arcs) are assigned one or more random discrete-time labels drawn from a set of natural numbers. The labels of an edge indicate the discrete moments in time at which the edge is available. In such networks, information (e.g., messages) have to follow temporal paths, i.e., paths, the edges of which are assigned a strictly increasing sequence of labels. We first examine a very hostile network: a clique, each edge of which is known to be available only one random time in the time period {1,2,⋯, n} (n is the number of vertices). How fast can a vertex send a message to all other vertices in such a network? To answer this, we define the notion of the Temporal Diameter for the random temporal clique and prove that it is T(log n) with high probability and in expectation. In fact, we show that information dissemination is very fast with high probability even in this hostile network with regard to availability. This result is similar to the results for the random phone-call model. Our model, though, is weaker. Our availability assumptions are different and randomness is provided only by the input. We show here that the temporal diameter of the clique is crucially affected by the clique's lifetime, a, e.g., when a is asymptotically larger than the number of vertices, n, then the temporal diameter must be Ω(a/n log n). We, then, consider the least number, r, of random points in time at which an edge is available, in order to guarantee at least a temporal path between any pair of vertices of the network (notice that the clique is the only network for which just one instance of availability per edge, even non-random, suffices for this). We show that r is Ω(log n) even for some networks of diameter 2. Finally, we compare this cost to an (optimal) deterministic allocation of labels of availability that guarantees a temporal path between any pair of vertices. For this reason, we introduce the notion of the Price of Randomness and we show an upper bound for general networks.
AB - In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are ephemeral: their links appear sporadically, only at certain times, within a given maximum time (lifetime of the net). More specifically, our temporal networks notion concerns networks, whose edges (arcs) are assigned one or more random discrete-time labels drawn from a set of natural numbers. The labels of an edge indicate the discrete moments in time at which the edge is available. In such networks, information (e.g., messages) have to follow temporal paths, i.e., paths, the edges of which are assigned a strictly increasing sequence of labels. We first examine a very hostile network: a clique, each edge of which is known to be available only one random time in the time period {1,2,⋯, n} (n is the number of vertices). How fast can a vertex send a message to all other vertices in such a network? To answer this, we define the notion of the Temporal Diameter for the random temporal clique and prove that it is T(log n) with high probability and in expectation. In fact, we show that information dissemination is very fast with high probability even in this hostile network with regard to availability. This result is similar to the results for the random phone-call model. Our model, though, is weaker. Our availability assumptions are different and randomness is provided only by the input. We show here that the temporal diameter of the clique is crucially affected by the clique's lifetime, a, e.g., when a is asymptotically larger than the number of vertices, n, then the temporal diameter must be Ω(a/n log n). We, then, consider the least number, r, of random points in time at which an edge is available, in order to guarantee at least a temporal path between any pair of vertices of the network (notice that the clique is the only network for which just one instance of availability per edge, even non-random, suffices for this). We show that r is Ω(log n) even for some networks of diameter 2. Finally, we compare this cost to an (optimal) deterministic allocation of labels of availability that guarantees a temporal path between any pair of vertices. For this reason, we introduce the notion of the Price of Randomness and we show an upper bound for general networks.
KW - Availability
KW - Diameter
KW - Random input
KW - Temporal networks
UR - http://www.scopus.com/inward/record.url?scp=84904479901&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904479901&partnerID=8YFLogxK
U2 - 10.1145/2612669.2612693
DO - 10.1145/2612669.2612693
M3 - Conference contribution
AN - SCOPUS:84904479901
SN - 9781450328210
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 267
EP - 276
BT - SPAA 2014 - Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
Y2 - 23 June 2014 through 25 June 2014
ER -