A Connectivity Model for Agreement in Dynamic Systems
A Connectivity Model for Agreement in Dynamic Systems
复制标题
动态系统中协议的连接模型
DOI：
10.1007/978-3-662-48096-0_26
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Larrea
中科院分区：
文献类型：
--
作者：
Carlos Gómez;A. Casteigts;A. Lafuente;M. Larrea
共识问题是分布式系统中的一个基本范式，因为它解决了其他协议问题的困难。许多当前的系统随着时间而演变，例如，由于节点的移动性，到目前为止，在这些系统中对一致性的研究很少。具体来说，它是没有很好地建立如何定义一组适当的假设，在动态分布式系统的共识。本文研究了三类时变图的层次结构，并针对每一类图给出了可靠广播终止（TRB）问题的解决方案。这些课程引入了越来越强的关于及时性的假设，以便可以分析弱点与可执行性和效率之间的权衡。TRB等价于同步系统中的一致性，本文将这种等价性扩展到动态系统。
The consensus problem is a fundamental paradigm in distributed systems, because it captures the difficulty to solve other agreement problems. Many current systems evolve with time, e.g., due to node mobility, and consensus has been little studied in these systems so far. Specifically, it is not well established how to define an appropriate set of assumptions for consensus in dynamic distributed systems. This paper studies a hierarchy of three classes of time-varying graphs, and provides a solution for each class to the problem of Terminating Reliable Broadcast (TRB). The classes introduce increasingly stronger assumptions on timeliness, so that the trade-off between weakness versus implementability and efficiency can be analysed. Being TRB equivalent to consensus in synchronous systems, the paper extends this equivalence to dynamic systems.