The problem emerged from a practical case, but thinking on it resulted more and more theoretical directions.

Typically, the lock-free algorithms do relative simple things in the practice, but their implementation is already not very simple. It has mainly debuggability reasons. However, it shouldn't be so, if there would be a way to construct lock-free algorithms automatically.

Consider we have:

  1. a (not very big) set of simple atomic operations
  2. a not lock-free algorithm, which uses exclusively these atomic operations, but itself is not lock-free. We can formally specify:
    1. what the algorithm does (= how the result depends on the initial state)
    2. how does it (= essentially the executed operations)

Is it, at least in theory, possible, to construct a lock-free version of the same algorithm algorithmically, if it is possible?

I think, if the answer is "no" in the general case, maybe it can be still possible with an (ideally, not very strict) condition on the algorithms, or on the operations.

  • $\begingroup$ Note: "lock-free" is a different, and typically much stronger thing as thread-safety. It is not enough to simply put a big lock before and after the procedure. It is like making a thread-safe algorithm without locks. $\endgroup$ – peterh Sep 26 '17 at 21:34
  • 1
    $\begingroup$ If your algorithm can be expressed in terms software transaction memory operations, i.e. your "atomic" operations can be implemented with STM, then you're done. Simply swap in those implementations. This may not be the most efficient approach though. $\endgroup$ – Derek Elkins left SE Sep 26 '17 at 21:59
  • $\begingroup$ @DerekElkins Thanks, I am reading after it! Beside that, my current best idea until now was some analogy to the determinization of the non-deterministic state machines, but I didn't get too far. $\endgroup$ – peterh Sep 26 '17 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.