Samenvatting
Summary Tentamen voorbereiding - Distributed Algorithms (X_400211)
Alle belangrijke termen, formules, voorbeelden en feiten die je moet kennen voor het tentamen voor Distributed Algorithms.
[Meer zien]Voorbeeld 3 van de 27 pagina's
Voorbeeld 3 van de 27 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
VolgenVoorbeeld van de inhoud
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:
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper sandervanwerkhooven. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 53068 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen