Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A Totally Distributed Fair Scheduler for Population Protocols by Randomized Handshakes
verfasst von : N. Ouled Abdallah, M. Jmaiel, M. Mosbah, A. Zemmari
Erschienen in: Theoretical Aspects of Computing - ICTAC 2015
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
A population protocol is a computational model based on pairwise interactions and designed for networks of passively mobile finite state agents. In the population protocol model, and also in the models that extend it, the interacting pairs are supposed to be chosen by a theoretical fair scheduler. In this paper, we present the HS Scheduler which is a totally distributed synchronous randomized handshake procedure. We then prove that this randomized handshake procedure can be a probabilistic consistent scheduler for population protocols that is fair with probability 1. By adopting a protocol aware version of the HS Scheduler, we introduce the iterated population protocols model where nodes can stop participating in the protocol’s computation once they reach a final state. We then study the time complexity of the computation of a particular case of this model where a final state is reached in only one computation step. We present some upper bounds that are later validated by simulations results.