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

Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election

JOURNAL OF THE ACM 2021年第1期68卷 1–21页

作者： Gasieniec, Leszek Stachowiak, Grzegorz Univ Liverpool Dept Comp Sci Liverpool Merseyside England Augusta Univ Sch Comp & Cyber Sci Augusta GA 30912 USA Uniwersytet Wroclawski Inst Informatyki Wroclaw Poland

The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this article, the emphasis is on the space complexity of fast leader election in population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions between n agents. One of the main results of this article is the first fast space optimal leader election protocol, which works with high probability. The new protocol operates in parallel time O(log(2) n) equivalent to O(n log(2) n) sequential pairwise interactions with each agent's memory space limited to O(log logn) states. This double logarithmic space utilisation matches asymptotically the lower bound 12 log logn on the number of states utilised by agents in any leader election algorithm with the running time o(n/polylog n);see Reference [7]. Our new solution expands also on the classical concept of phase clocks used to synchronise and to coordinate computations in distributed algorithms. In particular, we formalise the concept and provide a rigorous analysis of phase clocks operating in nested modes. Our arguments are also valid for phase clocks propelled by multiple leaders. The combination of the two results in the first time-space efficient leader election algorithm. We also provide a complete formal argumentation, indicating that our solution is always correct, fast, and it works with high probability.

关键词： Population protocols leader election randomised algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Diversity, Fairness, and Sustainability in Population Protocols 21

Diversity, Fairness, and Sustainability in Population Protoc...

引用

40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Kang, Nan Mallmann-Trenn, Frederik Rivera, Nicolas Kings Coll London London England IMDF Santiago Chile Univ Valparaiso Santiago Chile

ISBN: (纸本)9781450385480

Over the years, population protocols with the goal of reaching consensus have been studied in great depth. However, many systems in the real-world do not result in all agents eventually reaching consensus, but rather in the opposite: they converge to a state of rich diversity. Consider for example task allocation in ants. If eventually all ants perform the same task, then the colony will perish (lack of food, no brood care, etc.). Then, it is vital for the survival of the colony to have a diverse set of tasks and enough ants working on each task. What complicates matters is that ants need to switch tasks periodically to adjust the needs of the colony;e.g., when too many foragers fell victim to other ant colonies. A further difficulty is that not all tasks are equally important and maybe they need to keep certain proportions in the distribution of the task. How can ants keep a healthy and balanced allocation of tasks? To answer this question, we propose a simple population protocol for n agents on a complete graph and an arbitrary initial distribution of k colours (tasks). In this protocol we assume that each colour i has an associated weight (importance or value) w(i) >= 1. By denoting w as the sum of the weights of different colours, we show that the protocol converges in O(w(2)n logn) rounds to a configuration where the number of agents supporting each colour i is concentrated on the fair share w(i)n/w and will stay concentrated for a large number of rounds, w.h.p. Our protocol has many interesting properties: agents do not need to know other colours and weights in the system, and our protocol requires very little memory per agent. Furthermore, the protocol guarantees fairness meaning that over a long period each agent has each colour roughly a number of times proportional to the weight of the colour. Finally, our protocol also fulfils sustainability meaning that no colour ever vanishes. All of these properties still hold when an adversary adds agents or colours.

关键词： Distributed Systems Population Protocols Self-organisation randomised algorithm

来源：评论

学校读者我要写书评

暂无评论

Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols 19

Almost Logarithmic-Time Space Optimal Leader Election in Pop...

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Gasieniec, Leszek Stachowiak, Grzegorz Uznanski, Przemyslaw Univ Liverpool Liverpool Merseyside England Uniwersytet Wroclawski Wroclaw Poland

ISBN: (纸本)9781450361842

The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called agents. The agents communicate and perform computation through pairwise interactions. We study fast and space efficient leader election in population of cardinality n governed by a random scheduler, where during each time step the scheduler uniformly at random selects for interaction exactly one pair of agents. We present the first o(log(2))-time leader election protocol. It operates in expected parallel time O(logn log logn) which is equivalent to O(n logn log logn) pairwise interactions. This is the fastest currently known leader election algorithm in which each agent utilises asymptotically optimal number of O(log logn) states. The new protocol incorporates and amalgamates successfully the power of assorted synthetic coins with variable rate phase clocks.

关键词： Population protocols leader election randomised algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Output-feedback control for sampled-data systems with variable sampling rate

引用

