[{"doi":"10.1016/j.tcs.2023.113733","date_published":"2023-02-28T00:00:00Z","date_created":"2023-02-19T23:00:55Z","has_accepted_license":"1","isi":1,"year":"2023","day":"28","publication":"Theoretical Computer Science","publisher":"Elsevier","quality_controlled":"1","oa":1,"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 805223 ScaleML) and under the Marie Skłodowska-Curie grant agreement No. 840605 and from the Natural Sciences and Engineering Research Council of Canada grant RGPIN-2020-04178. Part of this work was done while Faith Ellen was visiting IST Austria.","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"first_name":"Faith","full_name":"Ellen, Faith","last_name":"Ellen"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","last_name":"Rybicki"}],"article_processing_charge":"Yes (via OA deal)","external_id":{"isi":["000934262700001"]},"title":"Wait-free approximate agreement on graphs","citation":{"chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” Theoretical Computer Science. Elsevier, 2023. https://doi.org/10.1016/j.tcs.2023.113733.","ista":"Alistarh D-A, Ellen F, Rybicki J. 2023. Wait-free approximate agreement on graphs. Theoretical Computer Science. 948(2), 113733.","mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Theoretical Computer Science, vol. 948, no. 2, 113733, Elsevier, 2023, doi:10.1016/j.tcs.2023.113733.","apa":"Alistarh, D.-A., Ellen, F., & Rybicki, J. (2023). Wait-free approximate agreement on graphs. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.113733","ama":"Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. Theoretical Computer Science. 2023;948(2). doi:10.1016/j.tcs.2023.113733","ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” Theoretical Computer Science, vol. 948, no. 2. Elsevier, 2023.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023)."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"},{"_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Coordination in constrained and natural distributed systems","grant_number":"840605"}],"article_number":"113733","issue":"2","volume":948,"ec_funded":1,"publication_identifier":{"issn":["0304-3975"]},"publication_status":"published","file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"b27c5290f2f1500c403494364ee39c9f","file_id":"12570","success":1,"date_updated":"2023-02-20T07:30:20Z","file_size":602333,"creator":"dernst","date_created":"2023-02-20T07:30:20Z","file_name":"2023_TheoreticalCompScience_Alistarh.pdf"}],"language":[{"iso":"eng"}],"scopus_import":"1","month":"02","intvolume":" 948","abstract":[{"lang":"eng","text":"Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a node of the graph as input and, if non-faulty, must output a node such that\r\n– all the outputs are within distance 1 of one another, and\r\n– each output value lies on a shortest path between two input values.\r\nFrom prior work, it is known that there is no wait-free algorithm among processes for this problem on any cycle of length , by reduction from 2-set agreement (Castañeda et al., 2018).\r\n\r\nIn this work, we investigate the solvability of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length , via a generalisation of Sperner's Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a different class of graphs, which properly contains the class of chordal graphs."}],"oa_version":"Published Version","department":[{"_id":"DaAl"}],"file_date_updated":"2023-02-20T07:30:20Z","date_updated":"2023-08-01T13:17:20Z","ddc":["000"],"article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","_id":"12566"},{"oa_version":"Published Version","abstract":[{"text":"Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node.\r\nIn this work, we consider the more general setting where G is an arbitrary regular graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.","lang":"eng"}],"intvolume":" 217","month":"02","scopus_import":"1","alternative_title":["LIPIcs"],"language":[{"iso":"eng"}],"file":[{"creator":"dernst","file_size":959406,"date_updated":"2022-05-02T08:06:33Z","file_name":"2022_LIPICs_Alistarh.pdf","date_created":"2022-05-02T08:06:33Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"checksum":"2c7c982174c6f98c4ca6e92539d15086","file_id":"11346"}],"publication_status":"published","publication_identifier":{"isbn":["9783959772198"],"issn":["1868-8969"]},"ec_funded":1,"volume":217,"_id":"11184","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"OPODIS","start_date":"2021-12-13","end_date":"2021-12-15","location":"Strasbourg, France"},"type":"conference","ddc":["510"],"date_updated":"2022-05-02T08:09:39Z","file_date_updated":"2022-05-02T08:06:33Z","department":[{"_id":"DaAl"}],"acknowledgement":"Dan Alistarh: This project has received funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has received from the European Union’s Horizon 2020 research and\r\ninnovation programme under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock construction to non-regular graphs. We also thank anonymous reviewers for their useful comments on earlier versions of this manuscript.","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","publication":"25th International Conference on Principles of Distributed Systems","day":"01","year":"2022","has_accepted_license":"1","date_created":"2022-04-17T22:01:47Z","doi":"10.4230/LIPIcs.OPODIS.2021.14","date_published":"2022-02-01T00:00:00Z","article_number":"14","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"},{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical Population Protocols.” In 25th International Conference on Principles of Distributed Systems, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14.","ista":"Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 14.","mla":"Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” 25th International Conference on Principles of Distributed Systems, edited by Quentin Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.OPODIS.2021.14.","ama":"Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols. In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles of Distributed Systems. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.OPODIS.2021.14","apa":"Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2022). Fast graphical population protocols. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems (Vol. 217). Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14","short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population protocols,” in 25th International Conference on Principles of Distributed Systems, Strasbourg, France, 2022, vol. 217."},"editor":[{"full_name":"Bramas, Quentin","last_name":"Bramas","first_name":"Quentin"},{"full_name":"Gramoli, Vincent","last_name":"Gramoli","first_name":"Vincent"},{"first_name":"Alessia","full_name":"Milani, Alessia","last_name":"Milani"}],"title":"Fast graphical population protocols","external_id":{"arxiv":["2102.08808"]},"article_processing_charge":"No","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"}]},{"_id":"12182","status":"public","conference":{"end_date":"2022-10-27","location":"Augusta, GA, United States","start_date":"2022-10-25","name":"DISC: Symposium on Distributed Computing"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","ddc":["000"],"date_updated":"2023-01-27T06:59:29Z","file_date_updated":"2023-01-27T06:58:02Z","department":[{"_id":"DaAl"}],"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms; these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms."}],"intvolume":" 246","month":"10","scopus_import":"1","language":[{"iso":"eng"}],"file":[{"date_created":"2023-01-27T06:58:02Z","file_name":"2022_LIPICs_Pacut.pdf","creator":"dernst","date_updated":"2023-01-27T06:58:02Z","file_size":524804,"file_id":"12409","checksum":"11bbb56f68a00f2cf6bcce6cc7f5c5f9","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication_status":"published","publication_identifier":{"eisbn":["9783959772556"],"eissn":["1868-8969"]},"ec_funded":1,"volume":246,"article_number":"52","project":[{"grant_number":"840605","name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020","_id":"26A5D39A-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Pacut, Maciej, et al. “Brief Announcement: Temporal Locality in Online Algorithms.” 36th International Symposium on Distributed Computing, vol. 246, 52, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.DISC.2022.52.","ieee":"M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, and A. Tereshchenko, “Brief announcement: Temporal locality in online algorithms,” in 36th International Symposium on Distributed Computing, Augusta, GA, United States, 2022, vol. 246.","short":"M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, A. Tereshchenko, in:, 36th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","apa":"Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J., & Tereshchenko, A. (2022). Brief announcement: Temporal locality in online algorithms. In 36th International Symposium on Distributed Computing (Vol. 246). Augusta, GA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2022.52","ama":"Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. Brief announcement: Temporal locality in online algorithms. In: 36th International Symposium on Distributed Computing. Vol 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.DISC.2022.52","chicago":"Pacut, Maciej, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko. “Brief Announcement: Temporal Locality in Online Algorithms.” In 36th International Symposium on Distributed Computing, Vol. 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.DISC.2022.52.","ista":"Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. 2022. Brief announcement: Temporal locality in online algorithms. 36th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing vol. 246, 52."},"title":"Brief announcement: Temporal locality in online algorithms","article_processing_charge":"No","author":[{"last_name":"Pacut","full_name":"Pacut, Maciej","first_name":"Maciej"},{"first_name":"Mahmoud","last_name":"Parham","full_name":"Parham, Mahmoud"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"full_name":"Suomela, Jukka","last_name":"Suomela","first_name":"Jukka"},{"full_name":"Tereshchenko, Aleksandr","last_name":"Tereshchenko","first_name":"Aleksandr"}],"acknowledgement":"This research has received funding from the German Research Foundation (DFG), grant\r\n470029389 (FlexNets), 2021-2024, and the Marie Skłodowska-Curie grant agreement No. 840605.","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"36th International Symposium on Distributed Computing","day":"17","year":"2022","has_accepted_license":"1","date_created":"2023-01-13T11:06:28Z","date_published":"2022-10-17T00:00:00Z","doi":"10.4230/LIPIcs.DISC.2022.52"},{"status":"public","conference":{"name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2022-07-25","end_date":"2022-07-29","location":"Salerno, Italy"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","_id":"11844","file_date_updated":"2022-08-16T08:05:15Z","department":[{"_id":"DaAl"}],"ddc":["000"],"date_updated":"2023-06-14T12:06:01Z","month":"07","scopus_import":"1","oa_version":"Published Version","abstract":[{"lang":"eng","text":"In the stochastic population protocol model, we are given a connected graph with n nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this model is stable leader election, in which all nodes start in an identical state and the aim is to reach a configuration in which (1) exactly one node is elected as leader and (2) this node remains as the unique leader no matter what sequence of interactions follows. On cliques, the complexity of this problem has recently been settled: time-optimal protocols stabilize in Θ(n log n) expected steps using Θ(log log n) states, whereas protocols that use O(1) states require Θ(n2) expected steps.\r\n\r\nIn this work, we investigate the complexity of stable leader election on general graphs. We provide the first non-trivial time lower bounds for leader election on general graphs, showing that, when moving beyond cliques, the complexity landscape of leader election becomes very diverse: the time required to elect a leader can range from O(1) to Θ(n3) expected steps. On the upper bound side, we first observe that there exists a protocol that is time-optimal on many graph families, but uses polynomially-many states. In contrast, we give a near-time-optimal protocol that uses only O(log2n) states that is at most a factor log n slower. Finally, we show that the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor n log n slower than the fast polynomial-state protocol. Moreover, among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs."}],"ec_funded":1,"language":[{"iso":"eng"}],"file":[{"creator":"cchlebak","date_updated":"2022-08-16T08:05:15Z","file_size":1593474,"date_created":"2022-08-16T08:05:15Z","file_name":"2022_PODC_Alistarh.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"4c6b29172b8e355b4fbc364a2e0827b2","file_id":"11854","success":1}],"publication_status":"published","publication_identifier":{"isbn":["9781450392624"]},"project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"title":"Near-optimal leader election in population protocols on graphs","external_id":{"arxiv":["2205.12597"]},"article_processing_charge":"Yes (via OA deal)","author":[{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646"},{"first_name":"Sasha","full_name":"Voitovych, Sasha","last_name":"Voitovych"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal Leader Election in Population Protocols on Graphs.” In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 246–56. Association for Computing Machinery, 2022. https://doi.org/10.1145/3519270.3538435.","ista":"Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election in population protocols on graphs. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 246–256.","mla":"Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols on Graphs.” Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2022, pp. 246–56, doi:10.1145/3519270.3538435.","short":"D.-A. Alistarh, J. Rybicki, S. Voitovych, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2022, pp. 246–256.","ieee":"D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election in population protocols on graphs,” in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Salerno, Italy, 2022, pp. 246–256.","apa":"Alistarh, D.-A., Rybicki, J., & Voitovych, S. (2022). Near-optimal leader election in population protocols on graphs. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (pp. 246–256). Salerno, Italy: Association for Computing Machinery. https://doi.org/10.1145/3519270.3538435","ama":"Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population protocols on graphs. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2022:246-256. doi:10.1145/3519270.3538435"},"oa":1,"publisher":"Association for Computing Machinery","quality_controlled":"1","acknowledgement":"We thank the anonymous reviewers for their helpful comments. We gratefully acknowledge funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","date_created":"2022-08-14T22:01:46Z","doi":"10.1145/3519270.3538435","date_published":"2022-07-21T00:00:00Z","page":"246-256","publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing","day":"21","year":"2022","has_accepted_license":"1"},{"series_title":"LNCS","_id":"11707","conference":{"end_date":"2022-06-29","location":"Paderborn, Germany","start_date":"2022-06-27","name":"SIROCCO: Structural Information and Communication Complexity"},"type":"conference","status":"public","date_updated":"2023-08-03T12:16:29Z","department":[{"_id":"DaAl"}],"abstract":[{"lang":"eng","text":"In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs the structure is much more diverse."}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.08703"}],"scopus_import":"1","intvolume":" 13298","month":"06","publication_status":"published","publication_identifier":{"isbn":["9783031099922"],"eissn":["1611-3349"],"issn":["0302-9743"]},"language":[{"iso":"eng"}],"ec_funded":1,"volume":13298,"project":[{"call_identifier":"H2020","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","grant_number":"840605","name":"Coordination in constrained and natural distributed systems"}],"citation":{"ista":"Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local mending. International Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol. 13298, 1–20.","chicago":"Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela. “Local Mending.” In International Colloquium on Structural Information and Communication Complexity, edited by Merav Parter, 13298:1–20. LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-09993-9_1.","short":"A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J. Suomela, in:, M. Parter (Ed.), International Colloquium on Structural Information and Communication Complexity, Springer Nature, 2022, pp. 1–20.","ieee":"A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela, “Local mending,” in International Colloquium on Structural Information and Communication Complexity, Paderborn, Germany, 2022, vol. 13298, pp. 1–20.","apa":"Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., & Suomela, J. (2022). Local mending. In M. Parter (Ed.), International Colloquium on Structural Information and Communication Complexity (Vol. 13298, pp. 1–20). Paderborn, Germany: Springer Nature. https://doi.org/10.1007/978-3-031-09993-9_1","ama":"Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending. In: Parter M, ed. International Colloquium on Structural Information and Communication Complexity. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:10.1007/978-3-031-09993-9_1","mla":"Balliu, Alkida, et al. “Local Mending.” International Colloquium on Structural Information and Communication Complexity, edited by Merav Parter, vol. 13298, Springer Nature, 2022, pp. 1–20, doi:10.1007/978-3-031-09993-9_1."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"arxiv":["2102.08703"],"isi":["000876977400001"]},"article_processing_charge":"No","author":[{"last_name":"Balliu","full_name":"Balliu, Alkida","first_name":"Alkida"},{"full_name":"Hirvonen, Juho","last_name":"Hirvonen","first_name":"Juho"},{"last_name":"Melnyk","full_name":"Melnyk, Darya","first_name":"Darya"},{"first_name":"Dennis","full_name":"Olivetti, Dennis","last_name":"Olivetti"},{"first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646"},{"last_name":"Suomela","full_name":"Suomela, Jukka","first_name":"Jukka"}],"title":"Local mending","editor":[{"first_name":"Merav","last_name":"Parter","full_name":"Parter, Merav"}],"acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 840605. This work was supported in part by the Academy of Finland, Grants 314888 and 333837. The authors would also like to thank David Harris, Neven Villani, and the anonymous reviewers for their very helpful comments and feedback on previous versions of this work.","oa":1,"quality_controlled":"1","publisher":"Springer Nature","year":"2022","isi":1,"publication":"International Colloquium on Structural Information and Communication Complexity","day":"25","page":"1-20","date_created":"2022-07-31T22:01:49Z","doi":"10.1007/978-3-031-09993-9_1","date_published":"2022-06-25T00:00:00Z"},{"citation":{"mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population Protocols.” 35th International Symposium on Distributed Computing, vol. 209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.43.","apa":"Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2021). Brief announcement: Fast graphical population protocols. In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.43","ama":"Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical population protocols. In: 35th International Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.43","short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast graphical population protocols,” in 35th International Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement: Fast Graphical Population Protocols.” In 35th International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.43.","ista":"Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical population protocols. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 43."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"},{"last_name":"Gelashvili","full_name":"Gelashvili, Rati","first_name":"Rati"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"arxiv":["2102.08808"]},"article_processing_charge":"No","title":"Brief announcement: Fast graphical population protocols","article_number":"43","project":[{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"has_accepted_license":"1","year":"2021","day":"04","publication":"35th International Symposium on Distributed Computing","date_published":"2021-10-04T00:00:00Z","doi":"10.4230/LIPIcs.DISC.2021.43","date_created":"2021-11-07T23:01:24Z","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 840605.","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"date_updated":"2023-02-21T09:24:08Z","ddc":["000"],"file_date_updated":"2021-11-12T08:16:44Z","department":[{"_id":"DaAl"}],"_id":"10218","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"DISC: Distributed Computing ","start_date":"2021-10-04","location":"Freiburg, Germany","end_date":"2021-10-08"},"status":"public","publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"publication_status":"published","file":[{"date_created":"2021-11-12T08:16:44Z","file_name":"2021_LIPIcsDISC_Alistarh.pdf","date_updated":"2021-11-12T08:16:44Z","file_size":534219,"creator":"cchlebak","checksum":"fd2a690f6856d21247e9aa952b0e2885","file_id":"10274","success":1,"content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"volume":209,"ec_funded":1,"abstract":[{"text":"Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As an example, this implies that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties.","lang":"eng"}],"oa_version":"Published Version","scopus_import":"1","alternative_title":["LIPIcs"],"month":"10","intvolume":" 209"},{"article_number":"58","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"mla":"Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” 35th International Symposium on Distributed Computing, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.58.","apa":"Korhonen, J., Paz, A., Rybicki, J., Schmid, S., & Suomela, J. (2021). Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.58","ama":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In: 35th International Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.58","short":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","ieee":"J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement: Sinkless orientation is hard also in the supported LOCAL model,” in 35th International Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.","chicago":"Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” In 35th International Symposium on Distributed Computing, Vol. 209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.58.","ista":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. 35th International Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol. 209, 58."},"title":"Brief announcement: Sinkless orientation is hard also in the supported LOCAL model","author":[{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","full_name":"Korhonen, Janne","last_name":"Korhonen"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"last_name":"Rybicki","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"first_name":"Jukka","full_name":"Suomela, Jukka","last_name":"Suomela"}],"article_processing_charge":"No","external_id":{"arxiv":["2108.02655"]},"acknowledgement":"Janne H. Korhonen: Project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","quality_controlled":"1","oa":1,"day":"04","publication":"35th International Symposium on Distributed Computing","has_accepted_license":"1","year":"2021","doi":"10.4230/LIPIcs.DISC.2021.58","date_published":"2021-10-04T00:00:00Z","date_created":"2021-11-07T23:01:24Z","_id":"10219","status":"public","type":"conference","conference":{"name":"DISC: Distributed Computing ","start_date":"2021-10-04","end_date":"2021-10-08","location":"Freiburg, Germany"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"],"date_updated":"2021-11-12T09:37:18Z","department":[{"_id":"DaAl"}],"file_date_updated":"2021-11-12T08:27:42Z","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n)."}],"month":"10","intvolume":" 209","alternative_title":["LIPIcs"],"scopus_import":"1","file":[{"date_created":"2021-11-12T08:27:42Z","file_name":"2021_LIPIcsDISC_Korhonen.pdf","date_updated":"2021-11-12T08:27:42Z","file_size":474242,"creator":"cchlebak","file_id":"10275","checksum":"c43188dc2070bbd2bf5fd6fdaf9ce36d","success":1,"content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"publication_status":"published","volume":209,"ec_funded":1},{"department":[{"_id":"DaAl"}],"date_updated":"2023-02-23T14:09:49Z","conference":{"start_date":"2021-06-28","location":"Wrocław, Poland","end_date":"2021-07-01","name":"SIROCCO: Structural Information and Communication Complexity"},"type":"conference","status":"public","_id":"9823","volume":12810,"publication_status":"published","publication_identifier":{"issn":["03029743"],"isbn":["9783030795269"],"eissn":["16113349"]},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/2103.08949","open_access":"1"}],"scopus_import":"1","alternative_title":["LNCS"],"intvolume":" 12810","month":"06","abstract":[{"lang":"eng","text":"Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a vertex of the graph as input and, if non-faulty, must output a vertex such that\r\nall the outputs are within distance 1 of one another, and\r\n\r\neach output value lies on a shortest path between two input values.\r\n\r\nFrom prior work, it is known that there is no wait-free algorithm among 𝑛≥3 processes for this problem on any cycle of length 𝑐≥4 , by reduction from 2-set agreement (Castañeda et al. 2018).\r\n\r\nIn this work, we investigate the solvability and complexity of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length 𝑐≥4 , via a generalisation of Sperner’s Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a class of graphs that properly contains the class of chordal graphs."}],"oa_version":"Preprint","article_processing_charge":"No","external_id":{"arxiv":["2103.08949"]},"author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Ellen","full_name":"Ellen, Faith","first_name":"Faith"},{"full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"}],"title":"Wait-free approximate agreement on graphs","citation":{"ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” in Structural Information and Communication Complexity, Wrocław, Poland, 2021, vol. 12810, pp. 87–105.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 87–105.","ama":"Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. In: Structural Information and Communication Complexity. Vol 12810. Springer Nature; 2021:87-105. doi:10.1007/978-3-030-79527-6_6","apa":"Alistarh, D.-A., Ellen, F., & Rybicki, J. (2021). Wait-free approximate agreement on graphs. In Structural Information and Communication Complexity (Vol. 12810, pp. 87–105). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_6","mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Structural Information and Communication Complexity, vol. 12810, Springer Nature, 2021, pp. 87–105, doi:10.1007/978-3-030-79527-6_6.","ista":"Alistarh D-A, Ellen F, Rybicki J. 2021. Wait-free approximate agreement on graphs. Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 12810, 87–105.","chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” In Structural Information and Communication Complexity, 12810:87–105. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_6."},"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","page":"87-105","date_created":"2021-08-08T22:01:29Z","doi":"10.1007/978-3-030-79527-6_6","date_published":"2021-06-20T00:00:00Z","year":"2021","publication":"Structural Information and Communication Complexity","day":"20","oa":1,"quality_controlled":"1","publisher":"Springer Nature"},{"month":"05","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.07637"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"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?\r\nTo 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 labelled graph under batch changes. We investigate, when a batch of alpha edge label changes arrive, - how much time as a function of alpha we need to update an existing solution, and - how much information the nodes have to keep in local memory between batches in order to update the solution quickly.\r\nOur 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. The diverse time complexity of our model spans from constant time, through time polynomial in alpha, and to alpha time, which we show to be enough for any task."}],"related_material":{"record":[{"id":"10855","status":"public","relation":"extended_version"}]},"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450380720"]},"publication_status":"published","status":"public","type":"conference","conference":{"location":"Virtual, Online","end_date":"2021-06-18","start_date":"2021-06-14","name":"SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems"},"_id":"10854","department":[{"_id":"DaAl"}],"date_updated":"2023-09-26T10:40:55Z","publisher":"Association for Computing Machinery","quality_controlled":"1","oa":1,"acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili and the reviewers for their time and suggestions on how to improve the paper. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","date_published":"2021-05-01T00:00:00Z","doi":"10.1145/3410220.3453923","date_created":"2022-03-18T08:48:41Z","page":"71-72","day":"01","publication":"Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems","year":"2021","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","grant_number":"840605","name":"Coordination in constrained and natural distributed systems"}],"title":"Input-dynamic distributed algorithms for communication networks","author":[{"first_name":"Klaus-Tycho","full_name":"Foerster, Klaus-Tycho","last_name":"Foerster"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","last_name":"Korhonen","full_name":"Korhonen, Janne"},{"first_name":"Ami","full_name":"Paz, Ami","last_name":"Paz"},{"first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"external_id":{"arxiv":["2005.07637"]},"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp. 71–72, doi:10.1145/3410220.3453923.","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems (pp. 71–72). Virtual, Online: Association for Computing Machinery. https://doi.org/10.1145/3410220.3453923","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. In: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery; 2021:71-72. doi:10.1145/3410220.3453923","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, in:, Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp. 71–72.","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” in Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Virtual, Online, 2021, pp. 71–72.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, 71–72. Association for Computing Machinery, 2021. https://doi.org/10.1145/3410220.3453923.","ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems, 71–72."}},{"department":[{"_id":"DaAl"}],"date_updated":"2023-09-26T10:40:55Z","article_type":"original","type":"journal_article","keyword":["Computer Networks and Communications","Hardware and Architecture","Safety","Risk","Reliability and Quality","Computer Science (miscellaneous)"],"status":"public","_id":"10855","ec_funded":1,"volume":5,"issue":"1","related_material":{"record":[{"id":"10854","status":"public","relation":"shorter_version"}]},"publication_status":"published","publication_identifier":{"issn":["2476-1249"]},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.07637"}],"scopus_import":"1","intvolume":" 5","month":"03","abstract":[{"lang":"eng","text":"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 α edge label changes arrive, \\beginitemize \\item how much time as a function of α 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."}],"oa_version":"Preprint","external_id":{"arxiv":["2005.07637"]},"article_processing_charge":"No","author":[{"last_name":"Foerster","full_name":"Foerster, Klaus-Tycho","first_name":"Klaus-Tycho"},{"first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","full_name":"Korhonen, Janne","last_name":"Korhonen"},{"full_name":"Paz, Ami","last_name":"Paz","first_name":"Ami"},{"first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","last_name":"Rybicki"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"title":"Input-dynamic distributed algorithms for communication networks","citation":{"mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33, doi:10.1145/3447384.","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. Association for Computing Machinery. https://doi.org/10.1145/3447384","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2021;5(1):1-33. doi:10.1145/3447384","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 5, no. 1. Association for Computing Machinery, pp. 1–33, 2021.","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” Proceedings of the ACM on Measurement and Analysis of Computing Systems. Association for Computing Machinery, 2021. https://doi.org/10.1145/3447384.","ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 5(1), 1–33."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"H2020","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","grant_number":"840605","name":"Coordination in constrained and natural distributed systems"},{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"page":"1-33","date_created":"2022-03-18T09:10:27Z","doi":"10.1145/3447384","date_published":"2021-03-01T00:00:00Z","year":"2021","publication":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","day":"01","oa":1,"publisher":"Association for Computing Machinery","quality_controlled":"1","acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how to improve the paper. This project\r\nhas received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N."},{"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively."}],"month":"07","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/2005.07761","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450380706"]},"publication_status":"published","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"15074"}]},"ec_funded":1,"_id":"9678","status":"public","type":"conference","conference":{"start_date":"2021-07-06","end_date":"2021-07-08","location":" Virtual Event, United States","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures "},"date_updated":"2024-03-05T07:13:12Z","department":[{"_id":"DaAl"}],"acknowledgement":"We thank Orr Fischer, Juho Hirvonen, and Tuomo Lempiäinen for valuable discussions. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 840605.","quality_controlled":"1","oa":1,"day":"06","publication":"Annual ACM Symposium on Parallelism in Algorithms and Architectures","year":"2021","doi":"10.1145/3409964.3461785","date_published":"2021-07-06T00:00:00Z","date_created":"2021-07-18T22:01:22Z","page":"129-139","project":[{"grant_number":"840605","name":"Coordination in constrained and natural distributed systems","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","citation":{"chicago":"Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. “Efficient Load-Balancing through Distributed Token Dropping.” In Annual ACM Symposium on Parallelism in Algorithms and Architectures, 129–39, 2021. https://doi.org/10.1145/3409964.3461785.","ista":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2021. Efficient load-balancing through distributed token dropping. Annual ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures , 129–139.","mla":"Brandt, Sebastian, et al. “Efficient Load-Balancing through Distributed Token Dropping.” Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2021, pp. 129–39, doi:10.1145/3409964.3461785.","short":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2021, pp. 129–139.","ieee":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Efficient load-balancing through distributed token dropping,” in Annual ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, United States, 2021, pp. 129–139.","ama":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Efficient load-balancing through distributed token dropping. In: Annual ACM Symposium on Parallelism in Algorithms and Architectures. ; 2021:129-139. doi:10.1145/3409964.3461785","apa":"Brandt, S., Keller, B., Rybicki, J., Suomela, J., & Uitto, J. (2021). Efficient load-balancing through distributed token dropping. In Annual ACM Symposium on Parallelism in Algorithms and Architectures (pp. 129–139). Virtual Event, United States. https://doi.org/10.1145/3409964.3461785"},"title":"Efficient load-balancing through distributed token dropping","author":[{"full_name":"Brandt, Sebastian","last_name":"Brandt","first_name":"Sebastian"},{"full_name":"Keller, Barbara","last_name":"Keller","first_name":"Barbara"},{"first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki"},{"first_name":"Jukka","full_name":"Suomela, Jukka","last_name":"Suomela"},{"full_name":"Uitto, Jara","last_name":"Uitto","first_name":"Jara"}],"external_id":{"arxiv":["2005.07761"]},"article_processing_charge":"No"},{"isi":1,"has_accepted_license":"1","year":"2020","day":"01","publication":"Ecology Letters","page":"506-517","date_published":"2020-03-01T00:00:00Z","doi":"10.1111/ele.13450","date_created":"2020-01-04T11:04:30Z","publisher":"Wiley","quality_controlled":"1","oa":1,"citation":{"ama":"Rybicki J, Abrego N, Ovaskainen O. Habitat fragmentation and species diversity in competitive communities. Ecology Letters. 2020;23(3):506-517. doi:10.1111/ele.13450","apa":"Rybicki, J., Abrego, N., & Ovaskainen, O. (2020). Habitat fragmentation and species diversity in competitive communities. Ecology Letters. Wiley. https://doi.org/10.1111/ele.13450","ieee":"J. Rybicki, N. Abrego, and O. Ovaskainen, “Habitat fragmentation and species diversity in competitive communities,” Ecology Letters, vol. 23, no. 3. Wiley, pp. 506–517, 2020.","short":"J. Rybicki, N. Abrego, O. Ovaskainen, Ecology Letters 23 (2020) 506–517.","mla":"Rybicki, Joel, et al. “Habitat Fragmentation and Species Diversity in Competitive Communities.” Ecology Letters, vol. 23, no. 3, Wiley, 2020, pp. 506–17, doi:10.1111/ele.13450.","ista":"Rybicki J, Abrego N, Ovaskainen O. 2020. Habitat fragmentation and species diversity in competitive communities. Ecology Letters. 23(3), 506–517.","chicago":"Rybicki, Joel, Nerea Abrego, and Otso Ovaskainen. “Habitat Fragmentation and Species Diversity in Competitive Communities.” Ecology Letters. Wiley, 2020. https://doi.org/10.1111/ele.13450."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"last_name":"Rybicki","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Abrego, Nerea","last_name":"Abrego","first_name":"Nerea"},{"last_name":"Ovaskainen","full_name":"Ovaskainen, Otso","first_name":"Otso"}],"article_processing_charge":"Yes (via OA deal)","external_id":{"isi":["000503625200001"]},"title":"Habitat fragmentation and species diversity in competitive communities","project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"},{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"publication_identifier":{"eissn":["1461-0248"],"issn":["1461-023X"]},"publication_status":"published","file":[{"file_size":3005474,"date_updated":"2020-07-14T12:47:54Z","creator":"dernst","file_name":"2020_EcologyLetters_Rybicki.pdf","date_created":"2020-02-14T12:02:50Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"7486","checksum":"372f67f2744f4b6049e9778364766c22"}],"language":[{"iso":"eng"}],"issue":"3","volume":23,"ec_funded":1,"abstract":[{"text":"Habitat loss is one of the key drivers of the ongoing decline of biodiversity. However, ecologists still argue about how fragmentation of habitat (independent of habitat loss) affects species richness. The recently proposed habitat amount hypothesis posits that species richness only depends on the total amount of habitat in a local landscape. In contrast, empirical studies report contrasting patterns: some find positive and others negative effects of fragmentation per se on species richness. To explain this apparent disparity, we devise a stochastic, spatially explicit model of competitive species communities in heterogeneous habitats. The model shows that habitat loss and fragmentation have complex effects on species diversity in competitive communities. When the total amount of habitat is large, fragmentation per se tends to increase species diversity, but if the total amount of habitat is small, the situation is reversed: fragmentation per se decreases species diversity.","lang":"eng"}],"oa_version":"Published Version","scopus_import":"1","month":"03","intvolume":" 23","date_updated":"2023-09-05T16:04:30Z","ddc":["000"],"file_date_updated":"2020-07-14T12:47:54Z","department":[{"_id":"DaAl"}],"_id":"7224","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public"},{"article_number":"40","author":[{"full_name":"Brandt, Sebastian","last_name":"Brandt","first_name":"Sebastian"},{"first_name":"Barbara","last_name":"Keller","full_name":"Keller, Barbara"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel"},{"first_name":"Jukka","full_name":"Suomela, Jukka","last_name":"Suomela"},{"last_name":"Uitto","full_name":"Uitto, Jara","first_name":"Jara"}],"article_processing_charge":"No","external_id":{"arxiv":["2005.07761"]},"title":"Brief announcement: Efficient load-balancing through distributed token dropping","citation":{"ista":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2020. Brief announcement: Efficient load-balancing through distributed token dropping. 34th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 179, 40.","chicago":"Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. “Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping.” In 34th International Symposium on Distributed Computing, Vol. 179. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.DISC.2020.40.","ieee":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Brief announcement: Efficient load-balancing through distributed token dropping,” in 34th International Symposium on Distributed Computing, Virtual, 2020, vol. 179.","short":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, 34th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","apa":"Brandt, S., Keller, B., Rybicki, J., Suomela, J., & Uitto, J. (2020). Brief announcement: Efficient load-balancing through distributed token dropping. In 34th International Symposium on Distributed Computing (Vol. 179). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2020.40","ama":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Brief announcement: Efficient load-balancing through distributed token dropping. In: 34th International Symposium on Distributed Computing. Vol 179. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.DISC.2020.40","mla":"Brandt, Sebastian, et al. “Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping.” 34th International Symposium on Distributed Computing, vol. 179, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.DISC.2020.40."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"date_published":"2020-10-07T00:00:00Z","doi":"10.4230/LIPIcs.DISC.2020.40","date_created":"2024-03-05T07:09:12Z","has_accepted_license":"1","year":"2020","day":"07","publication":"34th International Symposium on Distributed Computing","type":"conference","conference":{"start_date":"2020-10-12","end_date":"2020-10-16","location":"Virtual","name":"DISC: Symposium on Distributed Computing"},"tmp":{"short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"status":"public","_id":"15074","department":[{"_id":"DaAl"}],"file_date_updated":"2024-03-05T07:08:27Z","date_updated":"2024-03-05T07:13:13Z","ddc":["000"],"scopus_import":"1","alternative_title":["LIPIcs"],"month":"10","intvolume":" 179","abstract":[{"text":"We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for the stable orientation problem, which is a special case of the more general locally optimal semi-matching problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal semi-matching in O(Δ⁵) rounds in graphs of maximum degree Δ, which directly implies an algorithm with the same runtime for stable orientations. We improve the runtime to O(Δ⁴) for stable orientations and prove a lower bound of Ω(Δ) rounds.","lang":"eng"}],"oa_version":"Published Version","volume":179,"related_material":{"record":[{"id":"9678","status":"public","relation":"later_version"}]},"license":"https://creativecommons.org/licenses/by/3.0/","publication_status":"published","file":[{"creator":"dernst","file_size":303529,"date_updated":"2024-03-05T07:08:27Z","file_name":"2020_LIPIcs_Brandt.pdf","date_created":"2024-03-05T07:08:27Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"checksum":"23e2d9321aef53092dc1e24a8ab82d72","file_id":"15075"}],"language":[{"iso":"eng"}]},{"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Nowak T, Rybicki J. 2019. Byzantine approximate agreement on graphs. 33rd International Symposium on Distributed Computing. DISC: International Symposium on Distributed Computing, LIPIcs, vol. 146, 29:1--29:17.","chicago":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” In 33rd International Symposium on Distributed Computing, 146:29:1--29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.DISC.2019.29.","apa":"Nowak, T., & Rybicki, J. (2019). Byzantine approximate agreement on graphs. In 33rd International Symposium on Distributed Computing (Vol. 146, p. 29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.DISC.2019.29","ama":"Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: 33rd International Symposium on Distributed Computing. Vol 146. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:10.4230/LIPICS.DISC.2019.29","short":"T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17.","ieee":"T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in 33rd International Symposium on Distributed Computing, Budapest, Hungary, 2019, vol. 146, p. 29:1--29:17.","mla":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” 33rd International Symposium on Distributed Computing, vol. 146, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:10.4230/LIPICS.DISC.2019.29."},"title":"Byzantine approximate agreement on graphs","author":[{"full_name":"Nowak, Thomas","last_name":"Nowak","first_name":"Thomas"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646"}],"external_id":{"arxiv":["1908.02743"]},"article_processing_charge":"No","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"publication":"33rd International Symposium on Distributed Computing","has_accepted_license":"1","year":"2019","doi":"10.4230/LIPICS.DISC.2019.29","date_published":"2019-01-01T00:00:00Z","date_created":"2019-10-08T12:41:38Z","page":"29:1--29:17","_id":"6931","status":"public","keyword":["consensus","approximate agreement","Byzantine faults","chordal graphs","lattice agreement"],"type":"conference","conference":{"end_date":"2019-10-18","location":"Budapest, Hungary","start_date":"2019-10-14","name":"DISC: International Symposium on Distributed Computing"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["004"],"date_updated":"2021-01-12T08:09:38Z","file_date_updated":"2020-07-14T12:47:44Z","department":[{"_id":"DaAl"}],"oa_version":"Published Version","abstract":[{"text":"Consider a distributed system with n processors out of which f can be Byzantine faulty. In the\r\napproximate agreement task, each processor i receives an input value xi and has to decide on an\r\noutput value yi such that\r\n1. the output values are in the convex hull of the non-faulty processors’ input values,\r\n2. the output values are within distance d of each other.\r\n\r\n\r\nClassically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1.\r\nIn this work, we study the task in a discrete setting, where input values with some structure\r\nexpressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to\r\noutput vertices that are within distance d of each other in G, but still remain in the graph-induced\r\nconvex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with\r\na deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1,\r\nwe show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f,\r\nwhere ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a\r\nvariant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact\r\nvariants of these and related tasks over a large class of combinatorial structures.","lang":"eng"}],"intvolume":" 146","scopus_import":1,"alternative_title":["LIPIcs"],"file":[{"date_updated":"2020-07-14T12:47:44Z","file_size":639378,"creator":"jrybicki","date_created":"2019-10-08T12:47:19Z","file_name":"LIPIcs-DISC-2019-29.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"2d2202f90c6ac991e50876451627c4b5","file_id":"6934"}],"language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["978-3-95977-126-9"]},"publication_status":"published","volume":146,"ec_funded":1},{"quality_controlled":"1","publisher":"Wiley","oa":1,"day":"01","publication":"Ecography","isi":1,"has_accepted_license":"1","year":"2019","date_published":"2019-11-01T00:00:00Z","doi":"10.1111/ecog.04444","date_created":"2019-10-08T13:01:24Z","page":"1877-1886","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ista":"Ovaskainen O, Rybicki J, Abrego N. 2019. What can observational data reveal about metacommunity processes? Ecography. 42(11), 1877–1886.","chicago":"Ovaskainen, Otso, Joel Rybicki, and Nerea Abrego. “What Can Observational Data Reveal about Metacommunity Processes?” Ecography. Wiley, 2019. https://doi.org/10.1111/ecog.04444.","ama":"Ovaskainen O, Rybicki J, Abrego N. What can observational data reveal about metacommunity processes? Ecography. 2019;42(11):1877-1886. doi:10.1111/ecog.04444","apa":"Ovaskainen, O., Rybicki, J., & Abrego, N. (2019). What can observational data reveal about metacommunity processes? Ecography. Wiley. https://doi.org/10.1111/ecog.04444","ieee":"O. Ovaskainen, J. Rybicki, and N. Abrego, “What can observational data reveal about metacommunity processes?,” Ecography, vol. 42, no. 11. Wiley, pp. 1877–1886, 2019.","short":"O. Ovaskainen, J. Rybicki, N. Abrego, Ecography 42 (2019) 1877–1886.","mla":"Ovaskainen, Otso, et al. “What Can Observational Data Reveal about Metacommunity Processes?” Ecography, vol. 42, no. 11, Wiley, 2019, pp. 1877–86, doi:10.1111/ecog.04444."},"title":"What can observational data reveal about metacommunity processes?","author":[{"full_name":"Ovaskainen, Otso","last_name":"Ovaskainen","first_name":"Otso"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Abrego, Nerea","last_name":"Abrego","first_name":"Nerea"}],"article_processing_charge":"No","external_id":{"isi":["000486348700001"]},"oa_version":"Published Version","abstract":[{"lang":"eng","text":"A key challenge for community ecology is to understand to what extent observational data can be used to infer the underlying community assembly processes. As different processes can lead to similar or even identical patterns, statistical analyses of non‐manipulative observational data never yield undisputable causal inference on the underlying processes. Still, most empirical studies in community ecology are based on observational data, and hence understanding under which circumstances such data can shed light on assembly processes is a central concern for community ecologists. We simulated a spatial agent‐based model that generates variation in metacommunity dynamics across multiple axes, including the four classic metacommunity paradigms as special cases. We further simulated a virtual ecologist who analysed snapshot data sampled from the simulations using eighteen output metrics derived from beta‐diversity and habitat variation indices, variation partitioning and joint species distribution modelling. Our results indicated two main axes of variation in the output metrics. The first axis of variation described whether the landscape has patchy or continuous variation, and thus was essentially independent of the properties of the species community. The second axis of variation related to the level of predictability of the metacommunity. The most predictable communities were niche‐based metacommunities inhabiting static landscapes with marked environmental heterogeneity, such as metacommunities following the species sorting paradigm or the mass effects paradigm. The most unpredictable communities were neutral‐based metacommunities inhabiting dynamics landscapes with little spatial heterogeneity, such as metacommunities following the neutral or patch sorting paradigms. The output metrics from joint species distribution modelling yielded generally the highest resolution to disentangle among the simulated scenarios. Yet, the different types of statistical approaches utilized in this study carried complementary information, and thus our results suggest that the most comprehensive evaluation of metacommunity structure can be obtained by combining them.\r\n"}],"month":"11","intvolume":" 42","scopus_import":"1","file":[{"date_created":"2019-10-08T13:07:44Z","file_name":"ecog.04444.pdf","date_updated":"2020-07-14T12:47:45Z","file_size":1682718,"creator":"jrybicki","file_id":"6937","checksum":"6c9fbbd5ea8ce10ae93e55ad560a7bf9","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0906-7590"],"eissn":["1600-0587"]},"publication_status":"published","volume":42,"issue":"11","ec_funded":1,"_id":"6936","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["577"],"date_updated":"2023-08-30T06:57:25Z","file_date_updated":"2020-07-14T12:47:45Z","department":[{"_id":"DaAl"}]},{"scopus_import":"1","intvolume":" 66","month":"09","abstract":[{"lang":"eng","text":"We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of thennodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e.,the initial state of the system may be arbitrary, and there can be up to fJournal of the ACM. ACM, 2019. https://doi.org/10.1145/3339471.","ista":"Lenzen C, Rybicki J. 2019. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. 66(5), 32.","mla":"Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” Journal of the ACM, vol. 66, no. 5, 32, ACM, 2019, doi:10.1145/3339471.","short":"C. Lenzen, J. Rybicki, Journal of the ACM 66 (2019).","ieee":"C. Lenzen and J. Rybicki, “Self-stabilising Byzantine clock synchronisation is almost as easy as consensus,” Journal of the ACM, vol. 66, no. 5. ACM, 2019.","ama":"Lenzen C, Rybicki J. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. 2019;66(5). doi:10.1145/3339471","apa":"Lenzen, C., & Rybicki, J. (2019). Self-stabilising Byzantine clock synchronisation is almost as easy as consensus. Journal of the ACM. ACM. https://doi.org/10.1145/3339471"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"publication":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing","day":"01","year":"2019","isi":1,"date_created":"2019-10-08T12:57:14Z","doi":"10.1145/3293611.3331581","date_published":"2019-08-01T00:00:00Z","page":"259-261","oa":1,"quality_controlled":"1","publisher":"ACM","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ama":"Foerster K-T, Korhonen J, Rybicki J, Schmid S. Does preprocessing help under congestion? In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM; 2019:259-261. doi:10.1145/3293611.3331581","apa":"Foerster, K.-T., Korhonen, J., Rybicki, J., & Schmid, S. (2019). Does preprocessing help under congestion? In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (pp. 259–261). Toronto, ON, Canada: ACM. https://doi.org/10.1145/3293611.3331581","ieee":"K.-T. Foerster, J. Korhonen, J. Rybicki, and S. Schmid, “Does preprocessing help under congestion?,” in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, Toronto, ON, Canada, 2019, pp. 259–261.","short":"K.-T. Foerster, J. Korhonen, J. Rybicki, S. Schmid, in:, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–261.","mla":"Foerster, Klaus-Tycho, et al. “Does Preprocessing Help under Congestion?” Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–61, doi:10.1145/3293611.3331581.","ista":"Foerster K-T, Korhonen J, Rybicki J, Schmid S. 2019. Does preprocessing help under congestion? Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 259–261.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Joel Rybicki, and Stefan Schmid. “Does Preprocessing Help under Congestion?” In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 259–61. ACM, 2019. https://doi.org/10.1145/3293611.3331581."},"title":"Does preprocessing help under congestion?","article_processing_charge":"No","external_id":{"isi":["000570442000037"],"arxiv":["1905.03012"]},"author":[{"first_name":"Klaus-Tycho","full_name":"Foerster, Klaus-Tycho","last_name":"Foerster"},{"first_name":"Janne","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","last_name":"Korhonen","full_name":"Korhonen, Janne"},{"first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","last_name":"Rybicki"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"}],"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9781450362177"]},"ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does\r\npreprocessing help in the CONGEST model."}],"month":"08","main_file_link":[{"url":"https://arxiv.org/abs/1905.03012","open_access":"1"}],"scopus_import":"1","date_updated":"2023-09-08T11:37:22Z","department":[{"_id":"DaAl"}],"_id":"6935","status":"public","conference":{"start_date":"2019-07-29","location":"Toronto, ON, Canada","end_date":"2019-08-02","name":"PODC: Symposium on Principles of Distributed Computing"},"type":"conference"},{"page":"10690 - 10695","date_published":"2018-10-02T00:00:00Z","doi":"10.1073/pnas.1721061115","date_created":"2018-12-11T11:44:19Z","has_accepted_license":"1","isi":1,"year":"2018","day":"02","publication":"PNAS","publisher":"National Academy of Sciences","quality_controlled":"1","oa":1,"acknowledgement":"J.R. and J.V.A. were also supported by the Academy of Finland Grants 1273253 and 267541.","author":[{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel"},{"first_name":"Eva","last_name":"Kisdi","full_name":"Kisdi, Eva"},{"last_name":"Anttila","full_name":"Anttila, Jani","first_name":"Jani"}],"publist_id":"8011","article_processing_charge":"No","external_id":{"isi":["000447491300057"]},"title":"Model of bacterial toxin-dependent pathogenesis explains infective dose","citation":{"apa":"Rybicki, J., Kisdi, E., & Anttila, J. (2018). Model of bacterial toxin-dependent pathogenesis explains infective dose. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.1721061115","ama":"Rybicki J, Kisdi E, Anttila J. Model of bacterial toxin-dependent pathogenesis explains infective dose. PNAS. 2018;115(42):10690-10695. doi:10.1073/pnas.1721061115","short":"J. Rybicki, E. Kisdi, J. Anttila, PNAS 115 (2018) 10690–10695.","ieee":"J. Rybicki, E. Kisdi, and J. Anttila, “Model of bacterial toxin-dependent pathogenesis explains infective dose,” PNAS, vol. 115, no. 42. National Academy of Sciences, pp. 10690–10695, 2018.","mla":"Rybicki, Joel, et al. “Model of Bacterial Toxin-Dependent Pathogenesis Explains Infective Dose.” PNAS, vol. 115, no. 42, National Academy of Sciences, 2018, pp. 10690–95, doi:10.1073/pnas.1721061115.","ista":"Rybicki J, Kisdi E, Anttila J. 2018. Model of bacterial toxin-dependent pathogenesis explains infective dose. PNAS. 115(42), 10690–10695.","chicago":"Rybicki, Joel, Eva Kisdi, and Jani Anttila. “Model of Bacterial Toxin-Dependent Pathogenesis Explains Infective Dose.” PNAS. National Academy of Sciences, 2018. https://doi.org/10.1073/pnas.1721061115."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"volume":115,"issue":"42","ec_funded":1,"publication_status":"published","file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"6258","checksum":"df7ac544a587c06b75692653b9fabd18","creator":"dernst","file_size":4070777,"date_updated":"2020-07-14T12:46:26Z","file_name":"2018_PNAS_Rybicki.pdf","date_created":"2019-04-09T08:02:50Z"}],"language":[{"iso":"eng"}],"scopus_import":"1","month":"10","intvolume":" 115","abstract":[{"text":"The initial amount of pathogens required to start an infection within a susceptible host is called the infective dose and is known to vary to a large extent between different pathogen species. We investigate the hypothesis that the differences in infective doses are explained by the mode of action in the underlying mechanism of pathogenesis: Pathogens with locally acting mechanisms tend to have smaller infective doses than pathogens with distantly acting mechanisms. While empirical evidence tends to support the hypothesis, a formal theoretical explanation has been lacking. We give simple analytical models to gain insight into this phenomenon and also investigate a stochastic, spatially explicit, mechanistic within-host model for toxin-dependent bacterial infections. The model shows that pathogens secreting locally acting toxins have smaller infective doses than pathogens secreting diffusive toxins, as hypothesized. While local pathogenetic mechanisms require smaller infective doses, pathogens with distantly acting toxins tend to spread faster and may cause more damage to the host. The proposed model can serve as a basis for the spatially explicit analysis of various virulence factors also in the context of other problems in infection dynamics.","lang":"eng"}],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:46:26Z","department":[{"_id":"DaAl"}],"date_updated":"2023-09-13T08:57:38Z","ddc":["570","577"],"type":"journal_article","status":"public","pubrep_id":"1063","_id":"43"},{"abstract":[{"text":"Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C>1. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions.","lang":"eng"}],"oa_version":"Published Version","scopus_import":"1","month":"09","publication_status":"published","file":[{"creator":"dernst","date_updated":"2020-07-14T12:48:01Z","file_size":799337,"date_created":"2018-12-17T14:21:22Z","file_name":"2018_DistributedComputing_Lenzen.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"872db70bba9b401500abe3c6ae2f1a61","file_id":"5711"}],"language":[{"iso":"eng"}],"_id":"76","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","date_updated":"2023-09-13T09:01:06Z","ddc":["000"],"department":[{"_id":"DaAl"}],"file_date_updated":"2020-07-14T12:48:01Z","quality_controlled":"1","publisher":"Springer","oa":1,"has_accepted_license":"1","isi":1,"year":"2018","day":"12","publication":"Distributed Computing","date_published":"2018-09-12T00:00:00Z","doi":"10.1007/s00446-018-0342-6","date_created":"2018-12-11T11:44:30Z","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"citation":{"apa":"Lenzen, C., & Rybicki, J. (2018). Near-optimal self-stabilising counting and firing squads. Distributed Computing. Springer. https://doi.org/10.1007/s00446-018-0342-6","ama":"Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads. Distributed Computing. 2018. doi:10.1007/s00446-018-0342-6","short":"C. Lenzen, J. Rybicki, Distributed Computing (2018).","ieee":"C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing squads,” Distributed Computing. Springer, 2018.","mla":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” Distributed Computing, Springer, 2018, doi:10.1007/s00446-018-0342-6.","ista":"Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing squads. Distributed Computing.","chicago":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” Distributed Computing. Springer, 2018. https://doi.org/10.1007/s00446-018-0342-6."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Christoph","last_name":"Lenzen","full_name":"Lenzen, Christoph"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel"}],"publist_id":"7978","article_processing_charge":"Yes (via OA deal)","external_id":{"isi":["000475627800005"]},"title":"Near-optimal self-stabilising counting and firing squads"},{"page":"101-110","date_published":"2017-07-01T00:00:00Z","doi":"10.1145/3087801.3087833","date_created":"2019-10-08T12:47:46Z","publication_identifier":{"isbn":["9781450349925"]},"year":"2017","publication_status":"published","day":"01","language":[{"iso":"eng"}],"quality_controlled":"1","publisher":"ACM Press","month":"07","abstract":[{"lang":"eng","text":"LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids.\r\nNevertheless, if we correctly guess that the complexity of a problem is Θ(log* n), we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form A' o Sk, where A' is a finite function, Sk is an algorithm for finding a maximal independent set in kth power of the grid, and k is a constant.\r\nFinally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations."}],"oa_version":"None","author":[{"first_name":"Sebastian","full_name":"Brandt, Sebastian","last_name":"Brandt"},{"first_name":"Juho","full_name":"Hirvonen, Juho","last_name":"Hirvonen"},{"first_name":"Janne H.","full_name":"Korhonen, Janne H.","last_name":"Korhonen"},{"first_name":"Tuomo","last_name":"Lempiäinen","full_name":"Lempiäinen, Tuomo"},{"last_name":"Östergård","full_name":"Östergård, Patric R.J.","first_name":"Patric R.J."},{"first_name":"Christopher","full_name":"Purcell, Christopher","last_name":"Purcell"},{"full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel"},{"first_name":"Jukka","full_name":"Suomela, Jukka","last_name":"Suomela"},{"last_name":"Uznański","full_name":"Uznański, Przemysław","first_name":"Przemysław"}],"article_processing_charge":"No","title":"LCL problems on grids","date_updated":"2021-01-12T08:09:39Z","citation":{"ista":"Brandt S, Hirvonen J, Korhonen JH, Lempiäinen T, Östergård PRJ, Purcell C, Rybicki J, Suomela J, Uznański P. 2017. LCL problems on grids. PODC: Principles of Distributed Computing, 101–110.","chicago":"Brandt, Sebastian, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. “LCL Problems on Grids,” 101–10. ACM Press, 2017. https://doi.org/10.1145/3087801.3087833.","ama":"Brandt S, Hirvonen J, Korhonen JH, et al. LCL problems on grids. In: ACM Press; 2017:101-110. doi:10.1145/3087801.3087833","apa":"Brandt, S., Hirvonen, J., Korhonen, J. H., Lempiäinen, T., Östergård, P. R. J., Purcell, C., … Uznański, P. (2017). LCL problems on grids (pp. 101–110). Presented at the PODC: Principles of Distributed Computing, Washington, DC, United States: ACM Press. https://doi.org/10.1145/3087801.3087833","ieee":"S. Brandt et al., “LCL problems on grids,” presented at the PODC: Principles of Distributed Computing, Washington, DC, United States, 2017, pp. 101–110.","short":"S. Brandt, J. Hirvonen, J.H. Korhonen, T. Lempiäinen, P.R.J. Östergård, C. Purcell, J. Rybicki, J. Suomela, P. Uznański, in:, ACM Press, 2017, pp. 101–110.","mla":"Brandt, Sebastian, et al. LCL Problems on Grids. ACM Press, 2017, pp. 101–10, doi:10.1145/3087801.3087833."},"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","conference":{"name":"PODC: Principles of Distributed Computing","end_date":"2017-07-27","location":"Washington, DC, United States","start_date":"2017-07-25"},"status":"public","_id":"6932"}]