On Verifying and Maintaining Connectivity of Interval Temporal Networks

Akrida, Eleni C.; Spirakis, Paul G.

Abstract

An interval temporal network is, informally speaking, a network whose links change with time. The term interval means that a link may exist for one or more time intervals, called availability intervals of the link, after which it does not exist (until, maybe, a further moment in time when it starts being available again). In this model, we consider continuous time and high-speed (instantaneous) information dissemination. An interval temporal network is connected during a period of time [x,y], if it is connected for all time instances t∈[x,y] (instantaneous connectivity). In this work, we study instantaneous connectivity issues of interval temporal networks. We provide a polynomial-time algorithm that answers if a given interval temporal network is connected during a time period. If the network is not connected throughout the given time period, then we also give a polynomial-time algorithm that returns large components of the network that remain connected and remain large during [x,y]; the algorithm also considers the components of the network that start as large at time t=x but dis-connect into small components within the time interval [x,y], and answers how long after time t=x these components stay connected and large. Finally, we examine a case of interval temporal networks on tree graphs where the lifetimes of links and, thus, the failures in the connectivity of the network are not controlled by us; however, we can “feed” the network with extra edges that may re-connect it into a tree when a failure happens, so that its connectivity is maintained during a time period. We show that we can with high probability maintain the connectivity of the network for a long time period by making these extra edges available for re-connection using a randomized approach. Our approach also saves some cost in the design of availabilities of the edges; here, the cost is the sum, over all extra edges, of the length of their availability-to-reconnect interval.

Citation

Akrida, E. C., & Spirakis, P. G. (2019). On Verifying and Maintaining Connectivity of Interval Temporal Networks. Parallel Processing Letters, 29(02), Article 1950009. https://doi.org/10.1142/s0129626419500099

• Journal Article Type: Article
• Acceptance Date: Jul 9, 2019
• Online Publication Date: Jul 23, 2019
• Publication Date: 2019
• Deposit Date: Jun 20, 2020
• Publicly Available Date: Oct 26, 2021
• Journal: Parallel Processing Letters
• Print ISSN: 0129-6264
• Electronic ISSN: 1793-642X
• Publisher: World Scientific Publishing
• Peer Reviewed: Peer Reviewed
• Volume: 29
• Issue: 02
• Article Number: 1950009
• DOI: https://doi.org/10.1142/s0129626419500099
• Public URL: https://durham-repository.worktribe.com/output/1268405