08 07 16

Page 1

Politecnico di Milano 090950 – Distributed Systems Prof. G. Cugola – July 8th, 2016 Rules:  You are not allowed to use books, notes, or other material.  You can answer in Italian or English.  Total time for the test: 2 hours. 1. Describe and compare the data-centered (Linda) model of communication with the event-based one. 2. Describe structured naming in general and DNS in particular. 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 mutual exclusion . Define it in precise terms and show the fully distributed protocol to achieve it using scalar clocks (clarify the assumptions for the protocol to work correctly). 5. Given the following schedule over 2 variables (both initialized with zero): P0 R(x)2 W(y)1 W(x)3 R(y)2 P1 W(x)1 R(x)1 R(y)2 R(x)2 P2 R(y)0 R(y)1 R(x)1 R(y)3 P3 W(x)2 W(y)2 R(x)2 W(y)3 Is it FIFO/causal/sequential consistent? 6. Describe what is access control, how it works and th e two main ways of implementing it in a distributed system. 7. Describe what an epidemic algorithm is, how it works and what properties it entails. How does this compare to gossiping and other propagation strategies?