---
_id: '10554'
abstract:
- lang: eng
  text: 'We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol
    that achieves optimal resilience, optimal amortized communication complexity,
    and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all
    values proposed by correct processes eventually get delivered. We construct DAG-Rider
    in two layers: In the first layer, processes reliably broadcast their proposals
    and build a structured Directed Acyclic Graph (DAG) of the communication among
    them. In the second layer, processes locally observe their DAGs and totally order
    all proposals with no extra communication.'
acknowledgement: "Oded Naor is grateful to the Technion Hiroshi Fujiwara Cyber-Security
  Research Center for providing a research grant. Part of Oded’s work was done while
  at Novi Research. This work was funded by the Novi team at Facebook. We also wish
  to thank the Novi Research team for valuable feedback, and in particular George
  Danezis, Alberto Sonnino, and Dahlia Malkhi.\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Idit
  full_name: Keidar, Idit
  last_name: Keidar
- first_name: Eleftherios
  full_name: Kokoris Kogias, Eleftherios
  id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
  last_name: Kokoris Kogias
- first_name: Oded
  full_name: Naor, Oded
  last_name: Naor
- first_name: Alexander
  full_name: Spiegelman, Alexander
  last_name: Spiegelman
citation:
  ama: 'Keidar I, Kokoris Kogias E, Naor O, Spiegelman A. All You Need is DAG. In:
    <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>.
    Association for Computing Machinery; 2021:165-175. doi:<a href="https://doi.org/10.1145/3465084.3467905">10.1145/3465084.3467905</a>'
  apa: 'Keidar, I., Kokoris Kogias, E., Naor, O., &#38; Spiegelman, A. (2021). All
    You Need is DAG. In <i>Proceedings of the 2021 ACM Symposium on Principles of
    Distributed Computing</i> (pp. 165–175). Virtual, Italy: Association for Computing
    Machinery. <a href="https://doi.org/10.1145/3465084.3467905">https://doi.org/10.1145/3465084.3467905</a>'
  chicago: Keidar, Idit, Eleftherios Kokoris Kogias, Oded Naor, and Alexander Spiegelman.
    “All You Need Is DAG.” In <i>Proceedings of the 2021 ACM Symposium on Principles
    of Distributed Computing</i>, 165–75. Association for Computing Machinery, 2021.
    <a href="https://doi.org/10.1145/3465084.3467905">https://doi.org/10.1145/3465084.3467905</a>.
  ieee: I. Keidar, E. Kokoris Kogias, O. Naor, and A. Spiegelman, “All You Need is
    DAG,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed
    Computing</i>, Virtual, Italy, 2021, pp. 165–175.
  ista: 'Keidar I, Kokoris Kogias E, Naor O, Spiegelman A. 2021. All You Need is DAG.
    Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing.
    PODC: Principles of Distributed Computing, 165–175.'
  mla: Keidar, Idit, et al. “All You Need Is DAG.” <i>Proceedings of the 2021 ACM
    Symposium on Principles of Distributed Computing</i>, Association for Computing
    Machinery, 2021, pp. 165–75, doi:<a href="https://doi.org/10.1145/3465084.3467905">10.1145/3465084.3467905</a>.
  short: I. Keidar, E. Kokoris Kogias, O. Naor, A. Spiegelman, in:, Proceedings of
    the 2021 ACM Symposium on Principles of Distributed Computing, Association for
    Computing Machinery, 2021, pp. 165–175.
conference:
  end_date: 2021-07-30
  location: Virtual, Italy
  name: 'PODC: Principles of Distributed Computing'
  start_date: 2021-07-26
date_created: 2021-12-16T13:21:13Z
date_published: 2021-07-21T00:00:00Z
date_updated: 2023-08-17T06:24:44Z
day: '21'
department:
- _id: ElKo
doi: 10.1145/3465084.3467905
external_id:
  arxiv:
  - '2102.08325'
  isi:
  - '000744439800016'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2102.08325
