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

Proceedings of the 2013 ACM symposium on Principles of distributed computing

作者： Valerie King Jared Saia University of Victoria Victoria BC Canada University of New Mexico Albuquerque NM USA

ISBN: (纸本)9781450320658

In a paper appearing in STOC 2013, we considered Byzantine agreement in the classic asynchronous message-passing model. The adversary is adaptive: it can determine which processors to corrupt and what strategy these processors should use as the algorithm proceeds. Communication is asynchronous: the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm. Finally, the adversary has full information: it knows the states of all processors at any time, and is assumed to be computationally unbounded. Such an adversary is also known as "strong". We presented the first known polynomial expected time algorithm to solve asynchronous Byzantine Agreement when the adversary controls a constant fraction of processors. This is the first improvement in running time for this problem since Ben-Or's exponential expected time solution in 1983.

关键词： randomized algorithms byzantine agreement distributed computing consensus

来源：评论

学校读者我要写书评

暂无评论

Byzantine agreement in polynomial expected time: [extended abstract] 13

Byzantine agreement in polynomial expected time: [extended a...

引用

Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

作者： Valerie King Jared Saia University of Victoria Victoria BC Canada University of New Mexico Albuquerque NM USA

ISBN: (纸本)9781450320290

In the classic asynchronous Byzantine agreement problem, communication is via asynchronous message-passing and the adversary is adaptive with full information. In particular, the adversary can adaptively determine which processors to corrupt and what strategy these processors should use as the algorithm proceeds; the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm; and the adversary knows the states of all processors at any time, and is assumed to be computationally unbounded. Such an adversary is also known as "strong". We present a polynomial expected time algorithm to solve asynchronous Byzantine Agreement with a strong adversary that controls up to a constant fraction of the processors. This is the first improvement in running time for this problem since Ben-Or's exponential expected time solution in 1983. Our algorithm tolerates an adversary that controls up to a $1/500$ fraction of the processors.

关键词： consensus Byzantine agreement distributed computing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Robust, Optimal PI-Controller Tuning for Integrator Plus Delay Plants With Varying Parameters Based on Randomised algorithms

Robust, Optimal PI-Controller Tuning for Integrator Plus Del...

引用

Conference on Control and Fault-Tolerant Systems

作者： Tim Konings Jonas Esch Christoph Kandler Steven X. Ding Chris Louen Institute of Automatic Control and Complex Systems (AKS) University of Duisburg-Essen

ISBN: (纸本)9781479928569

In this paper we consider the problem of tuning a PI-controller for robust, optimal performance with an integrator plus delay plant with varying plant parameters. The integrated absolute error for set-point tracking is considered as the performance index to be minimised by tuning. To this end, classical worst case and mean value based techniques for robust, performance optimal controller tuning are discussed. It is shown that these techniques require the consideration of an infinite amount of possible plant parameters in the optimisation step and are thus infeasible. To overcome this, we adopt randomised algorithms that allow an approximation of the original problem with a finite number of plant parameter samples in every step. Furthermore, we show that the minimisation problems to be solved in the randomised algorithm are convex and can thus be solved to their global minimiser, using readily available iterative algorithms. This is shown to introduce convexity of the set of stabilising controller parameters as a necessary condition, which is proven to hold for the problems considered here. Application of the proposed algorithm is shown for the tuning of a level controller in a continuous stirred tank heater demonstrator plant.

关键词： randomized algorithms integrators tuning variable parameter plant parameters PI control level controller Convexity performance indicators original problem

来源：评论

学校读者我要写书评

暂无评论

Exponential Lower Bounds for the PPSZ k-SAT Algorithm 13

Exponential Lower Bounds for the PPSZ k-SAT Algorithm

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Shiteng Chen Dominik Scheder Navid Talebanfard Bangsheng Tang Tsinghua University Aarhus University

ISBN: (纸本)9781611972511

In 1998, Paturi, Pudlak, Saks, and Zane presented PPSZ, an elegant randomized algorithm for k-SAT. Fourteen years on, this algorithm is still the fastest known worst-case algorithm. They proved that its expected running time on k-CNF formulas with n variables is at most 2~((1-ε_k)n), whereε_k ∈ Ω(1/k). So far, no exponential lower bounds at all have been known. In this paper, we construct hard instances for PPSZ. That is, we construct satisfiable k-CNF formulas over n variables on which the expected running time is at least 2~((1-ε_k)n), forε_k ∈ O(log~2 k/k).

关键词： Lower bound Runtime algorithms Exponential formula randomized algorithms Recombinant DNA

来源：评论

学校读者我要写书评

暂无评论

On the Sample Complexity of Uncertain Linear and Bilinear Matrix Inequalities

On the Sample Complexity of Uncertain Linear and Bilinear Ma...

引用

IEEE Annual Conference on Decision and Control

作者： Mohammadreza Chamanbaz Fabrizio Dabbene Roberto Tempo Venkatakrishnan Venkataramanan Qing-Guo Wang Data Storage Institute Singapore IEIIT-CNR Torino Italy Department of Electrical and Computer Engineering National University of Singapore

ISBN: (纸本)9781467357159

In this paper, we consider uncertain linear and bilinear matrix inequalities which depend in a possibly nonlinear way on a vector of uncertain parameters. Motivated by recent results in statistical learning, we show that probabilistic guaranteed solutions can be obtained by means of randomized algorithms. In particular, we show that the Vapnik-Chevonenkis dimension (VC-dimension) of the two problems is finite, and we compute upper bounds on it. In turn, these bounds allow us to derive explicitly the sample complexity of the problems. Using these bounds, in the second part of the paper, we derive a sequential scheme, based on a sequence of optimization and validation steps. The algorithm is on the same lines of recent schemes proposed for similar problems, but improves both in terms of complexity and generality.

关键词： sample complexity Plant uncertain bilinearity Statistical learning randomized algorithms inequalities Upper bound Uncertainty Finite

来源：评论

学校读者我要写书评

暂无评论

randomized optimal consensus of multi-agent systems

引用

AUTOMATICA 2012年第12期48卷 3018-3030页

作者： Shi, Guodong Johansson, Karl Henrik Royal Inst Technol KTH Sch Elect Engn ACCESS Linnaeus Ctr Automat Control Lab S-10044 Stockholm Sweden

In this paper, we formulate and solve a randomized optimal consensus problem for multi-agent systems with stochastically time-varying interconnection topology. The considered multi-agent system with a simple randomized iterating rule achieves an almost sure consensus meanwhile solving the optimization problem min(z is an element of Rd) Sigma(n)(i=1) f(i)(z), in which the optimal solution set of objective function f(i) can only be observed by agent i itself. At each time step, simply determined by a Bernoulli trial, each agent independently and randomly chooses either taking an average among its neighbor set, or projecting onto the optimal solution set of its own optimization component. Both directed and bidirectional communication graphs are studied. Connectivity conditions are proposed to guarantee an optimal consensus almost surely with proper convexity and intersection assumptions. The convergence analysis is carried out using convex analysis. We compare the randomized algorithm with the deterministic one via a numerical example. The results illustrate that a group of autonomous agents can reach an optimal opinion by each node simply making a randomized trade-off between following its neighbors or sticking to its own opinion at each time step. (c) 2012 Elsevier Ltd. All rights reserved.

关键词： Multi-agent systems Optimal consensus Set convergence Distributed optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Simple Asymptotically Optimal randomized Algorithm for Decentralized Blanket Coverage Self-deployment of Mobile Robotic Sensor Networks

A Simple Asymptotically Optimal Randomized Algorithm for Dec...

引用

IEEE International Conference on Control Applications (CCA) Part of 6th IEEE Multi-Conference on Systems and Control (IEEE MSC)

作者： Savkin, Andrey V. Javed, Faizan Matveev, Alexey S. Xi, Zhiyu Univ New South Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia St Petersburg State Univ Dept Math & Mech St Petersburg 199034 Russia

ISBN: (纸本)9781467345057

We propose a novel distributed randomized algorithm for self-deployment of a network of mobile robotic sensors in the problem of blanket coverage. The aim is to deploy sensors in a bounded connected region so that any point of the region is sensed by at least one mobile robotic sensor. The proposed algorithm is based only on information about the closest neighbours of each sensor. The monitoring region is of an arbitrary shape and not known to the sensors a priori. We give mathematically rigorous proofs of asymptotic optimality and convergence with probability 1 of the proposed algorithm.

关键词： Robotic networks mobile sensor networks sensor deployment decentralized control distributed algorithms blanket coverage randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized control design through probabilistic validation

Randomized control design through probabilistic validation

引用

American Control Conference (ACC)

作者： Alamo, T. Luque, A. Ramirez, D. R. Tempo, R. Univ Seville Dept Ingn Sistemas & Automat Escuela Super Ingenieros Camino Descubrimientos S-N Seville 41092 Spain Politecn Torino CNR IEIIT I-10129 Turin Italy

ISBN: (纸本)9781457710964;9781457710957

In this paper, we present a randomized strategy for design under uncertainty. The main contribution is to provide a general class of sequential algorithms which satisfy the required specifications using probabilistic validation. At each iteration of the sequential algorithm, a candidate solution is probabilistically validated by means of a set of randomly generated uncertainty samples. The idea of validation sets has been used in some randomized algorithms when a given candidate solution is classified as probabilistic solution when it satisfies all the constraints on the validation set. In this paper, we show the limitations of this strategy and present a more general setting where the candidate solution may violate the specifications for a reduced number of elements of the validation set. This generalized scheme exhibits some advantages, in particular in terms of obtaining a probabilistic solution.

关键词： Probabilistic robustness randomized algorithms uncertain systems

来源：评论

学校读者我要写书评

暂无评论

randomized Distributed Decision

Randomized Distributed Decision

引用

26th International Symposium on Distributed Computing (DISC)

作者： Fraigniaud, Pierre Korman, Amos Parter, Merav Peleg, David CNRS F-75700 Paris France Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9783642336515

The paper tackles the power of randomization in the context of locality by analyzing the ability to "boost" the success probability of deciding a distributed language. The main outcome of this analysis is that the distributed computing setting contrasts significantly with the sequential one as far as randomization is concerned. Indeed, we prove that in some cases, the ability to increase the success probability for deciding distributed languages is rather limited. We focus on the notion of a (p q)-decider for a language r, which is a distributed randomized algorithm that accepts instances in L with probability at least p and rejects instances outside of L with probability at least q. It is known that every hereditary language that can be decided in t rounds by a (p, q)-decider, where p(2) + q > 1, can be decided deterministically in O(t) rounds. One of our results gives evidence supporting the conjecture that the above statement holds for all distributed languages and not only for hereditary ones, by proving the conjecture for the restricted case of path topologies. For the range below the aforementioned threshold, namely, p(2)+ q < 1, we study the class Bk(t) (for k E N* U {cc}) of all languages decidable in at most t rounds by a (p,q)-decider, where pl+i + q > 1. Since every language is decidable (in zero rounds) by a (p q)-decider satisfying p + q = 1, the hierarchy Bk provides a spectrum of complexity classes between determinism (k = 1, under the above conjecture) and complete randomization (k = co). We prove that all these classes are separated, in a strong sense: for every integer k > 1, there exists a language L satisfying L E Bk+i (0) but L Bk(t) for any t = o(n). In addition, we show that B(t) does not contain all languages, for any t = o(n). In other words, we obtain the hierarchy B1 (t) c B2 (t) C C B,o(t) C All. Finally, we show that if the inputs can be restricted in certain ways, then the ability to boost the success probability becomes almost null, an

关键词： Local distributed algorithms local decision randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for randomized Load Balancing on Arbitrary Network Topologies

Tight Bounds for Randomized Load Balancing on Arbitrary Netw...

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Sauerwald, Thomas Sun, He Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9781467343831

We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbors. The goal is to achieve a distribution where all nodes have nearly the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is fairly well-understood in terms of their spectral gap. However, in many applications load items cannot be divided arbitrarily and we need to deal with the discrete case where the load is composed of indivisible tokens. This discretization entails a non-linear behavior due to its rounding errors, which makes the analysis much harder than in the continuous case. Therefore, it has been a major open problem to understand the limitations of discrete load balancing and its relation to the continuous case. We investigate several randomized protocols for different communication models in the discrete case. Our results demonstrate that there is almost no difference between the discrete and continuous case. For instance, for any regular network in the matching model, all nodes have the same load up to an additive constant in (asymptotically) the same number of rounds required in the continuous case. This generalizes and tightens the previous best result, which only holds for expander graphs.

关键词： randomized algorithms parallel and distributed algorithms graph expansion Markov chains load balancing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：