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

Privacy in population protocols with probabilistic scheduling

THEORETICAL COMPUTER SCIENCE 2025年 1024卷

作者： Amir, Talley Aspnes, James Yale Univ New Haven CT 06511 USA

The population protocol model [2] offers a theoretical framework for designing and analyzing distributed algorithms among limited-resource mobile agents. While the original population protocol model considers the concept of anonymity, the issue of privacy is not investigated thoroughly. However, there is a need for time- and space-efficient privacy-preserving techniques in the population protocol model if these algorithms are to be implemented in settings handling sensitive data, such as sensor networks, IoT devices, and drones. In this work, we introduce several formal definitions of privacy, ranging from assuring only plausible deniability of the population input vector to having a full information-theoretic guarantee that knowledge beyond an agent's input and output bear no influence on the probability of a particular input vector. We then apply these definitions to both existing and novel protocols. We show that the Remainder-computing protocol from [9] (which is proven to satisfy output independent privacy under adversarial scheduling) is not information-theoretically private under probabilistic scheduling. In contrast, we provide a new algorithm and demonstrate that it correctly and information-theoretically privately computes Remainder under probabilistic scheduling.

关键词： Mobile ad-hoc networks population protocols Information-theoretic privacy

来源：评论

学校读者我要写书评

暂无评论

Complete Graph Identification in population protocols 26th

Complete Graph Identification in Population Protocols

引用

26th International Symposium on Stabilization, Safety, and Security of Distributed Systems

作者： Kanaya, Haruki Sudo, Yuichi Nara Inst Sci & Technol Nara Japan Hosei Univ Tokyo Japan

ISBN: (纸本)9783031744976;9783031744983

We consider the population protocol model where indistinguishable state machines, referred to as agents, communicate in pairs. The communication graph specifies potential interactions (i.e., communication) between agent pairs. This paper addresses the complete graph identification problem, requiring agents to determine if their communication graph is a clique or not. We evaluate various settings based on: (i) the fairness preserved by the adversarial scheduler-either global fairness or weak fairness, and (ii) the knowledge provided to agents beforehand-either the exact population size n, a common upper bound P on n, or no prior information. Positively, we show that O(n(2)) states per agent suffice to solve the complete graph identification problem under global fairness without prior knowledge. With prior knowledge of n, agents can solve the problem using only O(n) states under weak fairness.

关键词： population protocols Graph class identification

来源：评论

学校读者我要写书评

暂无评论

population protocols with faulty interactions: The impact of a leader

引用

THEORETICAL COMPUTER SCIENCE 2019年 754卷 35-49页

作者： Di Luna, Giuseppe A. Flocchini, Paola Izumi, Taisuke Izumi, Tomoko Santoro, Nicola Viglietta, Giovanni Univ Ottawa Dept Elect & Comp Engn 800 King Edward Ave Ottawa ON Canada Nagoya Inst Technol Dept Comp Sci & Engn Showa Ward Nagoya Aichi 4668555 Japan Ritsumeikan Univ Coll Informat Sci & Engn Kita Ku 56-1 Tojiin Kitamachi Kyoto 6038577 Japan Carleton Univ Sch Comp Sci 125 Colonel By Dr Ottawa ON Canada

We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-way interactions (as opposed to two-way interactions) and omission faults (i.e., failure by an agent to read its partner's state during an interaction), which in turn may be detectable or undetectable. We focus on the impact of a leader, and we give a complete characterization of the models in which the presence of a unique leader in the system allows the construction of simulators: when simulations are possible, we give explicit protocols;when they are not, we give proofs of impossibility. Specifically, if each agent has only a finite amount of memory, the simulation is possible only if there are no omission faults. If agents have an unbounded amount of memory, the simulation is possible as long as interactions are detectable. If an upper bound on the number of omissions involving the leader is known, the simulation is possible in all omissive models. (C) 2018 Elsevier B.V. All rights reserved.

关键词： population protocols Omission failures Two-way simulation

来源：评论

学校读者我要写书评

暂无评论

population protocols with Unreliable Communication 1

引用

17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)

作者： Raskin, Mikhail Tech Univ Munich Munich Germany

ISBN: (数字)9783030892401

ISBN: (纸本)9783030892395;9783030892401

population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication occurs nondeterministically, allowing the involved agents to change their states based on each other's states. In the present paper we study unreliable models based on population protocols and their variations from the point of view of expressive power. We model the effects of message loss. We show that for a general definition of protocols with unreliable communication with constant-storage agents such protocols can only compute predicates computable by immediate observation (IO) population protocols (sometimes also called one-way protocols). Immediate observation population protocols are inherently tolerant to unreliable communication and keep their expressive power under a wide range of fairness conditions. We also prove that a large class of message-based models that are generally more expressive than IO becomes strictly less expressive than IO in the unreliable case.

关键词： population protocols Message loss Expressive power

来源：评论

学校读者我要写书评

暂无评论

population protocols on Graphs: A Hierarchy

引用

12th International Conference on Unconventional Computation and Natural Computation (UCNC)

作者： Bournez, Olivier Lefevre, Jonas Ecole Polytech LIX F-91128 Palaiseau France

ISBN: (纸本)9783642390746;9783642390739

population protocols have been introduced as a model in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. In this paper, we consider population protocols acting on families of graphs, that is to say on particular topologies. Stably computable predicates on strings of size n correspond exactly to languages of NSPACE(n), that is to say to non-deterministic space of Turing machines. Stably computable predicates on cliques correspond to semi-linear predicates, namely exactly those definable in Presburger's arithmetic. Furthermore, we exhibit a strict hierarchy in-between when considering graphs between strings and cliques.

关键词： population protocols computability hierarchy space complexity

来源：评论

学校读者我要写书评

暂无评论

