[{"intvolume":"       209","publication":"35th International Symposium on Distributed Computing","author":[{"orcid":"0000-0002-2742-4028","last_name":"Chatterjee","full_name":"Chatterjee, Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","first_name":"Bapi"},{"full_name":"Peri, Sathya","last_name":"Peri","first_name":"Sathya"},{"full_name":"Sa, Muktikanta","last_name":"Sa","first_name":"Muktikanta"}],"scopus_import":"1","file_date_updated":"2021-11-12T09:23:22Z","publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"oa":1,"acknowledgement":"This work was partially funded by National Supercomputing Mission, Govt. of India under the project “Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs”(DST/NSM/R&D_Exascale/2021/16).\r\n","file":[{"relation":"main_file","access_level":"open_access","success":1,"checksum":"76546df112a0ba1166c864d33d7834e2","content_type":"application/pdf","date_updated":"2021-11-12T09:23:22Z","file_id":"10276","date_created":"2021-11-12T09:23:22Z","file_name":"2021_LIPIcsDISC_BChatterjee.pdf","creator":"cchlebak","file_size":795860}],"publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"external_id":{"arxiv":["2003.01697"]},"date_created":"2021-11-07T23:01:23Z","quality_controlled":"1","volume":209,"abstract":[{"lang":"eng","text":"This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking."}],"license":"https://creativecommons.org/licenses/by/4.0/","article_number":"52","oa_version":"Published Version","year":"2021","date_updated":"2025-05-14T10:54:39Z","date_published":"2021-10-04T00:00:00Z","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","type":"conference","day":"04","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"ddc":["000"],"doi":"10.4230/LIPIcs.DISC.2021.52","alternative_title":["LIPIcs"],"title":"Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds","month":"10","_id":"10216","citation":{"ieee":"B. Chatterjee, S. Peri, and M. Sa, “Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","mla":"Chatterjee, Bapi, et al. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 52, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>.","short":"B. Chatterjee, S. Peri, M. Sa, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","chicago":"Chatterjee, Bapi, Sathya Peri, and Muktikanta Sa. “Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>.","ista":"Chatterjee B, Peri S, Sa M. 2021. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 52.","ama":"Chatterjee B, Peri S, Sa M. Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">10.4230/LIPIcs.DISC.2021.52</a>","apa":"Chatterjee, B., Peri, S., &#38; Sa, M. (2021). Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.52\">https://doi.org/10.4230/LIPIcs.DISC.2021.52</a>"},"article_processing_charge":"No","conference":{"location":"Freiburg, Germany","end_date":"2021-10-08","name":"DISC: Distributed Computing","start_date":"2021-10-04"}},{"abstract":[{"text":"This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution.","lang":"eng"}],"article_number":"4","quality_controlled":"1","volume":209,"language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"date_created":"2021-11-07T23:01:23Z","publication_status":"published","publication_identifier":{"issn":["1868-8969"],"isbn":["9-783-9597-7210-5"]},"oa":1,"acknowledgement":"Dan Alistarh: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Giorgi Nadiradze: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). The authors would like to thank the DISC anonymous reviewers for their useful\r\nfeedback and comments.","file":[{"file_id":"10277","date_created":"2021-11-12T09:33:26Z","file_name":"2021_LIPIcsDISC_Alistarh.pdf","creator":"cchlebak","file_size":706791,"content_type":"application/pdf","checksum":"b4cdc6668c899a601c5e6a96b8ca54d9","date_updated":"2021-11-12T09:33:26Z","success":1,"relation":"main_file","access_level":"open_access"}],"ec_funded":1,"intvolume":"       209","file_date_updated":"2021-11-12T09:33:26Z","publication":"35th International Symposium on Distributed Computing","author":[{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"orcid":"0000-0001-5634-0731","last_name":"Nadiradze","full_name":"Nadiradze, Giorgi","first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","citation":{"short":"D.-A. Alistarh, R. Gelashvili, G. Nadiradze, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","mla":"Alistarh, Dan-Adrian, et al. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>.","ieee":"D.-A. Alistarh, R. Gelashvili, and G. Nadiradze, “Lower bounds for shared-memory leader election under bounded write contention,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","ama":"Alistarh D-A, Gelashvili R, Nadiradze G. Lower bounds for shared-memory leader election under bounded write contention. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">10.4230/LIPIcs.DISC.2021.4</a>","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Nadiradze, G. (2021). Lower bounds for shared-memory leader election under bounded write contention. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Giorgi Nadiradze. “Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.4\">https://doi.org/10.4230/LIPIcs.DISC.2021.4</a>.","ista":"Alistarh D-A, Gelashvili R, Nadiradze G. 2021. Lower bounds for shared-memory leader election under bounded write contention. 35th International Symposium on Distributed Computing. DISC: Distributed Computing, LIPIcs, vol. 209, 4."},"article_processing_charge":"No","conference":{"start_date":"2021-10-04","name":"DISC: Distributed Computing","end_date":"2021-10-08","location":"Freiburg, Germany"},"title":"Lower bounds for shared-memory leader election under bounded write contention","month":"10","_id":"10217","doi":"10.4230/LIPIcs.DISC.2021.4","alternative_title":["LIPIcs"],"ddc":["000"],"type":"conference","day":"04","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","year":"2021","date_updated":"2025-05-14T10:54:30Z","project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"date_published":"2021-10-04T00:00:00Z","has_accepted_license":"1"},{"publication_status":"published","external_id":{"arxiv":["2102.08808"]},"department":[{"_id":"DaAl"}],"date_created":"2021-11-07T23:01:24Z","language":[{"iso":"eng"}],"volume":209,"quality_controlled":"1","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."}],"article_number":"43","author":[{"last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","full_name":"Rybicki, Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646"}],"publication":"35th International Symposium on Distributed Computing","scopus_import":"1","file_date_updated":"2021-11-12T08:16:44Z","ec_funded":1,"intvolume":"       209","file":[{"content_type":"application/pdf","checksum":"fd2a690f6856d21247e9aa952b0e2885","date_updated":"2021-11-12T08:16:44Z","file_name":"2021_LIPIcsDISC_Alistarh.pdf","creator":"cchlebak","date_created":"2021-11-12T08:16:44Z","file_id":"10274","file_size":534219,"access_level":"open_access","relation":"main_file","success":1}],"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.","oa":1,"publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"arxiv":1,"ddc":["000"],"doi":"10.4230/LIPIcs.DISC.2021.43","alternative_title":["LIPIcs"],"_id":"10218","title":"Brief announcement: Fast graphical population protocols","month":"10","article_processing_charge":"No","conference":{"name":"DISC: Distributed Computing ","start_date":"2021-10-04","location":"Freiburg, Germany","end_date":"2021-10-08"},"citation":{"ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast graphical population protocols,” in <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population Protocols.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>.","short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement: Fast Graphical Population Protocols.” In <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>.","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.","ama":"Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical population protocols. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">10.4230/LIPIcs.DISC.2021.43</a>","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2021). Brief announcement: Fast graphical population protocols. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.43\">https://doi.org/10.4230/LIPIcs.DISC.2021.43</a>"},"date_published":"2021-10-04T00:00:00Z","project":[{"name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425"}],"has_accepted_license":"1","year":"2021","oa_version":"Published Version","date_updated":"2025-04-14T07:50:55Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","status":"public","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"day":"04","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","type":"conference"},{"language":[{"iso":"eng"}],"date_created":"2021-11-07T23:01:24Z","department":[{"_id":"DaAl"}],"external_id":{"arxiv":["2108.02655"]},"publication_status":"published","article_number":"58","abstract":[{"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).","lang":"eng"}],"quality_controlled":"1","volume":209,"intvolume":"       209","ec_funded":1,"file_date_updated":"2021-11-12T08:27:42Z","publication":"35th International Symposium on Distributed Computing","scopus_import":"1","author":[{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","last_name":"Korhonen","full_name":"Korhonen, Janne"},{"full_name":"Paz, Ami","last_name":"Paz","first_name":"Ami"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel","full_name":"Rybicki, Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"last_name":"Suomela","full_name":"Suomela, Jukka","first_name":"Jukka"}],"oa":1,"publication_identifier":{"isbn":["9-783-9597-7210-5"],"issn":["1868-8969"]},"file":[{"success":1,"relation":"main_file","access_level":"open_access","file_size":474242,"date_created":"2021-11-12T08:27:42Z","file_id":"10275","creator":"cchlebak","file_name":"2021_LIPIcsDISC_Korhonen.pdf","date_updated":"2021-11-12T08:27:42Z","checksum":"c43188dc2070bbd2bf5fd6fdaf9ce36d","content_type":"application/pdf"}],"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"],"doi":"10.4230/LIPIcs.DISC.2021.58","ddc":["000"],"arxiv":1,"citation":{"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 <i>35th International Symposium on Distributed Computing</i>, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>.","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.","ama":"Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In: <i>35th International Symposium on Distributed Computing</i>. Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>","apa":"Korhonen, J., Paz, A., Rybicki, J., Schmid, S., &#38; Suomela, J. (2021). Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In <i>35th International Symposium on Distributed Computing</i> (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">https://doi.org/10.4230/LIPIcs.DISC.2021.58</a>","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 <i>35th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2021, vol. 209.","mla":"Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.” <i>35th International Symposium on Distributed Computing</i>, vol. 209, 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2021.58\">10.4230/LIPIcs.DISC.2021.58</a>.","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":{"location":"Freiburg, Germany","end_date":"2021-10-08","name":"DISC: Distributed Computing ","start_date":"2021-10-04"},"article_processing_charge":"No","month":"10","title":"Brief announcement: Sinkless orientation is hard also in the supported LOCAL model","_id":"10219","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-05-14T10:54:13Z","oa_version":"Published Version","year":"2021","project":[{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020"}],"has_accepted_license":"1","date_published":"2021-10-04T00:00:00Z","day":"04","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","type":"conference","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public"}]