Distributed computing

WILL IT EVER END?

• ack your ack

• ack your ack to my ack

• A

• A

• B

• B

IT NEVER ENDS

• Theorem: Assume that communication is unreliable. Any protocol that guarantees that if one of the generals attacks, then the other does so at the same time, is a protocol in which necessarily neither general attacks.
• Have you ever had this problem when making an appointment by electronic mail?

• 10 AM?

• OK

• A

• A

• B

• B

• But will he show up?

BACK TO COMPUTERS

• While ostensibly about military matters, the Two Generals problem and the Byzantine Agreement problem should remind you of the commit problem.
• In all three problems, there are two possibilities: commit (attack) and abort (don’t attack).
• In all three problems, all sites (generals) must agree.
• In all three problems, always aborting (not attacking) is not an interesting solution.
• The theorem shows that no non-blocking commit protocol is possible when the network can drop messages.
• Corollary: If the decision must be made within a fixed time period, then unbounded network delays prevent the sites from ever committing.

ROAD MAP: KNOWLEDGE LOGIC AND TRANSMISSION

• Knowledge Logic and Transmission.
• Common knowledge is unnecessary.

• Knowledge Logic:
• consensus

• Failures of all types

BASIC MODEL FOR KNOWLEDGE LOGIC

• Each processor is in some local state. That is, it knows some things.
• The global state is just the set of all local states.
• Two global states are indistinguishable to a processor if the processor has the same local state in both global states.