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.

Algorithm for uniform agreement explenation:

  • 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.