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

1.2 Defenitions

Def 1- 1-An operation in T_{i} is said to have ”changed” or ”affected” some data structure in correspondece to all members of OP_{T −T_{i}} , when it reflects the changes in the filesystem in such a way that the modification is durable and irreversible. A transaction with such an operation T_{i} in its operation set is said to have changed the data 2- An operation in T_{i} is said to have ”changed or affeced the data in correspondence to all the operations in OP_{T_{i}} as soon as the operation is encountered

Def 2- An operation in T_{i} is said to have ”used” the data when it has read some data and has done some actions that is potentially irreversible. hence if the data in question was to change, op would have different results.

A transaction with such an operation in its operations set is said to have used that data. Any data read and used within a transaction at its commit instant does not count as using. ”Use” can just be attributed to the operations actually reading data before commit instant.

Def 3- A transaction T_{i} is said to ”commit” at instant t_{i}, if and only if it reflects its ”changes” in the filesystem or equivalently makes it changes 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 changes are refleted in the file system together.

Def 4- ∀op_{i} ∈ OP_{T_{i}}, ∀op_{j}inOP T_{i}, op_{i} precedes op_{j} if and only if op_{j} does not use the data changed by op_{i} OR if it does, then op_{j} should be able to see the changes made by op_{i} unless data has been changed by a more recent precedessor

Def 5- Succeds relationship is defined similarly.

Def 6- If operation a both precedes and succeds operation b since they do not share any resources so the changes can be made visible, a both precedes and succeds b.

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} can → T_{j}) (this defines precedes relationship for members of T)

Def 8- An operation op ∈ OP_{T_{i}} should be able to see the ”changes” 1made by OP_{T_{c}ommited} and 2-oper ∈ OP_{T_{i}} that in natural order of transaction occur before op

1.3 Rules

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, TransactionaFile.Read, TransactionalFile.Write, EndTransactioni} we would have:

Rule 1- for any pair of operations (transactions) a and b their relationship is taken from the set {→, ←, ← and →}

proof: Follows from defenition.

Rule 2) If an operation a ∈ OP T_{i} has multiple prcedecors (denoted as OP_{precedesors}) that their changes overlap each other, then if all of them are from sets other than OP T_{i}, a sees the ”changes” made by the op_{i} ∈ OP_{predecesors} such that op_{i} has the greatest ”commit instant” . Otherwise, a sees the most recent precedesor in OP T_{i}.

proof: the first part follows from Def 4 , second derives from Def 4 and second part of Def 1.

Rule 3- ∀op_{i} ∈ OP T_{i}, ∀op_{j} ∈ OP T_{j}, ∀op_{k} ∈ opT_{k} if op_{i} → op_{k} and op_{k} → op_{j} then op_{i} → op_{j}

proof: Follows from the defenition of →

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

proof: Follows from Rule 2 and Def 7.

Rule 5- If T_{j} ”commits” at instant t_{j}, and T_{commited} denotes the set of all commited transactions at t_{i} such that t_{j} > t_{i} then T_{j} should not ONLY precede any members of T_{commited} (hence they should succed)

proof: T_{i} denotes the last commited member of T_{commited}. Lets assume on the contrary T_{j} only precedes T_{i}. This means according to def 7, all operations in OP_{i} sees the effects made by those in OP_{j}.

If an operation op_{i_{1}} in OP_{i}, affects some data used by an operation op_{j_{i}} in OP_{j}, then op_{j_{1}} can not precede op_{i_{1}} since then it could not have seen the changes by it, however def 3 says it does, this is in contrats to the assumption. On the other hand, if op_{j_{1}} affects some data used by opi_{1}, then since opi_{1} has not seen the change, opj_{1} can not precede opi_{1}. If no operations in OP_{i} affects another in OP_{j}, then the set of all opeartions in OP_{i} both precede and succed those in OP_{j}, and hence the contraray to the assumption. In this case, the transaction are conceptually interchangable. In either case, T_{j} either ”succeds” or ”succeds and precedes” T_{i}. Either way it succeds the other.

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