month: '07'
oa: 1
oa_version: Preprint
page: 165-175
publication: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - 978-1-4503-8548-0
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: All You Need is DAG
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '9935'
abstract:
- lang: eng
  text: "We present a deterministic O(log log log n)-round low-space Massively Parallel
    Computation (MPC) algorithm for the classical problem of (Δ+1)-coloring on n-vertex
    graphs. In this model, every machine has sublinear local space of size n^φ for
    any arbitrary constant φ \\in (0,1). Our algorithm works under the relaxed setting
    where each machine is allowed to perform exponential local computations, while
    respecting the n^φ space and bandwidth limitations.\r\n\r\nOur key technical contribution
    is a novel derandomization of the ingenious (Δ+1)-coloring local algorithm by
    Chang-Li-Pettie (STOC 2018, SIAM J. Comput. 2020). The Chang-Li-Pettie algorithm
    runs in T_local =poly(loglog n) rounds, which sets the state-of-the-art randomized
    round complexity for the problem in the local model. Our derandomization employs
    a combination of tools, notably pseudorandom generators (PRG) and bounded-independence
    hash functions.\r\n\r\nThe achieved round complexity of O(logloglog n) rounds
    matches the bound of log(T_local ), which currently serves an upper bound barrier
    for all known randomized algorithms for locally-checkable problems in this model.
    Furthermore, no deterministic sublogarithmic low-space MPC algorithms for the
    (Δ+1)-coloring problem have been known before."
acknowledgement: This work is partially supported by a Weizmann-UK Making Connections
  Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty
  Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083,
  the Minerva foundation with funding from the Federal German Ministry for Education
  and Research No. 713238, and the European Union’s Horizon 2020 programme under the
  Marie Skłodowska-Curie grant agreement No 754411.
article_processing_charge: No
author:
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- first_name: Peter
  full_name: Davies, Peter
  id: 11396234-BB50-11E9-B24C-90FCE5697425
  last_name: Davies
  orcid: 0000-0002-5646-9524
- first_name: Merav
  full_name: Parter, Merav
  last_name: Parter
citation:
  ama: 'Czumaj A, Davies P, Parter M. Improved deterministic (Δ+1) coloring in low-space
    MPC. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed
    Computing</i>. Association for Computing Machinery; 2021:469–479. doi:<a href="https://doi.org/10.1145/3465084.3467937">10.1145/3465084.3467937</a>'
  apa: 'Czumaj, A., Davies, P., &#38; Parter, M. (2021). Improved deterministic (Δ+1)
    coloring in low-space MPC. In <i>Proceedings of the 2021 ACM Symposium on Principles
    of Distributed Computing</i> (pp. 469–479). Virtual, Italy: Association for Computing
    Machinery. <a href="https://doi.org/10.1145/3465084.3467937">https://doi.org/10.1145/3465084.3467937</a>'
  chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Improved Deterministic
    (Δ+1) Coloring in Low-Space MPC.” In <i>Proceedings of the 2021 ACM Symposium
    on Principles of Distributed Computing</i>, 469–479. Association for Computing
    Machinery, 2021. <a href="https://doi.org/10.1145/3465084.3467937">https://doi.org/10.1145/3465084.3467937</a>.
  ieee: A. Czumaj, P. Davies, and M. Parter, “Improved deterministic (Δ+1) coloring
    in low-space MPC,” in <i>Proceedings of the 2021 ACM Symposium on Principles of
    Distributed Computing</i>, Virtual, Italy, 2021, pp. 469–479.
  ista: 'Czumaj A, Davies P, Parter M. 2021. Improved deterministic (Δ+1) coloring
    in low-space MPC. Proceedings of the 2021 ACM Symposium on Principles of Distributed
    Computing. PODC: Symposium on Principles of Distributed Computing, 469–479.'
  mla: Czumaj, Artur, et al. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.”
    <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>,
    Association for Computing Machinery, 2021, pp. 469–479, doi:<a href="https://doi.org/10.1145/3465084.3467937">10.1145/3465084.3467937</a>.
  short: A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2021 ACM Symposium
    on Principles of Distributed Computing, Association for Computing Machinery, 2021,
    pp. 469–479.
conference:
  end_date: 2021-07-30
  location: Virtual, Italy
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2021-07-26
date_created: 2021-08-17T18:14:15Z
date_published: 2021-07-21T00:00:00Z
date_updated: 2023-08-17T07:11:03Z
day: '21'
department:
- _id: DaAl
doi: 10.1145/3465084.3467937
ec_funded: 1
external_id:
  isi:
  - '000744439800048'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://wrap.warwick.ac.uk/153753
month: '07'
oa: 1
oa_version: Submitted Version
page: 469–479
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - 978-1-4503-8548-0
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Improved deterministic (Δ+1) coloring in low-space MPC
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...