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

作者： Eftekhari, Mahsa University of California Davis

学位级别：Ph.D., Doctor of Philosophy

We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. Concretely, *population protocols*are asynchronous, complete networks that consist of computational entities called *agents*with no control over the schedule of interactions with other *** a population of n agents,repeatedly a random pair of agents are chosen to interact,each observing the state of the other agent before updating its own state. population protocols are equivalent to the model of chemical reaction networks, describing abstract chemical reactions such as A+B rightarrow C+D , when the latter is subject to the restriction that all reactions have two reactants and two products, and all rate constants are 1. In this thesis, we demonstrate an algorithmic advance for the exact majority problem: starting in a population of n agents, each with one of two opinions A or B , the agents must determine whether there are more A , more B , or a tie. The proposed algorithm is emph{nonuniform}: assume that the agents are initialized with an approximate estimate of n (specifically, a value that is geq log n ). We introduce *uniform* population protocols:networks of anonymous agents whose pairwise interactions are chosen at random,where each agent uses an *identical* transition algorithm that does not depend on the population size n .Moreover, we study almost optimal protocols that solve static counting problem: the *counting* problem is that of designing a protocol so that n agents, all starting in the same state, eventually converge to states where each agent encodes in its state an exact or approximate description of population size n . Finally, we introduce population protocols with dynamic size and finish this thesis with a novel counting protocol robust to an adversary who can add or

关键词： Distributed computing population protocols Dynamic models

来源：评论

学校读者我要写书评

暂无评论

Time-Optimal Self-Stabilizing Leader Election in population protocols 21

Time-Optimal Self-Stabilizing Leader Election in Population ...

引用

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

作者： Burman, Janna Chen, Ho-Lin Chen, Hsueh-Ping Doty, David Nowak, Thomas Severson, Eric Xu, Chuan Univ Paris Saclay CNRS Paris France Natl Taiwan Univ Taipei Taiwan Univ Calif Davis Davis CA 95616 USA Inria Sophia Antipolis Nice France

ISBN: (纸本)9781450385480

We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, andWada [Theor. Comput. Syst. 50] runs in expected parallel time Theta(n(2)) and has the optimal number of n states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents' states eventually stop changing. Observing that any silent protocol solving self-stabilizing leader election requires Omega(n) expected parallel time, we introduce a silent protocol that uses optimal O(n) parallel time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected parallel time of O(log n), but using at least exponential states (a quasipolynomial number of bits). All of our protocols (and also that of Cai et al.) work by solving the more difficult ranking problem: assigning agents the ranks 1,...,n.

关键词： leader election self-stabilization population protocols

来源：评论

学校读者我要写书评

暂无评论

Smoothed analysis of population protocols 35

Smoothed analysis of population protocols

引用

35th International Symposium on Distributed Computing, DISC 2021

作者： Schwartzman, Gregory Sudo, Yuichi JAIST Nomi Japan Hosei University Tokyo Japan

ISBN: (纸本)9783959772105

In this work, we initiate the study of smoothed analysis of population protocols. We consider a population protocol model where an adaptive adversary dictates the interactions between agents, but with probability p every such interaction may change into an interaction between two agents chosen uniformly at random. That is, p-fraction of the interactions are random, while (1 − p)-fraction are adversarial. The aim of our model is to bridge the gap between a uniformly random scheduler (which is too idealistic) and an adversarial scheduler (which is too strict). We focus on the fundamental problem of leader election in population protocols. We show that, for a population of size n, the leader election problem can be solved in O(p−2n log3 n) steps with high probability, using O((log2 n) · (log(n/p))) states per agent, for all values of p ≤ 1. Although our result does not match the best known running time of O(n log n) for the uniformly random scheduler (p = 1), we are able to present a smooth transition between a running time of O(n polylog n) for p = 1 and an infinite running time for the adversarial scheduler (p = 0), where the problem cannot be solved. The key technical contribution of our work is a novel phase clock algorithm for our model. This is a key primitive for much-studied fundamental population protocol algorithms (leader election, majority), and we believe it is of independent interest. © Gregory Schwartzman and Yuichi Sudo;licensed under Creative Commons License CC-BY 4.0

