Distributed computing

EXERCISE

• Suppose that the symbol after y is y’ and y’  y.
• Then can S send y’ as soon as it receives ack to y? (Assume R has a way of knowing that it received y and y’ correctly.)
• S sends y
• R sends ack
• S sends y’
• R sends ack …

• y

• Ack

• y’

• Kr y

• Kr y’; Kr Ks Kr y

• R

• S

• Ks Kr y

ENCODING PROTOCOL IN 0’s and 1’s

Protocol Symbol	Encoding
Blank	11
0	00
ack	0
1	01
ack3	1
ack2	10

• WHAT IS SENT

• S

• R

• 0

• 1

• blank

• ack2

• 0

• 1

• ack

• ack3

• 10

• 00

• 01

• 11

• WHAT IS SENT

WHAT DO WE WANT FROM AN ENCODING?

• Unique decidability. If e(x) is received uncorrupted, then recipient knows that it is uncorrupted and is an encoding of x.
• Corruption detectability. If e(x) is corrupted, the recipient knows that it is.
• Thus, receiver knows when it receives good data and when it receives a garbled message.

ENCODING FOR DELETIONS AND MUTATIONS

• Recall that mutation means that a 0 can become a 1 or vice versa.
• Encoding (b is blank)

Protocol Symbol	Encoding
Blank	bbb1
0	1bb b
ack	1b
1	b1b b
ack3	b1
ack2	bb1 b

• The same extended alphabet protocol will work.
• Any insertion will result in two non-blank characters. A mutation can only change a 1 to a 0.

• Note:

• S

• S

• S

• R

• R

• R

• ack

• ack2

• ack3

Exercise for you

• Suppose we had deletion errors (1 becomes blank or 0 becomes blank) and insertion errors (blank becomes 0 or blank becomes 1), but no mutation errors (so 1 never becomes 0 and 0 never becomes 1).
• Now try mutation and insertion.

Self-Stabilizing Systems

• A distributed system is self-stabilizing if, when started from an arbitrary initial configuration, it is guaranteed to reach a legitimate configuration as execution progresses, and once a legitimate configuration is achieved, all subsequent configurations remain legitimate.

Self-Stabilizing Systems (using invariants)

• There is an invariant I which implies a safety condition S.
• When failures occur, S is maintained though I may not be.
• However when the failures go away, I returns.
• http://theory.lcs.mit.edu/classes/6.895/fall02/papers/Arora/masking.pdf