检索结果-内蒙古大学图书馆

2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

作者： Bramson, Maury Lu, Yi Prabhakar, Balaji Univ Minnesota Sch Math Minneapolis MN 55455 USA

ISBN: (纸本)9781450302111

randomized load balancing greatly improves the sharing of resources in a number of applications while being simple to implement. One model that has been extensively used to study randomized load balancing schemes is the supermarket model. In this model, jobs arrive according to a rate-n lambda Poisson process at a bank of n rate-1 exponential server queues. A notable result, due to Vvedenskaya ***. (1996), showed that when each arriving job is assigned to the shortest of d >= 2 randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as n -> infinity. This is a substantial improvement over the case d = 1, where queue sizes decay exponentially. The method of analysis used in the above paper and in the subsequent literature applies to jobs with exponential service time distributions and does not easily generalize. It is desirable to study load balancing models with more general, especially heavy-tailed, service time distributions since such service times occur widely in practice. This paper describes a modularized program for treating randomized load balancing problems with general service time distributions and service disciplines. The program relies on an ansatz which asserts that any finite set of queues in a randomized load balancing scheme becomes independent as n ->infinity. This allows one to derive queue size distributions and other performance measures of interest. We establish the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate (this includes heavy-tailed service times). Assuming the ansatz, we also obtain the following results: (i) as n ->infinity, the process of job arrivals at any fixed queue tends to a Poisson process whose rate depends on the size of the queue, (ii) when the service discipline at each server is processor sharing or LIFO with preemptive resume, the distribution of the number of jobs is insensitive to the service distribution, and (iii) the tail

关键词： Load Balancing randomized algorithms Asymptotic Independence

来源：评论

学校读者我要写书评

暂无评论

Multi-Sided Shared Coins and randomized Set-Agreement 10

Multi-Sided Shared Coins and Randomized Set-Agreement

引用

22nd ACM Symposium on Parallelism in algorithms and Architectures

作者： Hillel, Keren Censor Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781450300797

This paper presents wait-free randomized algorithms for solving set-agreement in asynchronous shared-memory systems under a strong adversary First, the definition of a shared-coin algorithm is generalized to a multi-sided shared-coin algorithm, and it is shown how to use any multi-sided shared coin in order to obtain a randomized set-agreement algorithm for agreeing on k values out of k + 1 Then, an implementation is given for a (k + 1)-sided shared coin for n processes with a constant agreement parameter, O(n(2)/k) total step complexity. and O(n/k) individual step complexity This implementation yields a randomized set-agreement algorithm for agreeing on k values out of k + 1 with a total step complexity of O(n(2)/k + nk) and an individual step complexity of O(n/k + k) Next, other set-agreement algorithms for agreeing on E values out of k + 1, where e is smaller than k, are presented This includes the case of multi-valued consensus in which l = 1, k > 1 To the best of our knowledge, these are the first wait-free algorithms for set-agreement in the asynchronous shared-memory model under a strong adversary that are not for the specific case of binary consensus, where l = k = 1 Finally, an application of asynchronous wait-free multi-valued consensus is presented, in implementing at-most-once semantics with optimal effectiveness.

关键词： distributed computing shared memory randomized algorithms set-agreement multi-valued shared coins

来源：评论

学校读者我要写书评

暂无评论

A new approximation algorithm for the multilevel facility location problem

引用

DISCRETE APPLIED MATHEMATICS 2010年第5期158卷 453-460页

作者： Gabor, Adriana F. van Ommeren, Jan-Kees C. W. Erasmus Univ Inst Econometr NL-3000 DR Rotterdam Netherlands Univ Twente Fac Elect Engn Math & Comp Sci NL-7500 AE Enschede Netherlands

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Facility location Approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

VISION-BASED PURSUIT-EVASION IN A GRID

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第3期24卷 1177-1204页

作者： Dumitrescu, Adrian Kok, Howi Suzuki, Ichiro Zylinski, Pawel Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA Univ Gdansk Inst Informat PL-80952 Gdansk Poland

