Distributed K07 LH 4 Tanenbaum Ch 5 or CoDoKi Ch 11, 12 1. Total-ordered multicasting can be implemented as follows (the ISIS algorithm; see CoDoKi, 2nd ed. Fig. 11.10, 3rd. ed. Fig. 11.15): - the client multicasts the message to all replica managers - each replica manager replies to the client with a proposed sequence number for the message - the client selects the largest to become the agreed sequence number, the client multicasts it to the replica managers - the replica manager delivers the message to the application when two conditions are met: the message has received its agreed sequence number and there are no undelivered messages with a smaller (proposed or agreed) sequence number. Specify more accurately the steps related with the timestamps and delaying the message. Explain why the algorithm works correctly. Compare the algorithm with the one presented in Tanenbaum's book (the essential similarities and differences; performance, other aspects). 2. There is another version of the ring-based election algorithm. Here the message contains only the id of the current candidate. If several members start an election concurrently we have several election messages circu- lating in parallel. Describee an algorithm which destroys the superfluos messages. 3. a) Assume that serializability is implemented using two-phase locking (2PL). Which different orderings of events (in real time) are possible, when the following transactions are started at the same time: T: x:=Read(i); Write(j,44) U: Write(i,55); Write(j,66) ? b) Explain why serial equivalence requires that once a transaction has released a lock on a data item, it is not allowed to obtain any more locks. Give an example. c) Consider a relaxation of two-phase locks in which a read lock can be released after the transaction has finished using the corresponding data item. Is it feasible? d) Who is responsible for granting and releasing the locks in distributed transactions? 4. The following transactions proceed concurrently: T: ... x=Read(i); Write(j,2*x); ... U: y=Read(i); z=Read(j); Write(i,y+z); (i,j are database entries; x,y,z are variables in the program). Use these transactions, assuming various real-time advancing speeds, to illustrate a) the (pessimistic) timestamp-based method b) the optimistic (timestamp-) based method (with backward validation) (in both cases you can assume that TS(T)