Verteilte System an der TU Berlin | Karteikarten & Zusammenfassungen

Lernmaterialien für Verteilte System an der TU Berlin

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Verteilte System Kurs an der TU Berlin zu.

TESTE DEIN WISSEN

Two criteria that a hardware clock should meet

Lösung anzeigen
TESTE DEIN WISSEN

Correctness: it drift rate falls within known bound p

Monotonicity (is implied by correctness) : clock never runs backwards

Lösung ausblenden
TESTE DEIN WISSEN

How fault tolerant are mutual exclusion algos?

Lösung anzeigen
TESTE DEIN WISSEN

dist. mutual exclusion :

centralized vs. distr.

- message loss: neither

- process failure:

  • centralized: only of those that dont hold or have requested access
  • distr., if crashed process are seen to grant immediately
    • but that needs failure detection
Lösung ausblenden
TESTE DEIN WISSEN

Lamport Logical Clock - Algorithm

Lösung anzeigen
TESTE DEIN WISSEN

Local: 

Li is incremeneted before each event is processed (local)

Messages:

LC2(a) when pi sends message m, it carries time of sending event

LC2(b) recievieng (m,t) a process pj computes Li=max(Lj, t) and then applies +1 for event recieve


Lösung ausblenden
TESTE DEIN WISSEN

Vector clock algorithm

Lösung anzeigen
TESTE DEIN WISSEN
  1. Initially: vector is null vector
  2. before pi timestamps an event, it sets Vi[i] = Vi[i] +1
  3.  pi includes the value t = Vi in every message it sends
  4. recieving timestamp t in: performs a merge operation, it sets Vi[j] := max(Vi[j], t[j]) for j = 1,2, …N aka bigger value for each Eintrag



Lösung ausblenden
TESTE DEIN WISSEN

How to compare vector clocks?

Lösung anzeigen
TESTE DEIN WISSEN

Two Vectors V and V'

  •  𝑉 = 𝑉´ 𝑖𝑓𝑓 𝑉 𝑗 = 𝑉´ 𝑗 𝑓𝑜𝑟 𝑗 = 1,2,…𝑁 
  •  𝑉 ≤ 𝑉´ 𝑖𝑓𝑓 𝑉 𝑗 ≤ 𝑉´ 𝑗 𝑓𝑜𝑟 𝑗 = 1,2,…𝑁
  •  𝑉 < 𝑉´ 𝑖𝑓𝑓 (𝑉 ≤ 𝑉´) AND ( 𝑉 ≠ 𝑉´)


Lösung ausblenden
TESTE DEIN WISSEN

Bully Algorithm steps:

Lösung anzeigen
TESTE DEIN WISSEN
  • process notices failure
  • if process has highest id, elects itself and sends coordinator message
  • else sends election to all with higher ID and waits for answer message
    • if no answer within T, considers itself coordinator and sends coordinator message
    • if answer (aka die klären es unter sich), waits another T time to get coordinator message. 
      • if no message, starts new election (smth crashed)
      • when recieves coordinator: it sets elected_i to that coordinator
  • on recieving end:
    • when recieving coordinator, set elected_i (wie oben gesagt)
    • when recieving election, reply to (lower id process) and start another election (to only higher ID processes)
Lösung ausblenden
TESTE DEIN WISSEN

How to interpret vector values in vector clocks

Lösung anzeigen
TESTE DEIN WISSEN
  • Vi[i] is he number of events that pi has timestamped 
  • Vi[j] with 𝑗 ≠ 𝑖 is the number of events that have occurred at pj that have potentially affected pi
Lösung ausblenden
TESTE DEIN WISSEN

happened-before relation by Lamport

Lösung anzeigen
TESTE DEIN WISSEN

 HB1: If ∃ 𝑝𝑟𝑜𝑐𝑒𝑠𝑠 𝑝𝑖:𝑒 →𝑖𝑒´,𝑡ℎ𝑒𝑛 𝑒 → 𝑒´ (local history)

 HB2: For any message 𝑚: 

𝑠𝑒𝑛𝑑 𝑚 → 𝑟𝑒𝑐𝑒𝑖𝑣𝑒 𝑚

 HB3: If e, e´ and e´´ are events such that 𝑒 → 𝑒´ and 𝑒´ → 𝑒´´ , then 𝑒 → 𝑒´´

Lösung ausblenden
TESTE DEIN WISSEN

How to get total ordering from lamport clocks? Usage?

Lösung anzeigen
TESTE DEIN WISSEN

Add unique identifier per process (eg proces number).

Usage: entering critical section

Lösung ausblenden
TESTE DEIN WISSEN

Vector clocks components

Lösung anzeigen
TESTE DEIN WISSEN

Each process pi keeps its own vector Vi used to timestamp local events − Array of N integers for N processes − Carried with each message


Lösung ausblenden
TESTE DEIN WISSEN

NTP operational modes

Lösung anzeigen
TESTE DEIN WISSEN

Multicast: lowest accuracy, multicast time to other server (for LANs)

Procedure call: similar to cristians', server accepts requests and replies with timestapm. higher accuracy

symmetric: highers accuracy, used in low startum, servers keep timing data as part of association for accuracy

