1 Requirements

1.1 Transactions

We have a set of Threads T each representing a transaction.The code for a Transaction is like below:

Thread.doIt(new Callable)(){ // code for transaction }

This is adopted from dstm and can and may be changed. Within this block which represents a member of set T. The functions beginTransction and endTransaction are implicitly called by the system without the intervention of the programmer.However, the programmer can read and write from TransactionalFile Objects within the blocks of a member of T. To provide consisteny the read and write from ordinary Java object files should be prohibited, otherwise the semantics of transactions would not be preserved. Hence, the sequence of operations provided to the programmer within a member of T is the set {TransactionalFile.Read(), TransactionalFile.Write()i, TransactionalFile.Seek()}. However, always a beginTransaction() and commitTransaction() (if the transaction does not abort prior to this point) are performed too.

A Transaction consists of a sequence of operations. Thus, a transaction can be represented as the {OP_{1}, OP_{2}, ..., OP_{n}}. The flow of program should be in a manner that we could have an arbitrary serial order of the members of T (e.g. T_{5}, T_{6}, T_{1},...) or any other order. The serial order should be in such a way that for any given two members of the set T, it looks all the operations of one occur before all the operation of the other. In the first case we would say the T_{i} precedes T_{j} and in the seconds case T_{j} preceds T_{i} and T_{i} can observe all the effects made by the operations in T_{j}.

1.2 Defenitions

Def 1- Set of Operations: Operations are taken from the set {readoffset(fildescriptor), writeoffset(filedescriptor), readdata(inode, offset, length), writedata(inode, offset, length)}. We denote read operations as readoffset and readdata and write operations as writeoffset and writedata.

Def 2- Operations Sharing Resources 1- A readoffset operation and writeoffset operations are said to be sharing resources if they both operate on the same filedescriptor. 2- A readdata and writedata operations are said to be sharing resources if they both operate on the same inode AND the range of (offset, offset + length) within one overlaps with that of the other.

Def 3- A read operation can only see the writes made by write operations sharing reources.

Def 4- Commit Instant: A transaction T_{i} is said to ”commit” at instant t_{i}, if and only if it reflects its ”writes” mabe by write operations in the filesystem or equivalently makes it writes visible to the whole system for all members of T accesing the data at instant t_{j} such that t_{j} > t_{i} . An operation ∈ OP_{T_{i}} is said to commit if and only if T_{i} commits. Commit instant are not splittable, hence it appears to other transactions that all writes are refleted in the file system together.

Def 5- No See In Future: Assume T_{i} is an uncomiited transaction and T_{commited} indicates the set of commited transaction. A read operation b ∈ OP_{T_{i}} MAY ONLY see the writes(changes) made by write operation b that shares resources with b AND also is subject to one of the following conditions:

1- a ∈ OP_{T_{j}} (j ≠ i) such that T_{j} ∈ T_{commited}

2- a ∈ OP_{T_{i}} and a happens before b in the natural order of the transaction. Formally, a has a lower position than that of b in OP_{T_{i}} = {OP_{1}, ..., OP_{n}}

Def 6- Precedence Relationship for Read-Write Operations: Assume b is a read operation and a is a write operation, and a and b share resource r_{i}, a precedes b (a → b) if complying with Def 5, b is allowed to see the writes to r_{i} made by a. Otherwise, b → a. For other pairs of operations or read-writes that do not share resources a → b and b → a.

Corrolary 1- Read Must See Most Recent Comitted Write: If a ∈ OP T_{i} reads the resource r_{i}, in case a has multiple precedessors sharing r_{i} (denoted as OP_{precedessors−for−r_{i}}), then if all of them are from sets other than OP_{T_{i}}, a sees the writes made by op_{T_{j}} ∈ OP_{precedessors−for−r_{i}} such that T_{j} has the greatest ”commit instant” between all transaction with such operations. Otherwise, a sees the most recent precedessor in OP_{T_{i}}.

proof: Consider case 1 that all precedessors are from sets of operations other than that of a’s, according to Def 4 all these prcedessors belong to comitted transactions. Assume T_{i} is accessing data at t_{i}, t_{i} is neccasarily gretaer than all members of {committime_{T_{1}}, ..., commitime_{T_{i−1}}},and hence the writes to r_{i} made by these commited transaction, have accroding to Def 1 been already reflected in the file system. Since, T_{i−1} has the greatest commit instant its changes have overriiden that of previously commited transactions and thus, a reading r_{i} from file system sees these changes.

In case 2 that there are operations preceding a in OP_{T_{i}}, according to defenition of transaction r_{i} should be read from the writes made by write operations in T_{i}, and as the last of such write operation overrides the written data to r_{i} by other operations, a gets to see the most recent precedessor in T_{i}.

Def 7- ∀ op_{T_{i}} ∈ OP_{T_{i}} and ∀op_{T_{j}} ∈ OP_{T_{j}} if and only if op_{T_{i}} → op_{T_{j}} then T_{i} → T_{j} (this defines precedes relationship for members of T)

Def 8- A sequence of tarnsaction are said to be consistent if and only if a total ordeing of them according to precedence relationship can be established that demonstrates the same behavior as the behavior of the program.

Corrolary 2: Upon Commit All Mebers of T_{commit} Should Precede T_{i} proof: Follows imeediately from Def 8 and Def 9. This is later proven

formally.i

1.3 Rules

Rule 1- if T_{i} → T_{k} and T_{k} → T_{j} then T_{i} → T_{j}

proof: Since Def 9 ensures all operations in OP_{T_{i}} precede those in OP_{T_{j}}.

Rule 2- Committed transaction Should Precede the About to Commit Transaction: T_{j} ”commits” at instant t_{j} - T_{commited} denotes the set of all commited transactions at t_{i} such that t_{j} > t_{i}- only if all members of T_{commited} precede T_{j} (hence they should succed)

proof: T_{i} denotes the last commited member of T_{commited}. Lets assume on the contrary T_{i} does not precede T_{j} and hence T_{j} → T_{i}.

If there is not a pair of (read, write) or (write, read), sharing resource r_{n} in the two transaction, then T_{i} → T_{j} according to Def 7 and Def 9.

If there are such operations, 1-At least an operation a reads from r_{n} in OP_{i} sees the writes made by a write operation on r_{n}(b) in OP_{j}, however since T_{j} has commited after T_{i} and writes are not reflected till commit instant, hence a could not have read the writes made by b and consequently a does not precede b contradicting the assumption T_{j} → T_{i} . OR 2- An operation a in T_{i} writes to resource r_{i} and operation b in T_{j} reads resource r_{i}, according to Def 5 a precedes b and b does not precede a, hence contradicting the assumption that T_{j} → T_{i}.

The same reasoning could be done for T_{i} and T_{i−1}, T_{i−1} the last commited transaction before T_{i}. Now according to rule 3, since T_{i−1} precedes T_{i} and T_{i} precedes T_{j}, hence T_{i−1} precedes T_{j}. Same reasoning is applied for all the members of T_{commited}.

Rule 3-Operation in the Committed Transactions Precede Those in The Transaction About to Commit: T_{j} ”commits” at instant t_{j} - T_{commited} denoting the set of all commited transactions at t_{i} such that t_{j} > t_{i}- only if ∀op_{i} ∈ OP_{T_{i}}, ∀op_{all} ∈ the union of OP_{j}, such that OP_{j} is the set of operations for every T_{j} ∈ T_{commited}, op_{all} should precede op_{i}.

proof: Follows immediately from Rul2 and Def 7.

Rule 4- If All committed Transactions Precede A Transaction About to Commit, It Commits: T_{i} commits if at its commit instant, ∀T_{j} ∈ T_{c}committedT_{j} → T_{i}.

proof: If ∀T_{j} ∈ T_{c}ommittedT_{j} → T_{i}, a total ordering can be established corresponding the precedence relationship and all writes made by committed transaction have been seen by reads in T_{i}, hence according to Def 8, a consistent sequence of transactions would be provided.

1.4 TransactionalFile Opeartions

TransactioalFiles can be either created inside or outside T. The TransactionalFile object ensures transactional access no matter where it is created and accessed. Meaning the first time T_{i} uses tf_{j} the flow of the program should look like no other piece of code (i.e Transactional and non-transactional) outside T_{i} will modify tf_{j} before OP (endtransaction)_{T_{i}}. Otherwise, T_{i} has to abort.

A Transactionalfile can be shared among any subset of the members of T. If shared, the offset is shared between these too.

2 Implications for the System

2.1 General Implications

Now, if T_{i} and T_{j} do not either write the data the other one reads, according to Rule 2 and 3 both can commit. This means even if T_{i} accesses r_{k} before T_{j} does, but T_{j} commits before T_{i}, given that T_{j} has not modified the data in use by T_{i}, T_{i} could still commit.

It should be noted that according to Rule 3 even if all but one of the transactions in the set of committed transaction precede T_{i} which is about to commit, , still the transaction can not commit. Therefore it takes only one operation to make the transaction dependent (all the committed transaction should precede this transaction but can not since one of the operations in the committed transaction does not precede an operation in this transaction). Formally, if there is an operation b ∈ OP_{T_{j}} and an operation a ∈ OP_{T_{i}} such that a does not precede b then T_{i} can not precede T_{j}. In the rules below T_{i} is not commited yet and T denotes the set of all commited or active transactions.

proof: Obviously such modifications are not valid and are probably part of a faulty operation.

Principle 1) Reads Should be Validated At Commit Instant: If an operation a that ”reads” some data r_{n} (reads the data at some t < t_{commit−of−the−transaction}(the commit instant)), it should be ensured that the data r_{n} is still valid in the actual file system at t_{commit−of−the−transaction} (commit instant) or T_{i} has to abort.