关键词： Leader election population protocols Smoothed analysis

来源：评论

学校读者我要写书评

暂无评论

Time-Optimal Self-Stabilizing Leader Election on Rings in population protocols

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2021年第12期E104A卷 1675-1684页

作者： Yokota, Daisuke Sudo, Yuichi Masuzawa, Toshimitsu Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan Hosei Univ Fac Comp & Informat Sci Koganei Tokyo 1848584 Japan

We propose a self-stabilizing leader election protocol on directed rings in the model of population protocols. Given an upper bound N on the population size n, the proposed protocol elects a unique leader within O(nN) expected steps starting from any configuration and uses O(N) states. This convergence time is optimal if a given upper bound N is asymptotically tight, i.e., N = O(n).

关键词： leader election self-stabilizing population protocols

来源：评论

学校读者我要写书评

暂无评论

Fast and succinct population protocols for Presburger arithmetic

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 140卷

作者： Czerner, Philipp Guttenberg, Roland Helfrich, Martin Esparza, Javier Tech Univ Munich Dept Comp Sci Munich Germany

In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m runs in O(m center dot n2log n) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states is exponential in m. Blondin et al. presented at STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with O(m) states that run in expected O(m7 center dot n2) interactions, optimal in n, for all inputs of size S2(m). For this, we introduce population computers, a generalization of population protocols, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols.(c) 2023 Elsevier Inc. All rights reserved.

关键词： population protocols Fast Succinct population computers

来源：评论

学校读者我要写书评

暂无评论

Loosely Stabilizing Leader Election on Arbitrary Graphs in population protocols without Identifiers or Random Numbers

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2020年第3期E103D卷 489-499页

作者： Sudo, Yuichi Ooshita, Fukuhito Kakugawa, Hirotsugu Masuzawa, Toshimitsu Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan Nara Inst Sci & Technol Grad Sch Sci & Technol Ikoma 6300192 Japan Ryukoku Univ Fac Sci & Technol Otsu Shiga 5202194 Japan

We consider the leader election problem in the population protocol model, which Angluin et al. proposed in 2004. A self-stabilizing leader election is impossible for complete graphs, arbitrary graphs, trees, lines, degree-bounded graphs, and so on unless the protocol knows the exact number of nodes. In 2009, to circumvent the impossibility, we introduced the concept of loose stabilization, which relaxes the closure requirement of self-stabilization. A loosely stabilizing protocol guarantees that starting from any initial configuration, a system reaches a safe configuration, and after that, the system keeps its specification (e.g., the unique leader) not forever but for a sufficiently long time (e.g., an exponentially long time with respect to the number of nodes). Our previous works presented two loosely stabilizing leader election protocols for arbitrary graphs;one uses agent identifiers, and the other uses random numbers to elect a unique leader. In this paper, we present a loosely stabilizing protocol that solves leader election on arbitrary graphs without agent identifiers or random numbers. Given upper bounds N and. of the number of nodes n and the maximum degree of nodes delta, respectively, the proposed protocol reaches a safe configuration within O(mn(2)d log n + mN Delta(2) log N) expected steps and keeps the unique leader for Omega(Ne-N) expected steps, where m is the number of edges and d is the diameter of the graph.

关键词： population protocols leader election loose stabilization

来源：评论

学校读者我要写书评

暂无评论

A combinatorial characterization of self-stabilizing population protocols

引用

INFORMATION AND COMPUTATION 2022年 285卷

作者： Mathur, Shaan Ostrovsky, Rafail Univ Calif Los Angeles Los Angeles CA 90095 USA