We revisit the problem of pursuit-evasion in a grid introduced by Sugihara and Suzuki [SIAM J. Discrete Math., 2 (1989), pp. 126-143] in the line-of-sight vision model. Consider an arbitrary evader Z with the maximum speed of 1 who moves (in a continuous way) on the streets and avenues of an n x n grid G(n). The cunning evader is to be captured by a group of pursuers, possibly only one. The maximum speed of the pursuers is s >= 1;s is a constant for each pursuit-evasion problem considered, but several values for s are studied. We prove several new results (no such algorithms were available for capture using one, two, or three pursuers having a constant maximum speed limit): (i) A randomized algorithm through which one pursuer A with a maximum speed of s >= 3 can capture an arbitrary evader Z in G(n) in expected polynomial time. For instance, the expected capture time is O(n(1+log6/5 16)) = O(n(16.21)) for s = 3, O(n(1+log 12)) = O(n(4.59)) for s = 4, O(n(1+log60/13)) = O(n(3.21)) for s = 6, and it approaches O(n(3)) with the further increase of s. (ii) A randomized algorithm for capturing an arbitrary evader in O(n(3)) expected time using two pursuers who can move slightly faster than the evader (s = 1 + epsilon for any epsilon > 0). (iii) randomized algorithms for capturing a certain "passive" evader using either a single pursuer who can move slightly faster than the evader (s = 1 + epsilon for any epsilon > 0) or two pursuers having the same maximum speed as the evader (s = 1). (iv) A deterministic algorithm for capturing an arbitrary evader in O(n(2)) time, using three pursuers having the same maximum speed as the evader (s - 1).

关键词： pursuit-evasion game line-of-sight vision model grids randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

The cost of probabilistic agreement in oblivious robot networks

引用

INFORMATION PROCESSING LETTERS 2010年第11期110卷 431-438页

作者： Clement, Julien Defago, Xavier Potop-Butucaru, Maria Gradinariu Izumi, Taisuke Messika, Stephane Univ Paris 11 LRI CNRS UMR 8623 Rech Informat Lab F-91405 Orsay France Univ Paris 06 CNRS UMR LIP6 7606 F-75016 Paris France JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan Nagoya Inst Technol Aichi 4668555 Japan

In this paper, we look at the time complexity of two agreement problems in networks of oblivious mobile robots, namely, at the gathering and scattering problems. Given a set of robots with arbitrary initial locations and no initial agreement on a global coordinate system, gathering requires that all robots reach the exact same but not predetermined location. In contrast, scattering requires that no two robots share the same location. These two abstractions are fundamental coordination problems in cooperative mobile robotics. Oblivious solutions are appealing for self-stabilization since they are self-stabilizing at no extra cost. As neither gathering nor scattering can be solved deterministically under arbitrary schedulers, probabilistic solutions have been proposed recently. The contribution of this paper is twofold. First, we propose a detailed time complexity analysis of a modified probabilistic gathering algorithm. Using Markov chains tools and additional assumptions on the environment, we prove that the convergence time of gathering can be reduced from O(n(2)) (the best known bound) to O(1) or O(log n . log(logn)), depending on the model of multiplicity detection. Second, using the same technique, we prove that scattering can also be achieved in fault-free systems with the same bounds. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Distributed systems Analysis of algorithms randomized algorithms Distributed computing Design of algorithms

来源：评论

学校读者我要写书评

暂无评论

A Simple and Scalable Algorithm for Alignment in Broadcast Networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2010年第7期28卷 1190-1199页

作者： Pagliari, Roberto Yildiz, Mehmet E. Kirti, Shrut Morgansen, Kristi A. Javidi, Tara Scaglione, Anna Cornell Univ Dept Elect & Comp Engn Ithaca NY 14853 USA Univ Washington Dept Aeronaut & Astronaut Seattle WA 98195 USA Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA

We consider the problem of coordinating a group of mobile nodes communicating through a wireless medium. The objective of the network is the alignment of all the nodes towards a common direction through local interactions, without the need for global knowledge such as the network topology or the maximum degree of the network, or even local parameters, such as the number of neighbors. The key feature of our algorithm is that each node state update is done through voting, where the probability of each vote is biased by the state of the node neighbors. We propose two possible physical implementations for our algorithm. The first is based on the explicit exchange of packetized messages, while the second is a cross-layer approach. Our analysis unveils key convergence properties of this simple class of alignment algorithms, via analytical and simulated results.

关键词： Wireless Sensor Networks Alignment Low-Complexity randomized algorithms Consensus

来源：评论

学校读者我要写书评

暂无评论

