Distributed Monitoring of Network Properties: The Power of Hybrid Networks

R. Gmyr, K. Hinnenthal, C. Scheideler, C. Sohler, in:, Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, pp. 137:1–137:15.

Download
Restricted 105-ICALP17-GHSS.pdf 504.16 KB
Conference Paper
Author
; ; ;
Abstract
We initiate the study of network monitoring algorithms in a class of hybrid networks in which the nodes are connected by an external network and an internal network (as a short form for externally and internally controlled network). While the external network lies outside of the control of the nodes (or in our case, the monitoring protocol running in them) and might be exposed to continuous changes, the internal network is fully under the control of the nodes. As an example, consider a group of users with mobile devices having access to the cell phone infrastructure. While the network formed by the WiFi connections of the devices is an external network (as its structure is not necessarily under the control of the monitoring protocol), the connections between the devices via the cell phone infrastructure represent an internal network (as it can be controlled by the monitoring protocol). Our goal is to continuously monitor properties of the external network with the help of the internal network. We present scalable distributed algorithms that efficiently monitor the number of edges, the average node degree, the clustering coefficient, the bipartiteness, and the weight of a minimum spanning tree. Their performance bounds demonstrate that monitoring the external network state with the help of an internal network can be done much more efficiently than just using the external network, as is usually done in the literature.
Publishing Year
Journal Title
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)
Page
137:1--137:15
LibreCat-ID

Cite this

Gmyr R, Hinnenthal K, Scheideler C, Sohler C. Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). Leibniz International Proceedings in Informatics (LIPIcs).; 2017:137:1-137:15. doi:10.4230/LIPIcs.ICALP.2017.137.
Gmyr, R., Hinnenthal, K., Scheideler, C., & Sohler, C. (2017). Distributed Monitoring of Network Properties: The Power of Hybrid Networks. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP) (pp. 137:1–137:15). http://doi.org/10.4230/LIPIcs.ICALP.2017.137
@inbook{Gmyr_Hinnenthal_Scheideler_Sohler_2017, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Distributed Monitoring of Network Properties: The Power of Hybrid Networks}, DOI={10.4230/LIPIcs.ICALP.2017.137}, booktitle={Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)}, author={Gmyr, Robert and Hinnenthal, Kristian and Scheideler, Christian and Sohler, Christian}, year={2017}, pages={137:1–137:15}, collection={Leibniz International Proceedings in Informatics (LIPIcs)}}
Gmyr, Robert, Kristian Hinnenthal, Christian Scheideler, and Christian Sohler. “Distributed Monitoring of Network Properties: The Power of Hybrid Networks.” In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 137:1–137:15. Leibniz International Proceedings in Informatics (LIPIcs), 2017. doi:10.4230/LIPIcs.ICALP.2017.137.
R. Gmyr, K. Hinnenthal, C. Scheideler, and C. Sohler, “Distributed Monitoring of Network Properties: The Power of Hybrid Networks,” in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, pp. 137:1–137:15.
Gmyr, Robert et al. “Distributed Monitoring of Network Properties: The Power of Hybrid Networks.” Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). N.p., 2017. 137:1–137:15. Web. Leibniz International Proceedings in Informatics (LIPIcs).
Main File(s)
File Name
105-ICALP17-GHSS.pdf 504.16 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-13T09:23:11Z

frontdoor.tabs.publications.cited_by
This publication cites the following data publications:

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar