In this project, we see how much we can generalize the core properties of ACID database transactions (atomicity, etc.) to general code and computer operations. The idea is to develop a framework that can provide these generalized capabilities.
First, we lay out the intended applications and use cases, to better understand how the concepts should be modeled. We first only consider atomicity for simplicity.
Use Cases
When would a concept like atomicity be useful? In other words, what are the use cases?
In terms of “all or none”, if the transaction is successful then it’ll just happen. Thus, issues arise (and the concept of atomicity becomes prominent) when there is a probability of failure.
Henceforth, we say that our framework deals with sequences of operations that are “primitive”, in the sense that an operation can’t be nontrivially reduced into “more basic” operations.
A transaction can fail for two reasons:
1. The intended sequence was not fully executed. (One of the operations failed.)
2. The intended sequence was fully executed, but it didn’t produce the intended result. (The operations all succeeded.)
If the intended sequence was fully executed, and it produced the intended result (the only other possibility, by basic Boolean logic), then the transaction succeeded, so these two reasons are comprehensive.
The framework implementing atomicity would have no clue how to distinguish between success and failure in the second case, unless the transaction was specifically marked (by the client) as a failure after say comparing the produced and the intended result.
In fact, we can combine (2) into (1) by adding a client-defined operation at the end that deliberately fails if the intended result isn’t found.
Thus, each operation, when called/executed, needs to either occur (perform a state transition) if successful, or give an indication of failure.
For computers, what types of state-modifying operations can there be?
- Local memory writes
- Communication with drivers and external components (including network calls)
With hard drives and networks being special cases of communication with drivers, these fully encapsulate support for database ACID transactions.
Hardware errors in communications with drivers (and external components) and in drivers themselves are encapsulated by failures in operations modeling communication with drivers and external components. Programming and human logic errors are encapsulated, as much as possible by our framework, by checks that deliberately fail, due to our framework having some failure keyword in defining the operation.
Rollback
In order to rollback previous operations, we need to understand, given an operation, what action we need to perform to rollback that operation. This entails: if the state before the operation was 
However, this can only be automatically understood for local memory writes. For driver calls, the framework cannot know what the state of the component being interfaced with is. Thus, for these calls, rollbacks would need to be defined by the user of the framework. For example, if an operation is made to change some data in a database, then the rollback needs to understand what the original data was.
Thus, assume that every driver call has an associated rollback that is provided to the framework.
Programmatic Rollback
The question is to enable programmatic rollback (rollback of a previous transaction at any time after its completion.) Say a string “abc” is written to the end of a file. Then, some stuff “de” is written later after. Trying to undo/rollback the “abc” writing after the “de” has been written may not even be a well-defined problem – state reconciliation may only be possible in special cases. Thus, for now we consider programmatic rollback (rolling back a previous operation at any time) to not be an option. Specifically, if an operation 
The “C” in ACID: Consistency
Consistency is not consistently defined among authors (ironically), according to the Wikipedia article (on 08/22/2020). The definition is also not very precise on https://www.tutorialspoint.com/dbms/dbms_transaction.htm#. We here take consistency to mean: “the database must satisfy any given constraints at any committed state (state after a transaction has been committed).” This is quick to extend generally and implement within the framework of generalized atomicity above: just have the last operations in the atomic transaction be of the form “check this constraint and it doesn’t hold then fail now.” Since this can be folded under atomicity for general code, we do not consider consistency further.
The “I” in ACID: Isolation
Isolation can be translated over almost exactly to the generalized atomicity framework, where the intermediate state of a sequence of operations is not visible to other threads. It provides an extra guarantee over just generalized atomicity and it is very reasonable that blocks that are all-or-none may not satisfy isolation, so this is an important concept to consider on its own.
The “D” in ACID: Durability
This can be implemented via say a file write / hard drive call operation in the generalized atomicity framework.
Terminology
It seems from some online discussion boards (https://cs.stackexchange.com/questions/109248/whats-exact-definition-of-atomicity-in-programming) that the word “atomic” is precisely defined differently in different contexts, with the general informal meaning nevertheless clear. Thus, we need to redefine our terms properly.
Above, we were considering how to translate the concepts over to general code based on their definitions for databases. However, we now see that the definition of atomic as “all-or-none” conflicts with the word’s roots from the Greek language referring to the concept of “indivisibility”, as if the transaction should be treated by all others as a single unit. Instead, that indivisibility corresponds better to all-or-none plus isolation, since without isolation other threads will see intermediate states of supposedly indivisible units.
We also see that “atomic” is the only term out of all the ACID properties where the word’s roots conflict with the translated definition. Thus, we will redefine some terms as follows: the translation of atomicity for databases will instead be referred to as just “all-or-none,” while “atomic” will be all-or-none plus isolation. No other terms will be changed. Note that isolation cannot happen without all-or-none, since if a sequence fails and is not all-or-none then other threads will eventually see the intermediate changes that happened within the sequence before the failure, contradicting the definition of isolation.
Thus, there are two concepts that ACID transactions boil down to in general: all-or-none and atomic.
Language Blocks
We will now designate the ultimate goal of this project (at least, this specific stage and this specific project), as providing language constructs for offering all-or-none and atomic. In other words, to provide all-or-none and atomic blocks.
We will now compare such constructs with already present language features that we suspect may already provide some of the functionality.
Comparison With Locks
Locks allow atomic modification of the status boolean of the lock. While this is not directly equivalent to atomicity of a sequence of statements, it could be an interesting question as to whether locks can be used to implement atomic blocks. But that is a question for the implementation section.
Comparison With Try-Catch Blocks
Based on a simple test with Repl.it, we can verify definitively that try-catch blocks are not all-or-none. (We used the following code. If all-or-none it will print 2, otherwise it will print 4. It printed 4.)
class Main {
public static void main(String[] args) {
// testing atomicity of try-catch block
int x = 2;
try {
x = 4;
throw new Exception();
}
catch (Exception e) {
// do nothing
}
System.out.println(x);
}
}
Implementation
Now, we discuss algorithms for implementing all-or-none and atomic blocks.
All-Or-None: Resetting Algorithm
The first optimization we can think of is: if we need to rollback a sequence of local memory writes, then we don’t need to do each in turn if we just revert back to the state before the sequence. This is doable since the state is controllable when the operations are local writes.
Isolation: Using Locks (Basic Algorithm)
The most obvious algorithm using locks to implement isolation could be to have a global lock and only allow one sequence to execute at a time. Of course, this can get very, very bad in terms of performance, so we will try to see if there is a better solution.
It remains to continue this.
First written June 24, 2020, then modified in August 2020, September 2020, and July 2021.
