02 12 15

Page 1

Politecnico di Milano 090950 – Distributed Systems Prof. G. Cugola – December 2nd, 2015 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 the data centered architectural style and its incarnation in the Linda model of interaction. 2. Describe the problem of removing unreferenced entities in a distributed system and possible solution s to such problem. 3. Calculate the recovery line for the two diagrams below using the rollback-dependency graph for the first one, and the checkpoint dependency graph for the second one . Finally, briefly describe when we build such diagrams, how we build them, and the general goal this algorithm solves. 4. Describe vector clocks in general, compare them with scalar clocks and describe how the former can be used to guarantee causal delivery in a multicast communication system (clarify the assumptions you make). 5. Consider the following schedule over 2 variables (both initialized at zero): P0 W(y)1 R(x)1 R(x)3 R(y)4 P1 R(y)1 W(x)1 R(y)3 W(x)3 P2 W(x)2 R(x)2 W(y)3 W(y)4 P3 R(y)1 W(y)2 R(x)1 R(x)3 P4 R(x)0 R(y)1 R(x)3 R(y)2 Is it FIFO/causal/sequential consistent? 6. a) Describe the logical key hierarchy approach, and for which problem it is used. b) Consider the following scenario: a server for secure group communication using the logical key hierarchy is set up, and it supports up to 16 members. The following members are currently connected: 0, 4, 5, 7, 9, 11, 13, 14. Describe the state of the server and the clients, i.e., the current tree for the server and which keys each client has. Now consider that member 2 joins and member 11 leaves. Describe which keys have been revoked and/or which keys have been (re)generated after each…