Caching GameContentsMotivationGame TheoryCaching ModelSelfish CachingCost ModelSelfish Caching (Single Object)Socially Optimal CachingMajor QuestionsMajor ResultsExistence of Nash EquilibriumPrice of Anarchy – Basic ResultsInefficiency of a Nash EquilibriumSpecial Network TopologySlide 16Simulation MethodologyVarying Placement CostVarying Demand DistributionDifferent Physical TopologyVarying Read-write RatioQuestions?Slide 23ExtensionsOngoing and future workRelated Work1Caching GameDec. 9, 2003Byung-Gon Chun, Marco Barreno2Contents•Motivation•Game Theory•Problem Formulation•Theoretical Results•Simulation Results•Extensions3MotivationServerServerServerServerWide-area file systems, web caches, p2p caches, distributed computation4Game Theory•Game–Players–Strategies S = (S1, S2, …, SN)–Preference relation of S represented by a payoff function (or a cost function)•Nash equilibrium –Meets one deviation property–Pure strategy and mixed strategy equilibrium•Quantification of the lack of coordination–Price of anarchy : C(WNE)/C(SO) –Optimistic price of anarchy : C(BNE)/C(SO)5Caching Model•n nodes (servers) (N)•m objects (M)•distance matrix that models a underlying network (D)•demand matrix (W)•placement cost matrix (P)•(uncapacitated)6Selfish Caching•N: the set of nodes, M: the set of objects•Si: the set of objects player i places S = (S1, S2, …, Sn)•Ci: the cost of node i7Cost Model•Separability for uncapacitated version–we can look at individual object placement separately–Nash equilibria of the game is the crossproduct of nash equilibria of single object caching game.•8Selfish Caching (Single Object)•Si : 1, when replicating the object 0, otherwise•Cost of node i9Socially Optimal Caching•Optimization of a mini-sum facility location problem•Solution: configuration that minimizes the total cost •Integer programming – NP-hard)(1scnii10Major Questions•Does a pure strategy Nash equilibrium exist?•What is the price of anarchy in general or under special distance constraints?•What is the price of anarchy under different demand distribution, underlying physical topology, and placement cost ?11Major Results•Pure strategy Nash equilibria exist.•The price of anarchy can be bad. It is O(n).–The distribution of distances is important.–Undersupply (freeriding) problem•Constrained distances (unit edge distance)–For CG, PoA = 1. For star, PoA 2.–For line, PoA is O(n1/2 )–For D-dimensional grid, PoA is O(n1-1/(D+1))•Simulation results show phase transitions, for example, when the placement cost exceeds the network diameter.12Existence of Nash Equilibrium•Proof (Sketch)13Price of Anarchy – Basic Results14Inefficiency of a Nash Equilibriumn/2 nodes n/2 nodes-1C(WNE) = + (-1)n/2C(SO) = 2PoA =22/)1( n15Special Network Topology•For CG, PoA = 1•For star, PoA 216Special Network Topology•For line, PoA = O(n1/2)17Simulation Methodology•Game simulations to compute Nash equilibria•Integer programming to compute social optima•Underlying topology – transit-stub (1000 physical nodes), power-law (1000 physical nodes), random graph, line, and tree•Demand distribution – Bernoulli(p)•Different placement cost and read-write ratio•Different number of servers•Metrics – PoA, Latency, Number of replicas18Varying Placement Cost(Line topology, n = 10)19Varying Demand Distribution(Transit-stub topology, n = 20)20Different Physical Topology(Power-law topology (Barabasi-Albert model), n = 20)21Varying Read-write Ratio(Transit-stub topology, n = 20)Percentage of writes22Questions?23Different Physical Topology(Transit-stub topology, n = 20)24Extensions •Congestion–d’ = d + (#access) PoA /•Payment–Access model–Store model [Kamalika Chaudhuri/Hoeteck Wee]=> Better price of anarchy from cost sharing?25Ongoing and future work•Theoretical analysis under–Different distance constraints–Heterogeneous placement cost–Capacitated version–Demand random variables•Large-scale simulations with realistic workload traces26Related Work•Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions [Vetta 02]•Cooperative Facility Location Games [Goemans/Skutella 00]•Strategyproof Cost-sharing Mechanisms for Set Cover and Facility Location Games [Devanur/Mihail/Vazirani 03]•Strategy Proof Mechanisms via Primal-dual Algorithms [Pal/Tardos
View Full Document
Unlocking...