Syncronization:
- Proparty: a boolian predicate that is evaluted as true or
false.
- Witness: checking a proparty.
- Safty: a Proparty who’s violations have a finite witness.
- Liveness: a Proparty who’s violations don’t have a finite
witness.
- non-safty & non-liveness (NSNL): something that is not purely
one or the other.
- State: Each protocol has a state, in which there are different
variables. In the two general problem the state are (input, message,
decision). They are all binary, except for the decision which can also
accept a NULL value.
- Coordination: multiple proccesses deciding together.
- Agreement: If multiple decide, they have to decide the same
thing.
- Termination: Everyone eventually decides. Notice decides,
it doesn’t have to be an “attack” decision, it can also be the latte r,
no obligations.
- Validity: if not everyone is ready -> you can’t decide to attack
(kinda ruins the point), and if everyone is ready, and nothing was lost,
you cannot decide to not attack (also ruins the point).
- Coordinated Attack: something that achieves Agreement, Termination
and Validity.
- Weak Termination: if nothing is lost -> everyone evantually
decides.
- Unanimous Termination: if any process decides at some point ->
then everyone decides. Notice that no-one deciding does not
contradict this.
Two generals problem
- To prove there is no solution, it’s enough to show that for every
algorithm, there exists a run, such that the algorithm fails for it. The
easiest runs to show it on are the ones where all of the messages fail
to arrive. That is a valid run.
- Important concept for proofs: If all messages are lost,
process A cannot tell the difference between the case where B votes yes
and B votes no. And simillarly for B’s point of view.
- Lemma 1: No protocol solves the coordinated attack problem for the
runs that have all of their messages be lost.
- Lemma 1’: No protocol solves the weak cooridanted attack problem,
such that it doesn’t send any messages before the decision,
where both processes have an input of “ready”.
- The point of Lemma 1’: It’s the base case for an induction proof
that proves, no protocol, with any number of messages can solve the weak
coordination problem.
Broadcasting:
- correct process: a node that never violates the specification at any
point.
+------------------------------------+
| Application Layer |
+------------------------------------+
| ^
broadcast | (API call / downcall) | deliver (Callback / upcall)
v |
+------------------------------------+
| Broadcast Protocol Layer |
| (Buffers, Ordering, Reliability) |
+------------------------------------+
| ^
network | | network
send v | recv
+------------------------------------+
| Physical Network |
+------------------------------------+
- broadcast: It’s the API call to the abstraction layer that is the
broadcast protocol layer.
- deliver: It’s also an API call, executed for every
recipiant, the API layer is the one in charge that it delivers correctly
according to the specification.
- Validity: If someone broadcasts -> evantually everyone gets it.
Agreement: If someone gets it -> evantually everyone gets it.
Integrity: Someone gets only something that was actaully broadcasted and
it gets it only once.
- FIFO order: if a message m was broadcasted and after a message m’
was -> then m must be delivered before m’ for each process that does
the deliverance.
- FIFO Broadcast: Relaible broadcast that is also in FIFO order.
- Causal Broadcast: The order of deliver has to be with the order of
causation of the messages. Causal Order: e -> f means f is caused by
e. So a process executing in that order, or e is a broadcast and f is
delivery, or and order of e -> h and h -> f.
- Causal vs FIFO: FIFO is the order of the same sender, causal on the
other hand is the order of cause and effect between all of the
senders.
- Atomic Broadcast: Reliable one and also atomic, meaning that p
delivers m and m’ in that order if and only if q delivers them
in that order as well.
- How to make an Atomic Broadcast: You need a global
queue.
- notice that for the validity proof -> it’s not uniform validity
-> so we can just start with a correct process that broadcasts the
message -> because it’s a correct process, by definition it won’t
crash and deliver everyone with the message -> therefore everyone
(including the other correct processes) will learn and ack the process
-> every learn that is executed means that that correct process will
ack himself in his set and in every other set -> because of that
every correct process will have the ack of every other correct
process.
- Important to understand that all of the sets are local to each
process.
- At most t crashes, n processes and n > 2t -> t < n/2 ->
therefore if a process has a message with at least n/2 acks,
that means that at least one of them has to be a correct
process -> correct processes are guaranteed to not crash
-> correct processes are guaranteed to have successfully sent the
message data to everyone and add himself to everyones set of acks ->
that means for sure everyone has this message now -> that
includes all of the other correct processes -> that means that
all of the correct processes will run learn on it -> therefore we can
now deliver the message because agreement is met.