population protocols with Convergence Detection 17

Population Protocols with Convergence Detection

引用

17th IEEE International Symposium on Network Computing and Applications (NCA)

作者： Mocquard, Yves Sericola, Bruno Anceaume, Emmanuelle Univ Rennes 1 IRISA Rennes France INRIA Rennes Bretagne Atlantique Rennes France CNRS IRISA Rennes France

ISBN: (纸本)9781538676592

This paper focuses on pairwise interaction-based protocols, and proposes an universal mechanism that allows each agent to locally detect that the system has converged to the sought configuration with high probability. To illustrate our mechanism, we use it to detect the instant at which the proportion problem is solved. Specifically, let n(A) (resp. n(B)) be the number of agents that initially started in state A (resp. B) and gamma(A) = n(A)/n, where n is the total number of agents. Our protocol guarantees, with a given precision epsilon > 0 and any high probability 1 - delta, that after 0(n ln(n/delta) interactions, any queried agent that has set the detection flag will output the correct value of the proportion gamma A of agents which started in state A, by maintaining no more than 0 (1n(n)/epsilon) integers. We are not aware of any such results. Simulation results illustrate our theoretical analysis.

关键词： population protocols Detection of convergence Large scale systems Anonymous agents Probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

Time-Optimal Leader Election in population protocols

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第11期31卷 2620-2632页

作者： Sudo, Yuichi Ooshita, Fukuhito Izumi, Taisuke Kakugawa, Hirotsugu Masuzawa, Toshimitsu Osaka Univ Osaka 5650871 Japan Nara Inst Sci & Technol Nara 6300192 Japan Nagoya Inst Technol Nagoya Aichi 4668555 Japan Ryukoku Univ Otsu Shiga 5202194 Japan

In this article, we present the first leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of lg n such that m >= lg n and m = O(log n), the proposed protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter. This protocol is time-optimal because it was recently proven that any leader election protocol requires Omega(log n) parallel time.

关键词： protocols Voting Sociology Statistics Phase locked loops Schedules Epidemics population protocols leader election stabilization time

来源：评论

学校读者我要写书评

暂无评论

On automatic verification of self-stabilizing population protocols

引用

中国高等学校学术文摘·计算机科学 2008年第4期2卷 357-367页

作者： Jun PANG Zhengqin LUO Yuxin DENG Department of Computer Science and Communications Université du Luxembourg Luxembourg 1359 Luxembourg State Key Laboratory of Novel Software Technology Nanjing University Nanjing 210093 China Department of Computer Science and Engineering Shanghai Jiao Tong University Shanghai 200240China

The population protocol model has emerged as an elegant computation paradigm for describing mobile ad hoe networks, consisting of a number of mobile nodes that interact with each other to carry out a computation. The interactions of nodes are subject to a fairness con-straint. One essential property of population protocols is that all nodes must eventually converge to the correct out-put value (or configuration). In this paper, we aim to automatically verify self-stabilizing population protocols for leader election and token circulation in the Spin model checker. We report our verification results and discuss the issue of modeling strong fairness constraints in Spin.

关键词： distributed algorithms model checking population protocols verification

来源：评论

学校读者我要写书评

暂无评论

Data collection in population protocols with non-uniformly random scheduler

引用

THEORETICAL COMPUTER SCIENCE 2020年 806卷 516-530页

作者： Xu, Chuan Beauquier, Joffroy Burman, Janna Kutten, Shay Nowak, Thomas Univ Paris Sud Univ Paris Saclay CNRS LRI F-91405 Orsay France Technion Israel Inst Technol IL-32000 Haifa Israel

Contrary to many previous studies on population protocols using the uniformly random scheduler, we consider a more general non-uniform case. Here, pair-wise interactions between agents (moving and communicating devices) are assumed to be drawn non uniformly at random. While such a scheduler is known to be relevant for modeling many practical networks, it is also known to make the formal analysis more difficult. This study concerns data collection, a fundamental problem in mobile sensor networks (one of the target networks of population protocols). In this problem, pieces of information given to the agents (e.g., sensor readings) should be eventually delivered to a predefined sink node without loss or duplication. Following an idea of the known deterministic protocol TTF solving this problem, we propose an adapted version of it and perform a complete formal analysis of execution times in expectation and with high probability (w.h.p.). We further investigate the important issue of energy consumption. The goal is to improve TTF in terms of energy complexity, while still keeping good time complexities (in expectation and w.h.p.). Namely, we propose a new parameterized protocol for data collection, called lazy TTF, and present a study showing that an appropriate choice of the protocol parameters can considerably improve energy performances (compared to Tin at a slight expense of time performance. (C) 2019 Elsevier B.V. All rights reserved.

关键词： population protocols Data collection Non-uniformly random scheduler Energy consumption

来源：评论

学校读者我要写书评

暂无评论

Clocked population protocols

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 121卷 34-48页

作者： Aspnes, James Yale Univ Dept Comp Sci New Haven CT 06520 USA

We define an extension to the standard population protocol that provides each agent with a clock signal that indicates when the agent has waited long enough for the protocol to have converged. We represent "long enough" as an infinite time interval, and treat the protocol as operating over transfinite time. Over finite time intervals, the protocol behaves as in the standard model. At nonzero limit ordinals, corresponding to clock ticks, the protocol switches to a limit of previous configurations supplemented by a clock signal appearing as an extra component in some of the agents' states. Fairness generalizes to transfinite executions straightforwardly. We show that a clocked population protocol running in less than omega(kappa) time for any fixed k >= 2 is equivalent in power to a nondeterministic Turing machine with space complexity logarithmic in the population size, and can be simulated using only finitely many clock ticks. (C) 2021 Elsevier Inc. All rights reserved.

关键词： population protocols

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：