{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:03:49Z","timestamp":1760241829113,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2018,8,24]],"date-time":"2018-08-24T00:00:00Z","timestamp":1535068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. 61379157"],"award-info":[{"award-number":["No. 61379157"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Program of Science and Technology of Guangdong","award":["No. 2015B010111001"],"award-info":[{"award-number":["No. 2015B010111001"]}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2016YFB0200400"],"award-info":[{"award-number":["2016YFB0200400"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Guangzhou Science and Technology Bureau","award":["201704020030"],"award-info":[{"award-number":["201704020030"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>A dynamic network is the abstraction of distributed systems with frequent network topology changes. With such dynamic network models, fundamental distributed computing problems can be formally studied with rigorous correctness. Although quite a number of models have been proposed and studied for dynamic networks, the existing models are usually defined from the point of view of connectivity properties. In this paper, instead, we examine the dynamicity of network topology according to the procedure of changes, i.e., how the topology or links change. Following such an approach, we propose the notion of the \u201cinstant path\u201d and define two dynamic network models based on the instant path. Based on these two models, we design distributed algorithms for the problem of information dissemination respectively, one of the fundamental distributing computing problems. The correctness of our algorithms is formally proved and their performance in time cost and communication cost is analyzed. Compared with existing connectivity based dynamic network models and algorithms, our procedure based ones are definitely easier to be instantiated in the practical design and deployment of dynamic networks.<\/jats:p>","DOI":"10.3390\/info9090212","type":"journal-article","created":{"date-parts":[[2018,8,24]],"date-time":"2018-08-24T11:13:45Z","timestamp":1535109225000},"page":"212","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The (T, L)-Path Model and Algorithms for Information Dissemination in Dynamic Networks"],"prefix":"10.3390","volume":"9","author":[{"given":"Zhiwei","family":"Yang","sequence":"first","affiliation":[{"name":"College of Computational Science, Zhongkai University of Agriculture and Engineering, Guangzhou 510000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weigang","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,8,24]]},"reference":[{"key":"ref_1","first-page":"753","article-title":"Evolving graphs: Dynamical models, inverse problems and propagation","volume":"466","author":"Grindrod","year":"2010","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Hoffmann, M., and Kammer, F. (2015, January 6\u201310). On temporal graph exploration. Proceedings of the International Colloquium on Automata, Languages and Programming, Kyoto, Japan.","DOI":"10.1007\/978-3-662-47672-7_36"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Datta, S., Giannella, C., and Kargupta, H. (2006, January 20\u201322). K-means clustering over a large, dynamic network. Proceedings of the Sixth SIAM International Conference on Data Mining, Bethesda, MD, USA.","DOI":"10.1137\/1.9781611972764.14"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/263876.263885","article-title":"A Cluster-based approach for routing in dynamic networks","volume":"27","author":"Vaidya","year":"1997","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., and Spirakis, P.G. (2012, January 16\u201318). Naming and counting in anonymous unknown dynamic networks. Proceedings of the 26th International Symposium on Distributed Computing (DISC), Salvador, Brazil.","DOI":"10.1007\/978-3-642-33651-5_46"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1145\/1959045.1959064","article-title":"Dynamic networks: Models and algorithms","volume":"42","author":"Kuhn","year":"2011","journal-title":"ACM SIGACT News"},{"key":"ref_7","unstructured":"Van de Bovenkamp, R., kuipers, F., and van Mieghem, P. (2012, January 21\u201325). Gossip-based counting in dynamic networks. Proceedings of the 11th International IFIP TC 6 Networking Conference, Prague, Czech Republic."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., and Wattenhofer, R. (2005, January 2). Information dissemination in highly dynamic graphs. Proceedings of the 9th Joint Workshop on Foundations of Mobile Computing, Cologne, Germany.","DOI":"10.1145\/1080810.1080828"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Haeupler, B., and Karger, D. (2011, January 6\u20138). Faster information dissemination in dynamic networks via network coding. Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, CA, USA.","DOI":"10.1145\/1993806.1993885"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., and Oshman, R. (2010, January 6\u20138). Distributed computation in dynamic networks. Proceedings of the 42nd ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806760"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., and Kumar, A. (2000, January 21\u201323). Connectivity and inference problems for temporal networks. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), Portland, OR, USA.","DOI":"10.1145\/335305.335364"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1080\/17445760.2012.668546","article-title":"Time-Varying graphs and dynamic networks","volume":"27","author":"Casteigts","year":"2012","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"070201","DOI":"10.1088\/1674-1056\/19\/7\/070201","article-title":"Multi-agent coordination in directed moving neighbourhood random networks","volume":"19","author":"Shang","year":"2010","journal-title":"Chin. Phys. B"},{"key":"ref_14","first-page":"215","article-title":"Consensus in averager-copier-voter networks of moving dynamical agents","volume":"27","author":"Shang","year":"2017","journal-title":"Chaos Interdisciplin. J. Nonlinear Sci."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Clementi, A., Macci, C., Monti, A., Pasquale, F., and Silvestri, R. (2008, January 18\u201321). Flooding time in edge-markovian dynamic graphs. Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, Toronto, ON, Canada.","DOI":"10.1145\/1400751.1400781"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Avin, C., Koucky, M., and Lotker, Z. (2008, January 7\u201311). How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland.","DOI":"10.1007\/978-3-540-70575-8_11"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1137\/0147013","article-title":"On spreading a rumor","volume":"47","author":"Pittel","year":"1987","journal-title":"SIAM J. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Clementi, A., Monti, A., and Silvestri, R. (2010, January 25\u201328). Flooding over Manhattan. Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland.","DOI":"10.1145\/1835698.1835784"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/j.amc.2014.10.129","article-title":"The Estrada index of evolving graphs","volume":"250","author":"Shang","year":"2015","journal-title":"Appl. Math. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Shang, Y. (2015). Laplacian Estrada and normalized Laplacian Estrada indices of evolving graphs. PLoS ONE, 10.","DOI":"10.1371\/journal.pone.0123426"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.tcs.2016.08.017","article-title":"On multiaspect graphs","volume":"651","author":"Wehmuth","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_22","unstructured":"Ahmadi, M., Ghodselahi, A., Kuhn, F., and Molla, A.R. (2015, January 14\u201317). The cost of global broadcast in dynamic radio networks. Proceedings of the International Conference on Principles of Distributed Systems, Rennes, France."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Yang, Z., Wu, W., Chen, Y., Li, X., and Cao, J. (2018). (Q, S)-distance model and counting algorithms in dynamic distributed systems. Int. J. Distrib. Sens. Netw., 14.","DOI":"10.1177\/1550147718756872"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Jelasity, M., Guerraoui, R., Kermarrec, A., and Steem, M. (2004, January 18\u201322). The peer sampling service: Experimental evaluation of unstructured gossip-based implementations. Proceedings of the 5th ACM\/IFIP\/USENIX International Conference on Middleware, Toronto, ON, Canada.","DOI":"10.1007\/978-3-540-30229-2_5"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1002\/rsa.20586","article-title":"Rumor spreading in random evolving graphs","volume":"48","author":"Clementi","year":"2016","journal-title":"Random Struct. Algorithms"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/15M1033113","article-title":"On the push & pull protocol for rumor spreading","volume":"31","author":"Acan","year":"2017","journal-title":"SIAM J. Discret. Math."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Augustine, J., Chen, A., Liaee, M., Pandurangan, G., and Rajaraman, R. (2016, January 27\u201329). Information spreading in dynamic networks under oblivious adversaries. Proceedings of the International Symposium on Distributed Computing, Paris, France.","DOI":"10.1007\/978-3-662-53426-7_29"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/9\/212\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:20:50Z","timestamp":1760196050000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/9\/212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,24]]},"references-count":27,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2018,9]]}},"alternative-id":["info9090212"],"URL":"https:\/\/doi.org\/10.3390\/info9090212","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2018,8,24]]}}}