--- _id: '12566' 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." 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. article_number: '113733' article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Faith full_name: Ellen, Faith last_name: Ellen - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 citation: 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 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 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. ieee: D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” Theoretical Computer Science, vol. 948, no. 2. Elsevier, 2023. 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. short: D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023). date_created: 2023-02-19T23:00:55Z date_published: 2023-02-28T00:00:00Z date_updated: 2023-08-01T13:17:20Z day: '28' ddc: - '000' department: - _id: DaAl doi: 10.1016/j.tcs.2023.113733 ec_funded: 1 external_id: isi: - '000934262700001' file: - access_level: open_access checksum: b27c5290f2f1500c403494364ee39c9f content_type: application/pdf creator: dernst date_created: 2023-02-20T07:30:20Z date_updated: 2023-02-20T07:30:20Z file_id: '12570' file_name: 2023_TheoreticalCompScience_Alistarh.pdf file_size: 602333 relation: main_file success: 1 file_date_updated: 2023-02-20T07:30:20Z has_accepted_license: '1' intvolume: ' 948' isi: 1 issue: '2' language: - iso: eng month: '02' oa: 1 oa_version: Published Version project: - _id: 268A44D6-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '805223' name: Elastic Coordination for Scalable Machine Learning - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: Theoretical Computer Science publication_identifier: issn: - 0304-3975 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Wait-free approximate agreement on graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 948 year: '2023' ... --- _id: '11184' abstract: - lang: eng 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." 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." alternative_title: - LIPIcs article_number: '14' article_processing_charge: No arxiv: 1 author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Rati full_name: Gelashvili, Rati last_name: Gelashvili - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 citation: 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' 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. 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. 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. 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. conference: end_date: 2021-12-15 location: Strasbourg, France name: OPODIS start_date: 2021-12-13 date_created: 2022-04-17T22:01:47Z date_published: 2022-02-01T00:00:00Z date_updated: 2022-05-02T08:09:39Z day: '01' ddc: - '510' department: - _id: DaAl doi: 10.4230/LIPIcs.OPODIS.2021.14 ec_funded: 1 editor: - first_name: Quentin full_name: Bramas, Quentin last_name: Bramas - first_name: Vincent full_name: Gramoli, Vincent last_name: Gramoli - first_name: Alessia full_name: Milani, Alessia last_name: Milani external_id: arxiv: - '2102.08808' file: - access_level: open_access checksum: 2c7c982174c6f98c4ca6e92539d15086 content_type: application/pdf creator: dernst date_created: 2022-05-02T08:06:33Z date_updated: 2022-05-02T08:06:33Z file_id: '11346' file_name: 2022_LIPICs_Alistarh.pdf file_size: 959406 relation: main_file success: 1 file_date_updated: 2022-05-02T08:06:33Z has_accepted_license: '1' intvolume: ' 217' language: - iso: eng month: '02' oa: 1 oa_version: Published Version project: - _id: 268A44D6-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '805223' name: Elastic Coordination for Scalable Machine Learning - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: 25th International Conference on Principles of Distributed Systems publication_identifier: isbn: - '9783959772198' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Fast graphical population protocols tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 217 year: '2022' ... --- _id: '11707' 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.' 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. article_processing_charge: No arxiv: 1 author: - first_name: Alkida full_name: Balliu, Alkida last_name: Balliu - first_name: Juho full_name: Hirvonen, Juho last_name: Hirvonen - first_name: Darya full_name: Melnyk, Darya last_name: Melnyk - first_name: Dennis full_name: Olivetti, Dennis last_name: Olivetti - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Jukka full_name: Suomela, Jukka last_name: Suomela citation: 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' 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' 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. 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. 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.' 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. 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. conference: end_date: 2022-06-29 location: Paderborn, Germany name: 'SIROCCO: Structural Information and Communication Complexity' start_date: 2022-06-27 date_created: 2022-07-31T22:01:49Z date_published: 2022-06-25T00:00:00Z date_updated: 2023-08-03T12:16:29Z day: '25' department: - _id: DaAl doi: 10.1007/978-3-031-09993-9_1 ec_funded: 1 editor: - first_name: Merav full_name: Parter, Merav last_name: Parter external_id: arxiv: - '2102.08703' isi: - '000876977400001' intvolume: ' 13298' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2102.08703 month: '06' oa: 1 oa_version: Preprint page: 1-20 project: - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: International Colloquium on Structural Information and Communication Complexity publication_identifier: eissn: - 1611-3349 isbn: - '9783031099922' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' series_title: LNCS status: public title: Local mending type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 13298 year: '2022' ... --- _id: '11844' 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." 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). article_processing_charge: Yes (via OA deal) arxiv: 1 author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Sasha full_name: Voitovych, Sasha last_name: Voitovych citation: 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' 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' 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. 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. 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. conference: end_date: 2022-07-29 location: Salerno, Italy name: 'PODC: Symposium on Principles of Distributed Computing' start_date: 2022-07-25 date_created: 2022-08-14T22:01:46Z date_published: 2022-07-21T00:00:00Z date_updated: 2023-06-14T12:06:01Z day: '21' ddc: - '000' department: - _id: DaAl doi: 10.1145/3519270.3538435 ec_funded: 1 external_id: arxiv: - '2205.12597' file: - access_level: open_access checksum: 4c6b29172b8e355b4fbc364a2e0827b2 content_type: application/pdf creator: cchlebak date_created: 2022-08-16T08:05:15Z date_updated: 2022-08-16T08:05:15Z file_id: '11854' file_name: 2022_PODC_Alistarh.pdf file_size: 1593474 relation: main_file success: 1 file_date_updated: 2022-08-16T08:05:15Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 246-256 project: - _id: 268A44D6-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '805223' name: Elastic Coordination for Scalable Machine Learning publication: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing publication_identifier: isbn: - '9781450392624' publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: Near-optimal leader election in population protocols on graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2022' ... --- _id: '12182' 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.' 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." article_number: '52' article_processing_charge: No author: - first_name: Maciej full_name: Pacut, Maciej last_name: Pacut - first_name: Mahmoud full_name: Parham, Mahmoud last_name: Parham - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid - first_name: Jukka full_name: Suomela, Jukka last_name: Suomela - first_name: Aleksandr full_name: Tereshchenko, Aleksandr last_name: Tereshchenko citation: 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' 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' 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.' 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.' 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.' 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.' 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. conference: end_date: 2022-10-27 location: Augusta, GA, United States name: 'DISC: Symposium on Distributed Computing' start_date: 2022-10-25 date_created: 2023-01-13T11:06:28Z date_published: 2022-10-17T00:00:00Z date_updated: 2023-01-27T06:59:29Z day: '17' ddc: - '000' department: - _id: DaAl doi: 10.4230/LIPIcs.DISC.2022.52 ec_funded: 1 file: - access_level: open_access checksum: 11bbb56f68a00f2cf6bcce6cc7f5c5f9 content_type: application/pdf creator: dernst date_created: 2023-01-27T06:58:02Z date_updated: 2023-01-27T06:58:02Z file_id: '12409' file_name: 2022_LIPICs_Pacut.pdf file_size: 524804 relation: main_file success: 1 file_date_updated: 2023-01-27T06:58:02Z has_accepted_license: '1' intvolume: ' 246' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: 36th International Symposium on Distributed Computing publication_identifier: eisbn: - '9783959772556' eissn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Brief announcement: Temporal locality in online algorithms' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 246 year: '2022' ... --- _id: '10854' 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." 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. article_processing_charge: No arxiv: 1 author: - first_name: Klaus-Tycho full_name: Foerster, Klaus-Tycho last_name: Foerster - first_name: Janne full_name: Korhonen, Janne id: C5402D42-15BC-11E9-A202-CA2BE6697425 last_name: Korhonen - first_name: Ami full_name: Paz, Ami last_name: Paz - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: 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' 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' 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. 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. 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.' 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. 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. conference: end_date: 2021-06-18 location: Virtual, Online name: 'SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems' start_date: 2021-06-14 date_created: 2022-03-18T08:48:41Z date_published: 2021-05-01T00:00:00Z date_updated: 2023-09-26T10:40:55Z day: '01' department: - _id: DaAl doi: 10.1145/3410220.3453923 ec_funded: 1 external_id: arxiv: - '2005.07637' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2005.07637 month: '05' oa: 1 oa_version: Preprint page: 71-72 project: - _id: 268A44D6-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '805223' name: Elastic Coordination for Scalable Machine Learning - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems publication_identifier: isbn: - '9781450380720' publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' related_material: record: - id: '10855' relation: extended_version status: public scopus_import: '1' status: public title: Input-dynamic distributed algorithms for communication networks type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2021' ... --- _id: '10855' 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.' 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." article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Klaus-Tycho full_name: Foerster, Klaus-Tycho last_name: Foerster - first_name: Janne full_name: Korhonen, Janne id: C5402D42-15BC-11E9-A202-CA2BE6697425 last_name: Korhonen - first_name: Ami full_name: Paz, Ami last_name: Paz - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: 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 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 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. 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. 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. 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. 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. date_created: 2022-03-18T09:10:27Z date_published: 2021-03-01T00:00:00Z date_updated: 2023-09-26T10:40:55Z day: '01' department: - _id: DaAl doi: 10.1145/3447384 ec_funded: 1 external_id: arxiv: - '2005.07637' intvolume: ' 5' issue: '1' keyword: - Computer Networks and Communications - Hardware and Architecture - Safety - Risk - Reliability and Quality - Computer Science (miscellaneous) language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2005.07637 month: '03' oa: 1 oa_version: Preprint page: 1-33 project: - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems - _id: 268A44D6-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '805223' name: Elastic Coordination for Scalable Machine Learning publication: Proceedings of the ACM on Measurement and Analysis of Computing Systems publication_identifier: issn: - 2476-1249 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' related_material: record: - id: '10854' relation: shorter_version status: public scopus_import: '1' status: public title: Input-dynamic distributed algorithms for communication networks type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 5 year: '2021' ... --- _id: '9678' 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. 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. article_processing_charge: No arxiv: 1 author: - first_name: Sebastian full_name: Brandt, Sebastian last_name: Brandt - first_name: Barbara full_name: Keller, Barbara last_name: Keller - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Jukka full_name: Suomela, Jukka last_name: Suomela - first_name: Jara full_name: Uitto, Jara last_name: Uitto citation: 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 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. 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. 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. conference: end_date: 2021-07-08 location: ' Virtual Event, United States' name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures ' start_date: 2021-07-06 date_created: 2021-07-18T22:01:22Z date_published: 2021-07-06T00:00:00Z date_updated: 2024-03-05T07:13:12Z day: '06' department: - _id: DaAl doi: 10.1145/3409964.3461785 ec_funded: 1 external_id: arxiv: - '2005.07761' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2005.07761 month: '07' oa: 1 oa_version: Preprint page: 129-139 project: - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: Annual ACM Symposium on Parallelism in Algorithms and Architectures publication_identifier: isbn: - '9781450380706' publication_status: published quality_controlled: '1' related_material: record: - id: '15074' relation: earlier_version status: public scopus_import: '1' status: public title: Efficient load-balancing through distributed token dropping type: conference user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425 year: '2021' ... --- _id: '10218' abstract: - lang: eng 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.' 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. alternative_title: - LIPIcs article_number: '43' article_processing_charge: No arxiv: 1 author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Rati full_name: Gelashvili, Rati last_name: Gelashvili - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 citation: 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' 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' 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.' 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.' 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.' 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.' short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. conference: end_date: 2021-10-08 location: Freiburg, Germany name: 'DISC: Distributed Computing ' start_date: 2021-10-04 date_created: 2021-11-07T23:01:24Z date_published: 2021-10-04T00:00:00Z date_updated: 2023-02-21T09:24:08Z day: '04' ddc: - '000' department: - _id: DaAl doi: 10.4230/LIPIcs.DISC.2021.43 ec_funded: 1 external_id: arxiv: - '2102.08808' file: - access_level: open_access checksum: fd2a690f6856d21247e9aa952b0e2885 content_type: application/pdf creator: cchlebak date_created: 2021-11-12T08:16:44Z date_updated: 2021-11-12T08:16:44Z file_id: '10274' file_name: 2021_LIPIcsDISC_Alistarh.pdf file_size: 534219 relation: main_file success: 1 file_date_updated: 2021-11-12T08:16:44Z has_accepted_license: '1' intvolume: ' 209' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: 35th International Symposium on Distributed Computing publication_identifier: isbn: - 9-783-9597-7210-5 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Brief announcement: Fast graphical population protocols' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 volume: 209 year: '2021' ... --- _id: '10219' 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). 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" alternative_title: - LIPIcs article_number: '58' article_processing_charge: No arxiv: 1 author: - first_name: Janne full_name: Korhonen, Janne id: C5402D42-15BC-11E9-A202-CA2BE6697425 last_name: Korhonen - first_name: Ami full_name: Paz, Ami last_name: Paz - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid - first_name: Jukka full_name: Suomela, Jukka last_name: Suomela citation: 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' 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' 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.' 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.' 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.' 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.' 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. conference: end_date: 2021-10-08 location: Freiburg, Germany name: 'DISC: Distributed Computing ' start_date: 2021-10-04 date_created: 2021-11-07T23:01:24Z date_published: 2021-10-04T00:00:00Z date_updated: 2021-11-12T09:37:18Z day: '04' ddc: - '000' department: - _id: DaAl doi: 10.4230/LIPIcs.DISC.2021.58 ec_funded: 1 external_id: arxiv: - '2108.02655' file: - access_level: open_access checksum: c43188dc2070bbd2bf5fd6fdaf9ce36d content_type: application/pdf creator: cchlebak date_created: 2021-11-12T08:27:42Z date_updated: 2021-11-12T08:27:42Z file_id: '10275' file_name: 2021_LIPIcsDISC_Korhonen.pdf file_size: 474242 relation: main_file success: 1 file_date_updated: 2021-11-12T08:27:42Z has_accepted_license: '1' intvolume: ' 209' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: 268A44D6-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '805223' name: Elastic Coordination for Scalable Machine Learning publication: 35th International Symposium on Distributed Computing publication_identifier: isbn: - 9-783-9597-7210-5 issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Brief announcement: Sinkless orientation is hard also in the supported LOCAL model' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 volume: 209 year: '2021' ... --- _id: '9823' 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 \U0001D45B≥3 processes for this problem on any cycle of length \U0001D450≥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 \U0001D450≥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." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Faith full_name: Ellen, Faith last_name: Ellen - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 citation: 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' 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. 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. 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.' 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. short: D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 87–105. conference: end_date: 2021-07-01 location: Wrocław, Poland name: 'SIROCCO: Structural Information and Communication Complexity' start_date: 2021-06-28 date_created: 2021-08-08T22:01:29Z date_published: 2021-06-20T00:00:00Z date_updated: 2023-02-23T14:09:49Z day: '20' department: - _id: DaAl doi: 10.1007/978-3-030-79527-6_6 external_id: arxiv: - '2103.08949' intvolume: ' 12810' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2103.08949 month: '06' oa: 1 oa_version: Preprint page: 87-105 publication: Structural Information and Communication Complexity publication_identifier: eissn: - '16113349' isbn: - '9783030795269' issn: - '03029743' publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Wait-free approximate agreement on graphs type: conference user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf volume: 12810 year: '2021' ... --- _id: '7224' abstract: - lang: eng 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.' article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Nerea full_name: Abrego, Nerea last_name: Abrego - first_name: Otso full_name: Ovaskainen, Otso last_name: Ovaskainen 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 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. 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. ista: Rybicki J, Abrego N, Ovaskainen O. 2020. Habitat fragmentation and species diversity in competitive communities. Ecology Letters. 23(3), 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. short: J. Rybicki, N. Abrego, O. Ovaskainen, Ecology Letters 23 (2020) 506–517. date_created: 2020-01-04T11:04:30Z date_published: 2020-03-01T00:00:00Z date_updated: 2023-09-05T16:04:30Z day: '01' ddc: - '000' department: - _id: DaAl doi: 10.1111/ele.13450 ec_funded: 1 external_id: isi: - '000503625200001' file: - access_level: open_access checksum: 372f67f2744f4b6049e9778364766c22 content_type: application/pdf creator: dernst date_created: 2020-02-14T12:02:50Z date_updated: 2020-07-14T12:47:54Z file_id: '7486' file_name: 2020_EcologyLetters_Rybicki.pdf file_size: 3005474 relation: main_file file_date_updated: 2020-07-14T12:47:54Z has_accepted_license: '1' intvolume: ' 23' isi: 1 issue: '3' language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: 506-517 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: 26A5D39A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '840605' name: Coordination in constrained and natural distributed systems publication: Ecology Letters publication_identifier: eissn: - 1461-0248 issn: - 1461-023X publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Habitat fragmentation and species diversity in competitive communities tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 23 year: '2020' ... --- _id: '15074' 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 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. alternative_title: - LIPIcs article_number: '40' article_processing_charge: No arxiv: 1 author: - first_name: Sebastian full_name: Brandt, Sebastian last_name: Brandt - first_name: Barbara full_name: Keller, Barbara last_name: Keller - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Jukka full_name: Suomela, Jukka last_name: Suomela - first_name: Jara full_name: Uitto, Jara last_name: Uitto citation: 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' 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' 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.' 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.' 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.' 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. conference: end_date: 2020-10-16 location: Virtual name: 'DISC: Symposium on Distributed Computing' start_date: 2020-10-12 date_created: 2024-03-05T07:09:12Z date_published: 2020-10-07T00:00:00Z date_updated: 2024-03-05T07:13:13Z day: '07' ddc: - '000' department: - _id: DaAl doi: 10.4230/LIPIcs.DISC.2020.40 external_id: arxiv: - '2005.07761' file: - access_level: open_access checksum: 23e2d9321aef53092dc1e24a8ab82d72 content_type: application/pdf creator: dernst date_created: 2024-03-05T07:08:27Z date_updated: 2024-03-05T07:08:27Z file_id: '15075' file_name: 2020_LIPIcs_Brandt.pdf file_size: 303529 relation: main_file success: 1 file_date_updated: 2024-03-05T07:08:27Z has_accepted_license: '1' intvolume: ' 179' language: - iso: eng license: https://creativecommons.org/licenses/by/3.0/ month: '10' oa: 1 oa_version: Published Version publication: 34th International Symposium on Distributed Computing publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '9678' relation: later_version status: public scopus_import: '1' status: public title: 'Brief announcement: Efficient load-balancing through distributed token dropping' tmp: 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) short: CC BY (3.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 179 year: '2020' ... --- _id: '6931' abstract: - lang: eng 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." alternative_title: - LIPIcs article_processing_charge: No arxiv: 1 author: - first_name: Thomas full_name: Nowak, Thomas last_name: Nowak - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 citation: 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' 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' 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. 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. 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.' 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. 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. conference: end_date: 2019-10-18 location: Budapest, Hungary name: 'DISC: International Symposium on Distributed Computing' start_date: 2019-10-14 date_created: 2019-10-08T12:41:38Z date_published: 2019-01-01T00:00:00Z date_updated: 2021-01-12T08:09:38Z ddc: - '004' department: - _id: DaAl doi: 10.4230/LIPICS.DISC.2019.29 ec_funded: 1 external_id: arxiv: - '1908.02743' file: - access_level: open_access checksum: 2d2202f90c6ac991e50876451627c4b5 content_type: application/pdf creator: jrybicki date_created: 2019-10-08T12:47:19Z date_updated: 2020-07-14T12:47:44Z file_id: '6934' file_name: LIPIcs-DISC-2019-29.pdf file_size: 639378 relation: main_file file_date_updated: 2020-07-14T12:47:44Z has_accepted_license: '1' intvolume: ' 146' keyword: - consensus - approximate agreement - Byzantine faults - chordal graphs - lattice agreement language: - iso: eng oa: 1 oa_version: Published Version page: 29:1--29:17 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: 33rd International Symposium on Distributed Computing publication_identifier: eisbn: - 978-3-95977-126-9 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Byzantine approximate agreement on graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 146 year: '2019' ... --- _id: '6935' 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." article_processing_charge: No arxiv: 1 author: - first_name: Klaus-Tycho full_name: Foerster, Klaus-Tycho last_name: Foerster - first_name: Janne full_name: Korhonen, Janne id: C5402D42-15BC-11E9-A202-CA2BE6697425 last_name: Korhonen - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid 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' 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. 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. 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.' 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. 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. conference: end_date: 2019-08-02 location: Toronto, ON, Canada name: 'PODC: Symposium on Principles of Distributed Computing' start_date: 2019-07-29 date_created: 2019-10-08T12:57:14Z date_published: 2019-08-01T00:00:00Z date_updated: 2023-09-08T11:37:22Z day: '01' department: - _id: DaAl doi: 10.1145/3293611.3331581 ec_funded: 1 external_id: arxiv: - '1905.03012' isi: - '000570442000037' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1905.03012 month: '08' oa: 1 oa_version: Preprint page: 259-261 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing publication_identifier: isbn: - '9781450362177' publication_status: published publisher: ACM quality_controlled: '1' scopus_import: '1' status: public title: Does preprocessing help under congestion? type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2019' ... --- _id: '6936' 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" article_processing_charge: No article_type: original author: - first_name: Otso full_name: Ovaskainen, Otso last_name: Ovaskainen - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Nerea full_name: Abrego, Nerea last_name: Abrego citation: 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 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. 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. ista: Ovaskainen O, Rybicki J, Abrego N. 2019. What can observational data reveal about metacommunity processes? Ecography. 42(11), 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. short: O. Ovaskainen, J. Rybicki, N. Abrego, Ecography 42 (2019) 1877–1886. date_created: 2019-10-08T13:01:24Z date_published: 2019-11-01T00:00:00Z date_updated: 2023-08-30T06:57:25Z day: '01' ddc: - '577' department: - _id: DaAl doi: 10.1111/ecog.04444 ec_funded: 1 external_id: isi: - '000486348700001' file: - access_level: open_access checksum: 6c9fbbd5ea8ce10ae93e55ad560a7bf9 content_type: application/pdf creator: jrybicki date_created: 2019-10-08T13:07:44Z date_updated: 2020-07-14T12:47:45Z file_id: '6937' file_name: ecog.04444.pdf file_size: 1682718 relation: main_file file_date_updated: 2020-07-14T12:47:45Z has_accepted_license: '1' intvolume: ' 42' isi: 1 issue: '11' language: - iso: eng month: '11' oa: 1 oa_version: Published Version page: 1877-1886 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: Ecography publication_identifier: eissn: - 1600-0587 issn: - 0906-7590 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: What can observational data reveal about metacommunity processes? tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 42 year: '2019' ... --- _id: '6972' 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. 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 chicago: Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3339471. 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. 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). date_created: 2019-10-24T17:12:48Z date_published: 2019-09-01T00:00:00Z date_updated: 2023-08-30T07:07:23Z day: '01' ddc: - '000' department: - _id: DaAl doi: 10.1145/3339471 ec_funded: 1 external_id: arxiv: - '1705.06173' isi: - '000496514100001' file: - access_level: open_access checksum: 7e5d95c478e0e393f4927fcf7e48194e content_type: application/pdf creator: dernst date_created: 2019-10-25T12:58:38Z date_updated: 2020-07-14T12:47:46Z file_id: '6975' file_name: 2019_JACM_Lenzen.pdf file_size: 2183085 relation: main_file file_date_updated: 2020-07-14T12:47:46Z has_accepted_license: '1' intvolume: ' 66' isi: 1 issue: '5' language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: Journal of the ACM publication_identifier: issn: - 0004-5411 publication_status: published publisher: ACM quality_controlled: '1' scopus_import: '1' status: public title: Self-stabilising Byzantine clock synchronisation is almost as easy as consensus tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 66 year: '2019' ... --- _id: '76' abstract: - lang: eng 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.' article_processing_charge: Yes (via OA deal) author: - first_name: Christoph full_name: Lenzen, Christoph last_name: Lenzen - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 citation: ama: Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads. Distributed Computing. 2018. doi:10.1007/s00446-018-0342-6 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 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. ieee: C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing squads,” Distributed Computing. Springer, 2018. ista: Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing squads. Distributed Computing. 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. short: C. Lenzen, J. Rybicki, Distributed Computing (2018). date_created: 2018-12-11T11:44:30Z date_published: 2018-09-12T00:00:00Z date_updated: 2023-09-13T09:01:06Z day: '12' ddc: - '000' department: - _id: DaAl doi: 10.1007/s00446-018-0342-6 external_id: isi: - '000475627800005' file: - access_level: open_access checksum: 872db70bba9b401500abe3c6ae2f1a61 content_type: application/pdf creator: dernst date_created: 2018-12-17T14:21:22Z date_updated: 2020-07-14T12:48:01Z file_id: '5711' file_name: 2018_DistributedComputing_Lenzen.pdf file_size: 799337 relation: main_file file_date_updated: 2020-07-14T12:48:01Z has_accepted_license: '1' isi: 1 language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: B67AFEDC-15C9-11EA-A837-991A96BB2854 name: IST Austria Open Access Fund publication: Distributed Computing publication_status: published publisher: Springer publist_id: '7978' quality_controlled: '1' scopus_import: '1' status: public title: Near-optimal self-stabilising counting and firing squads tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2018' ... --- _id: '43' abstract: - lang: eng 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.' acknowledgement: J.R. and J.V.A. were also supported by the Academy of Finland Grants 1273253 and 267541. article_processing_charge: No author: - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Eva full_name: Kisdi, Eva last_name: Kisdi - first_name: Jani full_name: Anttila, Jani last_name: Anttila citation: 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 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 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. 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. ista: Rybicki J, Kisdi E, Anttila J. 2018. Model of bacterial toxin-dependent pathogenesis explains infective dose. PNAS. 115(42), 10690–10695. 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. short: J. Rybicki, E. Kisdi, J. Anttila, PNAS 115 (2018) 10690–10695. date_created: 2018-12-11T11:44:19Z date_published: 2018-10-02T00:00:00Z date_updated: 2023-09-13T08:57:38Z day: '02' ddc: - '570' - '577' department: - _id: DaAl doi: 10.1073/pnas.1721061115 ec_funded: 1 external_id: isi: - '000447491300057' file: - access_level: open_access checksum: df7ac544a587c06b75692653b9fabd18 content_type: application/pdf creator: dernst date_created: 2019-04-09T08:02:50Z date_updated: 2020-07-14T12:46:26Z file_id: '6258' file_name: 2018_PNAS_Rybicki.pdf file_size: 4070777 relation: main_file file_date_updated: 2020-07-14T12:46:26Z has_accepted_license: '1' intvolume: ' 115' isi: 1 issue: '42' language: - iso: eng month: '10' oa: 1 oa_version: Submitted Version page: 10690 - 10695 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships publication: PNAS publication_status: published publisher: National Academy of Sciences publist_id: '8011' pubrep_id: '1063' quality_controlled: '1' scopus_import: '1' status: public title: Model of bacterial toxin-dependent pathogenesis explains infective dose type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 115 year: '2018' ... --- _id: '6932' 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." article_processing_charge: No 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 full_name: Lempiäinen, Tuomo last_name: Lempiäinen - first_name: Patric R.J. full_name: Östergård, Patric R.J. last_name: Östergård - first_name: Christopher full_name: Purcell, Christopher last_name: Purcell - first_name: Joel full_name: Rybicki, Joel id: 334EFD2E-F248-11E8-B48F-1D18A9856A87 last_name: Rybicki orcid: 0000-0002-6432-6646 - first_name: Jukka full_name: Suomela, Jukka last_name: Suomela - first_name: Przemysław full_name: Uznański, Przemysław last_name: Uznański citation: 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' 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. 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.' 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.' mla: Brandt, Sebastian, et al. LCL Problems on Grids. ACM Press, 2017, pp. 101–10, doi:10.1145/3087801.3087833. 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. conference: end_date: 2017-07-27 location: Washington, DC, United States name: 'PODC: Principles of Distributed Computing' start_date: 2017-07-25 date_created: 2019-10-08T12:47:46Z date_published: 2017-07-01T00:00:00Z date_updated: 2021-01-12T08:09:39Z day: '01' doi: 10.1145/3087801.3087833 extern: '1' language: - iso: eng month: '07' oa_version: None page: 101-110 publication_identifier: isbn: - '9781450349925' publication_status: published publisher: ACM Press quality_controlled: '1' status: public title: LCL problems on grids type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2017' ...