1. Homepage
2. Exam
3. [2020] COMPSCI 711 Parallel and Distributed Computing - Logical clocks and applications

[2020] COMPSCI 711 Parallel and Distributed Computing - Logical clocks and applications

This question has been solved

Question 2 [10 marks] - Logical clocks and applications

Discuss logical clocks, compare Lamport clocks with vector clocks, and - as an application - illustrate the Money count distributed snapshot.

(a) Define logical time in terms of the happens-before relation between events.

(b) Consider the following events sequences at processes P1, P2, P3, where si and ri are corresponding send and receive events.

P1 time-line: s1, r2, r6, r5

P2 time-line: s2, r1, s3, r4, s5

P3 time-line: s4, r3, s6

(c) Annotate all events with Lamport clock values – one line for each process, e.g.

P1 time-line: s1:1, …

(d) Consider that each process starts with an initial value of 100 \$\$ and each message represents a transfer of 10 \$\$.

(e) According to the Money Count algorithm, what are the processes’ balances at Lamport time 4.5?

(f) Annotate all events with vector clock values, e.g.

P1 time-line: s1:(1,0,0), …

(g) Critically compare Lamport clocks with vector clocks (essential differences, why would one use vector clocks instead of Lamport clocks).

QQ
WeChat
Whatsapp