期刊
JOURNAL OF CELLULAR AUTOMATA
卷 10, 期 1-2, 页码 1-21出版社
OLD CITY PUBLISHING INC
关键词
One-dimensional cellular automata; leader election problem; upper bound performance; symmetric configuration; loosely-coupled configuration
资金
- VEGA [1/0553/12, 1/0458/13]
Leader election plays a crucial role in numerous distributed protocols and biological societies. Yet, there is a fundamental gap in understanding its simplest variant employing components that are fully uniform, deterministic, and anonymous, such as in one-dimensional cellular automata (CA). In our previous work we found several binary CAs that elect a leader by using spatial-temporal patterns, domains and particles, which carry and exchange information across distance. The best strategy reached performance of 94 - 99% with a modulo 6 limitation for the number of cells. As opposed to state-of-the-art distributed algorithms, a CA consists just of binary components without any extra memory or communication capabilities, and therefore operates with minimal resources possible. In this paper we identify fundamental limitations of leader election for one-dimensional CAs and formulate an upper bound on performance. We show that configurations that are symmetric or loosely-coupled are insolvable. The proportion of configurations that are insolvable decreases dramatically with the system size. Our findings could help to design more effective distributed protocols and also to model biological processes such as morphogenesis of cell differentiation, where leader election breaks symmetry in a newly formed organism.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据