Distributed computing

Self-Stabilizing Systems components

• A corrector returns a program from state S to I: e.g. error correction codes, exception handlers, database recovery.
• A detector sees whether there is a problem: e.g. acceptance tests, watchdog programs, parity ...

Self-Stabilizing Systems example

• Error model: messages may be dropped.
• Message sending protocol called the alternating bit protocol, which we explain in stages.
• Sender sends a message, Receiver acknowledges if message is received and uncorrupted (can use checksum).
• Sender sends next message.

Alternating Bit Protocol continued

• If Sender receives no ack, then it resends.
• But: What if receiver has received the message but the ack got lost.
• In that case, the receiver thinks of this as a new message.

Alternating Bit Protocol -- we’ve arrived.

• Solution 1: Send a sequence number with the message so receiver knows whether a message is new or old. Receiver still acks.
• But: This number increases as the log of the number of messages.
• Better: Send the low order bit of the sequence number. This is the alternating bit protocol.
• Invariant: Output equals what was sent perhaps without the last message.

Why is this Self-Stabilizing?

• Safety: output is a prefix of what was sent even in the face of failures (provided checksums are sufficient to detect corruption).
• Invariant: (Output equals what was sent perhaps without the last message) is a strong liveness guarantee.

Exercise: what do sender/receiver know at each stage of protocol

• When sender receives ack?
• When receiver receives a message with low order bit?

MQ Series a reliable transmission protocol

• Idea is to guarantee that a message that is sent is received exactly once.
• Sender deposits a message at a queue manager and the queue manager ensures that the message arrives exactly once at the receiver.
• How can this be made to work?
• Assume: fail-stop failures (stable storage does not fail).