Patterns of communication in consensus protocols
Cynthia Dwork, Dale Skeen · 1984
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 P1 reduces to problem P2 whenever each set of communication patterns of a protocol for P2 is the set of communication patterns of a protocol for P1. This means intuitively that any protocol for P2 can solve P1 by relabeling local states and padding messages. Consequently, the message complexity (measured in number of messages) of P1 is not greater than the message complexity of P2. Our method of characterizing and comparing problems is the principal contribution of this paper.