INTERNATIONAL JOURNAL OF CONTROL 2018年第4期91卷 897-906页

作者： Lee, Hojin Fujisaki, Yasumasa Osaka Univ Dept Informat & Phys Sci Osaka Japan

In this paper, we propose design method of controller for sampled-data systems with variable sampling rate. First, we give design method for both H-2 and H-infinity controller. For H-2 control, performance of the system is introduced according to a standard sampled-data setting. A discrete-time H-2 control problem is employed for solving the original problem. Its solvability condition is then established as a parameter-dependent linear matrix inequality. A probabilistic approach is taken for coping with the parameter-dependency. H-infinity controller is designed by almost the same manner. Applying both results, we have design method for multi-objective control.

关键词： Sampled-data control H-2 control H-infinity control multi-objective control randomised algorithm

来源：评论

学校读者我要写书评

暂无评论

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields

引用

algorithmICA 2018年第2期80卷 560-575页

作者： Ivanyos, Gabor Karpinski, Marek Santha, Miklos Saxena, Nitin Shparlinski, Igor E. Hungarian Acad Sci Inst Comp Sci & Control H-1111 Budapest Hungary Univ Bonn Dept Comp Sci D-53113 Bonn Germany Univ Paris Diderot CNRS F-75013 Paris France Natl Univ Singapore CQT Singapore 117543 Singapore Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India Univ New South Wales Dept Pure Math Sydney NSW 2052 Australia

We consider the problem of recovering (that is, interpolating) and identity testing of a "hidden" monic polynomial f, given an oracle access to for , where is finite field of q elements (extension fields access is not permitted). The naive interpolation algorithm needs queries and thus requires . We design algorithms that are asymptotically better in certain cases;requiring only queries to the oracle. In the randomized (and quantum) setting, we give a substantially better interpolation algorithm, that requires only queries. Such results have been known before only for the special case of a linear f, called the hidden shifted power problem. We use techniques from algebra, such as effective versions of Hilbert's Nullstellensatz, and analytic number theory, such as results on the distribution of rational functions in subgroups and character sum estimates.

关键词： Hidden polynomial power Black-box interpolation Nullstellensatz Rational function Deterministic algorithm randomised algorithm Quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

Packing degenerate graphs

引用

ADVANCES IN MATHEMATICS 2019年 354卷 106739-000页

作者： Allen, Peter Bottcher, Julia Hladky, Jan Piguet, Diana London Sch Econ Dept Math Houghton St London WC2A 2AE England Czech Acad Sci Inst Math Zitna 25 Prague 11000 Czech Republic Czech Acad Sci Inst Comp Sci Pod Vodarenskou Vezi 2 Prague 18207 Czech Republic

Given D and gamma > 0, whenever c > 0 is sufficiently small and n sufficiently large, if g is a family of D-degenerate graphs of individual orders at most cn/log n, maximum degrees at most , and total number of edges at most (1 - gamma)((2)(n)), then G packs into the complete graph K-n. Our proof proceeds by analysing a natural random greedy packing algorithm. (C) 2019 The Authors. Published by Elsevier Inc.

关键词： Graph packing randomised algorithm

来源：评论

学校读者我要写书评

暂无评论

Robust maximum likelihood estimation for stochastic state space model with observation outliers

引用

INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE 2016年第11期47卷 2733-2744页

作者： AlMutawa, J. King Fahd Univ Petr & Minerals Dept Math & Stat Dhahran 31261 Saudi Arabia

The objective of this paper is to develop a robust maximum likelihood estimation (MLE) for the stochastic state space model via the expectation maximisation algorithm to cope with observation outliers. Two types of outliers and their influence are studied in this paper: namely,the additive outlier (AO) and innovative outlier (IO). Due to the sensitivity of the MLE to AO and IO, we propose two techniques for robustifying the MLE: the weighted maximum likelihood estimation (WMLE) and the trimmed maximum likelihood estimation (TMLE). The WMLE is easy to implement with weights estimated from the data;however, it is still sensitive to IO and a patch of AO outliers. On the other hand, the TMLE is reduced to a combinatorial optimisation problem and hard to implement but it is efficient to both types of outliers presented here. To overcome the difficulty, we apply the parallel randomised algorithm that has a low computational cost. A Monte Carlo simulation result shows the efficiency of the proposed algorithms.

关键词： EM algorithm weighted likelihood estimation trimmed maximum likelihood estimation parallel algorithms maximum likelihood estimation randomised algorithm outliers stochastic state space model

