Verteilte System at TU Berlin

Flashcards and summaries for Verteilte System at the TU Berlin

Arrow Arrow

It’s completely free

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

Study with flashcards and summaries for the course Verteilte System at the TU Berlin

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

Two criteria that a hardware clock should meet

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

NTP operational modes

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

happened-before relation by Lamport

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

Lamport Logical Clock - Algorithm

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

How to get total ordering from lamport clocks? Usage?

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

Vector clocks components

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

Vector clock algorithm

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

How to interpret vector values in vector clocks

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

How to compare vector clocks?

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

Bully Algorithm steps:

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

How fault tolerant are mutual exclusion algos?

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

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

Your peers in the course Verteilte System at the TU Berlin create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Flashcard Flashcard

Exemplary flashcards for Verteilte System at the TU Berlin on StudySmarter:

Verteilte System

Two criteria that a hardware clock should meet

Correctness: it drift rate falls within known bound p

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

Verteilte System

NTP operational modes

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

Verteilte System

happened-before relation by Lamport

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

 HB2: For any message 𝑚: 

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

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

Verteilte System

Lamport Logical Clock - Algorithm

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


Verteilte System

How to get total ordering from lamport clocks? Usage?

Add unique identifier per process (eg proces number).

Usage: entering critical section

Verteilte System

Vector clocks components

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


Verteilte System

Vector clock algorithm

  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



Verteilte System

How to interpret vector values in vector clocks

  • 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

Verteilte System

How to compare vector clocks?

Two Vectors V and V'

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


Verteilte System

Bully Algorithm steps:

  • 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)

Verteilte System

How fault tolerant are mutual exclusion algos?

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

Verteilte System

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

im tired sorry

Sign up for free to see all flashcards and summaries for Verteilte System at the TU Berlin

Singup Image Singup Image
Wave

Other courses from your degree program

For your degree program Verteilte System at the TU Berlin there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to TU Berlin overview page

Rechnernetze und Verteilte Systeme

Softwaretechnik und Programmierparadigmen

Cloud Computing

Webdevelopment HTML

Diskrete Strukturen

Systemprogrammierung

Algorithmen und Datenstrukturen

What is StudySmarter?

What is StudySmarter?

StudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for Verteilte System at the TU Berlin or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards