Distributed computing

MODEL

• Messages are kept in order
• Sender and receiver are synchronous. This implies that sending a blank conveys information.
• Three possible type of errors:
• Deletion errors: either a 0 or a 1 is sent, but a blank is received.
• Mutation errors: a 0 (resp. 1) is sent, but a 1 (resp. 0) is received. Blanks are transmitted correctly.
• Insertion errors: a blank is sent, but a 0 or 1 is received.
• Question: Can we handle all three error types?

POSSIBLE ERROR TYPES

• If all error types are present, then a sent sequence can be transformed to any other sequence of the same length. So receiver R can gain no information about messages that sender S actually transmitted.
• For any two of the three, the problem is solvable.
• To show this, we will extend the transmission alphabet to consist of blank, 0, 1, ack, ack2, ack3.
• Eventually, we will encode these into 0s, 1s and blanks.

ERROR TYPE: DELETION ALONE

• So a 1,0, or any acknowledgement can become a blank.
• Suppose the input for S is 0,0,1…
• For any symbol y, we went to achieve that the sender knows that the receiver has received (knows) symbol y.
• Denote this Ks Kr (y).
• Imagine the following protocol: If S doesn’t receive an acknowledgement, then it resends the symbol it just sent. If S receives an acknowledgement, S sends the next symbol on its tape.
• Scenario: S sends y, R sends ack, S sends next symbol y’.
• Is there a problem?

GOAL OF PROTOCOL

• Yes, there is a problem. Look at this from R’s point of view. It may be that y’ = y.
• R doesn’t know whether S is resending y (because it didn’t receive R’s acknowledgement) or S is sending a new symbol.
• So, R needs more knowledge. Specifically, R must know that S received its acknowledgement. S must know that R knows this.
• We need Ks Kr Ks Kr y. To get this, S sends ack2 to R. Then R sends ack3 to S.

• y

• Ack

• Ack2

• Ack3

• Kr y

• Kr Ks Kr y

• R

• S

• Ks Kr Ks Kr y

• Ks Kr y