Distributed Abstractions

Last updated Jan 31, 2023 Edit Source

The basic building blocks of any distributed system is a set of distributed algorithms. which are implemented as a middleware between network (OS) and the application.

The distributed computing model consists of a set of processes and a network. Events can be used as messages between components of the same process, which trigger event handlers. Types of events

• Requests: incoming to component
• Indications: outgoing from component

A distributed system specification includes the interface, correctness properties and model/assumptions.

This specifies the API, importantly, the requests and events of the service

Any trace property can be expressed as a conjunction of Safety and Liveliness properties.

Processes that do not fail in an execution are correct.

Process is not correct if it stops taking steps like sending and receiving messages.

Process is not correct if it omits sending or receiving messages

• Send omission: not sending messages according to algorithm
• Receive omission: not receiving messages that have been sent to the process

Process is not correct if it crashes and

• never recover, or
• recovers an infinite number of times

May recover after crashing with a special recovery event automatically generated

Process behaves arbitrarily such as sending messages not in its algorithm, or behave maliciously attacking the system. Model B is a special case of model A if a process that works correctly under A, also works correctly under B.

• Crash is a special case of omission where all messages are omitted.
• Omission is a special case of crash-recovery, as it recovers but does not restore state
• Omission == Crash-recovery: where access to volatile memory means some messages after a crash are omitted as it cannot be restored

A quorum is any set of majority processes (i.e. $\lfloor N/2\rfloor+1$)

• Two quorums always intersect in at least 1 process
• There is at least 1 quorum with only correct processes
• There is at least 1 correct process in each quorum

Channels delivers any message sent with non-zero probability (no network partitions)

Channels delivers any message sent infinitely many times

We can implement stubborn links using fair loss links

• sender stores every message it sends in sent
• periodically resends all messages in sent

Channels that deliver any message sent exactly once.

Processes: bounds on time to make a computation step
Network: Bounds on time to transmit a message between a sender and a receiver
Clocks: Lower and upper bounds on clock rate-drift and clock skew w.r.t. real time

Asynchronous systems: no timing assumption on process and channels Partially synchronous systems: eventually every execution will exhibit synchrony Synchronous systems: build on solid timed operations and clocks

In the asynchronous model, we can only reason about the order of events by observing which events may cause other events.

A permutation of the same collection events whilst preserving causal order are said to be equivalent.

A logical clock is an algorithm that assigns a timestamp to each event occurring in a
distributed system. $$if \\ a\rightarrow b, t(a)<t(b)$$

• Note that this does not mean that $t(a)<t(b) \implies a\rightarrow b$. Lesser timestamps does not necessarily mean they are causally related We need to distinguish the total order of events for same timestamps across different processes.

We want to tell the causal relation using the timestamps. $$ \begin{align} v(a) < v(b), then\\ a\rightarrow_\beta b \\ if\\ a\rightarrow_\beta b,v(a)<v(b) \end{align} $$ Limitations

• Vectors need to be defined of size n
• cannot provide total event ordering

If two executions F and E have the same collection of events, and their causal order is preserved, F and E are said to be similar executions, written F~E

# Failure Detectors