JavaScript is disabled for your browser. Some features of this site may not work without it.
Patterns of Communication in Consensus Protocols

Author
Dwork, Cynthia; Skeen, Dale
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.
Date Issued
1984-06Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84-611
Type
technical report