An Improved Incentive Ratio of the Resource Sharing on Cycles
- PDF / 1,727,387 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 203 Views
An Improved Incentive Ratio of the Resource Sharing on Cycles Yu-Kun Cheng1 · Zi-Xin Zhou2 Received: 7 October 2018 / Revised: 8 December 2018 / Accepted: 21 February 2019 / Published online: 21 March 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract Consider a resource sharing system in peer-to-peer (P2P) networks where peers act as both suppliers and customers of resources. Each participant obtains the utility by exchanging its resources with its neighbors according to the preset rules. A series of recent work considered a market equilibrium mechanism and studied the robustness of such a protocol against the Sybil attack strategy, which is a kind of grave threat in P2P system. The concept of incentive ratio is applied to measure how much a participant could gain from the Sybil attack by splitting its identity and reconstructing its communication connections with others. Although Chen et al. (Incentive ratios of a proportional sharing mechanism in resource sharing. In: 23rd Annual International Computing and Combinatorics Conference, 2017) proved the incentive ratio on cycle networks is bounded by 2 and 4, an open problem is left that is how to narrow the gap furthermore. In this paper, we improve the upper bound of incentive ratio on cycle networks to 3. This improvement comes from a better understanding of the market equilibrium mechanism and a novel analysis technique for the improvement in utility. Keywords Game theory · Resource sharing · Market equilibrium mechanism · Incentive ratio · Sybil attack
This paper is dedicated to Professor Ding-Zhu Du in celebration of his 70th birthday. This research was supported by the National Natural Science Foundation of China (Nos. 11871366 and 61803279).
B
Yu-Kun Cheng [email protected] Zi-Xin Zhou [email protected]
1
Suzhou Key Laboratory for Big Data and Information Service, School of Business, Suzhou University of Science and Technology, Suzhou 215009, Jiangsu, China
2
Department of Computer Science and Technology, Peking University, Beijing 100871, China
123
410
Y.-K. Cheng, Z.-X. Zhou
Mathematics Subject Classification 90B10
1 Introduction The rapid growth of wireless and mobile Internet has facilitated resource sharing among peer-to-peer (P2P) network participants (or agents) who may act both as suppliers and customers of resources (such as processing power, disk storage, communication resource or network bandwidth). To motivate sharing, [1] pioneered the use of incentive techniques to drive cooperation and to promote voluntary contributions by participating agents. System designers develop preset rules [2] for their resources to be made available to others fairly. Generally, the underlying network is modeled as an undirected graph G in which each vertex v represents an agent and the weight wv denotes the amount of the divisible resources of agent v for sharing. The utility Uv considered is the sum of resources obtained from all of
Data Loading...
