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

distributed Alignment Processes With Samples of Group Average

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2023年第2期10卷 960-971页

作者： Korman, Amos Vacus, Robin HUJI WIS Int Joint Res Unit CNRS UMI FILOFOCSUP7French Israeli Lab Fdn Comp SciT Tel Aviv Israel Res Inst Fdn Comp Sci CNRS Paris France

This article studies a stochastic alignment problem assuming that agents can sense the general tendency of the system. More specifically, we consider $n$ agents, each being associated with a real number. In each round, each agent receives a noisy measurement of the system's average value and then updates its value. This value is then perturbed by random drift. We assume that both noise and drift are Gaussian. We prove that a distributed weighted-average algorithm optimally minimizes the deviation of each agent from the average value, and for every round. Interestingly, this optimality holds even in the centralized setting, where a master agent can gather all the agents' measurements and instruct a move to each one. We find this result surprising since it can be shown that the set of measurements obtained by all agents contains strictly more information about the deviation of Agent $i$ from the average value, than the information contained in the measurements obtained by Agent $i$ alone. Although this information is relevant for Agent $i$, it is not processed by it when running a weighted-average algorithm. Finally, we also analyze the drift of the center of mass and show that no distributed algorithm can achieve drift that is as small as the one that can be achieved by the best centralized algorithm.

关键词： Noise measurement Current measurement Weight measurement Synchronization Signal processing algorithms Protocols Position measurement biological distributed algorithms clock synchronization consensus distributed signal processing flocking Kalman filter noisy communication weighted-average algorithms

来源：评论

学校读者我要写书评

暂无评论

Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication 22

Early Adapting to Trends: Self-Stabilizing Information Sprea...

引用

ACM Symposium on Principles of distributed Computing (PODC)

作者： Korman, Amos Vacus, Robin Tel Aviv Univ French Natl Ctr Sci Res CNRS French Israeli Lab Fdn Comp Sci UMI FILOFOCSUP7HUJIWISInt Joint Res Unit Tel Aviv Israel French Natl Ctr Sci Res CNRS Inst Res Fundamental Comp Sci IRIF Paris France

ISBN: (纸本)9781450392624

How to efficiently and reliably spread information in a system is one of the most fundamental problems in distributed computing. Recently, inspired by biological scenarios, several works focused on identifying the minimal communication resources necessary to spread information under faulty conditions. Here we study the self-stabilizing bit-dissemination problem, introduced by Boczkowski, Korman, and Natale in [SODA 2017]. The problem considers a fully-connected network of n agents, with a binary world of opinions, one of which is called correct. At any given time, each agent holds an opinion bit as its public output. The population contains a source agent which knows which opinion is correct. This agent adopts the correct opinion and remains with it throughout the execution. We consider the basic PULL model of communication, in which each agent observes relatively few randomly chosen agents in each round. The goal of the non-source agents is to quickly converge on the correct opinion, despite having an arbitrary initial configuration, i.e., in a self-stabilizing manner. Once the population converges on the correct opinion, it should remain with it forever. Motivated by biological scenarios in which animals observe and react to the behavior of others, we focus on the extremely constrained model of passive communication, which assumes that when observing another agent the only information that can be extracted is the opinion bit of that agent. We prove that this problem can be solved in a poly-logarithmic in n number of rounds with high probability, while sampling a logarithmic number of agents at each round. Previous works solved this problem faster and using fewer samples, but they did that by decoupling the messages sent by agents from their output opinion, and hence do not fit the framework of passive communication. Moreover, these works use complex recursive algorithms with refined clocks that are unlikely to be used by biological entities. In contrast, our propo

关键词： Consensus protocols Population protocols biological distributed algorithms Self-stabilization Passive communication

来源：评论

学校读者我要写书评

暂无评论

Search via Parallel Levy Walks on Z² 21

Search via Parallel Levy Walks on Z<SUP>2</SUP>

引用

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

作者： Clementi, Andrea D'Amore, Francesco Giakkoupis, George Natale, Emanuele Univ Roma Tor Vergata Rome Italy Univ Cote dAzur INRIA CNRS I3S Sophia Antipolis France Univ Rennes CNRS INRIA IRISA Rennes France

ISBN: (纸本)9781450385480

Motivated by the Levy foraging hypothesis - the premise that various animal species have adapted to follow Levy walks to optimize their search efficiency - we study the parallel hitting time of Levy walks on the infinite two-dimensional grid. We consider k independent discrete-time Levy walks, with the same exponent alpha is an element of(1, infinity), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance l. We show that for any choice of k and l from a large range, there is a unique optimal exponent alpha(k,l) is an element of(2, 3), for which the hitting time is (O) over tilde (l(2)/k) w.h.p., while modifying the exponent by any constant term epsilon > 0 increases the hitting time by a factor polynomial in l, or the walks fail to hit the target almost surely. Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and l are unknown: The exponent of each Levy walk is just chosen independently and uniformly at random from the interval (2, 3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). Our results should be contrasted with a line of previous work showing that the exponent alpha = 2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and l, and that randomizing the choice of the exponents works simultaneously for all k and l.

关键词： Levy walk parallel Levy walks infinite 2D grid hitting time distributed search Levy foraging hypothesis ANTS problem biological distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A feedback control principle common to several biological and engineered systems

