txn-rw-register workload does not detect g0 write cycles under read-uncommitted consistency

[sitano]

Maelstrom does not detect g0 (write-cycle) for me, like in the following history:

t3:           ["r",0,1],["w",0,10],                               ["r",0,3],["w",0,11]
t2: ["w",0,1],["r",0,1],           ["r",0,10],["w",0,2],["w",0,3],["r",0,3]

So t2 observes the read value of 3 at operation index 5 (0-indexed), while it just previously wrote 2 and 3 on top of ww-conflict (10). It's a G0 and maelstrom ignored it.

$ go build && ~/.../maelstrom test -w txn-rw-register --bin ./maelstrom-txn --node-count 1 --time-limit 20 --rate 10 --concurrency 10n --consistency-models read-uncommitted --max-txn-length 20 --max-writes-per-key 10000000 --key-count 1

2023/03/29 12:11:11 Received {c3 n0 {"txn":[["w",0,1],["r",0,null],["r",0,null],["w",0,2],["w",0,3],["r",0,null],["w",0,4],["r",0,null],["r",0,null],["r",0,null],["w",0,5],["w",0,6],["r",0,null],["w",0,7],["w",0,8],["r",0,null],["w",0,9]],"type":"txn","msg_id":1}}
910670418 + 0 = 1 [#2]  - write key 0, value 1, tx 2
991888336 - 0 = 0 [#2]
2023/03/29 12:11:11 Received {c4 n0 {"txn":[["r",0,null],["w",0,10],["r",0,null],["w",0,11]],"type":"txn","msg_id":1}}
997560527 - 0 = 0 [#3]
8713188 + 0 = 10 [#3] - write key 0, value 10, tx 3 (ww-edge)
17116025 - 0 = 0 [#2]
60262526 + 0 = 2 [#2] - write key 0, value 2, tx 2 (ww-edge - cycle with 3)
77438615 + 0 = 3 [#2] - write key 0, value 3, tx 2 (ww-edge - cycle with 3)
90639108 - 0 = 0 [#2] - read key 0, value 3, tx 2 (wr-edge - cycle with 3)
...
2023/03/29 12:11:12 Sent {"src":"n0","dest":"c4","body":{"in_reply_to":1,"txn":[["r",0,1],["w",0,10],["r",0,3],["w",0,11]],"type":"txn_ok"}}
2023/03/29 12:11:12 Sent {"src":"n0","dest":"c3","body":{"in_reply_to":1,"txn":[["w",0,1],["r",0,1],["r",0,10],["w",0,2],["w",0,3],["r",0,3],["w",0,4],["r",0,11],["r",0,17],["r",0,19],["w",0,5],["w",0,6],["r",0,14],["w",0,7],["w",0,8],["r",0,34],["w",0,9]],"type":"txn_ok"}}

Here we have many cycles of tx 2 and tx3: w2(1), w3(10), w2(2), w2(3). MS could alone detect the g0 based only on the received responses going from that (1) every written value is unique (2) all writes in those 2 txs covered with reads.

[aphyr]

Right, so I think this is a shortcoming in Elle's rw-register checker, which does pretty much all its inference through external reads and writes--IIRC, my rationale was that internal anomalies would be glaringly obvious, and it offers a pretty major speedup--a lot of problems gain an extra level of iteration if you consider internal reads/writes. I took a stab at changing that, and after seven hours I have to admit--this is a bigger problem than I was hoping. Elle is... fantastically complex, and has a lot of moving parts. Gotta shelve this for now.

[sitano]

Thank you @aphyr for your quick response and for all the work you have put into the Elle! This is an incredible project. And thank you for the Maelstrom. I had lots of pleasure playing with it. I will leave this thing open for future interesants. If you want just close it.

[tobiajo]

I don't know yet what a g0 write cycle is but my read ("r") responses can be completely arbitrary and still pass the same workload. To verify the boilerplate I had sat up, I simply put returned the same txn payload from request in the reply. No logic at all and to my surprise "Everything looks good!". Even a random integer as read value will do.

Is that the same issue as @sitano reported?

[aphyr]

Naw, that's more like a garbage read, which is also something the rw-register workload should detect, but doesn't, because I am lazy and my entire life has been consumed with moving and house repairs for the last six months :(

[tobiajo]

I have now also reproduced the same with read-committed consistency. Random integers or null as read value passes for example:

maelstrom test -w txn-rw-register --bin ~/go/bin/maelstrom-txn --node-count 2 --concurrency 2n --time-limit 20 --rate 1000 --consistency-models read-committed --availability total –-nemesis partition