Ephemeral networks with random availability of links: The case of fast networks

Eleni C. Akrida, Leszek Gąsieniec, George B. Mertzios, Paul G. Spirakis

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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 characterization 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.

Original languageEnglish (US)
Pages (from-to)109-120
Number of pages12
JournalJournal of Parallel and Distributed Computing
StatePublished - Jan 1 2016
Externally publishedYes


  • Availability
  • Diameter
  • Random input
  • Temporal networks

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Ephemeral networks with random availability of links: The case of fast networks'. Together they form a unique fingerprint.

Cite this