Paper Info
Title
Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions
Abstract
Decision tasks require that nonfaulty processes make decisions based on their input values. Simultaneous decision tasks require that nonfaulty processes decide in the same round. Most decision tasks have known worst-case lower bounds. Most also have known worst-case optimal protocols that halt in the number of rounds given by the worst-case lower bound, and some have early-stopping protocols that can halt earlier than the worst-case lower bound (sometimes in as early as two rounds). We consider what might be called earliest-possible protocols for simultaneous decision tasks. We present a new technique that converts worst-case optimal decision protocols into all-case optimal simultaneous decision protocols: For every behavior of the adversary, the all-case optimal protocol decides as soon as any protocol can decide in a run with the same adversarial behavior. Examples to which this can be applied include set consensus, condition-based consensus, renaming and order-preserving renaming. Some of these tasks can be solved significantly faster than the classical simultaneous consensus task. A byproduct of the analysis is a proof that improving on the worst-case bound for any simultaneous task by even a single round is as hard as reaching simultaneous consensus.
Year
DOI
Venue
2011
10.1145/1993806.1993849
PODC
Keywords
Field
DocType
worst-case optimal solution,worst-case optimal decision protocol,classical simultaneous consensus task,nonfaulty process,simultaneous consensus,decision task,all-case optimal solution,simultaneous task,simultaneous decision task,worst-case lower bound,all-case optimal simultaneous decision,worst-case optimal protocol,consensus,common knowledge,message passing,topology,lower bound
Optimal decision,Computer science,Upper and lower bounds,Common knowledge,Theoretical computer science,Adversary,Adversarial system,Distributed computing
Conference
Citations 
PageRank 
References 
4
0.44
20
Authors
3
Name
Order
Citations
PageRank
Maurice Herlihy18623920.94
Yoram Moses22120417.71
Mark R. Tuttle31060135.70