Stopping, completing, reversing and concurrency

Keeping on schedule is tough, but I want to keep to this Wednesday thing. I want to talk about some concepts that seem to be important to concurrency (more specifically, shared memory concurrency) but don't seem to be distinguished too often.

The first concept is stopping, a process can stop for a number of reasons. One thing to think about is what happens when a process stops. In lock based systems, it usually means that a lock won't get released, so a process can't continue running. So one of thing that is nice to do is to ensure that the system can keep running even if a process stops. Also, in some systems, such as a database, it is also good to be able to arbitrarily stop a process, perhaps to be able to undo a deadlock.

Once a process is stopped for some reason, in the middle of some action, what do we do now? In some cases we can just ignore the process, but usually this is not desirable. If we could complete the process' action then we should be ok. One way to do this is to use descriptors for actions, which would give a full description of what was to be done. Then it is possible for another process to complete the stopped process' action. In many lock-free algorithms, this completion is attempted immediately, to fulfill the lock-free progress condition. But helping is expensive. I prefer to think that the descriptor now gives you the option of helping, and helping is safe, but we should manage this helping to increase efficiency. Descriptors work for many actions, like as data structure operations such as add and delete. For a whole transaction, this information may be a lot harder to store, it has to include most, or all the power of a programming language.

There is another option, if we can't ignore the action and can't complete it, maybe we can reverse it and make it like it didn't happen. Reversing can be easier than completing, there are many ways to reverse, taking snapshots, recording actions performed and more. This is a good option for transactional systems, since full information cannot be known about the transaction, and even if it is, you know that reversing will be able to complete, but you don't know if the transaction will halt.

Stopping, completing and reversing are important concepts. It would be nice if there was a richer theory behind it. Reversing of operations is used in work by Herlihy and others in Transactional Boosting, in order to be able to use lock-free data structures with transactional memory, we need to be able to reverse things that happened to the data structure. These data structures require different augmentations to handle reversing. In some cases the ability to reverse or complete may depend on the current state of the system.

Two other aspects that are also important are idempotence and commutativity. These also can depend on the current state of the system.

I think a solid theory of stopping, completing, reversing, idempotence and commutativity operations on data structures would go a long way to making it easier to work with lock-free data structures.