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, Mostefaoui, 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 denned a notion of the waste W(F) of a failure pattern F (where 0 ≤ W(F) ≤ t- 1), and showed that t + -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 RS_(t, d, F) = (t + 1)-max( W(F),d]. Then, the main result of the paper is presented, namely the statement and the proof that R_(t, 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 RS_(t, d, F) = (t + 1) - W(F), or the condition world when RS_(t, 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.