A Consensus Algorithm Tolerating Adversarial Crash and Probabilistic Omission

摘要

The (uniform) consensus, which is one of fundamental and important pi'oblems 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 algrithms on the model. We propose a consensus algorithm with O(f) worst-case expected round complexity if p < 1 - 4,/y. 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 (/ + 2), our algorithm has the round complexity only a constant time as much as existing non-omission-tolorant algorithms.