deletions | additions       diff --git a/section_6_19_subsection_a__.tex b/section_6_19_subsection_a__.tex  index 20b47b2..e71a1de 100644  --- a/section_6_19_subsection_a__.tex  +++ b/section_6_19_subsection_a__.tex 
...
\section*{6.19}  \subsection*{a}  Consider %Consider  three equal-sized sets of odd, even, and flip agents; the odd agents initially prefer 1, the even agents initially prefer 0, and the flip agents change preferences depending on run. Consider two runs $r_1$ and $r_2$. In run $r_1$, the environment blocks all message receives by flip agents of messages from even agents, and all message sends of flip agents to even agents; in this run, the flips prefer 0. In run $r_2$, the environment blocks all sends from even agents to flip agents, and all receives at even agents of messages sent by flip agents; in this run, flip agents prefer 1. Consider the protocol $P$ in which all agents broadcast their initial preference to all other agents every round, and after $2t$ rounds agents simultaneously decide on the majority-preferred value among the messages they received, deciding on 0 in the case of a tie. As the only agents whose preferences change between $r_1$ and $r_2$ are flip agents, and no messages from flip agents reach even agents in either $r_1$ or $r_2$, the same messages are received by all even agents in both runs. It follows immediately that the local state of even processes are the same in runs $r_1$ and $r_2$ at all steps $m$. Let $i$ be some even agent. As $i$ is non-faulty in run $r_1$, it must decide on a value; as the local state of $i$ is identical at each step in $r_1$ and $r_2$, it follows that $i$ will also decide on the same value in run $r_2$, having the same local state at decision time. It %It  is clear from the protocol definition that $i$, having received an equal number of 1 and 0 preferences by round $2t$, will decide on 0 in both runs. In run $r_2$, flips receive only 1 preferences, and odds receive one 0 preference and two 1 preferences; thus flips and odds decide 1, as it is either tied for most-popular or definitively most-popular. In run $r_1$, flips receive 1 and 0, the odds receive 0, 1, 0, and the evens receive 0, 1; in this case, it is clear that all three partitions will decide 0. It %It  remains to show that the proposed protocol $P$ achieves SBA in all cases. We focus on the small instance involving three agents. To do this, we must check the SBA properties. $Decision$, $Validity$, and $Simultanaeity$ all follow immediately; there is a defined round on which the (single) decision is made, and as the decision is a majority-vote it is clear that if all agents prefer the same value it will be the majority. What %What  we know - focusing on the 3-case. Two of the agents need to maintain the same preference and send that preference to agent i; agent i must be one of these two agents. all failures in which there is a fail/nofail decision split must occur only when more than one link goes down - otherwise we could just be in the symmetric case, and have a nofail/nofail split. Consider I'm effectively setting up $i$ to fail here by baking into  the following devious case. There is protocol the fact that nodes are going to lie. It's not byzantine when it's part of the protocol!   I assume that we have some SBA protocol $P$, and construct a new "devious" protocol $P'$ in which the problem's desired constraints are satisfied. In the beginning of $P'$, we elect  a distinguished node N agreed upon by $i$ via  some consensus protocol. SBA-compliant leader-election protocol built off of $P$. Once the identity of $i$ is common knowledge, the protocol shifts radically.  For the first few next $k$  rounds, N $i$  broadcasts its initial  preference while the remaining to all nodes. After $k$ rounds, all non-$i$  nodes attempt broadcast a message  to determine if N all other non-$i$ nodes indicating whether they believe $i$  is faulty. If they *can* tell both that N They believe $i$  is faulty if, during the $k$ rounds of broadcast, they received fewer than $k$ messages from $i$. After this, the non-$i$ nodes will once again run $P$, except this time proposing "faulty" if they received "faulty" from a strict majority of total nodes,  and proposing "not faulty" otherwise. If the result of this SBA iteration is "faulty," we will say  that N desires $i$ is known to be faulty. Once this vote is complete, nodes run $P$ again to determine the final SBA result x; this time, nodes propose $i$'s  value x, if  they collude. They agree know it. After this value has been agreed, nodes enter a final "devious" iteration of $P$. In this iteration, all non-$i$ nodes prefer x, while $i$ retains its initial preference; in this round, we SBA  to lie y. After this round, if $i$ was known among non-$i$ nodes  to process N by saying that their initial preference is x, be faulty, all non-$i$ nodes decide $\neg$ x. If $i$ was not known among non-$i$ nodes to be faulty,  all nodes decide y.  Why this is correct - at every stage,  the while agreeing amongst themselves that resultant value is confirmed through a run of SBA; this should prevent any fiddly edge cases with consensus splits.  Now we consider the two runs $r_1$ and $r_2$ in which $i$ has  the same local state 0 and decides the same  value they 0, but in which the correct nodes  decide on will be ~x. If they *can't* tell that N two different values. In both $r_1$ and $r_2$, all initial preferences are identical. Also in both runs, the environment chooses not to interfere until after $i$ has been elected; thus $r_1$ and $r_2$ are entirely identical until the beginning of the broadcast step.  In run $r_1$ where $i$  is faulty but *can* tell that N desires value x, they non-faulty, the environment chooses not to intervene at all; because of this,  all nodes discover $i$'s preference of 0 during the $i$-broadcast step, discover $i$ to be non-faulty during the referendum step,  proposex as their preferred value  and decide agree  on x. If 0 during the pre-sba step, and once again propose and agree on 0 during the final step.   IN run $r_2$ where $i$ is faulty, the environment chooses only to block a single message from $i$ to each other agent during the broadcast step. Thus during the referendum all agents vote for $i$ being faulty; $i$ is thus declared faulty. During the pre-sba step, as all agents know $i$'s preference  they can't tell what N desired, propose and agree on 0 once again. During the final step,  theyjust  propose and agree on 0 as before (in fact it's the exact same trace); except this time,  their initially-preferred value. final decide action decides 1. All except $i$, who incorrectly decides 0.  It's easy to see that $i$'s state is the same across both runs; the initial election and the final referendum are the only components of the protocol during which $i$ receives messages, and the messages were identical across both runs during those components.