Chapter 13 : Distributed Transactions
---

- atomicity now affects multiple machines;

- flat distributed transacitons access one server at a time;

- with nested transactions, subtransactions in the same level can run
  concurrently;

- TIDs are assigned, in increasing order, by a coordinator, which handles
  the openTransaction requests;

- the coordinator is responsible for committing/aborting the distributed
  transactions;


- Two-Phase Commit (2PC)
  ----------------------

- in the first phase of 2PC the coordinator asks all the participants if
  they are prepared to commit.  In the second phse, it tells them either to
  commit or to abort the transaction; 

- voting phase + completion phase;

- to deal w/ server crashes, each server saves information related to 2PC
  in permanent storage;

- timeouts are used to avoid processes blocking forever;


	COORDINATOR			PARTICIPANT	

			can commit?
	1st phase	----------->	

			   yes/no
	1st phase	<-----------

		    doCommit/doNotCommit
	2nd phase	----------->

		   haveCommitted/haveAborted
	2nd phase	<-----------


- protocol is designed to complete eventually;

- 3PC designed to alleviate the problem when coordinator crashes;

- with nested transactions, either hierarchic 2PC (H2PC) or flat 2PC (F2PC)
  can be used;

- in H2PC, the coordinator of the top level contacts the coordinators for
  the transactions on the second level;

- in F2PC, the coordinators for ALL subtransactions are contacted;

- H2PC works in "stages", but each participant only needs to look for
  subtransactions of its immediate parent;

- a lock cannot be released until the transaction has committed (or
  aborted) at all the servers involved;

- in distributed transactions, it is required that each coordinator issue
  globally unique timestamps;

- to achieve a total ordering, the coordinators must agree as to the
  ordering of their timestamps; timestamps are of the form 
  <local timestamp, server-id>;

- the more synchronized the clocks are, the smaller the "importance" of the
  server-id field (or is it the opposite???);

- detection of a distributed deadlock requires a cycle to be found in the
  global transaction wait-for graph that is distributed among the servers
  involved in the transaction;

- simple solution: centralized deadlock detection; poor availability, lack
  of fault tolerance, and no scalability;

- "phantom" deadlocks: stale data is used by the deadlock detector;

- edge-chasing algorithm (3 steps):

	- initiation: when a server notes that a transaction T is waiting
	  for another transaction U, which is waiting to access an object
  	  at another server, it initiates detection by sending a probe
	  message containing the edge <T->U> to the server holding the
	  object U is waiting for;

	- detection: messages received are combined to construct a graph
	  (probes are sent when "waiting" objects are remote);

	- resolution: a transaction in the cycle is aborted;

- edge chaising is reasonably good, as most deadlock cycles are short;

- even if deadlock is detected at more than one server at the same time,
  they will abort the same transaction, based on global priority values
  (they can be the TIDs, for example);

- intentions list: for each transaction, contains a list of the references
  and the values of all modified objects; it's sort of like a repository of
  tentative versions;

- entries in a recovery file are of one out of 3 types: object, transaction
  status (TID + status), or intentions list;

- the recovery file gets new information when a transaction prepares to
  commit and when it commits (or aborts).  All 3 types of entries are logged;

- after a crash, any transaction that does not have a committed status in
  the log is aborted;

- after recovery, the log receives an aborted status entry for every
  non-committed transaction;

- the log file can be "run" either forward or backwards.  The second
  approach is better, as each object is restored only once (its last
  version);

- the purpose of making checkpoints is to reduce the number of transactions
  to be dealt with during recovery and to reclaim space;

- the shadow versions technique is an alternative way to organize the
  recovery file.  It uses a map to locate versions of the objects in a file
  called a version store;

- the shadow versions are the ones pointed by non-committed transactions;

- to complete the commit process, the new map replaces the old map; this
  needs to be atomic;