Wow, "Testing shared memories" paper is a gem. Last night I combined an idea from the paper with Jepsen and the complexity of checking linearizability dropped from O(n!) to O(n). It made possible to run consistency checking experiments for hourshttps://github.com/rystsov/fast-jepsen …
Does O(n!) mean n factorial in this context? Never seen it been used in big O notation before, so just checking if I understood it correctly 
-
-
Yes, it's factorial. Linearizability check belongs to NP-complete class and usually solving NP problems requires checking all permutations hence the factorial.
-
"Testing shared memory" paper adds restrictions which don't limit applications much (all writes have compare-and-set precondition) but shift the problem to O(n ln n) space. Also when all clients access a system from the same node (Jepsen case) O(n ln n) becomes O(n).
End of conversation
New conversation -
-
-
Yes!
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.