Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Realization of Periodic Functions by Self-stabilizing Population Protocols with Synchronous Handshakes
verfasst von : Anissa Lamani, Masafumi Yamashita
Erschienen in: Theory and Practice of Natural Computing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We consider in the following the problem of realizing periodic functions by a collection of finite state-agents that cooperate by interacting with each other. More formally, given a periodic non-negative integer function f that maps the set of non-negative integers \(\mathbf{N}\) to itself, we aim in this paper at designing a distributed protocol with a state set Q and a subset \(S \subseteq Q\), such that, for any initial configuration \(C_0\), with probability 1, there are a time instant \(t_0\) and a constant \(d \in \mathbf{N}\) satisfying \(f(t+d) = \nu _S(C_t)\) for all \(t \ge t_0\), where \(\nu _S(C)\) is the number of agents with a state in S in a configuration C. The model that we consider is a variant of the population protocol (PP) model in which we assume that each agent is involved in an interaction at each time instant t, hence the notion of synchronous handshakes. These additional assumptions on the model are necessary to solve the considered problem. We also assume that the interacting pairs are matched uniformly at random.