Validity Conditions in Agreement Problems and Time Complexity

摘要

We first introduce a new class of distributed agreement problems, ranging from Uniform Consensus to Non-Blocking Atomic Commitment, by varying the validity condition in the specification. We then provide an early deciding algorithm to solve each problem of this class in the synchronous model with crash failures. Our algorithm achieves the previously established lower bounds for time complexity showing that these lower bounds are tight.