Algorithm Wait Till Safe Sample Clauses

Algorithm Wait Till Safe. (WTS)‌ The Wait Till Safe algorithm (Algorithms 1 and 2) is divided in two phases: an initial Values Disclosure Phase where processes are asked to declare to the whole system values they intend to propose, and then a Deciding Phase where processes agree on which elements of the lattice can be decided on the basis of the proposed values. For the sake of clarity, processes are divided in proposers that propose an initial value, and then decide one decision value, and acceptors which help proposers decide. This distinction does not need to be enforced during deployment as each process can play both roles at the same time. The main idea in the Values Disclosure Phase is to make any proposer disclose its proposed value by performing a Byzantine reliable broadcast. The reliable broadcast prevents Byzantine processes from sending different messages to processes [12, 13]. The exact specification of this broadcast is in [14]. In the pseudocode the broadcast primitive is represented by the ReliableBrodcast (used for reliably broadcast messages) function and RBcastDelivery event (that indicates the delivery of a message sent with the reliable broadcast). Values delivered at each process are saved in a SvS (Safe-values Set). A process moves to the next phase as soon as he receives values from at least (n f ) proposers. Waiting for (n f ) messages is not strictly necessary, but allows us to show a bound of (f ) on the message delays of our algorithm. Note that, from this point on, some operations of Phase 1 could run in parallel with Phase 2. Thanks to Value Disclosure Phase a process is committed to its value and cannot change its proposal or introduce a new one during the Deciding Phase. During this latter phase, correct processes only handle messages that contain values in SvS, i.e. messages for which the SAFE() predicate is true. Messages that do not satisfy this condition are buffered for later use, i.e. if and when all the values they contain will be in SvS. The Deciding Phase is an extension of the algorithm described in [2] with a Byzantine quorum and additional checks used to thwart Byzantine attacks. Each correct proposer p sends its Proposed value to acceptors in a request message (Line 18). An acceptor receiving a request, sends an ack if the previously Accepted set is a subset of the value contained in the request, and updates its Accepted set using the Proposed set in the request (initially, the Accepted set of an acceptor is the empty set). Otherwise, th...