On space complexity of self-stabilizing leader election in mediated population protocol
On space complexity of self-stabilizing leader election in mediated population protocol
复制标题
介导群体协议中自稳定领导人选举的空间复杂度
DOI：
10.1007/s00446-012-0173-9
复制
发表时间：
2012
影响因子：
1.3
通讯作者：
Masafumi Yamashita
中科院分区：
文献类型：
--
作者：
Ryu Mizoguchi;Hirotaka Ono;Shuji Kijima;Masafumi Yamashita
Chatzigiannakis等人（Lect Notes Comput Sci 5734：56-76，2009）扩展了Angluin等人（2004）的种群协议（PP），并通过在每个代理到代理通信链路上引入额外的存储器（即，Edge），以便对具有有限资源的移动的代理的更强大的网络进行建模。对于一般的分布式自治代理系统，领导选举（LE）在他们的有效协调中起着关键作用。ASef-Stabilizing（SS）协议具有理想的属性所需的分布式系统的大量的不高度可靠的代理通常由PP或MPP建模，它不需要任何初始化和容忍有限数量的瞬时故障。Cai et al.（2009）证明了对于一个agent系统，SS-LE的PP至少需要-个状态，并给出了SS-LE的PP。在本文中，我们证明了，对于一个系统的代理，任何MPP的SS-LE与2边状态（即，1位存储器），并给出了一个在每条边上具有代理状态和2个边状态的SS-LE的MPP。此外，我们表明，在每个边缘上的边缘状态的常数并没有帮助设计一个MPP的SS-LE与常数的代理状态，并没有MPP的SS-LE与2代理状态，无论边缘状态的数量;边缘状态是不是一个完整的替代的代理状态，虽然它可以帮助减少代理状态的数量，当解决SS-LE。
Chatzigiannakis et al. (Lect Notes Comput Sci 5734:56–76, 2009) extended thePopulation Protocol(PP) of Angluin et al. (2004) and introduced theMediated Population Protocol(MPP) by introducing an extra memory on every agent-to-agent communication link (i.e., edge), in order to model more powerful networks of mobile agents with limited resources. For a general distributed system of autonomous agents,Leader Election(LE) plays a key role in their efficient coordination. ASelf-Stabilizing(SS) protocol has ideal properties required for distributed systems of huge numbers of not highly reliable agents typically modeled by PP or MPP; it does not require any initialization and tolerates a finite number of transient failures. Cai et al. (2009) showed that for a system ofagents, any PP for SS-LE requires at leastagent-states, and gave a PP withagent-states for SS-LE. In this paper, we show, for a system ofagents, any MPP for SS-LE with 2 edge-states (i.e., 1 bit memory) on every edge requires at leastagent-states, and give an MPP for SS-LE withagent-states and 2 edge-states on every edge. Furthermore, we show that a constant number of edge-states on every edge do not help in designing an MPP for SS-LE with a constant number of agent-states, and that there is no MPP for SS-LE with 2 agent-states, regardless of the number of edge-states; the edge-state is not a complete alternative of the agent-state, although it can help in reducing the number of agent-states, when solving SS-LE.
登录
查看更多内容
影响因子：
1.3
作者：
Angluin, Dana;Aspnes, James;Eisenstat, David
通讯作者：
Eisenstat, David
稳定人口协议中的领导人选举
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
D. Canepa;M. Potop
通讯作者：
M. Potop
人口协议的最新进展
DOI：
10.1007/978-3-642-03816-7_6
发表时间：
2009
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
I. Chatzigiannakis;O. Michail;P. Spirakis
通讯作者：
P. Spirakis
DOI：
10.1007/3-540-45438-1_8
发表时间：
2001
期刊：
--
影响因子：
--
作者：
M. Gouda
通讯作者：
M. Gouda
被动移动匿名代理自稳定领导者选举的空间复杂度
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
S. Cai;T. Izumi;K. Wada
通讯作者：
K. Wada