A fundamental problem of fault-tolerant distributed computing is for the reliable processes to reach a consensus. For a synchronous distributed system of n processes with up to t crash failures and f failures actually occur, we prove using a straightforward bivalency argument that the lower bound for reaching uniform consensus is (f + 2)-rounds in the case of 0 < f ≤ t −2, and a new lower bound for early-stopping consensus is min (t + 1, f + 2)-rounds where 0 ≤ f ≤ t. Both proofs are simpler and more intuitive than the traditional methods such as backward induction. Our main contribution is that we solve the open problem of proving that bivalency can be applied to show the (f + 2)-rounds lower bound for synchronous uniform consensus. / Singapore-MIT Alliance (SMA)

<p>During task-switching, if we occasionally encounter stimuli that cue more than one task (i.e. bivalent stimuli), response slowing is observed on all univalent trials within that block, even when no features overlap with the bivalent stimuli. This observation is known as the bivalency effect. Here, I show that the bivalency effect reflects a form of top-down cognitive control that is not easily explained by most current models of control in the literature. The research presented within my thesis reveals that the bivalency effect reflects an adjustment in cognitive control that is highly dependent on past experience with response conflict (chapters 4 and 5), violations of expectancy (chapter 3 and 5), and recent inhibition (chapters 3, 4, and 5). Furthermore, the processes in response to these factors are likely captured by the dorsal anterior cingulate cortex (dACC) and the temporal parietal junction (TPJ) (chapters 2 and 5), reflecting responses to inhibitory demands, and extra visual feature extraction after encountering bivalent stimuli, respectively. These findings provide support for a recent cognitive control model that suggests that the role of the ACC is to track current and recent changes in the environment in order to optimize future performance by predicting changes in cognitive demand (Sheth et al., 2012).</p> / Doctor of Philosophy (PhD)