Created
April 29, 2019 17:57
-
-
Save aphyr/8e661dc2e45b35cd451f4831c524bb92 to your computer and use it in GitHub Desktop.
Cycle detection examples
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Let: | |
T1 = {:type :ok, :f :txn, :value [[:append 1 4] [:r 0 nil]], :process 3, :time 8230766125, :index 17} | |
T2 = {:type :ok, :f :txn, :value [[:r 1 [2]] [:r 1 [2]] [:append 0 3]], :process 4, :time 8212723312, :index 15} | |
Then: | |
- T1 < T2, because T1 observed the initial (nil) state of 0, which T2 created by appending 3. | |
- However, T2 < T1, because T2 did not observe T1's append of 4 to 1: a contradiction! | |
Let: | |
T1 = {:type :ok, :f :txn, :value [[:r 0 [3 5 6]] [:append 1 8]], :process 2, :time 8488927073, :index 31} | |
T2 = {:type :ok, :f :txn, :value [[:r 1 [2 4 6 7]] [:append 0 7] [:append 0 8]], :process 3, :time 8499796717, :index 33} | |
Then: | |
- T1 < T2, because T1 did not observe T2's append of 7 to 0. | |
- However, T2 < T1, because T2 did not observe T1's append of 8 to 1: a contradiction! | |
Let: | |
T1 = {:type :ok, :f :txn, :value [[:r 4 [1 2 3 5 6 10 11 12 13 16 17 18]] [:append 5 9] [:r 4 [1 2 3 5 6 10 11 12 13 16 17 18]]], :process 1, :time 11156581037, :index 279} | |
T2 = {:type :ok, :f :txn, :value [[:r 5 [1 2 4 5 7 8 6 11 12]] [:append 4 19] [:append 4 20]], :process 4, :time 11215063193, :index 281} | |
Then: | |
- T1 < T2, because T1 did not observe T2's append of 19 to 4. | |
- However, T2 < T1, because T2 did not observe T1's append of 9 to 5: a contradiction! | |
Let: | |
T1 = {:type :ok, :f :txn, :value [[:append 7 25] [:r 8 [1 2]] [:r 8 [1 2]]], :process 0, :time 14037686088, :index 463} | |
T2 = {:type :ok, :f :txn, :value [[:r 7 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24]] [:append 8 3] [:append 8 4]], :process 14, :time 14045729710, :index 467} | |
Then: | |
- T1 < T2, because T1 did not observe T2's append of 3 to 8. | |
- However, T2 < T1, because T2 did not observe T1's append of 25 to 7: a contradiction! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment