Geek asks and answers

Haskell "Wait-free" Data

I was fortunate that the GHC implementation is TVar lock-free , but not wait-free . Are there any implementations that are not available (e.g. Hackage package)?

+3
source share
2 answers

Wait-freedom is a term from distributed computing. The algorithm is unavailable if a stream (or a distributed node) is able to correctly shut down, even if all incoming from other flows are delayed / lost at any time.

If you care about consistency, you cannot guarantee freedom of expectation (provided that you always want to finish correctly, that is, guarantee accessibility). This follows from the CAP theorem [1], since freedom of expectation essentially implies the inadmissibility of partitions.

[1] http://en.wikipedia.org/wiki/CAP_theorem

+3
source

Your question: "Are there any implementations that don't take time?" a bit incomplete. STM (and therefore TVar) is quite complex and has built-in support for the compiler - you cannot build it correctly using Haskell primitives.

- , , IORef MVar ( , ).

+1

More articles:


All Articles