Recent Advances in Population Protocols
Recent Advances in Population Protocols
复制标题
人口协议的最新进展
DOI：
10.1007/978-3-642-03816-7_6
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
I. Chatzigiannakis;O. Michail;P. Spirakis
Angluin等人提出的群体协议模型（PP）描述了由被动移动有限状态智能体组成的传感器网络。智能体感知环境，并成对通信，对感知值进行计算。MPP (mediated population protocol model， MPP)[13]通过在通信链路上设置一个固定大小的缓冲区来扩展PP模型。在[13]中，MPP模型比PP模型更强。然而，它最重要的贡献是，它为我们提供了设计优化协议、近似协议和决定其运行的通信图属性的协议的能力。后一种情况提出了一种简化的模型，即GDM模型，该模型在2010年被正式定义和研究。GDM是MPP的一个特例，它捕获了MPP决定通信图属性的能力。在这里，我们调查了由PP模型的提议发起的领域的最新进展，同时我们提供了新的协议，新的想法和结果。
Thepopulation protocol model(PP) proposed by Angluin et al. [2] describes sensor networks consisting of passively mobile finite-state agents. The agents sense their environment and communicate in pairs to carry out some computation on the sensed values. Themediated population protocol model(MPP) [13] extended the PP model by communication links equipped with a constant size buffer. The MPP model was proved in [13] to be stronger than the PP model. However, its most important contribution is that it provides us with the ability to devise optimizing protocols, approximation protocols and protocols that decide properties of the communication graph on which they run. The latter case, suggests a simplified model, the GDM model, that was formally defined and studied in [11]. GDM is a special case of MPP that captures MPP’s ability to decide properties of the communication graph. Here we survey recent advances in the area initiated by the proposal of the PP model and at the same time we provide new protocols, novel ideas and results.