06 09 2024 E T

Page 1

Politecnico di Milano 090950 – Distributed Systems Prof. G. Cugola – September 6th, 2024 Rules: • You are not allowed to use books, notes, or other material. • You can answer in Italian or English and use either pen or pencil. • Total time for the test: 2 hours. 1. Discuss (classify) the various type of failures that may happen to a distributed system and make a practical example of each of them. 2. Describe and compare the various approaches to synchronize node clocks in a distributed system. 3. Calculate the recovery line for the two diagrams below using the rollback-dependency graph for the first one, the checkpoint dependency graph for the second one. 4. Describe scalable reliable multicast in details, clarifying the problem it solves and the assumptions it makes. 5. P0 W(y) 1 W(x) 2 R(y) 3 W(x) 6 R(y) 5 P1 R(y) 1 W(y) 3 R(x) 2 R(x) 4 R(y) 5 P2 R(x) 6 W(y) 5 R(x) 6 W(x) 4 R(x) 2 Consider the above schedule of read and write operations on a replicated data store. Is the schedule consistent with the FIFO, causal, and sequential consistency models? How do your answers change if you remove the last read (R(x) 2) from P2? Motivate your answers. 6. Consider the dataflow model for big data processing. (a) Describe the key characteristics of the model. (b) Describe what are the two architectures to implement it: scheduling of tasks and pipelining of tasks. 7. Consider the Raft consensus protocol. Which problem does it solve? Under which assumptions? Does the protocol guarantee safety (it is always correct) and liveness (it always makes progress)? Motivate your answers.