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.

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, either the effect of all opertaions of { TransactionalFile.Read, TransactionalFileWrite, TransactionalFile.Seek()} within T_{i} should be visible to T_{j} or none should be visible. 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}.

For an operation a to precede operation b it means b should be able to see the effects(if any on a shared data resource) made by a. Succeds relationship is defined similarly. However, between some operations no effectual relationship exists since they can not have any effect on each other anyway (e.g writing to block x and writing to block y). For these we would say they can either precede or succed each other. If we denote → as the relation precedes between operations and OP_{T_{i}} as the set of all operation within T_{i} from the set {BeginTransaction, TransactionalFile.Read, Transactional-File.Write, EndTransactioni} we would have:

Rule 1- if T_{j} commits after T_{i}, all of the operations in OP_{T_{i}} should precede those in OP_{T_{j}} (Rule 1 means they should be able to see the changes)

Rule 2- ∀ op_{T_{i}} ∈ OP_{T_{i}} if and only if ∀op_{T_{j}} ∈ OP_{T_{j}} such that op_{T_{i}} → op_{T_{j}}, then T_{i} can → T_{j} )

Rule 3- T_{i} and T_{j} would both commit if and only if either T_{i} precedes T_{j} or T_{j} preceds T_{i}

Rule 4- if opT_{i} → opT_{k} and opT_{k} → opT_{j} then opT_{i} → opT_{j}

Rule 2 defines the precedence relationship for transactions. It should be noted not all operations in OP_{T_{i}} should precede OP_{T_{j}} in order to for T_{i} to precede T_{j}, but none should succed any of those belonging to OP_{T_{j}}. It may seem like many of transaction are interchangable according to Rule 1 (for instance those who do not share any files), however Rule 4 ensures if there is a transactions in the serial order that T_{i} and T_{j} have a precedence relationship with, then there is a unique relationship between those two as well.

1.2 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.

Above we used the terms ”use” and ”modify”. Here we give a description of these terms. By ”use” we mean making the transaction T_{i} dependent on some specific data regarding tf_{j} (could be file contents, offset ant etc.). Modify in the similar way means changing the data regarding a tf_{j}.

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

Now, if T_{i} and T_{j} do not either modify the data the other one uses, according to Rule 2 and 3 both can commit. This means even if T_{i} accesses tr_{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.

Otherwise, if some data used by T_{i} has been changed by T_{j}, as T_{j} has commited before T_{i}, operations in OP_{T_{i}} should be able to see the effects made by OP_{T_{j}} (according to Rule 1). However, since T_{i} has already used the data in question, it has not seen the changes and hence there is at least one operaion in OP_{T_{i}} that precedes an operation in OP_{T_{j}}, hence T_{i} can not succed T_{j}. On the other hand, T_{i} can not precede T_{j} since it has not seen the changes. Thus, according to rule 3 it should be aborted.

Below we will give a list of principles with the proofs on the operations and how they affect the data. We would using this table then establish the rules our system would go by. Before going to this, it should be noted that according to rule 2 even if all but one operations in a set suucced all operations in the other, still the transaction can not commit. therefore ot takes only one operation to make the transaction dependent (it should succced others but can not since one of the operations in its set already preceded an operation in an already sommited transaction)

1) A seek operation in OP_{T_{i}} does not make T r_{i} dependent on any data and hence does not count as using.

proof: whenever T r_{i} seeks to the file, it means it wants to do some operationat a specific absolute offset chosen in the argument and hence no changes made by any other transaction would matter. Therefore, this operation can succeed any other operation within other commited transactions, since according to Rule 1 itsee the effects (there are no effects).

2) A read operation prior to any seek belonging to the same set of operations OP_{T_{i}} makes T r_{i} dependent on the data abd offset.

proof: since according to Rule 1, T r_{i} should be able to see the changes made by previouslt commited transactions and there is contents of the file and the starting offset that T R_{i} file has used.

3) A read operation after a seek operation both belonging to OP_{T_{i}} does not make T r_{i} dependent on the offset data but doesn on the contents of the file.

proof: the read operation only starts reading from the current local offset, if the offset is absolute, then it is not using any info that depends on the status of other transactions. Rule 1 settles here for the offset as well (not for the contents of the file according to last principle).

4) A write operation prior to any read does not make T r_{i} dependent on any data.

proof: The write could just simply store the data in local buffer for serving read purposes, and then would actually carry on the write at commit time on the most recent commited offset. Acording to 1, T r_{i} should see thee changes and by conforming to the most recent commited offset, we acknowledge the changes made by other commited transactions

5) A write opeartion after a read makes T r_{i} dependent.

proof: follows imediately from 2 and 3 with the same dpendencies according to the prior reads.

to be continued