The search functionality is under construction.

The search functionality is under construction.

*A passively mobile system* is an abstract notion of mobile ad-hoc networks. It is a collection of agents with computing devices. Agents move in a region, but the algorithm cannot control their physical behavior (i.e., how they move). The population protocol model is one of the promising models in which the computation proceeds by the pairwise communication between two agents. The communicating agents update their states by a specified transition function (algorithm). In this paper, we consider a general form of the *aggregation* problem with a base station. The base station is a special agent having the computational power more powerful than others. In the aggregation problem, the base station has to sum up for inputs distributed to other agents. We propose an algorithm that solves the aggregation problem in sub-linear parallel time using a relatively small number of states per agent. More precisely, our algorithm solves the aggregation problem with input domain *X* in *O*(√*n* log^{2} *n*) parallel time and *O*(|*X*|^{2}) states per agent (except for the base station) with high probability.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1187-1194

- Publication Date
- 2019/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E102.A.1187

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category
- Distributed algorithms

Ryota EGUCHI

Nagoya Institute of Technology

Taisuke IZUMI

Nagoya Institute of Technology

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Ryota EGUCHI, Taisuke IZUMI, "Sub-Linear Time Aggregation in Probabilistic Population Protocol Model" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1187-1194, September 2019, doi: 10.1587/transfun.E102.A.1187.

Abstract: *A passively mobile system* is an abstract notion of mobile ad-hoc networks. It is a collection of agents with computing devices. Agents move in a region, but the algorithm cannot control their physical behavior (i.e., how they move). The population protocol model is one of the promising models in which the computation proceeds by the pairwise communication between two agents. The communicating agents update their states by a specified transition function (algorithm). In this paper, we consider a general form of the *aggregation* problem with a base station. The base station is a special agent having the computational power more powerful than others. In the aggregation problem, the base station has to sum up for inputs distributed to other agents. We propose an algorithm that solves the aggregation problem in sub-linear parallel time using a relatively small number of states per agent. More precisely, our algorithm solves the aggregation problem with input domain *X* in *O*(√*n* log^{2} *n*) parallel time and *O*(|*X*|^{2}) states per agent (except for the base station) with high probability.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1187/_p

Copy

@ARTICLE{e102-a_9_1187,

author={Ryota EGUCHI, Taisuke IZUMI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Sub-Linear Time Aggregation in Probabilistic Population Protocol Model},

year={2019},

volume={E102-A},

number={9},

pages={1187-1194},

abstract={*A passively mobile system* is an abstract notion of mobile ad-hoc networks. It is a collection of agents with computing devices. Agents move in a region, but the algorithm cannot control their physical behavior (i.e., how they move). The population protocol model is one of the promising models in which the computation proceeds by the pairwise communication between two agents. The communicating agents update their states by a specified transition function (algorithm). In this paper, we consider a general form of the *aggregation* problem with a base station. The base station is a special agent having the computational power more powerful than others. In the aggregation problem, the base station has to sum up for inputs distributed to other agents. We propose an algorithm that solves the aggregation problem in sub-linear parallel time using a relatively small number of states per agent. More precisely, our algorithm solves the aggregation problem with input domain *X* in *O*(√*n* log^{2} *n*) parallel time and *O*(|*X*|^{2}) states per agent (except for the base station) with high probability.},

keywords={},

doi={10.1587/transfun.E102.A.1187},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - Sub-Linear Time Aggregation in Probabilistic Population Protocol Model

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1187

EP - 1194

AU - Ryota EGUCHI

AU - Taisuke IZUMI

PY - 2019

DO - 10.1587/transfun.E102.A.1187

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E102-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2019

AB - *A passively mobile system* is an abstract notion of mobile ad-hoc networks. It is a collection of agents with computing devices. Agents move in a region, but the algorithm cannot control their physical behavior (i.e., how they move). The population protocol model is one of the promising models in which the computation proceeds by the pairwise communication between two agents. The communicating agents update their states by a specified transition function (algorithm). In this paper, we consider a general form of the *aggregation* problem with a base station. The base station is a special agent having the computational power more powerful than others. In the aggregation problem, the base station has to sum up for inputs distributed to other agents. We propose an algorithm that solves the aggregation problem in sub-linear parallel time using a relatively small number of states per agent. More precisely, our algorithm solves the aggregation problem with input domain *X* in *O*(√*n* log^{2} *n*) parallel time and *O*(|*X*|^{2}) states per agent (except for the base station) with high probability.

ER -