跳到主要內容

臺灣博碩士論文加值系統

(3.235.227.117) 您好!臺灣時間:2021/08/01 23:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳友冠
研究生(外文):You-Guan Wu
論文名稱:有容量限制之資料儲存賽局的自主行為代價
論文名稱(外文):Price of Anarchy in Capacitated Selfish Replication Game
指導教授:陳和麟
指導教授(外文):Ho-Lin Chen
口試委員:呂學一魏宏宇于天立
口試委員(外文):Hsueh-I LuHung-Yu WeiTian-Li Yu
口試日期:2015-06-19
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:44
中文關鍵詞:賽局理論演算法機制設計大型系統設計計算機結構計算機網路
外文關鍵詞:Game TheoryAlgorithmMechanism DesignLarge-Scale SystemsComputer ArchitectureComputer Network
相關次數:
  • 被引用被引用:0
  • 點閱點閱:617
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
目前對等網路是分散式架構中最熱門的模型之一,這種模型不使用中心伺服器去進行管理,每個端點同時都是用戶端和伺服器端,而對等網路最常被用來共享資源或檔案。通常每一個端點都是終端使用者,這些使用者自己有能力去決定要不要分享自己的資源或檔案給其他使用者。當一個終端使用者需要檔案時,使用者可以選擇將這個檔案儲存在自己的計算機上,也可以透過對等網路到其他使用者的計算機上存取而不儲存在自己的計算機上。如何分配對等網路上每位終端使用者是否要儲存檔案將會嚴重影響到整個對等網路的效能。由於每位終端使用者都試圖最佳化自己的利益,而我們無法強制使用者儲存或不儲存檔案,因此,要對整體的對等網路做最佳化控管是很難的問題。在賽局演算法中,有兩種用來評估因為自私策略而導致系統效能下降的指標,分別是PoA和OPoA。我們使用PoA和OPoA去評估系統的效能,並且設計一套機制去改善整體對等網路的效能。

我們考慮每個端點都有儲存容量的限制,並且提出2-CSR game和2-CSRP game。我們首先提出FPNE演算法,這個演算法可以找到一組穩定的解,同時我們證明在2-CSR game中,永遠存在一組穩定的解。接著,我們使用PoA和OPoA去評估因為自私行為而影響的整體系統效能。我們發現在2-CSR game中,PoA和OPoA都不是很好,因此我們提出2-CSRP game,我們可以利用2-CSRP game去改善OPoA。

The peer-to-peer (P2P) model is one of the most popular a decentralized architecture to share resources among others without use the centralized administrative server. Each node is an end-user who has the ability to determine which object to provide to other end-users. To cache object or not, that is the question. The assignment on whether each node should cache object or not can impact the performance of the network. All end-users tries to optimize their own benefit, that is, we can''t control end-user''s strategy (cache or not cache), so, it''s hard to optimize the performance of the P2P file-sharing overlay network due to the selfish strategy.


We consider that the limit storage to servers and propose the 2-CSR game and the 2-CSRP game. We propose a FPNE algorithm to find a stable solution and prove that the stable solution (Nash equilibrium) always exists in the 2-CSR game. We use the Price of Anarchy (PoA) and the Optimistic Price of Anarchy (OPoA) to measure the system performance which is impacted by the strategy of selfish players. We observe that both the PoA and the OPoA may be inefficient in the 2-CSR game, so we use the payment mechanism to improve the OPoA (we call it the 2-CSRP game).

1 Introduction 1
2 Related Work 5
 2.1 Selfish Caching 5
 2.2 Capacitated Storage 6
 2.3 Price of Anarchy (PoA)  6
 2.4 Optimistic Price of Anarchy (OPoA) 7
 2.5 Our Results 8
 2.6 Comparison with previous works 9
3 Model 11
 3.1 2-CSR game 11
  3.1.1 Player Strategy 12
  3.1.2 Player Costs 12
  3.1.3 Pure-strategy Nash equilibrium 12
  3.1.4 Inefficiency of a Nash equilibrium 14
 3.2 2-CSRP game 17
  3.2.1 Strategy 17
  3.2.2 Player Costs 19
4 Main Results 20
 4.1 2-CSR game 20
  4.1.1 Find a Pure Nash equilibrium 20
  4.1.2 Time Complexity 27
  4.1.3 Nash equilibrium always exist 27
  4.1.4 A sufficient condition for PoA=OPoA=1 30
 4.2 2-CSRP game 31
  4.2.1 Bid strategy 31
  4.2.2 Threshold strategy 34
  4.2.3 Nash equilibrium 34
  4.2.4 Summary 35
  4.2.5 Example of 2-CSRP game 37
  4.2.6 An example network with OPoA greater than one 39
