Verteilte System at TU Berlin

• 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

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

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

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

Two Vectors V and V'

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

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

Correctness: it drift rate falls within known bound p

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

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

 HB2: For any message 𝑚: 

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

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

Add unique identifier per process (eg proces number).

Usage: entering critical section

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

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

im tired sorry