I assume it doesn’t like the n1 read returning 0, but this seems compatible with sequential consistency to me (this is the only operation involving n1, so it seems legitimate for it not to have observed n0’s add yet). It’s relying on seq-kv, and inheriting this behavior from there (n1 isn’t observing a write issued by n0). What are the specific requirements here that this needs to meet?
Thanks for the update. Is there a way to require the same behavior from seq-kv, if this service is meant to be implemented on top of seq-kv?
Under the assumption that adds are more common than reads, I had each node write to its own key to avoid any write contention, and reads read (potentially-stale versions of) other nodes’ keys. If this isn’t permitted for the final read, which is indistinguishable from other reads, it sounds like the requirements are just stronger than sequential consistency (it sounds bit like a partial synchrony assumption, but it seems odd to require it from my service and not from the underlying one it’s supposed to use). Is the specification hinting that it wants all the nodes to CAS a single key or something, to achieve this on top of seq-kv?
Also, looking at the implementation of the workload, it looks like it does try to account for multiple possible states in the final read. So I might still be missing something. This talks about adds that “definitely happened”, but in a sequentially-consistent non-linearizable system, one node is permitted to observe an add as having happened while another one may not see it yet, so I’m not sure what its model is.
Thanks for the response! I figured that CAS approach was being hinted at.
Sequential consistency has a total order so writes ensure that a client sees the latest version. Reads, on the other hand, simply cannot go backwards. I’m not sure if that helps clarify things?
Hmm, are you saying that if you send a write to node A, and then you send a read to node A, and it shows the write, and then you send a read to node B, and it doesn’t show the write, that violates sequential consistency? To me that sounds like some sort of linearizability requirement, not sequential consistency. Sequential consistency just requires the results to be compatible with some total order on operations which is compatible with the order seen by each node. So for
A: add 1
I would think that it’s valid to have B’s read ordered before A’s add. B’s read never went backwards from showing 1 to showing 0 or anything like that, it just didn’t see A’s add yet (because seq-kv didn’t propagate it to B yet). Am I missing something?
Attempting this challenge too and perhaps there is something I don’t understand about sequential consistency. Is it true that if I CAS a value and it succeeds then at some later time I shouldn’t be able to CAS a lesser value (assuming values are only growing)? For example, in the attached screenshot I find 121 in the kv store by CAS, then after I find 119 by CAS.
Hmm, I’m a little confused by the way everyone is talking about sequential consistency! My understanding is: A particular execution is valid as long as all operations and results are compatible with having executed in some total order, such that every node’s individual operation order is a valid suborder. (I.e. each node’s operations are executed in the given order, with an arbitrary interleaving.)
In particular, I don’t see why a read followed by a nop CAS would necessarily give you anything that a read doesn’t – the CAS can always come right after the read in the global order, and you don’t get any real-time guarantees from that, if you communicate with other nodes over a side channel.
Thinking about it, maybe what @benbjohnson2 was getting at can be accomplished with non-identity CAS. If your key holds both the counter value and a globally unique token, and each time you either write or read, you CAS to change the token (while maintaining the value, in read cases), then there’s no valid history where both CASes succeed, since tokens are never reused. E.g.
A: read (0@init)
A: cas 0@init -> 5@A1 (ok)
B: read (0@init)
B: cas 0@init -> 0@B1
If A acknowledges the add, meaning its CAS succeeded, then B’s CAS can’t possibly succeed as well, since the value will never go back to 0@init again (this isn’t true with an identity CAS, because that can happen before A’s CAS and still have them both succeed).
This seems like a very sad counter, with maximal contention on both reads and writes. It also still seems like a stronger requirement than sequential consistency, so I’m still confused about the specification. But it does seem like it could work to force synchronization.
Hi, I was able to solve the question and make the test cases pass, I have a few questions though, and I was hoping someone could answer them.
@benbjohnson1 I am not sure if this is correct, B’s write could also be reordered before A’s read or write. This is told in the formal definition here. Please let me know if I am wrong or right because I am very confused about this.
CAS (CompareAndSwap) is a specialized operation for the purpose of this challenge. The next few lines could be a spoiler.
Did we have to figure out ourselves that a special kind ofCAS can help us force the seq-kv to evaluate the pending actions?
Does the CAS operation exist in real-world scenarios? Any examples?
If you need a few hints, go through this and this.
The comments in this thread by @shachaf were very helpful. He/She does not assume anything other than what Sequential Consistency means, and I also had a lot of the same doubts as him.
The funny thing to me with this problem is the amount of how much it is underspecified.
With CAS ops they are useless IMHO as if you will be CAS-ing a global register you don’t have a guarantee that your CAS has exactly-once semantics. Basically, you don’t know if your CAS was successful or not with even a timeout. Especially with partitioning most of CAS responses can be dropped so you can’t be sure and can’t rely on that. For CASing only your own (node-specific key) its useless as you can just use a Store() call.
Then for the SeqCon model with no constraints on the consistent reads how can you guarantee in the end that you will ever return anything consistent if you are not guaranteed that your process will ever read any other update from the store beside the first one?