Stationary and Deterministic Leader Election in Self-organizing Particle Systems
Stationary and Deterministic Leader Election in Self-organizing Particle Systems
复制标题
自组织粒子系统中的固定和确定性领导者选举
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Joseph L. Briones
中科院分区：
文献类型：
--
作者：
R. Bazzi;Joseph L. Briones
我们提出了第一个固定的和确定性的协议的领导人选举问题的非简单连接的粒子系统的几何Amoebot模型中，粒子没有唯一的标识符，但有共同的手征。该解决方案不需要粒子运动来打破对称性（静止），也不允许粒子做出概率性选择（确定性）。我们表明，领导人选举是可能的，当且仅当所提出的协议成功地选出一个独特的领导人。我们表明，如果协议未能选出一个领导者，它将总是成功地找到一个有限的集合\（k \le 6\）领导者候选人和系统必须有k-对称性，防止选择少于k个候选人。该协议以\（O（n^2）\）步运行，其中n是系统中的粒子数。Amoebot模型中领导者选举问题的其他解决方案要么是概率性的，假设系统是简单连接的，和/或需要更强的原语来打破对称性。
We propose the first stationary and deterministic protocol for the leader election problem for non-simply connected particle systems in the geometric Amoebot model in which particles have no unique identifiers but have common chirality. The solution does not require particle movement to break symmetry (stationary) and does not allow particles to make probabilistic choices (deterministic). We show that leader election is possible if and only if the proposed protocol succeeds in electing a unique leader. We show that if the protocol fails to elect a leader, it will always succeed in finding a finite set of \(k \le 6\) leader candidates and the system must have k-symmetry that prevents the selection of less than k candidates. The protocols runs in \(O(n^2)\) steps, where n is the number of particles in the system. Other solutions to the leader election problem in the Amoebot model are either probabilistic, assume that the system is simply connected, and/or require stronger primitives to break symmetry.
自组织可编程物质的领导者选举和形态形成
DOI：
10.1007/978-3-319-21999-8_8
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Zahra Derakhshandeh;Robert Gmyr;Thim Strothmann;Rida A. Bazzi;Andrea W. Richa;Christian Scheideler
通讯作者：
Christian Scheideler
DOI：
10.1145/2933057.2933107
发表时间：
2016
期刊：
PODC
影响因子：
--
作者：
Cannon, Sarah;Daymude, Joshua J.;Randall, Dana;Richa, Andréa W.
通讯作者：
Richa, Andréa W.
影响因子：
2.1
作者：
Daymude, Joshua J.;Derakhshandeh, Zahra;Strothmann, Thim
通讯作者：
Strothmann, Thim