论文标题
$ t $ - 弹性$ k $ -immediate快照及其与协议问题的关系
$t$-Resilient $k$-Immediate Snapshot and its Relation with Agreement Problems
论文作者
论文摘要
即时快照对象是一个高级通信对象，该对象构建在读/写分布式系统的顶部，其中所有进程都可能崩溃。它允许一个过程编写一个值并获得一组代表写入对象的值快照的值，该值在写步骤之后立即发生。 考虑到最多$ t $流程可能会崩溃的$ n $过程模型，本文首先介绍了$ k $的即时快照对象，这是基本立即快照的自然概括（与$ k = t = t = n-1 $相对应）。除了基本立即快照的集合遏制属性外，$ k $的即时快照对象还要求返回到一个进程的每个集合都包含至少$（n-k）$对。 该论文首先表明，对于$ K，T <n-1 $，$ k $的即时快照在异步读/写系统中是不可能的。 ％然后，该论文调查了对象的空间，即不能在$ n $ - 过程$ t $ crash读取/写入系统中求解％。然后，本文研究了一个计算模型，该模型通过访问$ k $ iMMediate快照对象相互通信，并表明该模型比$ t $ crash模型强。考虑到$ x $ set协议问题的空间（无法在$ x \ leq t $的系统中解决），该论文表明，$ x $ set协议可以在富含$ k $ immediate快照对象的读/写入系统中解决，以$ x = \ max（1，t+k-（n-2））$。它还表明，在这些系统中，当$ 1 \ leq t <n/2 $和$ t \ leq k \ leq（n-1）-t $时，$ k $的即时快照和共识是等效的。因此，由于其提供的问题图，该论文建立了牢固的关系，该关系建立了牢固的关系，将基本分布式计算对象（一个与交流有关，另一个与协议有关），这是无法在纯读/写入系统中求解的。
An immediate snapshot object is a high level communication object, built on top of a read/write distributed system in which all except one processes may crash. It allows a process to write a value and obtain a set of values that represent a snapshot of the values written to the object, occurring immediately after the write step. Considering an $n$-process model in which up to $t$ processes may crash, this paper introduces first the $k$-resilient immediate snapshot object, which is a natural generalization of the basic immediate snapshot (which corresponds to the case $k=t=n-1$). In addition to the set containment properties of the basic immediate snapshot, a $k$-resilient immediate snapshot object requires that each set returned to a process contains at least $(n-k)$ pairs. The paper first shows that, for $k,t<n-1$, $k$-resilient immediate snapshot is impossible in asynchronous read/write systems. %Then the paper investigates the space of objects that %are impossible to solve in $n$-process $t$-crash read/write systems. Then the paper investigates a model of computation where the processes communicate with each other by accessing $k$-immediate snapshot objects, and shows that this model is stronger than the $t$-crash model. Considering the space of $x$-set agreement problems (which are impossible to solve in systems such that $x\leq t$), the paper shows then that $x$-set agreement can be solved in read/write systems enriched with $k$-immediate snapshot objects for $x=\max(1,t+k-(n-2))$. It also shows that, in these systems, $k$-resilient immediate snapshot and consensus are equivalent when $1\leq t<n/2$ and $t\leq k\leq (n-1)-t$. Hence, %thanks to the problem map it provides, the paper establishes strong relations linking fundamental distributed computing objects (one related to communication, the other to agreement), which are impossible to solve in pure read/write systems.