Stochastic ellipsoid methods for robust control: Multiple updates and multiple cuts

引用

AUTOMATICA 2010年第8期46卷 1339-1345页

作者： Wada, Takayuki Fujisaki, Yasumasa Kobe Univ Dept Syst Sci Grad Sch Syst Informat Nada Ku Kobe Hyogo 6578501 Japan

Efficient randomized algorithms are developed for solving robust feasibility problems with multiple parameter-dependent convex constraints. Two complementary strategies are presented, both of which exploit the multiplicity to achieve fast convergence. One is the stochastic ellipsoid method with multiple updates. In each iteration of this algorithm, an ellipsoid which describes a candidate of the solution set is updated many times via the multiple constraints with one random sample, while at most one update is allowed in the original method. The other is the stochastic ellipsoid method with multiple cuts. Here, a new update rule is presented to construct a smaller ellipsoid directly via multiple subgradients given by the constraints. A quantitative analysis of the volume of the ellipsoid is also provided, which guarantees the advantage of the proposed algorithm over the original one. The above features lead to a reduction of the total number of random samples necessary for convergence, which is extensively demonstrated through numerical examples. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Robust control randomized algorithms Stochastic ellipsoid methods Robust feasibility problems Parameter-dependent linear matrix inequalities Probabilistic robustness

来源：评论

学校读者我要写书评

暂无评论

Combining shared-coin algorithms

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2010年第3期70卷 317-322页

作者： Aspnes, James Attiya, Hagit Censor, Keren Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Yale Univ Dept Comp Sci New Haven CT 06520 USA

This paper shows that shared-coin algorithms can be combined to optimize several complexity measures, even in the presence of a strong adversary. By combining shared coins of Bracha and Rachman (1991) [10] and of Aspnes and Waarts (1996) [7], this yields a shared-coin algorithm, and hence, a randomized consensus algorithm, with O(n log(2) n) individual work and O(n(2) log n) total work, using single-writer registers. This improves upon each of the above shared coins (where the former has a high cost for individual work, while the latter reduces it but pays in the total work), and is currently the best for this model. Another application is to prove a construction of Saks, Shavit, and Woll (1991) [16], which combines a shared-coin algorithm that takes O(1) time in failure-free executions, with one that takes O(log n) time in executions where at most root n processes fail, and another one that takes O(n(3)/n-f) time in any other execution. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Distributed computing Shared memory randomized algorithms Consensus Shared coins

来源：评论

学校读者我要写书评

暂无评论

EFFECTIVE COMPUTATIONS ON SLIDING WINDOWS

引用

SIAM JOURNAL ON COMPUTING 2010年第6期39卷 2113-2131页

作者： Braverman, Vladimir Ostrovsky, Rafail Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

In the streaming model, elements arrive sequentially and can be observed only once. Maintaining statistics and aggregates is an important and nontrivial task in this model. These tasks become even more challenging in the sliding windows model, where statistics must be maintained only over the most recent n elements. In their pioneering paper, Datar et al. [SIAM J. Comput., 31 (2002), pp. 1794-1813] presented the exponential histogram, an effective method for estimating statistics on sliding windows. In this paper we present a novel smooth histogram method that is more general and achieves stronger bounds than the exponential histogram. In particular, the smooth histogram method improves the approximation error rate obtained via exponential histograms. Furthermore, the smooth histogram method not only captures and improves multiple previous results on sliding windows but also extends the class of functions that can be approximated on sliding windows. In particular, we provide the first approximation algorithms for the following functions: L-p norms, frequency moments, the length of the increasing subsequence, and the geometric mean.

关键词： sliding windows data streams randomized algorithms smooth histograms

来源：评论

学校读者我要写书评

暂无评论

Stable routing under the Spanning Tree Protocol

引用

OPERATIONS RESEARCH LETTERS 2010年第5期38卷 399-404页

作者： Grandoni, Fabrizio Nicosia, Gaia Oriolo, Gianpaolo Sanita, Laura Univ Roma Tor Vergata Dipartimento Ingn Impresa I-00133 Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Univ Roma Tre Dipartimento Informat & Automaz I-00146 Rome Italy Ecole Polytech Fed Lausanne Inst Math CH-1015 Lausanne Switzerland

The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q = 0(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Stable routing Spanning Tree Protocol randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：