# LambdaStore Optimistic Transaction Protocol

### Protocol Design

fn read(key) {
    get version_number for the given key
    read the value for the given key
    add (key, version_number) pair to read_set
    return value
}

fn write(key, update) {
    add (key, update) pair to write_set
}

fn commit(read_set, write_set) {
    // Prepare: acquire locks
    acquire write locks for all entries in write_set
    
    // Prepare: validate entries in read_set
    for (key, version_number) in read_set {
        if key is write-locked by another transaction{
            abort transaction
        }
        if version_number does not equal to the current version number {
            abort transaction
        }
    }
    
    // Commit: apply updates in-place
    for (key, update) in write_set {
        apply update
        increment version number
    }

    // Commit: release all locks
    release all locks
}

### Correctness
Since we always write the value back before updating the version number, we ensure that, at any point, for each key, the version number and value either matches, or the version number is stale. Since the commit phase is guarded by write locks, for each key, there can be at most one transaction updating it at any point of time. This ensures that the version number can be stale by at most 1 version (i.e., either the version number or (version number + 1) matches with the current value).

Then during the read, we read the version number before the value, which ensures that the version number read can be older than the value read. If they differ by more than 1 version, then, during commit, it will abort because this version does not equal to the latest version since latest version number is at most older than the value read by 1 version. If the version number is older than the value read by exactly 1 version, that means another transaction is currently writing to it. Two cases arise: 1. the writing transaction completes before the commit phase of our transaction, in which case it will see that the version number differs from the latest version number; 2. the writing transaction is still in progress, in which case it still holds the write lock, so our transaction will abort. Thus, a transaction can commit if and only if the read version matches with the read value, and that the read version has not been overwritten yet.

Note that the two checks for each key in commit phase do not have to be atomic: if the writing transaction releases the write lock before the first check (key is not write-locked), then it must have updated the version number, so the second check will fail and the transaction will abort; if the writing transaction acquires write lock after the first check, then we did not read the version written by that transaction during execution.