[cs63201] Exam Studying - check in

[Mikhail Nesterenko]

> In any case, you have my homework, so that will give you an idea of my
> current understanding of the algorithm; is it actually correct? Or did I
> goof up big time on a piece of how it works? I'm mainly very confused on
> the synchronization of it all; the algorithm is asynchronous, but the
> "wait" stipulation throws me off a little. Is a process frozen in wait for
> each other it doesn't suspect until it receives their message? Are other
> processes therefore frozen until they reply since they must then eventually
> hear back from the waiting process? In my HW, I think I assumed sort of
> not, where the very first process to send its message finishes the round
> without receiving anything. Otherwise, it seems to me everything tends to
> happen in one round?

Yes, both algorithms are asynchronous. "wait" means waiting for a
message. In the two algorithms the statement is

	 wait for a message or get the output from the detector
	 that the sender is suspected to have crashed.

Both S and diamond S guarantee completeness. This means that if the
process crashes, then the detector eventually outputs suspicion. This
means that no process gets blocked on the above statement: either the
sender is correct, in which case the receiver gets the message or the
sender crashed in which case the detector suspects it.

Now, the detector may inaccurately suspect a correct process. In case
of S, it is guaranteed that there is a single correct process, in the
paper it is referred to as "c", that is never suspected. In case of
diamond S, the existence of such correct process is guaranteed only
eventually. 

The two algorithms in Chandra and Toueg's paper differ by their power.
The algorithm with S solves consensus with arbitrary number of crashed
processes. The algorithm with diamond S requires that the majority of
the processes remain correct.

Thanks,
--
Mikhail