We characterize self-stabilizing functions in population protocols for complete interaction graphs. In particular, we investigate self-stabilization in systems of N finite state agents in which a malicious scheduler selects an arbitrary sequence of pairwise interactions under a global fairness condition. We show a necessary and sufficient condition for self stabilization. Specifically we show that functions without certain set-theoretic conditions are impossible to compute in a self-stabilizing manner. Our main contribution is in the converse, where we construct a self-stabilizing protocol for all other functions that meet this characterization. Our positive construction uses Dickson's Lemma to develop the notion of the root set, a concept that turns out to fundamentally characterize self-stabilization in this model. We believe it may lend to characterizing self-stabilization in more general models as well.(c) 2021 Elsevier Inc. All rights reserved.

关键词： population protocols Self-stabilization Anonymous Finite-state Chemical reaction networks

来源：评论

学校读者我要写书评

暂无评论

On parallel time in population protocols

引用

INFORMATION PROCESSING LETTERS 2023年 179卷

作者： Czumaj, Artur Lingas, Andrzej Univ Warwick Dept Comp Sci Coventry CV4 7AL England Univ Warwick Ctr Discrete Math & its Applicat DIMAP Coventry CV4 7AL England Lund Univ Dept Comp Sci Lund Sweden

The parallel time of a population protocol is defined as the average number of required interactions in which an agent in the protocol participates, i.e., the quotient between the total number of interactions required by the protocol and the total number n of agents, or just roughly the number of required rounds, where a round stands for a sequence of n consecutive interactions. This naming triggers an intuition that at least the expected number of parallel steps sufficient to implement a round is O (1). In a single parallel step only mutually independent interactions can be involved. We show that when the transition function of a population protocol is treated as a black box then the expected maximum number of parallel steps necessary to implement a round is omega( log n/log log n ). We also provide a combinatorial argument for a matching upper bound on the expected number of parallel steps under additional assumptions. Further, we extend these bounds by showing that the situation changes dramatically for sequences of m = omega(n log n) interactions. Then, the expected number of parallel steps required to implement such sequences is (sic)(n) under the aforementioned additional assumptions. Thus, it asymptotically coincides with the notion of parallel time, i.e., O(m/n ), for sequences of interactions produced by protocols solving any non-trivial problems requiring omega(nlog n) interactions. (C) 2022 The Author(s). Published by Elsevier B.V.

关键词： Distributed computing Randomized algorithms population protocols Parallel time complexity Directed acyclic graph

来源：评论

学校读者我要写书评

暂无评论

Leader Election Requires Logarithmic Time in population protocols

引用

PARALLEL PROCESSING LETTERS 2020年第1期30卷

作者： Sudo, Yuichi Masuzawa, Toshimitsu Osaka Univ Grad Sch Informat Sci & Technol 1-5 Yamadaoka Suita Osaka 5650871 Japan

This paper shows that every leader election protocol requires logarithmic stabilization time both in expectation and with high probability in the population protocol model. This lower bound holds even if each agent has knowledge of the exact size of a population and is allowed to use an arbitrarily large number of agent states. This lower bound concludes that the protocol given in [Sudo et al., SSS 2019] is time-optimal in expectation.

关键词： population protocols leader election stabilization time

来源：评论

学校读者我要写书评

暂无评论

Verifying Self-stabilizing population protocols with Coq

Verifying Self-stabilizing Population Protocols with Coq

引用

Third International Symposium on Theoretical Aspects of Software Engineering TASE 2009(第三届软件工程理论国际研讨会)

作者： Yuxin Deng Jean-Francois Monin Department of Computer Science and Engineering Shanghai Jiao Tong University China Universitéde Grenoble 1 France

population protocols are an elegant model recently introduced for distributed algorithms running in large and unreliable networks of tiny mobile agents. Correctness proofs of such protocols involve subtle arguments on infinite sequences of events. We propose a general formalization of self-stabilizing population protocols with the Coq proof assistant. It is used in reasoning about a concrete protocol for leader election in complete graphs. The protocol is formally proved to be correct for networks of arbitrarily large size. To this end we develop an appropriate theory of infinite sequences, including results for reasoning on abstractions, in addition, we provide a constructive correctness proof for a leader election protocol in directed rings. An advantage of using a constructive setting is that we get more informative proofs on the scenarios that converge to the desired configurations.

关键词： formal verification population protocols serfstabilization proof assistant Coq

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：