Consider a ring of $n$ nodes numbered $\{0,1,$dots,$n-1\}($but they are not necessarily

arranged in that order$).$ Each node has two binary variables: the input variable $x_i$ and

the output variable $y_i.$ Unlike the agreement problem as defined in class, the output

variable $y_i$ can be updated any number of times.

The goal is to design an algorithm for dynamic agreement, which we define as follows.

Initially, in round $0,$ all nodes i have their $x_i$ and $y_i$ set to $0.$ Only an external adversary

can update the $x_i$ values. At each round, the adversary can choose a subset of the

nodes $($possibly the empty subset$)$ and flip their $x_i$ values. A distributed algorithm that

updates the $y_i$ values according to the following rules is said to solve the $($fault free$)$

dynamic agreement problem on a ring.

Page $2$

Dynamic Agreement. If$,$ for some nodes i and $j,y_i{y}_j$ at some round $r,$ then, there

must exist, a round $y_0=y_1=y_2=$cdots$=y_{n-1}{x}_i{c}_{2}n{y}_{i}r{y}_0=y_1=y_2=$cdots$=y_{n-1}=brEEi{y}_i=1-br+1EE{r}^{\text{'}}r-c_{3}n{r}^{\text{'}}r{x}_0=x_1=x_2=$cdots$=x_{n-1}=1-b{c}_1,c_2{c}_3{r}^{\text{'}},r$ such that $y_0=y_1=y_2=$cdots$=y_{n-1}.$

Dynamic Validity. $If$ all $x_i$ have been $0(resp.,1)$ for some $c_{2}n$ consecutive rounds,

then, all $y_i$ must $be0as$ well $(resp.,1as$ well$).$

Lazy. Consider a round $r$ such that $y_0=y_1=y_2=$cdots$=y_{n-1}=bat$ round $r,$ but EEi

such that $y_i=1-bat$ round $r+1.$ Then, $EE{r}^{\text{'}}$ such that $r-c_{3}n{r}^{\text{'}}r$ when

$x_0=x_1=x_2=$cdots$=x_{n-1}=1-b.$

$(a)$ Design a distributed algorithm $to$ solve the fault free dynamic agreement problem $on$

a ring with $c_1,c_2,$ and $c_3$ being reasonably small $(ideally$ constants$).$ Give a precise

description $of$ your algorithm $in$ pseudocode, a theorem statement specifying the

constants, and a proof. This algorithm must $beas$ simple $as$ possible.

Solution: Write your solution here.

Theorem $1.$ You can slate your theorem $in$ this environment.

Lemma $1.$ And add any lemmas that you need.

$(b)$ Show that the problem $is$ impossible with two crash failures $(chosenby$ the adver$-$

sary$).$ Show a precise adversarial strategy.

Solution: write your solution here.