Partial order of transactions

Prerequisites define a partial order among transactions.

We've established that an object's state is dependent upon its history. All of the operations in the object's history are transactions. As such, they obey all four of the ACID principles.

An operation performed on an object is atomic. Remember that there is no method body for an operation. The system simply records that it has occurred. Since there are no imperative steps required to complete the operation, it cannot be partially done. It has either occurred, or it hasn't.

An operation is consistent. It exercises only one degree of freedom. Everything that depends upon that operation is represented by dependent data. When the operation is performed, and the dependent data is subsequently observed, it will be found to be consistent with the results of the operation.

An operation is durable. The system permanently records that it has occurred. When the object is observed later, the operation will be visible.

An operation is isolated from other operations occurring simultaneously. Again, since there are no imperative steps, this is easy to achieve. But there's more to it than that. Either of two operations that have occurred simultaneously could be assumed to have taken place before the other. There is no order prescribed between them. Instead of imposing a full order on the set of operations, we can only define a partial order.

Prerequisites of an operation
Every operation performed on an object is made within the context of prior information. All of the transactions that lead up to the current state of the object are known. These are prerequisites of the next operation.

Prerequisites are operations that must have occurred prior to a given operation. If those prerequisites themselves have prerequisites, we can trace a tree back to its root. This gives us a list of operations that must have occurred in the given order. But parallel branches of this tree that split off from the root could have occurred before or after any other branch.

Going back to the canonical chess board example, we have three operations:

  • CreatePlayer(): Player
  • CreateGame(black: Player, white: Player): Game
  • MakeMove(from: int, to: int, game: Game, prior: Move ?): Move

chess-game-model.pngA game must have two players. Those player objects must have been created prior to the game. Each move is made within the context of one game. The prior move must have been made before the current one. The first move will have a null prior, hence the question mark.

This chain of prerequisites constrains the moves such that they must have been made in the specified order. It makes no sense to play the moves out of order. But if the players decide to start a parallel game, that one is completely isolated. It could have occurred before, after, or during the current game, with no loss of integrity.

With this, we have enough theory to build a robust synchronization system. This system uses atomic operations for persistence, representation, caching, and communication. It relies upon the three axioms that we've just discussed:

  • All object behavior is either dependent or independent.
  • An object’s state is dependent upon its history.
  • Prerequisites define a partial order among transactions.

Now it's time to turn the theory into practice.

Leave a Reply

You must be logged in to post a comment.