A self-stabilizing transformer for population protocols with covering
详细信息 查看全文
- 作者：Joffroy Beauquier<sup>asup><sup> ; sup><sup>joffroy.beauquier@lri.fr"" rel=""nofollowsup> ; Janna Burman<sup>bsup><sup> ; sup><sup>janna.burman@inria.fr"" rel=""nofollowsup> ; Shay Kutten<sup>csup><sup> ; sup><sup>kutten@ie.technion.ac.il"" rel=""nofollowsup>
- 关键词：Population protocols ; Cover time ; Self-stabilization ; Transformer
- 刊名：Theoretical Computer Science
- 出版年：2011
- 出版时间：29 July 2011
- 年：2011
- 卷：412
- 期：33
- 页码：4247-4259
- 全文大小：295 K
文摘
Developing self-stabilizing solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an automatic transformer for algorithms in an extended population protocol model. Population protocols is a model that was introduced recently for networks with a large number of resource-limited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication “speed”, which is reflected by their cover times. Second, we assume the existence of a special agent with an unbounded memory, the base station. The automatic transformer takes as an input an algorithm solving a static problem (and meeting some additional rather natural requirements) and outputs a self-stabilizing algorithm for the same problem. The transformer is built using a re-execution approach (the technique consisting of executing an algorithm repeatedly in order to obtain its self-stabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.