No double discount: Condition-based simultaneity yields limited gain

We consider the consensus problem in synchronous message-passing distributed systems. A celebrated result states that every protocol that is guaranteed to tolerate up to t crash failures has a worst-case execution in which some process does not decide before the end of t+1 rounds. A variant of the problem in which the set of input vectors is restricted is called condition-based consensus. In this setting, Mostéfaoui, Rajsbaum and Raynal defined a natural degree of restriction called the condition of the set of input vectors that a protocol is assumed to handle. The condition is a natural number d⩽t, with a larger condition implying a smaller set of input values. Moreover, they showed that condition-d consensus can be solved in t+1−d rounds in the worst case.Dwork and Moses considered simultaneous consensus, a variant of (unconditional) consensus in which all correct processes must decide in the same round. Like ordinary consensus, this problem can be solved in t+1 rounds in the worst case. However, they showed that the stopping time depends on the pattern in which failures occur. They defined a notion of the waste W(F) of a failure pattern F (where 0⩽W(F)⩽t−1), and showed that t+1−W(F) rounds are necessary and sufficient for simultaneous consensus. They presented a solution that was optimal in all cases, and not just in the worst case: For every behavior of the adversary, their protocol stops as soon as any correct protocol can possibly stop.This paper considers condition-based simultaneous consensus in the synchronous model.1 It first presents a simple algorithm in which processes decide simultaneously at the end of the round RSt,d,F=(t+1)−max{W(F),d}. Then, the main result of the paper is presented, namely the statement and the proof that RSt,d,F is a lower bound for simultaneous condition-based consensus. This shows that, contrary to what could be hoped, when considering condition-based consensus with simultaneous decision, we can benefit from the best of both actual worlds (either the failure world when RSt,d,F=(t+1)−W(F), or the condition world when RSt,d,F=t+1−d), but we cannot benefit from the sum of savings offered by both. Only the best discount applies. From a technical point of view, the lower bound result is based on two new notions associated with conditions on input vectors, called d-coverability and d-tightness.