We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources...
详细信息
ISBN:
(纸本)9781581138023
We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources or cost for access to a remote replica. We show the existence of pure strategy Nash equilibria and investigate the price of anarchy, which is the relative cost of the lack of coordination. The price of anarchy can be high due to undersupply problems, but with certain network topologies it has better bounds. With a payment scheme the game can always implement the social optimum in the best case by giving servers incentive to replicate.
In this paper, we describe the design of a global infrastructure for monitoring and assertion-checking which is scalable and resilient to network and node failures, leveraging the benefits of distributed hash tables. ...
详细信息
ISBN:
(纸本)9781581138023
In this paper, we describe the design of a global infrastructure for monitoring and assertion-checking which is scalable and resilient to network and node failures, leveraging the benefits of distributed hash tables. Our mechanism distributes the event notification, predicate evaluation, and predicate reporting tasks across the Internet and is orthogonal to the specific monitoring techniques deployed. Our approach creates a hierarchy of event reporting and monitoring relationships, decoupling the event notification task from the monitored node and facilitating decomposition of the predicate evaluation and monitoring task if the semantics of the monitoring approach permits. The proposed infrastructure is designed for a best effort monitoring service, but may be strengthened to support stronger guarantees. The proposed has many desirable properties, including scalability, efficient routing, load balancing and good behavior under flash crowds, resiliency to node failure, including failure of monitored hosts and monitoring end-hosts, loose coupling of the monitored hosts and the monitoring task, and self-organizing behavior.
For an unweighted undirected graph G= (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G'= (V,H), H ⊆ E, is called an (α,β)-spanner of G if for every pair of vertices u, v ∈ V, distG'(u,...
详细信息
ISBN:
(纸本)9781581138023
For an unweighted undirected graph G= (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G'= (V,H), H ⊆ E, is called an (α,β)-spanner of G if for every pair of vertices u, v ∈ V, distG'(u,v) ≤ α • distG'(u,v) + β.It was shown in [20] that for any ε > 0, κ = 1,2, ..., there exists an integer β = β(ε,κ) such that for every n-vertex graph G there exists a (1+ε,β)-spanner G' with O(n1+1/κ) edges. An efficient distributed protocol for constructing (1+ε,β)-spanners was devised in [18]. The running time and the communication complexity of that protocol are O(n1+ρ) and O(|E|nρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β.In this paper we devise a protocol with a drastically improved running time (O(nρ) as opposed to (O(n1+ρ) for constructing (1+ε,β)-spanners. Our protocol has the same communication complexity as the protocol of [18], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [18].We also show that our protocol for constructing (1+ε, β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n1+1/κ • log n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1 + ε) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(nρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [21] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n1+1/κ) time for processing each edge of the input graph. However, the algorithm of [21] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space.
暂无评论