Patterns of Communication in Consensus Protocols

Abstract

This paper presents a taxonomy of consensus problems, based on their safeness and liveness properties, and then explores the relationships among the different problems in the taxonomy. Each problem is characterized by the communication patterns of protocols solving it. This then becomes the basis for a new notion of reducibility between problems. Formally, problem $P_{1}$ reduces to problem $P_{2}$ whenever each set of communication patterns of a protocol for $P_{2}$ is the set of comunication patterns of a protocol for $P_{1}$. This means intuitively that any protocol for $P_{2}$ can solve $P_{1}$ by relabeling local states and padding messages. Consequently, the message complexity (measured in number of messages) of $P_{1}$ is not greater than the message complexity of $P_{2}$. Our method of characterizing and comparing problems is the principal contribution of this paper.