An Exact Characterization of the Two-shot Deterministic Objects Solving Two-process Consensus

A key question in distributed computing is determining the synchronization power of a shared object. This power is commonly measured using consensus, a distributed problem in which processes agree on a common input value. An object has consensus number n when n is the largest number for which we may solve consensus with copies of this object and registers. The seminal work of Herlihy and Ruppert [14] provides an exact characterization of the consensus number for deterministic one-shot objects (that can be accessed by each process at most once). This paper extends that study to deterministic two-shot objects (that can be accessed by each process at most twice) in a two-process system. We introduce three disjoint classes of two-shot objects: The first class is similar to one-shot objects in the sense that the first operation call gives enough information to solve consensus. Objects in the second class do not provide any useful information after the first call to one of the two processes. The last class contains objects for which calling the object twice is always necessary. In this class, the second operation to call is chosen adaptively, which may lead to using different operations in different schedules. For instance, the second operation used in a solo run might differ from the one called when processes interleave. We show that these three classes provide an exact characterization of the two-shot deterministic objects able to solve two-process consensus. To establish this, we first prove that any two-shot deterministic object solving two-process consensus must belong to one of the three classes. Then, we present matching consensus algorithms, one for each class.