{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:27Z","timestamp":1750220427215,"version":"3.41.0"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001821","name":"WWTF","doi-asserted-by":"crossref","award":["ICT19-045"],"award-info":[{"award-number":["ICT19-045"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Austrian Science Fund (FWF) and netIDEE","award":["P 33775-N"],"award-info":[{"award-number":["P 33775-N"]}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["840605"],"award-info":[{"award-number":["840605"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["805223"],"award-info":[{"award-number":["805223"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2021,2,18]]},"abstract":"<jats:p>Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic \\congest model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of \u03b1 edge label changes arrive, \\beginitemize \\item how much time as a function of \u03b1 we need to update an existing solution, and \\item how much information the nodes have to keep in local memory between batches in order to update the solution quickly. \\enditemize Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.<\/jats:p>","DOI":"10.1145\/3447384","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T22:23:33Z","timestamp":1614032613000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Input-Dynamic Distributed Algorithms for Communication Networks"],"prefix":"10.1145","volume":"5","author":[{"given":"Klaus-Tycho","family":"Foerster","sequence":"first","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]},{"given":"Janne H.","family":"Korhonen","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}]},{"given":"Ami","family":"Paz","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]},{"given":"Joel","family":"Rybicki","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1007\/978-3-662-53426-7_3"},{"key":"e_1_2_1_2_1","volume-title":"Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 434--443","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2014. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 434--443. https:\/\/doi.org\/10. 1109\/FOCS.2014.53"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/3087556.3087595"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/3323165.3323196"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1989493.1989498"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.4230\/LIPIcs.ICALP.2019.13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/3188745.3188922"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1137\/1.9781611975482.116"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/3393691.3394205"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1391289.1391292"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/129712.129767"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/3293611.3331597"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/IPDPS.2019.00015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1007\/s00446-009-0088-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/3212734.3212769"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1137\/1.9781611975482.115"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1016\/j.ic.2018.02.005"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1080\/17445760.2012.668546"},{"key":"e_1_2_1_20_1","volume-title":"Fast Deterministic Algorithms for Highly-Dynamic Networks. CoRR abs\/1901.04008","author":"Censor-Hillel Keren","year":"2020","unstructured":"Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. 2020. Fast Deterministic Algorithms for Highly-Dynamic Networks. CoRR abs\/1901.04008 (2020). http:\/\/arxiv.org\/abs\/1901.04008"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/3293611.3331633"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/2933057.2933083"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1016\/j.tcs.2019.11.006"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1016\/S0304-"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1007\/s00446-019-00368-w"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1137\/11085178X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1137\/1.9781611975994.79"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/361179.361202"},{"doi-asserted-by":"crossref","unstructured":"Shlomi Dolev. 2000. Self-Stabilization. Cambridge MA.","key":"e_1_2_1_29_1","DOI":"10.7551\/mitpress\/6156.001.0001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_2_1_31_1","volume-title":"Improved Algorithms for Fully Dynamic Maximal Independent Set. CoRR abs\/1804.08908","author":"Du Yuhao","year":"2018","unstructured":"Yuhao Du and Hengjie Zhang. 2018. Improved Algorithms for Fully Dynamic Maximal Independent Set. CoRR abs\/1804.08908 (2018). http:\/\/arxiv.org\/abs\/1804.08908"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/3313276.3316379"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_2_1_34_1","volume-title":"arXiv preprint arXiv:1710.11583","author":"Feamster Nick","year":"2017","unstructured":"Nick Feamster and Jennifer Rexford. 2017. Why (and how) networks should run themselves. arXiv preprint arXiv:1710.11583 (2017)."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the Afternoon Workshop on Self- Driving Networks, SelfDN@SIGCOMM 2018","author":"Feamster Nick","year":"2018","unstructured":"Nick Feamster, Jennifer Rexford, and Walter Willinger (Eds.). 2018. Proceedings of the Afternoon Workshop on Self- Driving Networks, SelfDN@SIGCOMM 2018, Budapest, Hungary, August 24, 2018. ACM. http:\/\/dl.acm.org\/citation.cfm? id=3229584"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1109\/INFOCOM.2019.8737382"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/3293611.3331581"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1016\/j.tcs.2016.11.018"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/3007748.3007779"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1109\/NCA.2019.8935035"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1109\/INFCOM.2000.832225"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/2500098.2500103"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1145\/3350755.3400240"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.4230\/LIPIcs.ESA.2017.45"},{"key":"e_1_2_1_45_1","volume-title":"Simple dynamic algorithms for Maximal Independent Set and other problems. CoRR abs\/1804.01823","author":"Gupta Manoj","year":"2018","unstructured":"Manoj Gupta and Shahbaz Khan. 2018. Simple dynamic algorithms for Maximal Independent Set and other problems. CoRR abs\/1804.01823 (2018). http:\/\/arxiv.org\/abs\/1804.01823"},{"doi-asserted-by":"publisher","unstructured":"Monika Henzinger. 2018. The State of the Art in Dynamic Graph Algorithms. In SOFSEM 2018: Theory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science. 40--44. https:\/\/doi.org\/10.1007\/978--3--319--73117--9_3","key":"e_1_2_1_46_1","DOI":"10.1007\/978--3--319--73117--9_3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1137\/140957299"},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1145\/2746539.2746609"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1145\/320211.320215"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1145\/502090.502095"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1007\/BFb0022448"},{"doi-asserted-by":"publisher","key":"e_1_2_1_52_1","DOI":"10.1145\/3323165.3323202"},{"doi-asserted-by":"publisher","key":"e_1_2_1_53_1","DOI":"10.1007\/978-3-319-03850-6_14"},{"doi-asserted-by":"publisher","key":"e_1_2_1_54_1","DOI":"10.4230\/LIPIcs.OPODIS"},{"doi-asserted-by":"publisher","key":"e_1_2_1_55_1","DOI":"10.1145\/1806689.1806760"},{"volume-title":"Communication complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication complexity. Cambridge University Press.","key":"e_1_2_1_56_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_57_1","DOI":"10.1145\/2484239.2501983"},{"doi-asserted-by":"publisher","key":"e_1_2_1_58_1","DOI":"10.1137\/S0097539704441848"},{"doi-asserted-by":"publisher","key":"e_1_2_1_59_1","DOI":"10.1109\/SDS.2017.7939138"},{"doi-asserted-by":"publisher","key":"e_1_2_1_60_1","DOI":"10.1145\/2700206"},{"unstructured":"Juniper Networks. 2020. Expel complexity with a Self-Driving Network. https:\/\/www.juniper.net\/us\/en\/dm\/the-selfdriving- network\/","key":"e_1_2_1_61_1"},{"unstructured":"Krzysztof Nowicki. 2019. A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique. http:\/\/arxiv.org\/abs\/1912.04239 arXiv:1912.04239 [cs.DS].","key":"e_1_2_1_62_1"},{"key":"e_1_2_1_63_1","volume-title":"Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model. CoRR abs\/2002.07800","author":"Nowicki Krzysztof","year":"2020","unstructured":"Krzysztof Nowicki and Krzysztof Onak. 2020. Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model. CoRR abs\/2002.07800 (2020). https:\/\/arxiv.org\/abs\/2002.07800"},{"doi-asserted-by":"publisher","key":"e_1_2_1_64_1","DOI":"10.1145\/1080810.1080828"},{"doi-asserted-by":"publisher","key":"e_1_2_1_65_1","DOI":"10.1137\/1.9781611974331.ch17"},{"doi-asserted-by":"publisher","key":"e_1_2_1_66_1","DOI":"10.1007\/BFb0055050"},{"doi-asserted-by":"publisher","key":"e_1_2_1_67_1","DOI":"10.1137\/1.9780898719772"},{"doi-asserted-by":"publisher","key":"e_1_2_1_68_1","DOI":"10.1145\/319056.319004"},{"key":"e_1_2_1_69_1","volume-title":"Davie","author":"Peterson Larry L.","year":"2011","unstructured":"Larry L. Peterson and Bruce S. Davie. 2011. Computer Networks, Fifth Edition: A Systems Approach (5th ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA."},{"doi-asserted-by":"publisher","key":"e_1_2_1_70_1","DOI":"10.1007\/3-540-61440-0_136"},{"doi-asserted-by":"publisher","key":"e_1_2_1_71_1","DOI":"10.1016\/0304--3975(92)90260-M"},{"doi-asserted-by":"publisher","key":"e_1_2_1_72_1","DOI":"10.1145\/2491185.2491198"},{"volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"A. Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Springer.","key":"e_1_2_1_73_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_74_1","DOI":"10.1007\/978-3-319-43659-3_41"},{"doi-asserted-by":"publisher","key":"e_1_2_1_75_1","DOI":"10.1137\/1.9781611975499.8"},{"unstructured":"David Wang. 2020. Moving towards autonomous driving networks. https:\/\/www.huawei.com\/en\/publications\/ communicate\/87\/moving-towards-autonomous-driving-networks","key":"e_1_2_1_76_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_77_1","DOI":"10.1109\/ISCC.2015.7405564"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:46:56Z","timestamp":1750193216000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,18]]},"references-count":76,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,18]]}},"alternative-id":["10.1145\/3447384"],"URL":"https:\/\/doi.org\/10.1145\/3447384","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2021,2,18]]},"assertion":[{"value":"2021-02-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}