Show simple item record

dc.contributor.authorBazzi, Rida Adnanen_US
dc.contributor.authorNeiger, Gil
dc.date.accessioned2005-06-17T18:05:26Z
dc.date.available2005-06-17T18:05:26Z
dc.date.issued1993en_US
dc.identifier.urihttp://hdl.handle.net/1853/6789
dc.description.abstractThe 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.en_US
dc.format.extent194226 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCC Technical Report; GIT-CC-93-68en_US
dc.subjectComputational complexity
dc.subjectDistributed systems
dc.subjectFault-tolerant coordination
dc.subjectNP-hard
dc.subjectOptimization
dc.subjectSend/receive omission failures
dc.subjectSynchronous systems
dc.titleThe Complexity of Almost-Optimal Coordinationen_US
dc.typeTechnical Reporteng_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record