Samenvatting
IN4150 Distributed Algorithms - Summary
This PDF is a cheatsheet (but cannot be used during the exam) containing all relevant information very densely presented.
[Meer zien]Voorbeeld 1 van de 4 pagina's
Voorbeeld 1 van de 4 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
Volgen
Voorbeeld van de inhoud
CHAPTER 1 – INTRODUCTIONA distributed system (DS) consists of multiple autonomous processors that do not share memory, but cooperate by sending messages over a communications network.
DS characteristics: • Autonomy (distribution of authority) • Cooperation (distribution of functionality) • Communication (distribution of information)
DS properties: • No regular structure (need protocols) • No directly accessible common state (maintain a logical common state by message passing)
• No common clock (synchronize through message passing) • Non-determinism (individual progress) • Independent failure modes
DS motivations: • Organizational • Resource sharing • Extensibility • Availability • Reliability • Security • Performance
DS requirements: • Transparancy (a DS should present itself as a single entity) • Scalability (capacity should proportionally increase) • Consistency (in terms of performance, UI, global state)
Parallel vs. distributed: • Small vs. large task granularity • Frequent (ms scale) vs. infrequent (min scale) communication • Homogenous vs. heterogenous tasks • Simultaneous vs. synchronized
execution • Homogenous vs. heterogenous hardware
In general, DSs are relevant to the transport layer of the seven-layer OSI-model, which is concerned with the communication between processes. When we discuss DAs for specific interconnection
structures (e.g. unidirectional rings, complete networks) we base ourselves on the network layer. When we want distributed algorithms to be resilient to link failures, we’re talking link layer.
Important techniques: • Replication • Caching • Locality • Time stamps • Timeouts • Randomization
CHAPTER 2 – MODELING
A DS is modeled as a set – a connected network – of processors/processes connected by unidirectional communication channels/links that do local computations, send messages, and receive messages.
The set of values of all its variables constitute the state of a process. Initial states and terminal states are subsets of states. Messages sent along the channel that have not yet been received contitute the
state of a channel (initially empty). A configuration of a DS is a set of simultaneous states of all its processes and channels.
An event e1 takes a DS from one state to the next. An execution of a DA in an asynchronous system is an alternating sequence of configurations and events with all processes and channels.
Asynchronous communication Synchronous communication
Non-blocking send, receive message is later than send message, receive may block or not. Send and receive message simultaneously (both blocking), never messages in transit.
Simulating a synchronous system: requires explicit acknowledgements to force the sender Simulating an asynchronous system: introduce for every link a process with a buffer that
only to continue when the message has been received. may introduce artificial delays for messages
In an asynchronous system: • message delays are finite but arbitrary • the relative processor In a synchronous system: • message delays are bounded • the relative processor speeds are
speeds may be unbounded • there is no common clock bounded • there is a common clock
Event-driven: an asynchronous DA consists of pieces of code, one for the receipt of each Time-driven: a synchronous DA consists of rounds.
message type, and possibly for internal events.
0
Simulations make a system/model behave differently through a software layer, i.e. suppose you have a DA A on model M , model M is more complicated (e.g., may exhibit errors), design a simulation
0 0
(protocol) P for M to let M behave like M , run A on top of P .
0
In a local simulation M with P looks like M to every process in the system, but to an outside observer there may be a difference (e.g. processes can be in different rounds).
In a global simulation there is no difference also to an outside observer.
A symmetrical DA has identitical processes. A uniform network/DA has its nodes not know the number of nodes. A anonymous network/DA doesn’t have node IDs.
CHAPTER 3 – SYNCHRONIZATION
Three types of events: • internal eventsS • message-send events • message-receive events
Set of events in Pi : Ei (total set E = E
i i )
The happened-before relation (HB-relation) (or causality relation, →) on E is the smallest relation satisfying:
– local order: if a, b in Ei , and a occurs before b, then a → b
– message exchange: if a in Ei is the event of sending a message m and b in Pj is the event of receiving m, then a → b
– transivity: if a → b and b → c, then a → c
If neither a → b nor b → a holds, then a and b are concurrent (notation: a||b).
Causal past (history) of an event a: P (a) = {b ∈ E|b → a}. Causal future of an event a: F (a) = {b ∈ E|a → b}. Events concurrent with a: C(a) = {b ∈ E|a||b}. E = P (a) ∪ C(a) ∪ F (a).
A logical clock is a function C : E → S (where S is some partially ordered set) which
– is consistent with the HB relation if a → b, then C(a) < C(b) (converse may not hold)
– characterizes the HB relation if C(a) < C(b) iff a → b
Sufficient conditions for a local logical clock Ci :
– if a and b in Ei and a → b, then Ci (a) < Ci (b)
– if a is the event of sending message m in Pi and b is the event of receiving m in Pj , then Ci (a) < Cj (b)
Scalar clocks Vector clocks
If a ∈ Ei is not a message-receive event, then Pi first increments Ci (e.g. by 1) and then Comparing two vector clocks v , w :
sets C(a) to the new value of Ci . – v = w iff v[i] = w[i] for all i
If a is sending m in Pi and b is receiving m in Pj , then Pi sends C(a) with m, Pj assigns – v ≤ w iff v[i] ≤ w[i] for all i (Similar for ≥)
Cj = max(Cj + 1, C(a) + 1) and C(b) = Cj . – v < w iff v[i] ≤ w[i] for all i and v 6= w (Similar for >)
A scalar clock cannot characterize the HB relation. Component-wise maximum: max(v, w)[i] = max(v[i], w[i])
Unit vector in dimension i: ei = (0, 0, ..., 0, 1, 0, ..., 0)
If a ∈ Ei is not a message-receive event, then Pi first increments Vi [i] by 1 and then sets
V (a) to the new value of Vi .
If a is sending m in Pi and b is receiving m in Pj , then Pi sends V (a) with m, Pj assigns
Vj = max(Vj + ej , V (a)) and V (b) = Vj .
a||b if V (a)[i] > V (b)[i] and V (a)[j] < V (b)[j] for any i, j .
Vector clocks do characterize the HB relation. Theorem: For a k-dimensional vector clock
to characterize the HB relation in a system with n processes, we need k ≥ n.
Synchronizers
Synchronizers are local simulations that allow running non-fault-tolerant synchronous algorithms (rounds of sending messages, performing local computations, and receiving messages) on asynchronous
systems, by letting the processes proceed in (simulated) rounds, checking whether all messages of a round have been received, and then letting a synchronizer generate a ”clock pulse”. But when to
clock? After all, a process has no (direct) way of knowing when it has received all messages, as delays are unbounded.
Method 1: Using acknowledgements Method 2: Always send one message to each neighbour
A node is safe with respect to a certain pulse if each of its messages has been received, Pack multiple messages into one; send an empty message in case nothing needs to be sent. A
determined by an ACK from each of its recipients. A safe node sends a SAFE message to its node knows that it has received all its messages in a pulse when it has received one message
neighbors. Then, a node knows that it has received all its messages in a pulse when all its from each of its neighbors.
neighbors are safe.
Awerbuch’s three types of synchronizers:
• α-synchronizers: communication-inefficient, time-efficient
Basically method 1. A node generates a new local pulse after receiving a SAFE message from all its neighbors.
• β -synchronizers: communication-efficient, time-inefficient
Init: Elect a leader s and create a spanning tree rooted at s. When a node finds it is safe and all its descendants are safe, it sends a SAFE message to its parent. When the root gets a SAFE
message from all its descendants and is safe, it sends a new PULSE message down the tree.
• γ -synchronizers: efficiency depends on the original graph and the cluster partitioning
Init: partition nodes into clusters, elect leaders per cluster, create spanning tree per clusters, create a preferred link between each pair of clusters.
β –synchronizer is executed in every tree/cluster. When a root knows its whole tree is safe, it broadcasts a CLUSTER SAFE message down its tree and across the preferred links. Nodes
convergecast READY messages upwards when they have received a READY message from each of its descendants and a CLUSTER SAFE message along all its preferred links.
Message Ordering
0
In non-FIFO asynchronous systems, applications sometimes need message ordering (can be seen as a simulation). For every process P , assume an additional P that checks whether the arriving
0
messages can be delivered to P according to the required order. If not, P stores the message in a buffer, and re-checks when messages that arrive later have been delivered. This means reception (at
P 0 ) and delivery (at P ) are distinct.
Set of destinations of message m is denoted by Dest(m). The event of multicasting m is denoted by m(m). The event of delivering m to Pi is denoted by di (m).
Message order is causal when for every two messages m1 and m2 : if m(m1 ) → m(m2 ), then di (m1 ) → di (m2 ) for all i in both Dest(m1 ) and Dest(m2 ).
Message order is total when all processes receive all messages in the same order. They don’t imply each other.
• Birman-Schiper-Stephenson algorithm for causal message ordering of broadcast messages
1
A message m is send with vector clock Vm . The condition for delivery of a message m in Pi from Pj is (V + ej ≥ Vm ) (i.e. Pi expects the next message from Pj and Pi is at least as up to
date as Pj wrt other processes).
• Schiper-Eggli-Sandoz algorithm for causal ordering of point-to-point messages
2
Every process maintains a local buffer Si = {(Pj , Vj ); ...} of ordered ID-vector clock pairs (”the most recent knowledge about what Pj should know, used to tell Pj what it should know”).
Messages are sent with the complete Si .
Condition for delivering m with buffer Sm in Pi is that (i, V ) ∈ / Sm or (i, V ) ∈ Sm and V ≤ Vi . After delivery, Sm and Si are merged (component-wise max).
• Algorithm for total message ordering of broadcast messages
– Simple solution: processes send their messages to a special sequencer process P0 , which numbers the messages and broadcasts them.
– Sophisticated solution with scalar clocks (with process IDs as tie breakers) and FIFO channels: every process maintains an ordered message queue, and messages (i.e. broadcasts with
timestamps) can be delivered in a process when it is at the head of the local message queue (the oldest message it knows about), and the process has received an ACK for that message from
every process (so no older message will arrive), i.e. all processes acknowledge all messages to all processes. When a process receives a message, it broadcasts an ACK for it.
Detecting Global States
Non-trivial because of a lack of a common clock and arbitrary delays of messages. Used for debugging and detecting stable properties (once it holds, it holds forever, e.g. termination, deadlock).
A cut is a set consisting of one internal event for every process: {c1 , c2 , ..., cn } with ci an internal event in Pi .
The vector time of a cut C is the component-wise max of it’s events: V (C) = max{V (c1 ), V (c2 ), ..., V (cn )}.
A cut it consistent iff
– there are no events ei ∈ Pi and ej ∈ Pj with ei → ej AND ej → cj AND ei 6→ ci (else ei → ej would be an orphan message: sent after but received before cut).
– ci ||cj for all i, j .
– the local components are the maximums: V (C) = (V (c1 )[1], V (c2 )[2], ..., V (cn )[n]).
Global state detection = finding a set of concurrent state-recording events.
The state of a channel should be the sequence of messages sent before the sender records its state minus the messages that have been received before the recipient does so. It turns out that it is too
ambitious to determine a state an asynchronous system has actually been in. We assume fault-free, FIFO, infinite-capacity channels.
• Chandy’s and Lamport’s algorithm for determining global states
Any process may spontaneously start. It first records its own local state, and then sends a marker along every outgoing channel. Upon the first receipt of a marker along any channel, a process
records the state of that channel as the empty state, records its own local state, sends a marker along every outgoing channel, and creates an empty FIFO message buffer for each of its incoming
channels (except for the one along which the first marker is received), used for recording the channel state as defined above. Every subsequently message received along a channel is entered into
the corresponding buffer until a marker is received along it. A process has finished its part of the algorithm when it has received a marker along every incoming channel.
0
The resulting recorded state might not actually have occurred at the same moment in time. This is not actually a problem, because there is a sequence S of events equivalent to the actual
0 0
sequence S such that the recorded state does occur in S , i.e. the sequences of messages on the channels in S after all prerecording and before all post-recording events are identical to the
states recorded for these channels by the algorithm. The state can still be used for detecting stable properties.
Termination Detection
About determining that a distributed computation has finished. A process can be active or passive (cannot send computation-related messages). An active process can always become passive, but a
passive process can only become active when receiving a computational message.
• Termination detection algorithm for a unidirectional ring with FIFO links
Processes are numbered decreasingly, i.e. Pi can only send to Pi−1 . P0 starts by sending a token (to Pn−1 ) along the ring. Each process and the token can be white (good) or black (spoiled).
Termination is detected when the white token returns to P0 , indicating that all processes are passive. (If the token returns black, try again.) If a process sends a message to a higher-numbered
process (where the token may have already passed, i.e. it’s passiveness is spoiled), the sending process turns black. When the token arrives at a black process, it turns black, and the process
turns white again to prepare for the next attempt.
• General termination detection algorithm
There is one special process P that does not participate in the application itself. This process starts at weight 0, all other processes start with weight 1/n. When a message is send, the sending
3
process transfers half of its weight to the recipient. When a process becomes passive, it transfers its weight to P . Termination when P has weight 1.
1 Vector clocks are only used for message ordering
2 Vector clocks used for entire operation, not just message ordering.
3 Transferring means that the sender loses weight and the recipient gains weight.
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 emielbos. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €13,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 73918 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen