2018/01/11 by Ishan Tyagi, Heidarzadeh, Anoosheh, Tyagi, Ishan +4
Computer Science · #Blockchain Technology Applications and Security #Cooperative Communication and Network Coding #Distributed systems and fault tolerance #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1801.03865
openalex publication_date 2018/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
In this research, we address the stability issues in Cooperative Data Exchange (CDE),\none of the central problems in wireless network coding. We consider a setting in which the\nusers are selfish, i.e., would like to maximize their own utility. More specifically, we\nconsider a setting where each user has a subset of packets in the ground set X, and wants\nall other packets in X. The users can exchange data by broadcasting coded or uncoded\npackets over a lossless channel, and monetary transactions are allowed between any pair\nof users. We define the utility of each user as the sum of two sub-utility functions: (i)\nthe difference between the total payment received by the user and the total transmission\nrate of the user, and (ii) the difference between the total number of required packets by\nthe user and the total payment made by the user. A rate-vector and payment-matrix\npair (r, p) is said to stabilize the grand coalition (i.e., the set of all users) if (r, p) is Paretooptimal\nover all minor coalitions (i.e., all proper subsets of users who collectively know\nall packets in X). Our goal is to design algorithms that compute a stabilizing ratepayment\npair with minimum total sum-rate and minimum total sum-payment for any\ngiven instance of the problem. In this work, we propose two algorithms that maximize the\nsum of utility of all users (over all solutions), and one of the algorithms also maximizes\nthe minimum utility among all users (over all solutions). The second algorithm requires a\nbroker, where each user has to trust the broker and use the broker to exchange payments,\nwhereas in the first algorithm there is no such requirement. In the first algorithm, the users\ndirectly compensate user broadcasting the packet in that particular round. Our scheme\nminimizes the total number of transmitted packets, as well as the total amount of\npayments. We also perform an extensive simulation study to evaluate the performance of\nour scheme in practical setting.