Part of the book series:Lecture Notes in Computer Science ((LNCCN,volume 9536))
Included in the following conference series:
600Accesses
4Citations
Abstract
An interval temporal network is, informally speaking, a network whose links change with time. The terminterval means that a link may exist for one or more time intervals, calledavailability 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 \in [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 thelifetimes 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 randomised 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.
Supported in part by (i) the School of EEE and CS and the NeST initiative of the Univeristy of Liverpool, and (ii) the FET EU IP Project MULTIPLEX under contract No. 317532.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5491
- Price includes VAT (Japan)
- Softcover Book
- JPY 6864
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We can assume this, because if an edge\(e \in E\) has overlapping availability intervals, then we can consider their union as an availability interval ofe.
- 2.
E(t) are the edges that are available att and do not stop being available (immediately) after timet.
- 3.
Notice, here, the distinction between theavailability of an edge and thelifetime of an edge: availability refers to the interval that we assign to a reserved edge with the purpose to re-connect the tree when it breaks, and lifetime refers to the interval that the operator assigns to an edge after it is inserted in the tree structure and is the time interval after which the respective link in the tree structure will fail.
- 4.
An event occurs with high probability if, for any\(\gamma \ge 1\), the event occurs with probability at least\(1-{\frac{c_{\gamma }}{n^{\gamma }}}\), where\(c_{\gamma }\) depends only on\(\gamma \).
- 5.
The last box is not necessarily of size exactly\(\beta \log {n}\) but this does not affect the analysis.
- 6.
The size of a component is the number of its vertices.
- 7.
Note that increasing the size of the boxes by a constant factor, i.e., increasing the lower bound for\(\beta \) and\(\alpha \), can enforce the re-connection probability to also increase.
References
Akrida, E.C., Gąsieniec, L., Mertzios, G.B., Spirakis, P.G.: Ephemeral networks with random availability of links: diameter and connectivity. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2014)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput.18(4), 235–253 (2006)
Avin, C., Koucký, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 121–132. Springer, Heidelberg (2008)
Bui-Xuan, B.-M., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci.14(2), 267–285 (2003)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. (IJPEDS)27(5), 387–408 (2012)
Clementi, A.E.F., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time of edge-markovian evolving graphs. SIAM J. Discrete Math. (SIDMA)24(4), 1694–1712 (2010)
Cooper, C., Klasing, R., Radzik, T.: A randomized algorithm for the joining protocol in dynamic distributed networks. Theor. Comput. Sci.406(3), 248–262 (2008)
Duchon, P., Duvignau, R.: Local update algorithms for random graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 367–378. Springer, Heidelberg (2014)
Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z., Viola, E.: On the complexity of information spreading in dynamic networks. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 717–736 (2013)
Fleischer, L., Skutella, M.: Quickest flows over time. SIAM J. Comput.36(6), 1600–1630 (2007)
Fleischer, L., Tardos, É.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett.23(3–5), 71–80 (1998)
Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 210–219 (2001)
Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput.34(1), 23–40 (2004)
Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 504–513 (2000)
Koch, R., Nasrabadi, E., Skutella, M.: Continuous and discrete flows over time - a general model based on measure theory. Math. Methods OR73(3), 301–337 (2011)
Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 513–522 (2010)
Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013)
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol. 7702, pp. 269–283. Springer, Heidelberg (2012)
Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics, vol. 23. Springer, Heidelberg (2002)
O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104–110 (2005)
Scheideler, C.: Models and techniques for communication in dynamic networks. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, pp. 27–49. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Department of Computer Science, University of Liverpool, Liverpool, UK
Eleni C. Akrida & Paul G. Spirakis
Computer Technology Institute and Press “Diophantus” (CTI), Patras, Greece
Paul G. Spirakis
- Eleni C. Akrida
Search author on:PubMed Google Scholar
- Paul G. Spirakis
Search author on:PubMed Google Scholar
Corresponding author
Correspondence toEleni C. Akrida.
Editor information
Editors and Affiliations
Carleton University, Ottawa, Ontario, Canada
Prosenjit Bose
University of Liverpool, Liverpool, United Kingdom
Leszek Antoni Gąsieniec
Graz University of Technology, Graz, Austria
Kay Römer
ETH Zurich, Zürich, Switzerland
Roger Wattenhofer
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Akrida, E.C., Spirakis, P.G. (2015). On Verifying and Maintaining Connectivity of Interval Temporal Networks. In: Bose, P., Gąsieniec, L., Römer, K., Wattenhofer, R. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2015. Lecture Notes in Computer Science(), vol 9536. Springer, Cham. https://doi.org/10.1007/978-3-319-28472-9_11
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-319-28471-2
Online ISBN:978-3-319-28472-9
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative