[{"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.08325"}],"page":"165-175","type":"conference","date_updated":"2023-08-17T06:24:44Z","_id":"10554","publisher":"Association for Computing Machinery","doi":"10.1145/3465084.3467905","article_processing_charge":"No","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","date_published":"2021-07-21T00:00:00Z","conference":{"location":"Virtual, Italy","name":"PODC: Principles of Distributed Computing","end_date":"2021-07-30","start_date":"2021-07-26"},"status":"public","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","external_id":{"arxiv":["2102.08325"],"isi":["000744439800016"]},"year":"2021","isi":1,"publication_status":"published","publication_identifier":{"isbn":["978-1-4503-8548-0"]},"abstract":[{"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.","lang":"eng"}],"date_created":"2021-12-16T13:21:13Z","oa_version":"Preprint","title":"All You Need is DAG","author":[{"first_name":"Idit","last_name":"Keidar","full_name":"Keidar, Idit"},{"first_name":"Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","full_name":"Kokoris Kogias, Eleftherios","last_name":"Kokoris Kogias"},{"first_name":"Oded","full_name":"Naor, Oded","last_name":"Naor"},{"first_name":"Alexander","last_name":"Spiegelman","full_name":"Spiegelman, Alexander"}],"day":"21","scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","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>","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.","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.","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>.","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>.","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>"},"language":[{"iso":"eng"}],"oa":1,"department":[{"_id":"ElKo"}],"month":"07","arxiv":1},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","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>","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.","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.","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>.","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>.","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>"},"language":[{"iso":"eng"}],"oa":1,"department":[{"_id":"DaAl"}],"month":"07","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-8548-0"]},"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."}],"date_created":"2021-08-17T18:14:15Z","title":"Improved deterministic (Δ+1) coloring in low-space MPC","oa_version":"Submitted Version","day":"21","author":[{"first_name":"Artur","last_name":"Czumaj","full_name":"Czumaj, Artur"},{"full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","orcid":"0000-0002-5646-9524","first_name":"Peter"},{"full_name":"Parter, Merav","last_name":"Parter","first_name":"Merav"}],"conference":{"end_date":"2021-07-30","start_date":"2021-07-26","name":"PODC: Symposium on Principles of Distributed Computing","location":"Virtual, Italy"},"date_published":"2021-07-21T00:00:00Z","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.","ec_funded":1,"publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","status":"public","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"external_id":{"isi":["000744439800048"]},"year":"2021","isi":1,"quality_controlled":"1","main_file_link":[{"url":"http://wrap.warwick.ac.uk/153753","open_access":"1"}],"page":"469–479","type":"conference","_id":"9935","date_updated":"2023-08-17T07:11:03Z","publisher":"Association for Computing Machinery","article_processing_charge":"No","doi":"10.1145/3465084.3467937"}]