| Title: | The Complexity of Almost-Optimal Coordination |
| Author: | Bazzi, Rida Adnan ; Neiger, Gil |
| Abstract: | The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered the complexity of achieving optimal simultaneous coordination under various failure assumptions. This paper studies the complexity of achieving simultaneous coordination in synchronous systems in the presence of send/receive omission failures. It had been shown earlier that achieving optimal simultaneous coordination in these systems requires NP-hard local computation. In this paper, we study almost-optimal coordination, which requires processors to coordinate within a constant additive or multiplicative number of rounds of the coordination time of an optimal protocol. We show that achieving almost-optimal coordination also requires NP-hard computation. |
| Type: | Technical Report |
| URI: | http://hdl.handle.net/1853/6789 |
| Date: | 1993 |
| Relation: | CC Technical Report; GIT-CC-93-68 |
| Publisher: | Georgia Institute of Technology |
| Subject: |
Computational complexity
Distributed systems Fault-tolerant coordination NP-hard Optimization Send/receive omission failures Synchronous systems |
| Files | Size | Format | View |
|---|---|---|---|
| GIT-CC-93-68.pdf | 189.6Kb |
View/
|