来源：评论

学校读者我要写书评

暂无评论

Patterns from nature: Distributed greedy colouring with simple messages and minimal graph knowledge

引用

INFORMATION SCIENCES 2015年 316卷 550-566页

作者： Xu, Lei Jeavons, Peter Audaque Data Technol Ltd Shenzhen 518000 Peoples R China Univ Oxford Dept Comp Sci Oxford OX1 3QD England

A well-established problem in global optimization is the problem of colouring the vertices of an arbitrary graph using the minimal number of colours, such that adjacent vertices are assigned different colours. One way to restrict the number of colours used is to allow only greedy colourings. A greedy colouring is an assignment of colours to the vertices of a graph that can be obtained by an algorithm that considers each vertex in turn and assigns the first colour that is not already assigned to some neighbour. An optimal colouring can always be obtained in this way, by choosing an appropriate order on the vertices. Recently, a new bio-inspired approach to distributed pattern formation has been proposed, based on modelling the neurological development of the fruit fly. Building on that approach, we propose a new simple randomised algorithm for distributed greedy colouring using only local processing at the vertices and messages along the edges. In our approach the processors exchange only simple messages representing potential colour values and each processor has minimal graph knowledge. We discuss two variations of this algorithm, and investigate their time complexity and message complexity both theoretically and experimentally. In addition, we show experimentally that the number of colours used turns out to be optimal or near-optimal for many standard graph colouring benchmarks. Thus, for distributed networks, our algorithm serves as an effective heuristic approach to computing a colouring with a small number of colours. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Bio-inspired algorithm Distributed computing Greedy colouring randomised algorithm

来源：评论

学校读者我要写书评

暂无评论

randomised broadcasting: Memory vs. randomness

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期520卷 27-42页

作者： Berenbrink, Petra Elsaesser, Robert Sauerwald, Thomas Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Salzburg Univ Dept Comp Sci A-5020 Salzburg Austria Max Planck Inst Informat D-66123 Saarbrucken Germany

In this paper we analyse broadcasting in d-regular networks with good expansion properties. For the underlying communication, we consider modifications of the so-called random phone call model. In the standard version of this model, each node is allowed in every step to open a channel to a randomly chosen neighbour, and the channels can be used for bi-directional communication. Then, broadcasting on the graphs mentioned above can be performed in time O(log n), where n is the size of the network. However, every broadcast algorithm with runtime O(log n) needs on average Omega(log n/log d) message transmissions per node for random graphs with expected degree d [11]. In this paper we show that it is possible to save significantly on communications if the standard model is modified such that nodes can avoid opening channels to exactly the same neighbours in two consecutive steps. We consider the so-called RR model where we assume that every node has a cyclic list of all of its neighbours, ordered in a random way. Then, in step i the node communicates with the i-th neighbour from that list. We provide an O(logn) time algorithm which produces in average O(root logn) transmissions per node in networks with suitably defined expansion properties. Furthermore, we present a related lower bound of Omega(root log n/log log n) for the average number of message transmissions. These results show that by using memory it is possible to reduce the number of transmissions per node by almost a quadratic factor. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.

关键词： Distributed computing randomised algorithm Broadcasting Expander graphs

来源：评论

学校读者我要写书评

暂无评论

Delay analysis of randomised algorithms for link scheduling in wireless networks

引用

INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING 2013年第1期13卷 59-72页

作者： Ghiasian, Ali Saidi, Hossein Behdadfar, Mohammad Isfahan Univ Technol Dept Elect & Comp Engn Esfahan Iran IRIB Univ Broadcast Engn Dept Tehran Iran

To design a link scheduling algorithm that can maximise the throughput region yet meet the average delay constraint is a challenging issue in wireless networks. In this paper we aim to analyse and improve the delay performance of the well-studied randomised link scheduling algorithms. To this end, we first introduce a novel concept, the average hitting time, and analyse its impact on the upper bound of the average delay. We analytically show that for two given randomised algorithms achieving the same throughput region, the one with a smaller average hitting time has less average delay bound. We also show that by assigning traffic priorities in some specific applications, the achievable throughput region delivered by the randomised algorithm remains intact. This result is much valuable in the design of algorithms for some real-time applications by prioritising the traffic to reduce the average delay of those applications. The simulation results are consistent with our theoretical analysis.

关键词： wireless networks ad hoc networks link scheduling maximum weight matching randomised algorithm delay throughput region Lyapunov drift

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：