Value in Fast Rounds Sample Clauses

Value in Fast Rounds. In a fast round i , after receiving the “1b” messages from an i -quorum, if the coor- dinator is free to pick any value, it can delegate this task to acceptors; it does so by picking as placeholder the special value Any and sending it in a “2a” message to the acceptors. 〈 〉 〈 〉 After receiving the “2a” message with the value Any, acceptor a waits for a message “propose”, v , in case it has not received one yet, and behaves as if it had received a message “2a”, c, i , v from the coordinator c of round i . Hence, for Fast Paxos to work properly, proposers should send their “propose” messages to both coordinators and acceptors. In Fast Paxos, acceptors are still bound to accept just one value per round but, differently from Classic Paxos, different acceptors can accept different values in the same fast round. Hence, to ensure the property that if a value v is chosen at round i , then no acceptor will ever accept a value different from v at any round j such that j > i , we must revisit the rule used by the coordinator of round i to find pickable values after receiving the “1b” messages from an i -quorum. That is, we must redefine the PickValue function. Ensuring Safety with Fast Rounds To understand how a coordinator picks a value in a fast round i , consider a run of the algorithm in which the coordinator of i has just received the “1b” messages for i from an i -quorum Q . There are three cases to analyze. First, if none of the received messages has a valid proposal in the val field, then no value has been or might be chosen at lower-numbered rounds, since there is no quorum that could have chosen such a value that does not intersect with Q . Therefore, any proposed value is pickable and it is up to c to decide whether to pick one or to let proposers propose directly. If the first case does not apply, then let k be the greatest value for rnd received amongst the phase “1b” messages. If all messages in which rnd = k report the same value v as val, it might be the case that v was or will be chosen at a round j < k Because the coordinator of k was also aware of this fact, v is the only value that it could have sent to the acceptors. Moreover, since any k -quorum must intersect Q and acceptors a in Q are sure to have executed action Phase1b(a, i) for round i (i > k ), no value different from v can be chosen at k . Therefore, the coordinator can safely pick v in i . Now consider the third case, in which more than one value has been reported in the phase “1b” messa...