We present a novel framework, called balanced overlay networks (BON), that provides scalable, decentralized load balancing for distributed computing using large-scale pools of heterogeneous computers. Fundamentally, B...
详细信息
We present a novel framework, called balanced overlay networks (BON), that provides scalable, decentralized load balancing for distributed computing using large-scale pools of heterogeneous computers. Fundamentally, BON encodes the information about each node's available computational resources in the structure of the links connecting the nodes in the network. This distributed encoding is self-organized, with each node managing its in-degree and local connectivity via random-walk sampling. Assignment of incoming jobs to nodes with the most free resources is also accomplished by sampling the nodes via short random walks. Extensive simulations show that the resulting highly dynamic and self-organized graph structure can efficiently balance computational load throughout large-scale networks. These simulations cover a wide spectrum of cases, including significant heterogeneity in available computing resources and high burstiness in incoming load. Prior analytical results show BON's scalability for truly large-scale networks;under certain ideal conditions, the network structure converges to Erdos-Renyi (ER) random graphs. Our simulation results, however, show that the algorithm does much better, and the structures seem to approach the ideal case of d-regular random graphs. We also make a connection between highly-loaded BONs and the well-known ball-bin randomized load balancing framework.
Many robust control problems can be formulated in abstract form as convex feasibility programs, where one seeks a solution x that satisfies a set of inequalities of the form F = {f(x, delta) <= 0, delta is an eleme...
详细信息
Many robust control problems can be formulated in abstract form as convex feasibility programs, where one seeks a solution x that satisfies a set of inequalities of the form F = {f(x, delta) <= 0, delta is an element of D}. This set typically contains an infinite and uncountable number of inequalities, and it has been proved that the related robust feasibility problem is numerically hard to solve in general. In this paper, we discuss a family of cutting plane methods that solve efficiently a probabilistically relaxed version of the problem. Specifically, under suitable hypotheses, we show that an Analytic Center Cutting Plane scheme based on a probabilistic oracle returns in a finite and prespecified number of iterations a solution x which is feasible for most of the members of F, except possibly for a subset having arbitrarily small probability measure. (c) 2007 Elsevier Ltd. All rights reserved.
We give a randomized algorithm (the "Wedge Algorithm") of competitiveness 3/2H(k) - 1/2k for any metrical task system on a uniform space of k points, for any k >= 2, where H-k = Sigma(k)(i=1) 1/i, the kth...
详细信息
We give a randomized algorithm (the "Wedge Algorithm") of competitiveness 3/2H(k) - 1/2k for any metrical task system on a uniform space of k points, for any k >= 2, where H-k = Sigma(k)(i=1) 1/i, the kth harmonic number. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 10(8). The algorithm is better by a factor of 2 if k < 47. (c) 2007 Elsevier B.V. All rights reserved.
We study epidemic schemes in the context of collaborative data delivery. In this context, multiple chunks of data reside at different nodes, and the challenge is to simultaneously deliver all chunks to all nodes. Here...
详细信息
We study epidemic schemes in the context of collaborative data delivery. In this context, multiple chunks of data reside at different nodes, and the challenge is to simultaneously deliver all chunks to all nodes. Here we explore the inter-operation between the gossip of multiple, simultaneous message-chunks. In this setting, interacting nodes must select which chunk, among many, to exchange in every communication round. We provide an efficient solution that possesses the inherent robustness and scalability of gossip. Our approach maintains the simplicity of gossip, and has low message, connections and computation overhead. Because our approach differs from solutions proposed by network coding, we are able to provide insight into the tradeoffs and analysis of the problem of collaborative content distribution. We formally analyze the performance of the algorithm, demonstrating its efficiency with high probability. (c) 2007 Elsevier Inc. All rights reserved.
We study a particular aspect of the balanced allocation paradigm (also known as the "two-choices paradigm"): constant sized bins. packed as tightly as possible. Let d >= 1 be fixed, and assume there are m...
详细信息
We study a particular aspect of the balanced allocation paradigm (also known as the "two-choices paradigm"): constant sized bins. packed as tightly as possible. Let d >= 1 be fixed, and assume there are m bins of capacity at each. To each of it <= dm balls two possible bins are assigned at random. How close can dm/n = 1 + E epsilon be to 1 so that with high probability each ball can be put into one of the two bins assigned to it without any bin overflowing? We show that epsilon > (21e)d(-1) is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for epsilon > beta(d), for some constant beta < 1. An alternative way to describe the problem is in data structure language. Generalizing cuckoo hashing [R. Pagh, F.F. Rodler, Cuckoo hashing, J. algorithms 51 (2004) 122-144], we consider a hash table with in positions, each representing a bucket of capacity d >= 1. Keys are assigned to buckets by two fully random hash functions. How many keys can be placed in these bins, if key x may go to bin h(1) (x) or to bin h(2) (x)? We obtain an implementation of a dictionary that accommodates it keys in in = (1 + epsilon)n/d buckets of size d = O (log(1/epsilon)), so that key x resides in bucket h(1) (x) or h(2) (x). For a lookup operation, only two hash functions have to be evaluated and two segments of d contiguous memory cells have to be inspected. If d >= 1 + 3.26 center dot ln(1/epsilon), a static arrangement exists with high probability. If d >= 16 center dot ln(1/epsilon), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/epsilon) (O(log log(1/epsilon))). (C) 2007 Elsevier B. V. All rights reserved.
In this Letter, we investigate a special distribution, called eigen-distribution, on random assignments for a class of game trees T-2(k). There are two cases, where the assignments to leaves are independently distribu...
详细信息
In this Letter, we investigate a special distribution, called eigen-distribution, on random assignments for a class of game trees T-2(k). There are two cases, where the assignments to leaves are independently distributed (ID) and correlated distributed (CD). In the ID case, we prove that the distributional probability p belongs to [root 7-13, root 5-1/2], and rho is a strictly increasing function on rounds 3 2 k epsilon [1, infinity). In the CD case, we propose a reverse assigning technique (RAT) to form two particular sets of assignments, 1-set and 0-set, then show that the E-1-distribution (namely, a particular distribution on the assignments of I-set such that all the deterministic algorithms have the same complexity) is the unique eigen-distribution for T-2(k) in the global distribution. 2 (c) 2007 Elsevier B.V. All rights reserved.
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is 27/35. The other is for undirect...
详细信息
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is 27/35. The other is for undirected graphs and its approximation ratio is 7/8 - o(1). Both algorithms improve on the previous bests.
Bloom filters provide space-efficient storage of sets at the cost of a probability of false positives on membership queries. The size of the filter must be defined a priori based on the number of elements to store and...
详细信息
Bloom filters provide space-efficient storage of sets at the cost of a probability of false positives on membership queries. The size of the filter must be defined a priori based on the number of elements to store and the desired false positive probability, being impossible to store extra elements without increasing the false positive probability. This leads typically to a conservative assumption regarding maximum set size, possibly by orders of magnitude, and a consequent space waste. This paper proposes Scalable Bloom Filters, a variant of Bloom filters that can adapt dynamically to the number of elements stored, while assuring a maximum false positive probability. (c) 2006 Elsevier B.V. All rights reserved.
The d-Dim h-HOPS MST problem is defined as follows: given a set S of points in the d-dimensional Euclidean space and S E S, find a minimum-cost spanning tree for S rooted at s with height at most h. We investigate the...
详细信息
The d-Dim h-HOPS MST problem is defined as follows: given a set S of points in the d-dimensional Euclidean space and S E S, find a minimum-cost spanning tree for S rooted at s with height at most h. We investigate the problem for any constant h and d > 0. We prove the first nontrivial lower bound on the solution cost for almost all Euclidean instances (i.e. the lower bound holds with high probability). Then we introduce an easy-to-implement, fast divide et impera heuristic and we prove that its solution cost matches the lower bound. (C) 2007 Elsevier B.V. All rights reserved.
Solovay [R.M. Solovay, On random R.E. sets, in: A.I. Arruda, N.C.A. da Costa, R. Chaqui (Eds.), Non-Classical Logics, Model Theory and Computability, North-Holland, Amsterdam, 1977, pp. 283-307] has proved that the mi...
详细信息
Solovay [R.M. Solovay, On random R.E. sets, in: A.I. Arruda, N.C.A. da Costa, R. Chaqui (Eds.), Non-Classical Logics, Model Theory and Computability, North-Holland, Amsterdam, 1977, pp. 283-307] has proved that the minimal length of a program enumerating a set A is upper bounded by 3 times the negative logarithm of the probability that a random program will enumerate A. It is unknown whether one can replace the constant 3 by a smaller constant. In this paper, we show that the constant 3 can be replaced by the constant 2 for finite sets A. (c) 2007 Elsevier B.V. All rights reserved.
暂无评论