12 02 16

Page 1

Politecnico di Milano 090950 – Distributed Systems Prof. G. Cugola – February 12th, 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 publish/subscribe in details discussing the various alternatives for the subscription language, then describe and compare the various approaches to implement a distributed (acyclic) dispatcher. 2. Describe and compare the various approaches you know to implement flat naming. 3. Consider the system in figure, which is running a distributed snapshot. Suppose that every process works by adding the value held by the received messages to its internal state S. Process A started the snapshot , recording state 2 and sending the token s to processes B and E, which already processed them and sent out their own tokens. Assuming that channels exiting from B and E are much faster than others, and that no other operations occur apart those required to end the snapshot, show the state captured by every node at the end of the snapshot (local state and messages recorded for each link). 4. Describe the floodset algorithm. Which problem does it solves? Under which assumptions? May you provide a proof of its correctness? 5. Consider the following schedule over 2 variables (both initialized at zero): P0 R(y)0 R(x)1 R(y)3 R(x)2 P1 W(y)1 R(x)2 W(x)3 R(y)3 P2 R(x)0 W(y)2 R(x)1 W(y)3 P3 W(x)1 R(x)1 W(x)2 R(y)3 Is it FIFO/causal/sequential consistent? 6. Describe the use of symmetric and asymmetric encrypti on algorithms in the secure protocols we studied. What are the "session keys"? Why do we use them? 7. Describe the range of solutions in p2p systems regarding the problem of searching for items in the peers network: are there solutions offering any…