Question 1 Describe from a graphic point of view the relationship between sets of admissible runs of the following total order specifications: to(UA,suto), to(UA,wuto), to

Sistemi distribuiti 11/6/2010

Corso di Laurea Specialistica in Ingegneria Informatica

Cognome_______________________Nome________________Matricola_________
Question 1

Describe from a graphic point of view the relationship between sets of admissible runs of the following total order specifications: TO(UA,SUTO), TO(UA,WUTO), TO(NUA,SUTO), TO(NUA,WNUTO). Provide an example of a run which is TO(NUA,WNUTO) and that is not either TO(UA,WUTO) or TO(NUA,SUTO),

Question 2

Describe informally the logic of the Majority voting Algorithm used to implement a regular register. Specify in which way the algorithm is able to guarantee the validity property of the register.

Question 3

Consider the run depicted in the following picture

m1

m1

m2

m2

m3

m4

Broadcast

Deliver
Provide all the sequence of message deliveries which respect causal and total order.

Question 4

Explain why, in the worst case, SIENA event diffusion mechanism has similar performance than event flooding.

Question 5

Consider a distributed system formed by N processes owning a local physical clock each. A process can communicate with each other through a perfect point to point link with a maximum latency of 1 second. Moreover each process can access a leader election primitive. Write the pseudo code of a synchronization algorithm which is able to keep close the clock values of all processes.

Finally explain if the clock synchronization forced by the algorithm is either external or internal and why.

Il Sottoscritto, ai sensi della legge 675 del 31/12/96, autorizza il Docente a pubblicare in bacheca e su web i risultati della prova di esame. In fede

Firma leggibile: _________________________