Rule 6- If T_{j} ”commits” at instant t_{j}, and T_{commited} denotes the set of all commited transactions at t_{i} such that t_{j} > t_{i} then ∀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}, then op_{i} should not ONLY precede op_{all} (hence it should at least succed)

Follows immediately from rule 4 and def 7.

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

Now, if T_{i} and T_{j} do not either modify the data the other one uses, according to Rule 4 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.

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 6 even if all but one operations in a set suucced all operations in the other, still the transaction can not commit. therefore it 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 commited transaction). Formally, if there is an operation b ∈ OP_{T_{j}} and an operation a ∈ OP_{T_{j}} such that b does not succed a (or equivalently only precedes a) then T_{j} can not succed T_{i}. In the rules below T_{i} is not commited yet and T denotes the set of all commited or active transactions.

Assumption : The reads within transaction do actually occur when they are encountered. However, no change to the file system is done before commit instant as said before (writes, changing the offset and etc.)

Assumption: seek operation means after this operation is executed, the offset should be at the chosen value regardless of the actual value of the offset in the file system.

Principle 1) If an operation a that ”uses” some data (reads the data at some t < t_{commit}(the commit instant)), it should be ensured that the data is still valid in the actual file system at t_{commit} (commit instant) or T_{i} has to abort.//

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

Principle 2) 1-A seek operation in OP_{T_{i}} does not make T_{i} dependent on any data and hence does not count as ”using” (”use” as defined in Def 1).

The seek operations seeks to an offste within the file descriptor regardless of the changes made by opretaions in all transaction, hence the result would always be the same so according to Def 2 it does not count as using.

Principle 3) 1- A read operation in OP_{T_{i}} ”uses” contents read and makes T_{i} dependent on the file contents read.

proof: Due to assumtion 1 and since the data read by this operation can be used for computation, in case the data read would change, the data and hence computations results would be different. According to Def 2 it uses the data

Principle 4) 1- A write operation in OP_{T_{i}} does not make T_{i} dependent on file contents.

proof: The result of a write would always be the same contents thus, according to Def 2 does not count as using.

Assumption: Each operation has an offset status assioated with it.

Assumption: An operation with Speculative offset means the offset that the operation would be perfomed at can be relocated in the commit instant. An operation with absolute offset means the value is absolute and does not depend on any other operation. An operation with defenite offset means the offset value that operation has to be carried on from, can not be relocated, but still could have changed before commit instant by other committed transactions.

Principle 5: an operation with defeinte offset status assosiated with it is the only one ”using” the offset value.

proof: For speculative and absolute it comes form the defeniton that they do not count as using, since one is determined at commit instant and hence read at the same time, and the other is always the same value. However, with defenite, if some other transaction changes the offset of the file descriptor, then the result of the operation would have been possibly different. According to Def 2 it uses the offset data.

Assumption: Each operation can be considred as a function that takes as input ”a set of operations with their assostaed offsets status and a single offset status OR NOTHING”, and gives as the output ”a new set of operations with their assoisated offset status plus a new operation with its assosited offset status and a new single offset status”. Formally for this function we have:

f : {offsetstatus,{{op, op.offsetstatus}}} ∪ {} → {offsetstatus,{{op, op.offsetstatus}}}

Only the first operation takes as input the {}. The {{op, op.offsetstauts}} given by the last operation in the sequence of operations in the transaction, determines the offset status assosiated with each transaction. The single offsetstaus yielded in the output is given as the input to the consecutive operation. The {{op, op.offsetstatus}} is a sorted set sorted by the order operations have occured so far in the transaction. Each occurence of the function, adds the operation itself accompanied by it offset status to the end of the set. Principle 1 and principle 5 indicate if ony one operation has defenite offset status assosiated with it, then the transaction the operation belongs to has to abort.

Now we examine new principles regarding how operations affect the offset status:

1- Seek 2- Read: 3-Write

3 Implementation Overview

Now we will describe the components of our system and demosntrate how the algorithm

to be continued