@inproceedings{c89a0d7484b04413aa5ec3d039242cde,
title = "Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication",
abstract = "We develop deterministic algorithms for the problems of consensus, gossiping and checkpointing with nodes prone to failing. Distributed systems are modeled as synchronous complete networks. Failures are represented either as crashes or Byzantine faults with authentication. The algorithmic goal is to have both linear running time and linear amount of communication for as large an upper bound t on the number of faults as possible, with respect to the number of nodes n. For crash failures, these bounds of optimality are t = O(n / (log n)) for consensus and t = O(n / (log2 n)) for gossiping and checkpointing. For the model of Byzantine faults with authentication, we show how to reach consensus in both linear running time and communication for t = O(√n). We show how to implement the consensus algorithm for crash failures in the single-port model such as to preserve the range of t for which both the running time and communication are optimal. We prove a lower bound ω (t+log n) on the running time of algorithms for each of the considered problems.",
keywords = "authentication, byzantine fault, checkpointing, consensus, crash failure, gossiping, lower bound, ramanujan graph",
author = "Bogdan Chlebus and Kowalski, {Dariusz Rafal} and Jan Olkowski",
note = "Publisher Copyright: {\textcopyright} 2023 ACM.; 42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023 ; Conference date: 19-06-2023 Through 23-06-2023",
year = "2023",
month = jun,
day = "19",
doi = "10.1145/3583668.3594599",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
publisher = "Association for Computing Machinery",
pages = "344--354",
booktitle = "PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing",
}