Bibliography 41

[1] Byung-Gon Chun, Kamalika Chaudhuri, Hoeteck Wee, Marco Barreno, Christos H. Papadimitriou, and John Kubiatowicz, Selfish Caching in Distributed Systems: A Game-Theoretic Analysis, In PODC, pages 21-30, July 2004

[2] Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi,
C. Pandu Rangan, Rajmohan Rajaraman, and Ravi Sundaram, Cache Me If You Can: Capacitated Selfish Replication Games, In LATIN, pages 420-432, April 2012

[3] Edsger Wybe Dijkstra, A note on two problems in connexion with graphs, In Numerische Mathematik, Volume: 1, pages 269-271, 1959

[4] Robert Clay Prim, Shortest connection networks and some generalizations, In Bell System Technical Journal, pages 1389-1401, 1957

[5] John von Neumann, and Oskar Morgenstern, Theory of games and economic behavior, In Princeton University Press, pages 498-504, 1944

[6] Pradeep Dubey, Inefficiency of Nash Equilibria, In INFORMS, pages 1-8, 1986

[7] Yutian Chen, Data caching in ad hoc networks using game-theoretic analysis, In IEEE International Conference on Sensor Networks, pages 43-49, 2010

[8] Masahiro Sasabe, Naoki Wakamiya, Masayuki Murata, A Caching Algorithm using Evolutionary Game Theory in a File-Sharing System, In IEEE Computers and Communications, pages 631-636, July 2007

[9] Tim Roughgarden, Eva Tardos, How bad is selfish routing, In Journal of the ACM (JACM), pages 236-259, March 2002

[10] Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, Tom Wexler, Near-optimal Network Design with Selfish Agents, In Proc. of ACM STOC, pages 511-520, 2003

[11] Krishna P. Gummadi, Richard J. Dunn, Stefan Saroiu, Steven D. Gribble, Henry M. Levy, John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, In Proceeding SOSP ''03, pages 314-329, 2003

[12] Antony Rowstron, Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, In Proceeding SOSP ''01, pages 188-201, 2001

[13] Stefan Saroiu, P. Krishna Gummadi, Steven D. Gribble, A Measurement Study of Peer-to-Peer File Sharing Systems, In Proc. SPIE 4673, pages 156-170, 2002

[14] Sharrukh Zaman, Daniel Grosu, A Distributed Algorithm for the Replica Placement Problem, In IEEE Transactions on Parallel and Distributed Systems, pages 1455-1468, September 2011

[15] Jae-Ho Choi, Kyu-Sun Shim, SangKeun Lee, and Kun-Lung Wu, Handling Selfishness in Replica Allocation over a Mobile Ad Hoc Network, In IEEE Transactions on Mobile Computing, pages 278-291, February 2012

[16] Samee Ullah Khan, Ishfaq Ahmad, A Pure Nash Equilibrium-Based Game Theoretical Method for Data Replication across Multiple Servers, In IEEE Transactions on Knowledge and Data Engineering, pages 537-553, April 2009

[17] Nikolaos Laoutaris, Georgios Smaragdakis, Azer Bestavros, Ibrahim Matta, Distributed Selfish Caching, In IEEE Transactions on Parallel and Distributed Systems, pages 1361-1376, October 2007

[18] Mahmoud Taghizadeh, Charles Ofria, Eric Torng, and Subir Biswas, Distributed Cooperative Caching in Social Wireless Networks, In IEEE Transactions on Mobile Computing, pages 1037-1053, June 2013

[19] Minzhe Guo, Prabir Bhattacharya, Mechanism Design Based Secure Data Object Replication, In Trust, Security and Privacy in Computing and Communications, pages 580-587, June 2012

[20] Dilip Kumar,Pravin More, Social Wireless Networks By Distributed Cooperative Caching Policy, In International Engineering Research Journal, pages 118-121, 2015

[21] Liang Wang, Suzan Bayhan, Jussi Kangasharju, Cooperation Policies for Efficient In-Network Caching, In Proceedings of the ACM SIGCOMM, pages 533-534, 2013

[22] John Nash, Non-cooperative games, In Annals of Mathematics, pages 286-295, 1951

[23] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, In SIAM Journal on Computing, pages 1602-1623, 2008

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top