Distributed System Models

Fail-stop
Process abstraction: crash-stop process.
Link abstraction: perfect link.
Failure detection: perfect failure detector.

Fail-silent
Process abstraction: crash-stop process.
Link abstraction: perfect link.
Failure detection: no failure detector.

Fail-noisy
Process abstraction: crash-stop process.
Link abstraction: perfect link.
Failure detection: eventually failure detector.

Leader Election

Leader Election
Properties:
Either there is no correct process, or some correct process is eventually the leader.
If a process is leader, then all previously elected leaders have crashed.

Eventual Leader Election
Properties:
Eventual accuracy: There is a time after which every correct process trusts some correct process.
Eventual agreement: There is a time after which no two correct processes trust different correct processes.

Failure Detection

Perfect Failure Detection
Properties:
Strong completeness: Eventually every process that crashes is permanently detected by every correct process.
Strong accuracy: If a process p is detected by any process, then p has crashed.

Eventually Perfect Failure Detection
Properties:
Strong completeness: Eventually, every process that crashes is permanently suspected by every correct process.
Eventual strong accuracy: Eventually, no correct process is suspected by any correct process.

Logical Clock

Measure the passage of time in an asynchronous distributed system:
• Each process p keeps an integer called logical clock lp, initially 0.
• Any time an event occurs at process p, the logical clock lp is incremented by one unit.
• When a process sends a message, it timestamps the message with the value of its logical clock at the moment the message is sent and tags the message with that timestamp. The timestamp of event e is denoted by t(e).
• When a process p receives a message m with timestamp lm, p incrementsits timestamp in the following way: lp = max(lp, lm) + 1.

happened-before relation (e1 → e2):
We say that an event e1 may potentially have caused another event e2, denoted as e1 → e2, if the following relation applies:
• e1 and e2 occurred at the same process p and e1 occurred before e2.
• e1 corresponds to the transmission of a message m at a process p and e2 to the reception of the same message at some other process q.
• there exists some event e such that e1 → e' and e' → e2.

If the events are timestamped with logical clocks, then e1 → e2 ⇒ t(e1) < t(e2). The opposite implication is not true.

Communication Abstraction

Fair-Loss Links
Properties:
Fair-loss: If a message m is sent infinitely often by process pi to process pj, and neither pi nor pj crash, then m is delivered an infinite number of times by pj .
Finite duplication: If a message m is sent a finite number of times by process pi to process pj, then m cannot be delivered an infinite number of times by pj.
No creation: If a message m is delivered by some process pj, then m was reviously sent to pj by some process pi.

Stubborn Links
Properties:
Stubborn delivery: Let pi be any process that sends a message m to a correct process pj. If pi does not crash, then pj delivers m an infinite number of times.
No creation: If a message m is delivered by some process pj, then m was previously sent to pj by some process pi.

Perfect Links
Properties:
Reliable delivery: Let pi be any process that sends a message m to a process pj. If neither pi nor pj crashes, then pj eventually delivers m.
No duplication: No message is delivered by a process more than once.
No creation: If a message m is delivered by some process pj, then m was previously sent to pj by some process pi.

Liveness and safety

Safety: Nothing bad happens.
Liveness: Something good eventually happens.

Example: Tell the truth!
Having to say something is liveness.
Not lying is safety.