---
_id: '10216'
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.'
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"
alternative_title:
- LIPIcs
article_number: '52'
article_processing_charge: No
arxiv: 1
author:
- first_name: Bapi
  full_name: Chatterjee, Bapi
  id: 3C41A08A-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
- first_name: Sathya
  full_name: Peri, Sathya
  last_name: Peri
- first_name: Muktikanta
  full_name: Sa, Muktikanta
  last_name: Sa
citation:
  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>'
  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>.'
  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.'
  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.'
  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.
conference:
  end_date: 2021-10-08
  location: Freiburg, Germany
  name: 'DISC: Distributed Computing'
  start_date: 2021-10-04
date_created: 2021-11-07T23:01:23Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2021-11-12T09:42:55Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.52
external_id:
  arxiv:
  - '2003.01697'
file:
- access_level: open_access
  checksum: 76546df112a0ba1166c864d33d7834e2
  content_type: application/pdf
  creator: cchlebak
  date_created: 2021-11-12T09:23:22Z
  date_updated: 2021-11-12T09:23:22Z
  file_id: '10276'
  file_name: 2021_LIPIcsDISC_BChatterjee.pdf
  file_size: 795860
  relation: main_file
  success: 1
file_date_updated: 2021-11-12T09:23:22Z
has_accepted_license: '1'
intvolume: '       209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
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: Non-blocking dynamic unbounded graphs with worst-case
  amortized bounds'
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: '10217'
abstract:
- lang: eng
  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.
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."
alternative_title:
- LIPIcs
article_number: '4'
article_processing_charge: No
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: Giorgi
  full_name: Nadiradze, Giorgi
  id: 3279A00C-F248-11E8-B48F-1D18A9856A87
  last_name: Nadiradze
citation:
  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>.
  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.
  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.'
  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>.
  short: D.-A. Alistarh, R. Gelashvili, G. Nadiradze, 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:23Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2022-08-19T07:23:28Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.4
ec_funded: 1
file:
- access_level: open_access
  checksum: b4cdc6668c899a601c5e6a96b8ca54d9
  content_type: application/pdf
  creator: cchlebak
  date_created: 2021-11-12T09:33:26Z
  date_updated: 2021-11-12T09:33:26Z
  file_id: '10277'
  file_name: 2021_LIPIcsDISC_Alistarh.pdf
  file_size: 706791
  relation: main_file
  success: 1
file_date_updated: 2021-11-12T09:33:26Z
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: Lower bounds for shared-memory leader election under bounded write contention
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: 209
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: <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>'
  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>.'
  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.'
  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.” <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.
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: <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>'
  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>.'
  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.'
  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.” <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:
  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'
...