On the Complexity of Variants of Cooperative Peer-to- peer Repair

Cheung, Gene ; Li, Danjue ; Chuah, Chen-Nee

HP Development Company

关键词: multimedia;    wireless networks;    complexity;   

RP-ID  :  HPL-2006-90

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

The well-known NAK implosion problem for wireless broadcast can be addressed by leveraging cooperative peer-to-peer connectivity to repair corrupted data. This paper studies the Cooperative Peer-to-peer Repair (CPR) framework for multimedia broadcast. We show that CPR can be formulated as an optimization problem that minimizes the number of iterations it takes to wirelessly disseminate a desired message from peers 'with' the content to peers 'without' it. Complicating the problem are transmission conflicts, where pre- specified sets of links cannot simultaneously transmit due to interference. In this paper, we formalize CPR as a discrete optimization problem, and prove that CPR and its many variants are NP-hard. Notes: 4 Pages