引用

JOURNAL OF THE ROYAL SOCIETY INTERFACE 2022年第188期19卷 20210711-20210711页

作者： Suen, Jonathan Y. Navlakha, Saket Cold Spring Harbor Lab Simons Ctr Quantitat Biol Cold Spring Harbor NY 11724 USA

Feedback control is used by many distributed systems to optimize behaviour. Traditional feedback control algorithms spend significant resources to constantly sense and stabilize a continuous control variable of interest, such as vehicle speed for implementing cruise control, or body temperature for maintaining homeostasis. By contrast, discrete-event feedback (e.g. a server acknowledging when data are successfully transmitted, or a brief antennal interaction when an ant returns to the nest after successful foraging) can reduce costs associated with monitoring a continuous variable;however, optimizing behaviour in this setting requires alternative strategies. Here, we studied parallels between discrete-event feedback control strategies in biological and engineered systems. We found that two common engineering rules-additive-increase, upon positive feedback, and multiplicative-decrease, upon negative feedback, and multiplicative-increase multiplicative-decrease- are used by diverse biological systems, including for regulating foraging by harvester ant colonies, for maintaining cell-size homeostasis, and for synaptic learning and adaptation in neural circuits. These rules support several goals of these systems, including optimizing efficiency (i.e. using all available resources);splitting resources fairly among cooperating agents, or conversely, acquiring resources quickly among competing agents;and minimizing the latency of responses, especially when conditions change. We hypothesize that theoretical frameworks from distributed computing may offer new ways to analyse adaptation behaviour of biology systems, and in return, biological strategies may inspire new algorithms for discrete-event feedback control in engineering.

关键词： feedback control biological distributed algorithms ant colonies neural circuits cell size synaptic plasticity networks

来源：评论

学校读者我要写书评

暂无评论

Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model 20

Time- and Space-Optimal Discrete Clock Synchronization in th...

引用

32nd ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Feldmann, Michael Khazraei, Ardalan Scheideler, Christian Paderborn Univ Paderborn Germany Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9781450369350

We consider the clock synchronization problem in the (discrete) beeping model: Given a network of.. nodes with each node having a clock value delta(v) is an element of{0,...T - 1}, the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume arbitrary activations for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to {0,..., T - 1}). We give an asymptotically optimal algorithm that runs in 4D + (sic)D/(sic)T/4(sic)(sic) center dot (T mod 4) = O(D) rounds, where D is the diameter of the network. Once all nodes are in sync, they beep at the same round every T rounds. The algorithm drastically improves on the O(TD)-bound of [2] (where T is required to be at least 4n, so the bound is no better than O(nD)). Our algorithm is very simple as nodes only have to maintain 3 bits in addition to the (sic)log T(sic) bits needed to maintain the clock. Furthermore we investigate the complexity of self-stabilizing solutions for the clock synchronization problem: We first show lower bounds of Omega(max{T, n}) rounds on the runtime and Omega(log(max{T, n})) bits of memory required for any such protocol. Afterwards we present a protocol that runs in O(max{T, n}) rounds using at most O(log(max{T, n})) bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.

关键词： distributed Systems Discrete Clock Synchronization Beeping Model biological distributed algorithms Self-stabilization

来源：评论

学校读者我要写书评

暂无评论

Noisy rumor spreading and plurality consensus

引用

distributed COMPUTING 2019年第4期32卷 257-276页

作者： Fraigniaud, Pierre Natale, Emanuele CNRS Inst Rech Informat Fondamentale Paris France Univ Paris Diderot Paris France Max Planck Inst Informat D-66123 Saarbrucken Germany

Error-correcting codes are efficient methods for handling noisy communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman et al. (PODC 2014) that complex coordination tasks such as rumor spreading and majority consensus can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability 1/2 + epsilon, without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued opinions: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to k-valued opinions, for any constant k >= 2. Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying k-valued messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest.

关键词： Noise Rumor spreading Plurality consensus PUSH model biological distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Ant-inspired density estimation via random walks

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2017年第40期114卷 10534-10541页

作者： Musco, Cameron Su, Hsin-Hao Lynch, Nancy A. MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA

Many ant species use distributed population density estimation in applications ranging from quorum sensing, to task allocation, to appraisal of enemy colony strength. It has been shown that ants estimate local population density by tracking encounter rates: The higher the density, the more often the ants bump into each other. We study distributed density estimation from a theoretical perspective. We prove that a group of anonymous agents randomly walking on a grid are able to estimate their density within a small multiplicative error in few steps by measuring their rates of encounter with other agents. Despite dependencies inherent in the fact that nearby agents may collide repeatedly (and, worse, cannot recognize when this happens), our bound nearly matches what would be required to estimate density by independently sampling grid locations. From a biological perspective, our work helps shed light on how ants and other social insects can obtain relatively accurate density estimates via encounter rates. From a technical perspective, our analysis provides tools for understanding complex dependencies in the collision probabilities of multiple random walks. We bound the strength of these dependencies using local mixing properties of the underlying graph. Our results extend beyond the grid to more general graphs, and we discuss applications to size estimation for social networks, density estimation for robot swarms, and random walk-based sampling for sensor networks.

关键词： population density estimation random walk sampling network exploration ant colony algorithms biological distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：