Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 196-207 |
| Number of pages | 12 |
| Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Volume | 2932 |
| Publication status | Published - 1 Dec 2003 |
Keywords
- Complexity
- Distributed Algorithms