Distributed computability: Relating k-immediate snapshot and x-set agreement.

This paper introduces a generalization of the immediate snapshot object denoted k-immediate snapshot, requiring that the snapshot returned contains at least (n − k) pairs. The case k = n − 1 corresponds to the original immediate snapshot object, which requires that the snapshot returned contains at least one pair 〈process id, value〉 pair, that corresponds to the process id that invoked the operation). The paper first shows that k -immediate snapshot is impossible to implement in an asynchronous read/write system, even if k = n − 2 and t = 1. Then, the paper considers x -set agreement, another object stronger than the classical read/write t -crash read/write model (when x ≤ t), and studies the relation with the k -immediate snapshot object, establishing strong relations linking these two fundamental distributed computing abstractions. The paper shows conditions under which x -set agreement can be solved in read/write systems enriched with k -immediate snapshot objects. It also shwos when k -immediate snapshot and consensus are equivalent. [ABSTRACT FROM AUTHOR]