Nicholas Mc Guire, DSLab, Lanzhou University, China

Probabilistic synchronization primitives do not provide a deterministic behavior of the error free execution path - they allow for a probability of internal failure. Traditional synchronization primitives are internally deterministic - though only advisory in nature - and have some external error conditions - some of which are detectable. Strictly speaking traditional locks are also probabilistic in nature just that the probabilities associated with the failures are not quantifiable but assumed to be "extremely low" and thus tolerable.

With increasing number of cores though the cost of determinism is becoming problematic. At the same time the general assumption is that systems will not bet simpler in the future but tend towards even higher complexity. This is also true for hardware, where minimum feature size is approaching ranges where increased non-determinism at the hardware level is becoming visible (e.g. in asynchronous cache logic).

The key question for the design of a probabilistic synchronization primitive is - what level of failure probabilist is tolerable?

In 2011 we published our first quite speculative results on a probabilistic concurrency control called pWCS (probabilistic Write Copy Select). pWCS covered the problem of consistent access to a shared resource with a single writer asynchronously updating the shared object - more of less with arbitrary number of concurrent readers. This quite obviously begged the question of how to deal with multiple writers. Addressing this question is what the pMTX (Probabilistic MuTeX) project set out to do.

We introduce first code experiments and results on small multi-core systems. A first analysis of the types of inconsistencies found along with the possible mitigations are discussed.