A Consensus Algorithm Tolerating Adversarial Crash and Probabilistic Omission

摘要

The (uniform) consensus, which is one of fundamental and important problems for designing fault-tolerant distributed systems, is the problem that all processes have to agree on a common value that is proposed by a process. In this paper, we newly introduce a distributed system model that suffers crash faults and probabilistic omissions where each message is omitted with a probability p, and consider consensus algorithms on the model. We propose a consensus algorithm with O(f) worst-case expected round complexity if p<1-4{sup}(1/2). Interstingly, although the algorithm can tolerate high-probability message omission, its overhead is not so much: Since all of exiting consensus algorithms that can not tolerate omissions have the worst-case round complexity at least (f+2), our algorithm has the round complexity only a constant time as much as existing non-omission-tolerant algorithms.