9: Reliable Links and Failure Detectors

Channel Assumptions

• Messages should be transported between channels, from source to destination

• Real channels are unreliable

• Fair loss is usually a realistic assumption on channels

Fair Loss

A combination of assumptions that we make about the properties of communication links to provide an accurate modelling mechanism.

Fair Loss Link

Reflects the possibility for explicit retransmission.

Stubborn Link

A link that delivers a message infinitely often.

Fair Loss - Properties

• If a message m is sent infinitely often by p_i to p_j and neither p_i or p_j crash, then m is delivered infinitely often to p_j

• Finite duplication

• No creation

Finite Duplication

If m is sent finitely often by p_i to p_j then m is delivered a finite number of times to p_j.

No creation

No message is delivered unless it was sent.

Stubborn Link - Properties

• Stubborn delivery

• No creation

Stubborn Delivery

If a process p_i sends a message m to a correct process p_j and p_i does not crash, then p_j takes delivery of m an infinite number of times.

Reliable Links (Perfect Links)

Links that make sure a message is successfully sent once.

Reliable Links - Properties

• Validity

  • If p_i and p_j are correct, then every message sent by p_i to p_j is eventually delivered to p_j

• No duplication

• No creation

Timing Assumptions

• Processing speeds of processes (process asynchrony)

• Transmission speeds of messages (channel asynchrony)

Types of System Model

• Synchronous

• Partially Synchronous

  • Asynchronous

Synchronous System Model - Properties

• Processing - the time it takes for a process to execute a step is bound and known.

• Delays - there is a known upper bound on the time it takes for a message to be received.

• Clocks - the drift between local clock and global real time clock is bounded and known.

Partially Synchronous System Model - Properties

• Timing bounds eventually hold, but you never know when

Asynchronous System Model - Properties

• No assumptions - challenging to design for

• While one process takes one step, any other process can take any unbounded (but still finite) number of steps

Failure Detector

An abstraction that allows us to encapsulate timing assumptions for distributed systems, providing processes suspicions about crashed processes.

Failure Detector - Example

Timeouts - uses timing assumptions and failure detection.

Perfect Failure Detector - Properties

• Strong completeness

• Strong accuracy

Strong completeness

Eventually every process that crashes is permanently suspected by every correct process.

Strong Accuracy

No process is deteced by any process before it crashes.

Eventually Perfecy Failure Detector - Properties

• Strong completeness

• Eventually strong accuracy

Failure Detector - Algorithm

• Processes periodically exchange heartbeat messages

• A process sets a timeout based on the worst case round trip of a message exchange

• A process suspects another process if a timeout expires relating to that process

• A process that delivers a message