Protocol Overview Sample Clauses

Protocol Overview. The basic protocol operates in two phases, after which a pos- sible decision is taken. Each process maintains an estimate. In the first phase, each process broadcasts its estimate using a reliable broadcast service, bv-broadcast (discussed below), as introduced previously [1]. The protocol uses a rotating coordinator; whoever is the assigned coordinator for a round broadcasts its estimate with a special designation. All processes then wait until they receive at least one message, and until a timer expires. (The timeout is increased with each iteration, so that eventually once the network stabilizes it is long enough.) If a process receives a message from the coordinator, then it chooses the coordinator’s value to “echo”, i.e., to rebroadcast to everyone in the second phase. Otherwise, it simply echoes all the messages received in the first phase. At this point, each process 𝑝𝑖 waits until it receives enough − − − compatible ECHO messages. Specifically, it waits to receive at least (𝑛 𝑡0) messages sent by distinct processes where every value in those messages was also received by 𝑝𝑖 in the first phase. In this case, it adopts the collection of values in those (𝑛 𝑡0) messages as its candidate set. In fact, if a process 𝑝𝑖 receives a set of (𝑛 𝑡0) messages that all contain exactly the coordinator’s value, then it chooses only that value as the candidate value. 𝑝𝑖 has only one candidate value 𝑣, then 𝑝𝑖 adopts that value 𝑣 as its estimate. In that case, it can decide 𝑣 if it matches the parity of the round, i.e., if 𝑣 = 𝑟𝑖 mod 2. Otherwise, if 𝑝𝑖 has more than one candidate value, then it adopts as its estimate 𝑟𝑖 mod 2, the parity of the round. / − − + To see that this ensures agreement (when 𝑡 < 𝑛 3), con- sider a round in which some process 𝑝𝑖 decides value 𝑣 = 𝑟𝑖 mod 2. Since 𝑝𝑖 receives (�� 𝑡0) echo messages containing only the value 𝑣, we know that every honest process must have value 𝑣 in every possible set of (𝑛 𝑡0) echo messages, and hence every honest process included 𝑣 in its candidate set. Every honest process that only had 𝑣 as a candidate also decided 𝑣. The remaining honest processes must have adopted 𝑣 = 𝑟𝑖 mod 2 as their estimate when they adopted the parity bit of the round. And if all the honest processes begin a round 𝑟 with estimate 𝑣, then that is the only possible decision due to the reliable broadcast bv-broadcast in Phase 1 (see below) and all honest processes decide at round 𝑟 2 or earlier (regardless of whether 𝜏𝐺𝑆𝑇 is reached). / Pro...