Lösung ausblenden
TESTE DEIN WISSEN

Lower level is not aware of application needs and semantics! -> consider end-to-end principle when designing systems (no questions, just remember it)

Lösung anzeigen
TESTE DEIN WISSEN

im tired sorry

Lösung ausblenden
  • 42799 Karteikarten
  • 1646 Studierende
  • 57 Lernmaterialien

Beispielhafte Karteikarten für deinen Verteilte System Kurs an der TU Berlin - von Kommilitonen auf StudySmarter erstellt!

Q:

Two criteria that a hardware clock should meet

A:

Correctness: it drift rate falls within known bound p

Monotonicity (is implied by correctness) : clock never runs backwards

Q:

How fault tolerant are mutual exclusion algos?

A:

dist. mutual exclusion :

centralized vs. distr.

- message loss: neither

- process failure:

  • centralized: only of those that dont hold or have requested access
  • distr., if crashed process are seen to grant immediately
    • but that needs failure detection
Q:

Lamport Logical Clock - Algorithm

A:

Local: 

Li is incremeneted before each event is processed (local)

Messages:

LC2(a) when pi sends message m, it carries time of sending event

LC2(b) recievieng (m,t) a process pj computes Li=max(Lj, t) and then applies +1 for event recieve


Q:

Vector clock algorithm

A:
  1. Initially: vector is null vector
  2. before pi timestamps an event, it sets Vi[i] = Vi[i] +1
  3.  pi includes the value t = Vi in every message it sends
  4. recieving timestamp t in: performs a merge operation, it sets Vi[j] := max(Vi[j], t[j]) for j = 1,2, …N aka bigger value for each Eintrag



Q:

How to compare vector clocks?

A:

Two Vectors V and V'

  •  𝑉 = 𝑉´ 𝑖𝑓𝑓 𝑉 𝑗 = 𝑉´ 𝑗 𝑓𝑜𝑟 𝑗 = 1,2,…𝑁 
  •  𝑉 ≤ 𝑉´ 𝑖𝑓𝑓 𝑉 𝑗 ≤ 𝑉´ 𝑗 𝑓𝑜𝑟 𝑗 = 1,2,…𝑁
  •  𝑉 < 𝑉´ 𝑖𝑓𝑓 (𝑉 ≤ 𝑉´) AND ( 𝑉 ≠ 𝑉´)


Mehr Karteikarten anzeigen
Q:

Bully Algorithm steps:

A:
  • process notices failure
  • if process has highest id, elects itself and sends coordinator message
  • else sends election to all with higher ID and waits for answer message
    • if no answer within T, considers itself coordinator and sends coordinator message
    • if answer (aka die klären es unter sich), waits another T time to get coordinator message. 
      • if no message, starts new election (smth crashed)
      • when recieves coordinator: it sets elected_i to that coordinator
  • on recieving end:
    • when recieving coordinator, set elected_i (wie oben gesagt)
    • when recieving election, reply to (lower id process) and start another election (to only higher ID processes)
Q:

How to interpret vector values in vector clocks

A:
  • Vi[i] is he number of events that pi has timestamped 
  • Vi[j] with 𝑗 ≠ 𝑖 is the number of events that have occurred at pj that have potentially affected pi
Q:

happened-before relation by Lamport

A:

 HB1: If ∃ 𝑝𝑟𝑜𝑐𝑒𝑠𝑠 𝑝𝑖:𝑒 →𝑖𝑒´,𝑡ℎ𝑒𝑛 𝑒 → 𝑒´ (local history)

 HB2: For any message 𝑚: 

𝑠𝑒𝑛𝑑 𝑚 → 𝑟𝑒𝑐𝑒𝑖𝑣𝑒 𝑚

 HB3: If e, e´ and e´´ are events such that 𝑒 → 𝑒´ and 𝑒´ → 𝑒´´ , then 𝑒 → 𝑒´´

Q:

How to get total ordering from lamport clocks? Usage?

A:

Add unique identifier per process (eg proces number).

Usage: entering critical section

Q:

Vector clocks components

A:

Each process pi keeps its own vector Vi used to timestamp local events − Array of N integers for N processes − Carried with each message


Q:

NTP operational modes

A:

Multicast: lowest accuracy, multicast time to other server (for LANs)

Procedure call: similar to cristians', server accepts requests and replies with timestapm. higher accuracy

symmetric: highers accuracy, used in low startum, servers keep timing data as part of association for accuracy

Q:

Lower level is not aware of application needs and semantics! -> consider end-to-end principle when designing systems (no questions, just remember it)

A:

im tired sorry

Verteilte System

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Verteilte System an der TU Berlin

Für deinen Studiengang Verteilte System an der TU Berlin gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten Verteilte System Kurse im gesamten StudySmarter Universum

Verteilte Systeme

Hochschule Heilbronn

Zum Kurs
Verteilte Systeme

Universität zu Lübeck

Zum Kurs
Verteilte Systeme

FOM Hochschule für Oekonomie & Management

Zum Kurs
Verteilte Systeme

FOM Hochschule für Oekonomie & Management

Zum Kurs
Verteilte Systeme

Technische Hochschule Ingolstadt

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Verteilte System
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Verteilte System