Consider a distributed transaction, which is managed by a tree of transaction managers, as shown in the following diagram. Each node contains a transaction manager (TM). The root of the tree, C, is responsible for the entire (global) distributed transaction. The internal node of the trees, S, plays dual roles: it is a resource manager (RM) to its ancestor node, and it is also the TM of all its child nodes. A leaf node L, like S, plays dual roles too, except that its RMs are DBMSs (DB). The DBs are located within the same computer as its L-type TM, within the same circle, as shown in the following diagram.

(i) Fill in the appropriate cells in the following table the actions by C, S and L to complete the 2-phase commit process, assuming for the time being that the Ls have no children. Each step in sequence shows the action of one of entities, which can be a message propagation to another entity up/down the hierarchy, or a write/forced-write into the local log.

Step:	C	S	L	DB
1	To prepare->(to S)
.......	.... ....	... ....	... ....	.... ....

(ii) How does S recover from a system crash? How does S responds to enquiries from C and L? (iii) Estimate the maximum time it takes for the 2-phase commit to complete, from the moment when C is to send the To-prepare message to the moment when C receives the acknowledgement. Assume that the different transaction will commit, and all systems (C, S, L, and DB) respond instantaneously without unnecessary delay. A message from a coordinator to its child nodes is broadcast so that it is received at the same time by all child nodes. Conversely, all messages initiated at the RMs reach their TM at the same time. The following constants are known: The time to transmit a message between computers: t The communication time between L and DB: negligible The time to force-write (write synchronously) to a disk: d The time to write asynchronously: negligible

(iv) Revise your estimate if all sub-transactions to the DBs under the internal node S are read-only.

Root C DB DB DB Root C DB DB DB