Distributed computing

SOME USEFUL NOTATION FOR SUCH PROBLEMS

• Ki – agent i knows.
• CG – common knowledge among group G
• A statement x is common knowledge if
• Every agent knows x.  i Ki x.
• Every agent knows that every other agent knows x.
•  i  j Ki Kj x.
• Every agent knows that every other agent knows that every other agent knows x

• and so on.

• I know x.
• You know that I know x.
• You know that I know
• that you know x…
• …

EXAMPLES

• In coordinated attack problem, when A sends his message.
• KA “A says attack at dawn”
• When B receives that, then
• KBKA “A says attack at dawn”
• However, it is false that KAKBKA “A says attack at dawn”
• This is remedied when A receives the first acknowledge, at which point
• KAKBKA “A says attack at dawn”
• However, it is false that
• KBKAKBKA “A says attack at dawn”
• More knowledge but never common knowledge.

EXAMPLE: RELIABLE AND BOUNDED TIME COMMUNICATION

• If A knows that B will receive any message that A sends within one minute of A’s sending it, then if A sends
• “Attack at dawn”
• A knows that within two minutes
• CA,B “A says attack at dawn”

CONCLUSIONS

• Common knowledge is unattainable in systems with unreliable communication (or with unbounded delay)
• Common knowledge is attainable in systems with reliable communication in bounded time

APPLYING KNOWLEDGE TO SEQUENCE TRANSMISSION PROTOCOLS

• Problem: The two processes are the sender and the receiver.
• Sender S has an input tape with an infinite sequence of data elements (0,1, blank). S tries to transmit these to receiver R. R writes these onto the output tape.
• Correctness: Output tape should contain a prefix of input tape even in the face of errors (safety condition).
• Given a sufficiently long correct transmission, output tape should make progress (liveness condition).

• S

• R

• ….1

• 0

• 1

• 1

• 0

• 0

• 0

• 0

• 1