@inproceedings{10554,
  abstract     = {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.},
  author       = {Keidar, Idit and Kokoris Kogias, Eleftherios and Naor, Oded and Spiegelman, Alexander},
  booktitle    = {Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing},
  isbn         = {978-1-4503-8548-0},
  location     = {Virtual, Italy},
  pages        = {165--175},
  publisher    = {Association for Computing Machinery},
  title        = {{All You Need is DAG}},
  doi          = {10.1145/3465084.3467905},
  year         = {2021},
}

@inproceedings{9935,
  abstract     = {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.

Our 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.

The 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.},
  author       = {Czumaj, Artur and Davies, Peter and Parter, Merav},
  booktitle    = {Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing},
  isbn         = {978-1-4503-8548-0},
  location     = {Virtual, Italy},
  pages        = {469–479},
  publisher    = {Association for Computing Machinery},
  title        = {{Improved deterministic (Δ+1) coloring in low-space MPC}},
  doi          = {10.1145/3465084.3467937},
  year         = {2021},
}