Linearizability

Legacy: This article describes a concept that has been superseded in the course of ongoing development on the Organic Design wiki. Please do not develop this any further or base work on this concept, this is only useful for a historic record of work done. You may find a link to the currently used concept or function in this article, if not you can contact the author to find out what has taken the place of this legacy item.

On Wikipedia it is stated that:

"The easiest way to achieve linearizability is by forcing groups of primitive operations to run sequentially using critical sections and mutexes. Strictly independent operations can then be carefully permitted to overlap their critical sections, provided this does not violate linearizability. Such an approach must balance the cost of large numbers of mutexes against the benefits of increased parallelism.

Another approach, favoured by researchers but usually ignored by real programmers as too complex, is to design a linearizable object using the native atomic primitives provided by the hardware. This has the potential to maximise available parallelism and minimise synchronisation costs. Unfortunately, it also generally requires correctness proofs that are publishable results, as almost every conference on concurrent programming since the start of the 90s has demonstrated."

This is the method is that the project is using - the nodal-core provides the atomic primitives which integrate with the hardware level as closely as possible.

Starvation and lockups are reduced by the ability to distribute the use of resource over the network - ie optimisation of the parts is handled by the whole.

The OS part of the project (peerix) will use the local nodal space as its filing system, and use a nodal interface, but it still runs over the Linux kernel and therefore we have no control over the wait/lock performance of that level.

Why do we need to start at such a basic level, when powerful high-level data-structures already exist in most programming environments that can easily support this? Because writing a program that uses lock-free data structures is not a simple matter of merely rewriting the algorithms you would normally protect with a mutex to be lock-free.

Because lock-free algorithms are so difficult to write, researchers focus on writing lock-free versions of basic data structures such as stacks, queues, sets, and hash tables. These allow programs to easily exchange data between threads asynchronously.

For example, consider a banking program where each thread represents a virtual teller. A lock-based approach to making a deposit could be to have one teller lock an account to make a deposit, so that two tellers don't try to deposit into the same account simultaneously. To make the process lock-free, rather than designing a lock-free "deposit" algorithm you might have the teller submit a "deposit" request asynchronously to a centralized thread that handled all deposits.