Title | ||
---|---|---|
Brief Announcement: On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement |
Abstract | ||
---|---|---|
ABSTRACTThis paper investigates on the message complexity of the two fundamental problems, namely, leader election and agreement in the crash-fault synchronous and fully-connected distributed network. We present randomized algorithms for both the problems and also develop non-trivial lower bounds on the message complexity. In the so-called implicit version of the two problems, our algorithms achieve sublinear message complexity while tolerating more than a constant fraction of faulty nodes. The algorithms work in anonymous networks, where nodes do not know each other. Specifically, our main results are: (1)A randomized leader election algorithm which elects a leader with high probability in a complete network with n nodes, in which at least ⌉ n⌈ nodes are non-faulty and the remaining can be faulty, where ≥ (log2 n)/n. The time complexity of the algorithm is O (log nα) rounds and message complexity is O((n0.5 log2.5 n)/2.5) with high probability (i.e., with probability ≥ 1-1/n). A non-trivial lower bound of Ω(n0.5 / α1.5) messages for any leader election algorithm that tolerates at most (1-α)-fraction faulty nodes and succeeds with high probability. (2)A randomized algorithm, tolerating at most ⌊(1-α)n⌋ faulty nodes, solves agreement in O (log n/α) rounds and with high probability uses only O((n0.5 log1.5n)/α1.5) messages. A matching lower bound (up to a polylog n factor) of Ω (n0.5 /α1.5) messages for any agreement algorithm that tolerates at most (1-α)-fraction faulty nodes and succeeds with high probability. A full version of the paper is available at [17]. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1145/3465084.3467949 | Principles of Distributed Computing |
Keywords | DocType | Citations |
Distributed algorithm, randomized algorithm, fault-tolerant algorithm, crash-fault, leader election, agreement, message complexity | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
manish kumar | 1 | 401 | 69.07 |
Anisur Rahaman Molla | 2 | 59 | 12.90 |