After finishing rewriting my paper on this subject for PPoPP, several things are apparent:
1) CAS, LL/SC, or bounded-size transactions are the fundamental operation, not consensus. Consensus objects, because they are one-shot objects, end up increasing costs.
2) The lack of a universal construction is problematic. However, I doubt that such a construction can truly exist, at least for all kinds of objects.
3) The hierarchy emerges from the number of simultaneous CAS operations needed to implement a given data structure. At the moment, I've considered only constant number of operations. However, in a distributed object framework or transactional memory system, we might see something like a binary tree has a simultaneity of O(log2(n))
4) There may be a complexity gap between lock-freedom and wait-freedom. I suspect it to be O(n).
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment