{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T21:39:33Z","timestamp":1763415573620,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,12,19]],"date-time":"2021-12-19T00:00:00Z","timestamp":1639872000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,19]],"date-time":"2021-12-19T00:00:00Z","timestamp":1639872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P02002X\/1"],"award-info":[{"award-number":["EP\/P02002X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,4]]},"abstract":"Abstract<\/jats:title>We study here systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration to carry out a given task. Also, the distributed task itself may now require a global reconfiguration from a given initial network $$G_s$$<\/jats:tex-math>\n \n G<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to a target network $$G_f$$<\/jats:tex-math>\n \n G<\/mml:mi>\n f<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> from a desirable family of networks. To formally capture costs associated with creating and maintaining connections, we define three edge-complexity measures: the total edge activations<\/jats:italic>, the maximum activated edges per round<\/jats:italic>, and the maximum activated degree of a node<\/jats:italic>. We give (poly)log(n<\/jats:italic>) time algorithms for the task of transforming any $$G_s$$<\/jats:tex-math>\n \n G<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> into a $$G_f$$<\/jats:tex-math>\n \n G<\/mml:mi>\n f<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of diameter (poly)log(n<\/jats:italic>), while minimizing the edge-complexity. Our main lower bound shows that $$\\varOmega (n)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> total edge activations and $$\\varOmega (n\/\\log n)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> activations per round must be paid by any algorithm (even centralized) that achieves an optimum of $$\\varTheta (\\log n)$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds. We give three distributed algorithms for our general task. The first runs in $$O(\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, with at most 2n<\/jats:italic> active edges per round, a total of $$O(n\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edge activations, a maximum degree $$n-1$$<\/jats:tex-math>\n \n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter $$O(\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and uses O<\/jats:italic>(n<\/jats:italic>) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n<\/jats:italic>) then we can achieve $$o(\\log ^2 n)$$<\/jats:tex-math>\n \n o<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> running time.<\/jats:p>","DOI":"10.1007\/s00446-021-00415-5","type":"journal-article","created":{"date-parts":[[2021,12,19]],"date-time":"2021-12-19T13:02:12Z","timestamp":1639918932000},"page":"185-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Distributed computation and reconfiguration in actively dynamic networks"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6234-3960","authenticated-orcid":false,"given":"Othon","family":"Michail","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2514-8004","authenticated-orcid":false,"given":"George","family":"Skretas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5396-3749","authenticated-orcid":false,"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,19]]},"reference":[{"issue":"5","key":"415_CR1","doi-asserted-by":"publisher","first-page":"1316","DOI":"10.1007\/s00453-020-00784-6","volume":"83","author":"HA Akitaya","year":"2021","unstructured":"Akitaya, H.A., Arkin, E.M., Damian, M., Demaine, E.D., Dujmovi\u0107, V., Flatland, R., Korman, M., Palop, B., Parada, I., van Renssen, A., Sacrist\u00e1n, V.: Universal reconfiguration of facet-connected modular robots by pivots: the $${O(1)}$$ musketeers. Algorithmica 83(5), 1316\u20131351 (2021)","journal-title":"Algorithmica"},{"key":"415_CR2","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.tcs.2020.04.026","volume":"830\u2013831","author":"A Almethen","year":"2020","unstructured":"Almethen, A., Michail, O., Potapov, I.: Pushing lines helps: Efficient universal centralised transformations for programmable matter. Theor. Comput. Sci. 830\u2013831, 43\u201359 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"415_CR3","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Chen, J., Wu, Y., Yin, Y.: Fast construction of overlay networks. In: 17th ACM symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 145\u2013154 (2005)","DOI":"10.1145\/1073970.1073991"},{"issue":"4","key":"415_CR4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235\u2013253 (2006)","journal-title":"Distrib. Comput."},{"issue":"4","key":"415_CR5","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00446-007-0040-2","volume":"20","author":"D Angluin","year":"2007","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20(4), 279\u2013304 (2007)","journal-title":"Distrib. Comput."},{"key":"415_CR6","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Middleware for Network Eccentric and Mobile Applications, pp. 97\u2013120. Springer, Berlin (2009)","DOI":"10.1007\/978-3-540-89707-1_5"},{"issue":"4","key":"415_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/1290672.1290674","volume":"3","author":"J Aspnes","year":"2007","unstructured":"Aspnes, J., Shah, G.: Skip graphs. ACM Trans. Algorithms (TALG) 3(4), 37 (2007)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"415_CR8","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Wu, Y.: $$o(\\log n)$$-time overlay network construction from graphs with out-degree 1. In: 11th International Conference On Principles Of Distributed Systems (OPODIS), pp. 286\u2013300 (2007)","DOI":"10.1007\/978-3-540-77096-1_21"},{"key":"415_CR9","doi-asserted-by":"crossref","unstructured":"Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger\u2019s theorem. Networks 28(3), 125\u2013134 (1996)","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<125::AID-NET1>3.0.CO;2-P"},{"issue":"8","key":"415_CR10","first-page":"48","volume":"8","author":"S Berman","year":"2019","unstructured":"Berman, S., Fekete, S.P., Patitz, M.J., Scheideler, C.: Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 18331). Dagstuhl Rep. 8(8), 48\u201366 (2019)","journal-title":"Dagstuhl Rep."},{"key":"415_CR11","doi-asserted-by":"crossref","unstructured":"Bourgeois, J., Goldstein, S.C.: Distributed intelligent mems: progresses and perspectives. In: International Conference on ICT Innovations, pp. 15\u201325 (2011)","DOI":"10.1007\/978-3-642-28664-3_2"},{"issue":"5","key":"415_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"415_CR13","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A. W., Scheideler, C., Strothmann, T.: Amoebot\u2014a new model for programmable matter. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (New York, NY, USA), SPAA \u201914, pp. 220\u2013222 (2014)","DOI":"10.1145\/2612669.2612712"},{"key":"415_CR14","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.jcss.2021.01.007","volume":"119","author":"J Enright","year":"2021","unstructured":"Enright, J., Meeks, K., Mertzios, G.B., Zamaraev, V.: Deleting edges to restrict the size of an epidemic in temporal networks. J. Comput. Syst. Sci. 119, 60\u201377 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"415_CR15","unstructured":"Gmyr, R., Hinnenthal, K., Scheideler, C., Sohler, C.: Distributed monitoring of network properties: the power of hybrid networks. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 137:1\u2013137:15 (2017)"},{"key":"415_CR16","doi-asserted-by":"crossref","unstructured":"G\u00f6tte, T., Hinnenthal, K., Scheideler, C.: Faster construction of overlay networks. In: 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 262\u2013276 (2019)","DOI":"10.1007\/978-3-030-24922-9_18"},{"issue":"4","key":"415_CR17","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820\u2013842 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"415_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: 42nd ACM Symposium on Theory of Computing (STOC), pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"issue":"6228","key":"415_CR19","doi-asserted-by":"publisher","first-page":"1261689","DOI":"10.1126\/science.1261689","volume":"347","author":"MA McEvoy","year":"2015","unstructured":"McEvoy, M.A., Correll, N.: Materials that couple sensing, actuation, computation, and communication. Science 347(6228), 1261689 (2015)","journal-title":"Science"},{"issue":"4","key":"415_CR20","doi-asserted-by":"publisher","first-page":"1416","DOI":"10.1007\/s00453-018-0478-6","volume":"81","author":"GB Mertzios","year":"2019","unstructured":"Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 1416\u20131449 (2019)","journal-title":"Algorithmica"},{"issue":"22","key":"415_CR21","doi-asserted-by":"publisher","first-page":"2434","DOI":"10.1016\/j.tcs.2011.02.003","volume":"412","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theor. Comput. Sci. 412(22), 2434\u20132450 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"415_CR22","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P. G.: Naming and counting in anonymous unknown dynamic networks. In: 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 281\u2013295 (2013)","DOI":"10.1007\/978-3-319-03089-0_20"},{"key":"415_CR23","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jcss.2018.12.001","volume":"102","author":"O Michail","year":"2019","unstructured":"Michail, O., Skretas, G., Spirakis, P.G.: On the transformation capability of feasible mechanisms for programmable matter. J. Comput. Syst. Sci. 102, 18\u201339 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"415_CR24","doi-asserted-by":"crossref","unstructured":"Michail, O., Skretas, G., Spirakis, P.G.: Distributed computation and reconfiguration in actively dynamic networks. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, New York, NY, USA, PODC \u201920, pp. 448\u2013457 (2020)","DOI":"10.1145\/3382734.3405744"},{"issue":"3","key":"415_CR25","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00446-015-0257-4","volume":"29","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. Distrib. Comput. 29(3), 207\u2013237 (2016)","journal-title":"Distrib. Comput."},{"key":"415_CR26","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2016.02.040","volume":"671","author":"O Michail","year":"2017","unstructured":"Michail, O., Spirakis, P.G.: Connectivity preserving network transformers. Theor. Comput. Sci. 671, 36\u201355 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"415_CR27","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104\u2013110 (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"415_CR28","doi-asserted-by":"crossref","unstructured":"Piranda, B., Bourgeois, J.: Designing a quasi-spherical module for a huge modular robot to create programmable matter. Auton. Robot. 42, 1619\u20131633 (2018)","DOI":"10.1007\/s10514-018-9710-0"},{"key":"415_CR29","unstructured":"Scheideler, C., Setzer, A.: On the complexity of local graph transformations. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 150:1\u2013150:14 (2019)"},{"issue":"4","key":"415_CR30","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/964723.383071","volume":"31","author":"I Stoica","year":"2001","unstructured":"Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Comput. Commun. Rev. 31(4), 149\u2013160 (2001)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00415-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00415-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00415-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T03:02:48Z","timestamp":1646881368000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00415-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,19]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["415"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00415-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2021,12,19]]},"assertion":[{"value":"16 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}