_Posted on July 22, 2024_ ##### Introduction >"Leuccipus (c.440 B.C.) and Democritus (c.46O-c.370 B.C.) are notable because they were most explicit in affirming the doctrine of atomism. Their common philosophy was that the world is composed of an infinite number of simple, eternal atoms. These differ in shape, size, hardness, order, and position. Every object is some combination of these atoms. Though geometrical magnitudes such as a line segment are infinitely divisible, the atoms are ultimate, indivisible particles." >- Morris Kline, _Mathematics: The Loss of Certainty_ Similar to the atomists' 'atom', a compound computational operation[^1] can be _considered_ as atomic, or indivisible. However, by definition, a compound operation is never atomic in the strict sense; that is, being truly indivisible, whatever that may mean. While the question of whether _any_ computer operation can truly be atomic is an interesting question of physics (the answer is likely no), computer science is concerned with resolving consequences of the compound nature of operations in the context of real systems. The atomicity of a _compound_ computational operation is fundamentally based upon how state changes upon running the operation in different system conditions. Suppose we have an arbitrary compound operation `op` which arbitrarily modifies some arbitrary amount of data `D` stored on disk at arbitrary locations: - One system condition is where no failure occurs on the machine while running `op`. This will result in no errors and so the compound nature of the operation is not problematic. - Another condition is where a failure occurs on the machine running `op` _before_ `op` has completed its full execution. During the execution of `op`, some subset of `D` is being modified in volatile memory prior to being committed to disk. If the machine fails at this time, the disk will be in some __partial state__, as there may be some updates which have been committed, while the updates in volatile memory have been lost. - The next system condition is where multiple instances of `op`, which manipulate the same data `D` are concurrently running on different machines. In this case, different instances of `op` are reading, manipulating, then writing back `D` concurrently, so that the sub-operations are interleaved. Such concurrent modifications of a shared resource are called __race conditions__, which can result in inconsistent or incorrect final states. - The final system condition is where multiple instances of `op` which manipulate the same resource `D` are running concurrently across different machines, and a failure occurs on one or more of these machines prior to completing the operation. This results in both partial states and race conditions. #### Definitions ##### Recoverability To solve the problem of a partial state, we want the compound operation to be __recoverable__: A compound operation is recoverable if, from the point of view of its invoker, the operation always either 1) completes, or 2) aborts in such a way that it appears that the operation had never been undertaken. It is clear that a recoverable procedure would never end up in a partial state. ##### Isolation (or Serializability) To solve the problem of race conditions, we want the compound operation to be __isolated__: A compound operation is isolated if its effect, from the point of view of its invoker is the same as if the action occurred either 1) completely before, or 2) completely after every other isolated compound operation. Note that the term isolated may be used interchangeably with __serializable__. ##### Atomicity If a compound operation is both recoverable and isolated, then it is considered as an atomic operation. Corresponding to the notion of indivisibility above, the individual steps in such an operation are transparent to an invoker, "hiding" its compound nature. Note that the typical definition of atomicity is usually equivalent to recoverability, and therefore does not include isolation. However, a such a compound operation which is recoverable but not isolated does _not_ hide its compound nature from the invoker during race conditions. Alternatively, the compound nature of an operation which is both recoverable _and_ isloted is _always_ hidden from the invoker. --- The precise definitions given for recoverability, isolation, and atomicity are taken from [this lecture](https://youtu.be/Oo4iCE48xCc?si=Wyq9-nXNmeJFx89r). [^1]: I use the term 'compound computational operation' rather than 'computational operation' or simply 'procedure' because 1) a computational operation is more general than a procedure, including the primitive machine instructions, and 2) at the physical level, all computational operations are compound.