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.
This paper presents a new algorithm to answer top-k queries (e.g. "find the k objects with the highest aggregate values") in a distributed network. Existing algorithms such as the Threshold Algorithm [10] co...
详细信息
ISBN:
(纸本)9781581138023
This paper presents a new algorithm to answer top-k queries (e.g. "find the k objects with the highest aggregate values") in a distributed network. Existing algorithms such as the Threshold Algorithm [10] consume an excessive amount of bandwidth when the number of nodes, m, is high. We propose a new algorithm called "Three-Phase Uniform Threshold" (TPUT). TPUT reduces network bandwidth consumption by pruning away ineligible objects, and terminates in three round-trips regardless of data input. The paper presents two sets of results about TPUT. First, trace-driven simulations show that, depending on the size of the network, TPUT reduces network traffic by one to two orders of magnitude compared to existing algorithms. second, TPUT is proven to be instance-optimal on common data series. In particular, analysis shows that by using a pruning parameter α
A snapshot is an important object in distributedcomputing whose implementation in asynchronous systems has been studied extensively. It consists of a collection of m > 1 components, each storing a value, and suppo...
详细信息
ISBN:
(纸本)9781581138023
A snapshot is an important object in distributedcomputing whose implementation in asynchronous systems has been studied extensively. It consists of a collection of m > 1 components, each storing a value, and supports two atomic operations: an UPDATE of a specified component's value and a SCAN of all components to determine their values at some point in time. In this paper, we investigate implementations of a multiwriter snapshot object in a synchronous shared memory model. In this setting, we show that a snapshot object can be efficiently implemented and prove a tight tradeoff between the complexity of the SCAN and the UPDATE operations. First, we describe a wait-free implementation that performs UPDATE in O(1) time and SCAN in O(m) time, using only slightly more than twice the amount of space needed to simply store the m values. We also describe a variant that performs UPDATE in O(1) time and SCAN in O(n) time. second, we describe a wait-free implementation that performs UPDATE in O(log m) time and SCAN in O(1) time, and a variant that performs UPDATE in O(log n) time and SCAN in O(1) time. Third, we show how to combine these implementations to realize two implementations that perform UPDATE in θ(log(m/c)) time and SCAN in θ(c) time, for 1 ≤ c ≤ m, or perform UPDATE in θ(log(n/c)) time and SCAN in Θ(c) time, for 1 ≤ c ≤ n. This implies that Time[UPDATE] Ε O( log(min{m, n}/Time[SCAN]) ). We also prove that Time[UPDATE] Ε Ω (log (min {m, n]/Time[SCAN])), which matches our upper bound.
暂无评论