Given a collection of selfish agents who wish to establish links to route traffic among themselves, the set of equilibrium network topologies may appear quite different from the centrally enforced optimum. We study th...
详细信息
Given a collection of selfish agents who wish to establish links to route traffic among themselves, the set of equilibrium network topologies may appear quite different from the centrally enforced optimum. We study the quality (price of anarchy) of equilibrium networks in a game where links require the consent of both participants and are negotiated bilaterally and compare these networks to those generated by an earlier model due to Fabrikant et al. [6] in which links are formed unilaterally. We provide a characterization of stable and efficient networks in the bilateral network formation game, show that the set of stable networks is richer than those in the unilateral game, and that all stable networks of the unilateral game are also stable in the bilateral game. We also provide an upper and lower bound on the price of anarchy (tight in the size of the network n but not the link cost a) of the bilateral game and show that the worst-case price of anarchy of the bilateral model is worse than for the unilateral model. A careful empirical analysis demonstrates that the average price of anarchy Is better in the bilateral connection game than in the unilateral game for small Link costs but worse as Links become more expensive. In the process, a powerful equivalence between link-based graph stability and two game-theoretic equilibrium notions is also discussed. The equivalence establishes necessary and sufficient conditions for an equilibrium in the bilateral game that helps provide a partial geometric characterization of equilibrium graphs. Copyright 2005 acm.
In this paper we consider the weighted, capacitated vertex cover problem with hard capacities (capVC). Here, we are given an undirected graph G = (V, E), non-negative vertex weights wtv for all vertices v ∈ V, and no...
详细信息
ISBN:
(纸本)9781581139945
In this paper we consider the weighted, capacitated vertex cover problem with hard capacities (capVC). Here, we are given an undirected graph G = (V, E), non-negative vertex weights wtv for all vertices v ∈ V, and node-capacities Bv ≥ 1 for all v ∈ V. A feasible solution to a given capVC instance consists of a vertex cover C ⊆ V. Each edge e ∈ E is assigned to one of its endpoints in C and the number of edges assigned to any vertex v ∈ C is at most Bv. The goal is to minimize the total weight of C. For a parameter Ε > 0 we give a deterministic, distributed algorithm for the capVC problem that computes a vertex cover C of weight at most (2+Ε) · opt where opt is the weight of a minimum-weight feasible solution to the given instance. The number of edges assigned to any node v ∈ C is at most (4 + Ε) · B v. The running time of our algorithm is O(log(nW)/Ε), where n is the number of nodes in the network and W = wtmax/wtmin is the ratio of largest to smallest weight. This result is complemented by a lower-bound saying that any distributed algorithm for capVC which requires a poly-logarithmic number of rounds is bound to violate the capacity constraints by a factor two. The main feature of the algorithm is that it is derived in a systematic fashion starting from a primal-dual sequential algorithm. Copyright 2005 acm.
We present a framework for designing efficient distributed data structures for multi-dimensional data. Our structures, which we call skip-webs, extend and improve previous randomized distributed data structures, inclu...
详细信息
ISBN:
(纸本)9781581139945
We present a framework for designing efficient distributed data structures for multi-dimensional data. Our structures, which we call skip-webs, extend and improve previous randomized distributed data structures, including skipnets and skip graphs. Our framework applies to a general class of data querying scenarios, which include linear (one-dimensional) data, such as sorted sets, as well as multi-dimensional data, such as d-dimensional octrees and digital tries of character strings defined over a fixed alphabet. We show how to perform a query over such a set of n items spread among n hosts using O(log n /log log n) messages for one-dimensional data, or O(log n) messages for fixed-dimensional data, while using only O(log n) space per host. We also show how to make such structures dynamic so as to allow for insertions and deletions in O(log n) messages for quadtrees, octrees, and digital tries, and O(log n/ log log n) messages for one-dimensional data. Finally, we show how to apply a blocking strategy to skip-webs to further improve message complexity for one-dimensional data when hosts can store more data. Copyright 2005 acm.
The full disjunction is a variation of the join operator that maximally combines tuples from connected relations, while preserving all information in the relations. The full disjunction can be seen as a natural extens...
详细信息
ISBN:
(纸本)9781595930620
The full disjunction is a variation of the join operator that maximally combines tuples from connected relations, while preserving all information in the relations. The full disjunction can be seen as a natural extension of the binary outerjoin operator to an arbitrary number of relations and is a useful operator for information integration. This paper presents the algorithm INCREMENTALFD for computing the full disjunction of a set of relations. INCREMENTALFD improves upon previous algorithms for computing the full disjunction in three ways. First, it has a lower total runtime when computing the full result and a lower runtime when computing only k tuples of the result, for any constant k. Second, for a natural class of ranking functions, INCREMENTALFD returns tuples in ranking order. third, INCREMENTALFD can be adapted to have a block-based execution, instead of a tuple-based execution. Copyright 2005 acm.
Group mutual exclusion (GME) was first introduced by Joung in 1998 as a generalization of the n-process mutual exclusion problem, and subsequently modeled as the Congenial Talking Philosophers problem. GME allows proc...
详细信息
ISBN:
(纸本)9781581139945
Group mutual exclusion (GME) was first introduced by Joung in 1998 as a generalization of the n-process mutual exclusion problem, and subsequently modeled as the Congenial Talking Philosophers problem. GME allows processes requesting for the same resource to concurrently access the shared resource. However, a process requesting a resource that is different from the one currently being used will not be able to access the requested resource at the same time. At any time, only one resource may be in *** have been two solutions to the GME problem for a ring network. The first solution proposed by Wu and Joung [2] had an unbounded message size problem, while the second solution proposed by Cantarell et. al. [1] attempted to provide an upper-bound for the message size. However, in doing so, the second solution generated an unbounded number of messages. Hence, in this work we present a GME algorithm for a token-passing network that solves both of the problems found in the two previous solutions by providing an upper bound both to the number of messages and to message size.
Given a collection of selfish agents who wish to establish links to route traffic among themselves, the set of equilibrium network topologies may appear quite different from the centrally enforced optimum. We study th...
详细信息
ISBN:
(纸本)9781581139945
Given a collection of selfish agents who wish to establish links to route traffic among themselves, the set of equilibrium network topologies may appear quite different from the centrally enforced optimum. We study the quality (price of anarchy) of equilibrium networks in a game where links require the consent of both participants and are negotiated bilaterally and compare these networks to those generated by an earlier model due to Fabrikant et al. [6] in which links are formed unilaterally. We provide a characterization of stable and efficient networks in the bilateral network formation game, show that the set of stable networks is richer than those in the unilateral game, and that all stable networks of the unilateral game are also stable in the bilateral game. We also provide an upper and lower bound on the price of anarchy (tight in the size of the network n but not the link cost α) of the bilateral game and show that the worst-case price of anarchy of the bilateral model is worse than for the unilateral model. A careful empirical analysis demonstrates that the average price of anarchy is better in the bilateral connection game than in the unilateral game for small link costs but worse as links become more expensive. In the process, a powerful equivalence between link-based graph stability and two game-theoretic equilibrium notions is also discussed. The equivalence establishes necessary and sufficient conditions for an equilibrium in the bilateral game that helps provide a partial geometric characterization of equilibrium graphs.
The proceedings contains 53 papers from the twenty-second annualacmsymposium on principles of distributedcomputing, PODC 2003. The topics discussed include: simple and fast optimistic protocols for fair electronic ...
详细信息
The proceedings contains 53 papers from the twenty-second annualacmsymposium on principles of distributedcomputing, PODC 2003. The topics discussed include: simple and fast optimistic protocols for fair electronic exchange;distributed error confinement;broadcasting in undirected ad hoc radio networks;scalable and dynamic quorum systems;routing networks for distributed hash tables;asynchronous resource discovery;and scalable public key tracing and revoking.
The proceedings contain 39 papers from the proceedings of the 23rd annualacmsymposium on principles of distributedcomputing. The topics discussed include: completely fair SFE and coalition-safe cheap talk;mechanism...
详细信息
The proceedings contain 39 papers from the proceedings of the 23rd annualacmsymposium on principles of distributedcomputing. The topics discussed include: completely fair SFE and coalition-safe cheap talk;mechanism design for policy routing;selfish caching in distributed systems: a game-theoretic analysis;bringing practical lock-free synchronization to 64-bit applications;an almost non-blocking stack and lock-free linked lists and skip lists.
暂无评论