Hi, I want to show in my solution every anomaly mentioned. G1b and G1c are there. G1a (aborted reads) requires aborts. How to do proper aborts in terms of protocol?
Then the maelstrom does not detect G0 (dirty write cycle) or it does not generate them.
The naive implementation of the transaction processor that uses (Warning. Spoiler to 6a/b):
Summary
a single database mutex per the whole database that is ONLY acquired per single PUT/GET operation when the processor wants to do an op to the underlying storage
is immediately suspect to the G0 dirty writes anomaly, but Maelstrom does not detect them. It does not detect G0 even with 1 node, concurrency 10 and rate 10000, tx len 20, keys set 10 - which is nonsense. I of course added sleep to threads to make txn to last longer to improve conflict probability.
Did anyone have any luck seeing G0 in Maelstrom workload anomalies report with read-uncommitted anomaly?
Actually, it seems it just does not work. Here is the history I do have generated that has G0 and the Maelstrom does not see 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"}}
So c3
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.
If it were working correctly, it had to abort at
60262526 + 0 = 2 [#2] - write key 0, value 2, tx 2 (ww-edge - cycle with 3)
according to the definition from Challenge #6b: Totally-Available, Read Uncommitted Transactions · Fly Docs
G0 (dirty write): a cycle of transactions linked by write-write dependencies. For instance, transaction T1 appends 1 to key x, transaction T2 appends 2 to x, and T1 appends 3 to x again, producing the value [1, 2, 3].
Here we have many cycles of tx 2 and tx3: w2(1), w3(10), w2(2), w2(3)
. It can easily be proved that the MS could alone detect 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:
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]
Thus, if I am correct. It’s worth changing this line
For a hard challenge, try getting Maelstrom to fail because of a write-write cycle.
at the Challenge #6b: Totally-Available, Read Uncommitted Transactions · Fly Docs to something different as the Maelstrom does not detect ww cycles.