proof: If the data is not valid anymore it means the data r_{n} has been written since t_{i−1}. This implies at least one operation b has written the data since the use and b does not precede a and a precedes b. b is either an operation in the same transaction or a different one. According to Def 4, however if b is in the same transaction, then b can not have commited yet and hence the changes are not reflected in the filesystem so it is still valid at commit instant. Hence, b belongs to a different transaction namely T_{j}. Since T_{j} should have already commited, according to Rule 3 all operation in OP_{T_{j}} should precede those in OP_{T_{i}}, however, we know there is at least an operation b that does not precede a (since a has not seen the ”writes” made to r_{n} by b). Hence, T_{i} can not commit.

The same reasoning could be done for T_{i} and T_{i−1}, T_{i−1} the last commited transaction before T_{i}. Now according to rule 3, since T_{j} succeds T_{i} and T_{i} succeds T_{i−1}, hence T_{j} succeds T_{i−1}. Same reasoning is applied for all the members of T_{commited}.

Principle 2: emphIf Reads Are Valid At Commit Instant, the Transaction Commits: If by applying Principle 1 for T_{i} it is ensured that ∀r_{i} ∈ RT_{i} (all data read by T_{i}) is still valid at commit instant, then ∀T_{j} ∈ T_{committed}T_{j} → T_{j} and hence according to Rule 4 T_{i} commits.

proof: If all data read is still valid at commit instant, means all operation in the set of operations belonging to committed transactions, precede those in T_{i} (since no writes have been seen), and consequently all those transactions precede T_{i}.

3 Implementation Overview

Now we will describe the components of our system and demosntrate how the algorithm conforms to the function just described, and how all the rules principles are gurantedd.

to be continued