We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Ephemeral networks with random availability of links : the case of fast networks.

Akrida, E.C. and Gąsieniec, L. and Mertzios, G.B. and Spirakis, P.G. (2016) 'Ephemeral networks with random availability of links : the case of fast networks.', Journal of parallel and distributed computing., 87 . pp. 109-120.


We consider here a model of temporal networks, the links of which are available only at certain moments in time, chosen randomly from a subset of the positive integers. We define the notion of the Temporal Diameter of such networks. We also define fast and slow such temporal networks with respect to the expected value of their temporal diameter. We then provide a partial characterisation of fast random temporal networks. We also define the critical availability as a measure of periodic random availability of the links of a network, required to make the network fast. We finally give a lower bound as well as an upper bound on the (critical) availability.

Item Type:Article
Keywords:Temporal networks, Random input, Diameter, Availability.
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2015 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:14 October 2015
Date deposited:28 October 2015
Date of first online publication:24 October 2015
Date first made open access:24 October 2016

Save or Share this output

Look up in GoogleScholar