Abstract | ||
---|---|---|
The general omissions failure model, in which a faulty process may omit both to send and to receive messages is inherently more complex than the more popular sending omissions model. This fact is exemplified in tasks involving simultaneous decisions, such as the simultaneous consensus (SC) problem. While efficient polynomial protocols for SC that are optimal in all runs are known for the sending omissions model, they do not exists for general omissions. It has been shown that such a protocol must perform at least NP-hard computations (in the number of processes n) between rounds. In fact, the best previously known SC protocol that is optimal in all runs in this model performs PSPACE (in n) computations between rounds. The current paper closes this twenty-year old gap by presenting such an optimal SC protocol that performs PNP computations (polynomial-time computations using an oracle for NP; in fact, a constant number of accesses to the oracle are needed per round.) The result is based on a new characterization of common knowledge in the general omissions failure model. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-04355-0_45 | DISC |
Keywords | Field | DocType |
optimum simultaneous consensus,np oracle,general omissions failure model,simultaneous consensus,constant number,efficient polynomial protocol,optimal sc protocol,sc protocol,omissions model,general omission,processes n,simultaneous decision,polynomial time,common knowledge | Polynomial,Computer science,Oracle,Real-time computing,Common knowledge,PSPACE,Distributed computing,Computation | Conference |
Volume | ISSN | ISBN |
5805 | 0302-9743 | 3-642-04354-2 |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoram Moses | 1 | 2120 | 417.71 |