The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Sistem mudah alih pasif ialah tanggapan abstrak rangkaian ad-hoc mudah alih. Ia adalah koleksi ejen dengan peranti pengkomputeran. Ejen bergerak di rantau, tetapi algoritma tidak dapat mengawal tingkah laku fizikal mereka (iaitu, cara mereka bergerak). Model protokol populasi adalah salah satu model yang menjanjikan di mana pengiraan diteruskan dengan komunikasi berpasangan antara dua ejen. Ejen berkomunikasi mengemas kini keadaan mereka dengan fungsi peralihan tertentu (algoritma). Dalam makalah ini, kami mempertimbangkan satu bentuk umum pengagregatan masalah dengan stesen pangkalan. Stesen pangkalan ialah ejen khas yang mempunyai kuasa pengiraan lebih berkuasa daripada yang lain. Dalam masalah pengagregatan, stesen pangkalan perlu merumuskan input yang diedarkan kepada ejen lain. Kami mencadangkan algoritma yang menyelesaikan masalah pengagregatan dalam masa selari sub-linear menggunakan bilangan keadaan yang agak kecil bagi setiap ejen. Lebih tepat lagi, algoritma kami menyelesaikan masalah pengagregatan dengan domain input X in O(√n log2 n) masa selari dan O(|X|2) menyatakan setiap ejen (kecuali stesen pangkalan) dengan kebarangkalian tinggi.
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.
Salinan
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 log2 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
Salinan
@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 log2 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},}
Salinan
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 log2 n) parallel time and O(|X|2) states per agent (except for the base station) with high probability.
ER -