Summary
Summary Exam Preparation - Distributed Algorithms (X_400211)
- Course
- Institution
All the important terms, formulas, examples, and facts you need to know before the Distributed Algorithms exam.
[Show more]
Seller
Followsandervanwerkhooven
Content preview
Lecture 1.1. FoundationsDistributed systems differ from uniprocessor systems in three aspects:
- Lack of knowledge on the global state: A process has no up-to-date knowledge on
the local states of other processes. E.g., they don’t know about each other’s
termination and deadlock states.
- Lack of a global time frame: Concurrent may happen at different processes in any
order. E.g., mutual exclusion becomes a problem.
- Nondeterminism: Different executions of the same system can give different results.
E.g., race conditions are introduced.
Asynchronous communication means that the sending and receival of a message are two
different independent events. With synchronous communication, they are coordinated to
form one single event.
Unless stated otherwise, we make the following assumptions:
- The network N is strongly connected. That is, any node n ∈ N is reachable from any
other node n' ∈ N .
- Each process is only aware of its direct neighbors. And thus, lacks knowledge on the
rest of the network graph.
- Communication happens asynchronously.
- Channels do not lose, duplicate, or garble messages. Communication protocols are in
place to prevent and correct this.
- The delay of messages in channels is arbitrary, but finite. That is, any message will
arrive at its destination at some point.
- Channels can be non-FIFO. That is, messages can overtake each other, and the order
of sending does not necessarily equal the order of receival.
- The network is stable, and processes do not crash.
- Each process has a unique identifier ID.
A channel can be unidirectional, when it only allows message passing in one direction
(directed network), or bidirectional, when it allows messages to flow in either direction
(undirected network). An undirected network is required if:
- The algorithm in question requires acknowledgements.
- The network topology is acyclic. Otherwise, it would not be strongly connected.
Now follows a formal framework to describe distributed systems:
- The (global) state of a distributed network is called a configuration. A configuration is
made up of:
1. The local states of its processes.
2. The messages in its channels.
- The configuration evolves in discrete steps, called transitions. Transitions are
associated to events occurring at some process. A process can perform internal,
send, and receive events. A process is an initiator if its first event is an internal or
send event. In that case, it does not need to wait for another process to start up.
Moreover, an algorithm is centralized if there is exactly one initiator. In case of
multiple initiators, the algorithm is called decentralized.
, - A transition system consists of:
o A set C of configurations.
o A binary transition relation →.
o A set of I ⊆C of initial configurations.
- A configuration γ ∈C is terminal if γ →δ does not exist for any δ ∈ C .
- An execution is a sequence of configurations y 0 y 1 y 2 … that is either infinite, or ends
in a terminal configuration, such that:
o γ 0 ∈ I . That is, it starts in some initial configuration.
o γ i → y i+1 . That is, there exists a transition relation between any two
consecutive configurations, except for the terminal configuration, if the
execution is finite.
- A configuration δ is reachable if there exists a γ o ∈ I and a sequence γ 0 γ 1 … γ k , such
that y k =δ .
An assertion is a predicate on the configurations of an algorithm. We distinguish two types of
assertions:
- A safety property is a statement that is true in each configuration of each execution.
E.g., something bad will never happen.
- A liveness property is true is some configuration of each execution. E.g., something
good will always happen eventually.
An assertion P is an invariant if:
- P( γ) holds for any initial configuration γ ∈ I .
- If γ →δ and P(γ ), then P(δ).
Note that each invariant is a safety property.
The causal order ≺ between two occurrences of events denotes:
- If a and b are events at the same process and a occurs before b , then a ≺b .
- If a is a send event and b is the corresponding receive event, then a ≺ b .
If neither a ≼b nor a ≽ b , then a and b are concurrent events. A permutation of concurrent
events in an execution does not affect the result of the execution.
All possible permutations together form a computation. All executions of a computation
start in the same initial configuration. And if they are finite, they all end in the same terminal
configuration. E.g., for the finite execution abc with a ≺b , the computation is formed by
{abc , acb , cab }.
This causal relationship is used in logical clocks, that attempt to form a global real-time clock
by mapping occurrences of events in a computation to a partially ordered set such that
a ≺b ⇒ C ( a ) <C (b), with C (x) denoting the logical clock value of event x .
Lamport's clock LC assigns to each event a as clock value the length k of a longest causality
chain a 1 ≺… ≺ a k, with a k =a .
LC values can be computed at runtime, to be used during execution. Every message must
carry the clock value of its send event. Then, at a process with clock value k :
- If a is an internal or send event, LC ( a )=k +1 .
- If a is a receive event, and b is the corresponding receive event,
LC ( a )=max { k , LC ( b ) } +1.
, Given processes p0 , … , p N −1 , the vector clock VC maps each event in a computation to a
value in N N such that a ≺b ⇒VC ( a ) <VC ( b) . Because a clock value now contains N
numbers, the partial order is defined a little differently: ( k 0 ,… , k N−1 ) ≤ ( l 0 , … , l N −1 ) ⇔k i ≤l i for
all 0 ≤ i< N . The vector clock value VC ( a )=( k 0 , … , k N −1) where each k i is the length of the
i i i
longest causality chain a 1 ≺ … ≺a k of events at process pi with a k ≼ a .
i i
Just like with Lamport’s clock, these values are also computable at runtime. Let a be an event
at a process pi, and (k 0 , … , k N−1 ) the clock value of the previous event at pi (or (0 , … , 0) in
case of the first event).
Lecture 1.2. Snapshots
A snapshot of an execution of a distributed algorithm aims to return a configuration of this
execution. Snapshots consists of:
- A local snapshot of the state of each process.
- The channel state of messages in transit for each channel.
They have multiple use cases, like:
- Restarting after a failure or crash.
- Debugging purposes.
- Off-line determination of stable properties, which remain true as soon as they have
become true, like deadlocks or garbage collection.
We distinguish basic messages of the underlying distributed algorithm and control messages
of the snapshot algorithm. The snapshot only contains basic messages and state.
The two challenges of taking snapshots are:
1. Being able to take one without having to freeze the basic execution.
2. Take a meaningful snapshot. A snapshot is meaningful if it captures a configuration of
an execution in the same computation as the actual execution. In order to do this, we
have to avoid the following situations:
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller sandervanwerkhooven. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.88. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
53068 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now