P$2.(30$ points$)$ A recovery point is a set of consistent checkpoints in a distributed system. Consider the computation shown below. P$0$ to P$3$ are four check$-$pointed processes. Checkpoints are shown by the vertical filled bars. All checkpoints are named as Cix where i is the process number and x $=\{0,1,2,....\}$ is the checkpoint number for process Pi for i $=0$ to $3.$

The computations performed for each process between two checkpoints are named. Aj$,$ Bj$,$ Cj$,$ and Dj for j$=\{0\mathrm{.}1\mathrm{.}2\mathrm{.}3....)$ denote the computations performed for processes P$0,$ P$1,$ P$2,$ and P$3$

between the two checkpoints sequentially, as shown below. Messages are named mi for

i$=0,1,2,......$ etc. The time between the two consecutive checkpoints for each process is also

known. Computation names and time taken for each computation $($interval between two

checkpoints$)$ are shown below for all processes.

These processes are executed on a computer system with two computing nodes, E$0$ and E$1,$

where processes P$0$ and P$1$ are run on computer node E$0,$ and processes P$2$ and P$3$ are run on

computer node E$1.$ The two processes on a node run sequentially, one computation at a time,

and the scheduler alternates between the two processes and switches from one to another

after each checkpoint. Thus, node E$0$ will execute A$0,$ B$0,$ A$1,$ B$1,...,$ and so on$.$ Similarly,

computer E$1$ computes C$0,$ D$0,$ C$1,$ D$1,....,$ etc. Messages are handled appropriately. Also, note

that messages m$4$ and m$9$ are sent at times t$=11$ and t$=12$ in the original sequence.

$($a$)$ Draw the computation on a timeline for each computing node, marking message

exchanges, the computation performed, and the time taken clearly. Some computations

may have to wait$/$delay due to sequencing issues. Clearly mark the wait points and times.

$($b$)$ Consider two cases of failures of nodes E$0$ and E$1,$ one at a time. Assume that in each case,

failure occurs at t$=26.$ How will the computation roll back for each failure?