文章基本信息

标题：Brief Announcement: Fast Aggregation in Population Protocols
本地全文：下载
作者：Ryota Eguchi ; Taisuke Izumi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：91
页码：49:1-49:3
DOI：10.4230/LIPIcs.DISC.2017.49
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The coalescence protocol plays an important role in the population protocol model. The conceptual structure of the protocol is for two agents holding two non-zero values a, b respectively to take a transition (a,b) -> (a+b, 0), where + is an arbitrary commutative binary operation. Obviously, it eventually aggregates the sum of all initial values. In this paper, we present a fast coalescence protocol that converges in O(sqrt(n) log^2 n) parallel time with high probability in the model with an initial leader (equivalently, the model with a base station), which achieves an substantial speed-up compared with the naive implementation taking Omega(n) time.
关键词：population protocol; aggregation