Implementing set objects in dynamic distributed systems
Implementing set objects in dynamic distributed systems
复制标题
在动态分布式系统中实现集合对象
DOI：
10.1016/j.jcss.2015.11.002
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Raynal
中科院分区：
文献类型：
--
作者：
R. Baldoni;Silvia Bonomi;M. Raynal
本文考虑一个集合对象，即一个共享对象，允许用户（进程）向集合添加和删除元素，并获取其内容的一致快照。具体来说，我们表明，当底层分布式系统最终是同步的，并且受到进程的连续到达和离开的影响（这种现象也称为搅动）时，不存在任何使用有限内存实现集合对象的协议。然后，我们分析了系统模型假设与对象规范之间的关系，以便在有限内存条件下设计实现集合对象的协议。沿着一个方向（加强系统模型），我们提出了一个在同步分布式系统中实现集合对象的协议，沿着另一个方向（削弱对象规范），我们引入了ak-bounded集合对象的概念，提出了一个在最终同步系统上工作的协议。
This paper considers aset object, i.e., a shared object allowing users (processes) to add and remove elements to the set, as well as taking consistent snapshots of its content. Specifically, we show that there not exists any protocol implementing a set object, using finite memory, when the underlying distributed system is eventually synchronous and affected by continuous arrivals and departures of processes (phenomenon also known aschurn). Then, we analyze the relationship between system model assumptions and object specification in order to design protocols implementing the set object using finite memory. Along one direction (strengthening the system model), we propose a protocol implementing the set object in synchronous distributed systems and, along the other direction (weakening the object specification), we introduce the notion of ak-bounded set objectproposing a protocol working on an eventually synchronous system.