Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Distributed Algorithms #61

Draft
wants to merge 262 commits into
base: develop
Choose a base branch
from
Draft
Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
262 commits
Select commit Hold shift + click to select a range
157e0f4
Add docs to distributed API
olgalupuleac Dec 1, 2020
d2f3a3f
Add distributed failure detector algorithm as an example
olgalupuleac Dec 1, 2020
91dd70f
Merge remote-tracking branch 'origin/develop' into distributed-systems
olgalupuleac Dec 7, 2020
3aa7f0c
Make 'Message' a generic parameter in distributed algorithms
olgalupuleac Dec 9, 2020
c1893b1
Merge remote-tracking branch 'origin/develop' into distributed-systems
olgalupuleac Dec 9, 2020
1904435
Add API to distributed systems to validate messages
olgalupuleac Dec 9, 2020
5cd6e56
Merge remote-tracking branch 'origin/develop' into distributed-systems
olgalupuleac Dec 15, 2020
277d3c6
Add distributed mutex test
olgalupuleac Dec 15, 2020
ba3a161
Add token based distributed algorithm as test
olgalupuleac Dec 15, 2020
7a8f7a9
Fix distributed test API
olgalupuleac Dec 15, 2020
7d0e1a8
Add correct broadcast implementation for distributed algorithms
olgalupuleac Dec 22, 2020
73c4656
Fix incorrect broadcast implementation for distributed algorithms
olgalupuleac Dec 22, 2020
234898a
Add node failure handling for non-suspended methods
olgalupuleac Jan 24, 2021
d504368
Implement Chandy Lamport snapshot algorithm as test
olgalupuleac Feb 1, 2021
1427ce3
Separate message queue from DistributedRunner
olgalupuleac Feb 1, 2021
60a7706
Call 'onFinish' method after node failure without recovery
olgalupuleac Feb 1, 2021
e427d34
Extract 'Probability' and 'FailureStatistics' for stress distributed …
olgalupuleac Feb 1, 2021
9ff261d
Refactor stress distributed runner
olgalupuleac Feb 1, 2021
23a5fb5
Extract incorrect distributed kvstorage into separate file
olgalupuleac Feb 1, 2021
f2cf858
Fix node recovery
olgalupuleac Feb 1, 2021
f51a153
Fix 'onNodeFailure' for distributed runner in test thread execution
olgalupuleac Feb 2, 2021
6e6f2a8
Add access to logs for nodes
olgalupuleac Feb 2, 2021
3be74b3
Add 'Log' generic parameter to Environment in test algorithms
olgalupuleac Feb 2, 2021
0b651cc
Drft of coroutine design of DistributedRunner
olgalupuleac Feb 9, 2021
74ec9a2
Draft of TestNodeExecutionGenerator
olgalupuleac Feb 11, 2021
5336754
Draft of message delivery algorithm to test distributed lincheck
olgalupuleac Feb 11, 2021
3c67ce0
Draft of Raft algorithms to test distributed lincheck
olgalupuleac Feb 11, 2021
1a1b9fd
Add 'defineClass' for TestNodeExecution class
olgalupuleac Feb 11, 2021
ccaf23d
Add 'runOperationsAsyncronously' param to DistributedOptions
olgalupuleac Feb 11, 2021
ca60ba5
Join thread in NodeExecutor
olgalupuleac Feb 11, 2021
b5989c4
Change nodes' launch in DistributedRunner
olgalupuleac Feb 11, 2021
f6d5003
Remove unused import
olgalupuleac Feb 11, 2021
f0c286d
Fix 'NodeFailureResult' generation
olgalupuleac Feb 11, 2021
b259aee
Generate 'rupOperation(i)' to lauch node method
olgalupuleac Feb 13, 2021
f58e538
Implement draft of stress strategy of ds based on coroutines
olgalupuleac Feb 14, 2021
722d992
Fix 'FastQueue'
olgalupuleac Feb 24, 2021
477317a
Minor changes in TestNodeExecution and TestNodeExecutionGenerator
olgalupuleac Feb 26, 2021
618846d
Fix bugs in FastQueue
olgalupuleac Feb 26, 2021
42dbfec
Prevent node from broadcasting message to itself
olgalupuleac Feb 26, 2021
bacf61d
Implement new version of NodeExecutor
olgalupuleac Feb 26, 2021
e39dfd3
Rewrite part of test algorithms to coroutine style
olgalupuleac Feb 26, 2021
9a27b07
Implement new version of 'NodeFailureInfo'
olgalupuleac Feb 26, 2021
a8cadee
Modify 'Environment' interface
olgalupuleac Feb 26, 2021
6859978
Implement class to get ids for different node classes
olgalupuleac Feb 28, 2021
5a30970
Add 'reset' method to NodeFailureInfo
olgalupuleac Feb 28, 2021
3711c87
Extract DistributedRunner fields to DistributedRunnerContext
olgalupuleac Feb 28, 2021
bfec6a5
Extract EnvironmentImp into separate file
olgalupuleac Mar 2, 2021
854e3a0
Fix DistributedOptions
olgalupuleac Mar 2, 2021
d7f6f89
Fix 'NodeFailureInfo' in case of no failures
olgalupuleac Mar 2, 2021
89c2115
Add 'add' method to NodeExecutorContext
olgalupuleac Mar 2, 2021
cbf0fad
Modify Node and Environment interfaces
olgalupuleac Mar 2, 2021
5b812ab
Remove unused fields from TestNodeExecution
olgalupuleac Mar 2, 2021
c9581bb
Remove magic constants from 'Probability'
olgalupuleac Mar 2, 2021
8a5701b
Fix DistributedRunnerContext
olgalupuleac Mar 2, 2021
01b5794
Support node recoveries in runner for coroutines
olgalupuleac Mar 2, 2021
180d1a4
Add consensus with no failures + remove and rename some files
olgalupuleac Mar 3, 2021
5d17c32
Fix failures without recoveries
olgalupuleac Mar 3, 2021
5c61f0b
Implement naive consensus without failures
olgalupuleac Mar 3, 2021
f5233bb
Rewrite Chandy-Lamport algorithm to coroutine style
olgalupuleac Mar 3, 2021
e06f710
Modify distributed mutex algorithms
olgalupuleac Mar 4, 2021
43cf426
Merge remote-tracking branch 'origin/develop' into distributed-systems
olgalupuleac Mar 4, 2021
c38e63b
Fix node recovery (without timeout)
olgalupuleac Mar 6, 2021
aea5aeb
Fix NodeExecutor counter for 'withTimeout'
olgalupuleac Mar 9, 2021
b06a380
Comment out saving bytecode to file
olgalupuleac Mar 9, 2021
8a20657
Add and fix tests for distributed algorithms
olgalupuleac Mar 9, 2021
084de9d
Add 'AlreadyIncrementedContext' and change executor to dipatcher
olgalupuleac Mar 12, 2021
4cd278b
Implement asynchronous message order for coroutine style
olgalupuleac Mar 12, 2021
2aafff6
Add 'getLogs' to Environment
olgalupuleac Mar 12, 2021
96669cb
Fix broadcast test
olgalupuleac Mar 12, 2021
0ab9455
Add 'Signal primitive' and save current state
olgalupuleac Mar 13, 2021
15cd79f
Add test for multiple node types
olgalupuleac Mar 13, 2021
4bb3042
Fix test names
olgalupuleac Mar 13, 2021
b25b005
Change tests
olgalupuleac Mar 15, 2021
5acfb7c
Add verifier for failures
olgalupuleac Mar 15, 2021
ecc40db
Add no failure mode for some types of nodes
olgalupuleac Mar 17, 2021
b31d7fd
Rollback TestThreadExecutionGenerator
olgalupuleac Mar 17, 2021
db7d1a6
Add mixed recovery mode
olgalupuleac Mar 17, 2021
7dc2e19
Change recovery mode in Broadcast test
olgalupuleac Mar 17, 2021
5809fab
Fix thread local random
olgalupuleac Mar 17, 2021
6c88771
Fix bugs with recoveries
olgalupuleac Mar 18, 2021
0fd35b1
Fix state representation
olgalupuleac Mar 18, 2021
efb527a
Rename file
olgalupuleac Mar 18, 2021
88e0f84
Fix code style in tests
olgalupuleac Mar 19, 2021
96978b4
Renamed test
olgalupuleac Mar 22, 2021
20d2696
Add times and other fixes
olgalupuleac Mar 28, 2021
aae369f
Add replica tests
olgalupuleac Mar 28, 2021
4fa8479
Fix timeouts
olgalupuleac Mar 30, 2021
f6600fa
Implement Raft (draft)
olgalupuleac Mar 30, 2021
7055593
Move actorIds to TestNodeExecution
olgalupuleac Mar 30, 2021
5439858
Fix crash in TestNodeExecution
olgalupuleac Mar 30, 2021
acadd70
Add sequantial specification for mutex
olgalupuleac Mar 31, 2021
d1726e6
Add some debug info
olgalupuleac Mar 31, 2021
02d8d86
Change number of iterations and invocations in Lamport mutex
olgalupuleac Mar 31, 2021
d0cf830
Fix merge conflicts
olgalupuleac Apr 1, 2021
fd761df
Set 'minimizeScenario' to true
olgalupuleac Apr 1, 2021
4eea954
Add extra nodes minimization
olgalupuleac Apr 10, 2021
9c4414e
Add draft of probability model
olgalupuleac Apr 11, 2021
994c0aa
Add documentation and refactor NodeDispatcher
olgalupuleac Apr 11, 2021
3bca58f
Fix launching 'onMessage'
olgalupuleac Apr 11, 2021
eedc6e6
Fix launching coroutines
olgalupuleac Apr 12, 2021
8aeb615
Clean NodeDispatcher
olgalupuleac Apr 13, 2021
e06613b
Add docs for Node interface
olgalupuleac Apr 13, 2021
924726c
Some refactorings
olgalupuleac Apr 25, 2021
2e2f0a3
Fix distributed strategy
olgalupuleac Apr 25, 2021
9bcf123
Remove some debug output
olgalupuleac Apr 25, 2021
a2ca99a
Some refactoring
olgalupuleac Apr 25, 2021
fa8c628
Try to fix Raft
olgalupuleac Apr 28, 2021
02c9915
Fix probability distribution
olgalupuleac May 1, 2021
d6b3eed
Minimize crash probability & other fixes
olgalupuleac May 4, 2021
a5e143c
Fixes in Raft algorithm
olgalupuleac May 4, 2021
bb0ee55
Use CAS to change crash info
olgalupuleac May 4, 2021
e1e5ace
Add network partitions
olgalupuleac May 4, 2021
f59a0da
Fix network partitions
olgalupuleac May 4, 2021
8a3d3da
Remove debug output
olgalupuleac May 4, 2021
cd4bf1d
Add test
olgalupuleac May 5, 2021
e3444d3
Add storage to Raft
olgalupuleac May 5, 2021
5a29c07
Some fixes in Raft
olgalupuleac May 6, 2021
c6a4eb0
Add initial model checking model
olgalupuleac May 6, 2021
93ee1c5
Intermediate commit in model checking
olgalupuleac May 10, 2021
b466953
Model checking works for inversions
olgalupuleac May 11, 2021
965aecf
Fix bug in model checking
olgalupuleac May 11, 2021
5783b75
Add choosing failure
olgalupuleac May 11, 2021
b5f82b0
Try to add crashes to model checking
olgalupuleac May 17, 2021
5c79615
Reuse executors between dispatchers
olgalupuleac May 17, 2021
d44b708
Run onMessage into the same context
olgalupuleac May 17, 2021
e076f89
Force several nodes crash simultaneously
olgalupuleac May 18, 2021
698b85a
Make onMessage not suspended
olgalupuleac May 25, 2021
d1412f2
Decreased number of used coroutines
olgalupuleac May 25, 2021
f19957b
Current version of model checking
olgalupuleac May 25, 2021
fc1f4a5
Remove unused code from model checking
olgalupuleac May 31, 2021
ebc4c22
Some minor changes
olgalupuleac May 31, 2021
d59c7a9
Change crashMode and networkPartitions
olgalupuleac May 31, 2021
f63a5b0
Add prototype of single network partitions
olgalupuleac May 31, 2021
21dc735
Add testing mode option
olgalupuleac May 31, 2021
24ff0a6
Add network partition single
olgalupuleac May 31, 2021
d3f0783
Fix bug
olgalupuleac May 31, 2021
fca0a50
Finish NetworkCrashInfo
olgalupuleac May 31, 2021
4e7b879
Fix compilation errors
olgalupuleac May 31, 2021
c94c8e5
Fix mutex algorithms
olgalupuleac May 31, 2021
ef3be7c
Change Raft
olgalupuleac May 31, 2021
b07c830
Minor fixes
olgalupuleac May 31, 2021
c63bff2
Fix tests
olgalupuleac May 31, 2021
4a71178
Comment storing logs to file
olgalupuleac May 31, 2021
3d478d7
Increase number of iterations for incorrect broadcast
olgalupuleac May 31, 2021
ee46336
Remove test
olgalupuleac May 31, 2021
fbb8f24
Debug
olgalupuleac May 31, 2021
79e6e21
Remove redundunt test
olgalupuleac May 31, 2021
0ee170c
Comment out Raft tests because of time limit
olgalupuleac May 31, 2021
ddfe10d
Return tests again
olgalupuleac May 31, 2021
7743c7d
Try to make tests pass
olgalupuleac May 31, 2021
0e77bb5
Remove 'minimize failed scenario' for Raft test
olgalupuleac May 31, 2021
c6714d0
Fix Raft
olgalupuleac May 31, 2021
6cce989
Remove some code
olgalupuleac May 31, 2021
a634f1a
Remove some code
olgalupuleac May 31, 2021
4cccd1a
Last changes
olgalupuleac Jul 1, 2021
a892ad8
Fix multiple node crash probability
olgalupuleac Jul 2, 2021
3ee2ad8
Change thread local counter to local
olgalupuleac Jul 5, 2021
65d7f3e
Remove 'collectThreadDump'
olgalupuleac Jul 5, 2021
9b5f808
Fix network partitions single
olgalupuleac Jul 7, 2021
a3c67d2
Merge develop
olgalupuleac Jul 13, 2021
74d5de5
Add new test
olgalupuleac Jul 14, 2021
a88d346
Add queue iplementation
olgalupuleac Jul 14, 2021
1c462b5
Minor fixes & debug output
olgalupuleac Jul 18, 2021
a08e6f9
Fix same interleavings in model checking
olgalupuleac Jul 29, 2021
bed4efb
Fix bugs in stress mode
olgalupuleac Aug 3, 2021
7df7e61
Update model checking
olgalupuleac Aug 31, 2021
bb7e875
Add forgotten file
olgalupuleac Sep 6, 2021
4b59340
Refactor and implement single thread random strategy
olgalupuleac Sep 28, 2021
021acfc
Add json serialization library and update Kotlin version
olgalupuleac Sep 28, 2021
cc3b282
Move 'iNode' inside 'Event'
olgalupuleac Sep 28, 2021
97c68f8
Try to fix dispatcher
olgalupuleac Oct 1, 2021
b52dbeb
Fix compilation errors
olgalupuleac Oct 1, 2021
2896caf
Fix recover after crash
olgalupuleac Oct 5, 2021
a8cff2c
Move event to separate package
olgalupuleac Oct 6, 2021
b9311ff
Fix infra dependency
olgalupuleac Nov 9, 2021
f58027a
Add event formatter
olgalupuleac Nov 9, 2021
d8d360f
Fix access modifiers
olgalupuleac Nov 9, 2021
c8a6a71
Add initial doc about broadcast
olgalupuleac Nov 10, 2021
7fff541
Add new Raft template
olgalupuleac Nov 11, 2021
4c44404
Change persistent storage type (tests do not work)
olgalupuleac Nov 15, 2021
9c7ca48
Implement Raft (doesn't work)
olgalupuleac Nov 18, 2021
77a4f7f
Add TaskManager test
olgalupuleac Dec 2, 2021
abe631b
Add Poisson distribution for choosing timers
olgalupuleac Dec 3, 2021
adb0a6a
Finish TaskManager test
olgalupuleac Dec 6, 2021
c5fb3ab
Fix crash adding
olgalupuleac Dec 6, 2021
ca872ab
Add 'broadcastToGroup' to Environment
olgalupuleac Dec 6, 2021
d16c1c9
Reuse dispatcher
olgalupuleac Dec 6, 2021
acd40fe
Change dispatcher to executor
olgalupuleac Dec 14, 2021
1c55956
Add TimeoutCoroutine and LivelockInvocationResult
olgalupuleac Dec 15, 2021
9ac5bb7
Refactor CrashInfo & add tests for AddressResolver
olgalupuleac Jan 13, 2022
06270b9
Add NodeCrashTest & refactor partitions
olgalupuleac Jan 14, 2022
b04c906
Add CrashInfoSingle implementation
olgalupuleac Jan 16, 2022
293a4d1
Delete all outdated files
olgalupuleac Jan 16, 2022
171fbe0
Fix raft and broadcast test
olgalupuleac Jan 17, 2022
636b4c1
Add recover partition function
olgalupuleac Jan 17, 2022
5177bc1
Remove iNode from partition recover task
olgalupuleac Jan 17, 2022
9f1ea56
Refactor events
olgalupuleac Jan 17, 2022
dd81a67
Fix kvshrding test
olgalupuleac Jan 18, 2022
301074f
Fix remained tests
olgalupuleac Jan 19, 2022
5174fa5
Add Livelock and TaskLimitExceeded failures
olgalupuleac Jan 20, 2022
6583a5c
Made some refactorings
olgalupuleac Jan 22, 2022
53d1f78
Made some refactorings
olgalupuleac Jan 22, 2022
76336d8
Add crash notification test
olgalupuleac Jan 23, 2022
b16d977
Add some docs
olgalupuleac Jan 23, 2022
ba0a5c5
Move Broadcast to another package
olgalupuleac Jan 23, 2022
727e259
Fix bug in timeouts
olgalupuleac Jan 23, 2022
e813775
Add more docs
olgalupuleac Jan 24, 2022
507d8dd
Add some docs
olgalupuleac Jan 24, 2022
387319b
Fix bug when the operation is blocked
olgalupuleac Jan 24, 2022
6d34c6a
Add more docs
olgalupuleac Jan 25, 2022
e9302cc
Clean up code
olgalupuleac Jan 26, 2022
91d9136
Meeting changes
ndkoval Jan 26, 2022
fdf60d7
Fix tests for new API
olgalupuleac Jan 27, 2022
feabf7f
Refactor naive consensus
olgalupuleac Jan 28, 2022
8ab4301
Some fixes in probability & refactorings
olgalupuleac Feb 3, 2022
9d9da1f
Meeting
ndkoval Feb 3, 2022
510a3f0
Add docs to Chandy Lamport
olgalupuleac Feb 3, 2022
11bea26
Meeting
ndkoval Feb 3, 2022
ffbdd98
Separate verification from implementation
olgalupuleac Feb 7, 2022
ee93e3d
Fix bugs in algorithms
olgalupuleac Feb 8, 2022
051bc4f
Fix minimization
olgalupuleac Feb 10, 2022
9b78349
Remove useless option from test
olgalupuleac Feb 10, 2022
d0edbda
Review
ndkoval Feb 10, 2022
b84661d
Fix compile errors
olgalupuleac Feb 10, 2022
dd5f2e0
Add state holder
olgalupuleac Feb 10, 2022
3d2c54b
Remove 'isSignal'
olgalupuleac Feb 10, 2022
6a93f68
Minor changes
olgalupuleac Feb 11, 2022
38813f6
Update Kotlin version
olgalupuleac Feb 12, 2022
9a2f0cb
Refactor DistributedRunner
olgalupuleac Feb 14, 2022
a7be9f8
Delete old Raft implementation
olgalupuleac Feb 14, 2022
df1d79f
Add test for single dege partitions
olgalupuleac Feb 14, 2022
e34c56a
Add comments to FailureManagerComponents
olgalupuleac Feb 14, 2022
9a94552
Move TimeLimitExceeded logit to TaskManager
olgalupuleac Feb 14, 2022
386f140
Refactor NodeEnvironment
olgalupuleac Feb 14, 2022
317e4ad
Fix bug
olgalupuleac Feb 14, 2022
0ae99ef
Add comments
olgalupuleac Feb 14, 2022
16c698e
Remove CompletionCondition and move TimeoutCoroutine
olgalupuleac Feb 14, 2022
bfe95cd
Change TimeoutCancellationException
olgalupuleac Feb 14, 2022
28a019d
Optimize TaskManager and switch off coroutine debug
olgalupuleac Feb 15, 2022
3aa479b
Add log filename to report
olgalupuleac Feb 15, 2022
56ed1f6
Fix minimization
olgalupuleac Feb 15, 2022
9ca642b
Add comments to minimization
olgalupuleac Feb 16, 2022
719c57e
Minor changes
olgalupuleac Feb 16, 2022
0c702f3
Add some comments
olgalupuleac Feb 16, 2022
6078220
Add some extra classes for running interleaving
olgalupuleac Feb 16, 2022
4e12534
Start implementing InterleavingStrategy
olgalupuleac Feb 16, 2022
a3d910e
Set system property inside code
olgalupuleac Feb 16, 2022
2f576b1
Add some docs
olgalupuleac Feb 17, 2022
4301030
Probabilities: does not work :)
ndkoval Feb 17, 2022
eb9a58a
Last changes
olgalupuleac Feb 18, 2022
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Add 'runOperationsAsyncronously' param to DistributedOptions
  • Loading branch information
olgalupuleac committed Feb 11, 2021
commit ccaf23d379f46ed25169c20cf530668e9ddff947
Original file line number Diff line number Diff line change
Expand Up @@ -43,6 +43,7 @@ class DistributedCTestConfiguration<Message, Log>(testClass: Class<*>, iteration
val supportRecovery: Boolean,
val messageDuplication: Boolean,
val networkPartitions : Boolean,
val asyncRun : Boolean,
val nodeTypes: HashMap<Class<out Node<Message>>, Int>,
requireStateEquivalenceCheck: Boolean,
minimizeFailedScenario: Boolean,
Expand Down
Original file line number Diff line number Diff line change
Expand Up @@ -21,6 +21,7 @@ class DistributedOptions<Message, Log> : Options<DistributedOptions<Message, Log
private var networkPartitions: Boolean = false
private var testClasses = HashMap<Class<out Node<Message>>, Int>()
private var useVectorClock = false
private var asyncRun = false

fun networkReliable(isReliable: Boolean): DistributedOptions<Message, Log> {
this.isNetworkReliable = isReliable
Expand Down Expand Up @@ -57,6 +58,11 @@ class DistributedOptions<Message, Log> : Options<DistributedOptions<Message, Log
return this
}

fun runOperationsAsynchronously(asyncRun: Boolean): DistributedOptions<Message, Log> {
this.asyncRun = asyncRun
return this
}

fun networkPartitions(partitions: Boolean): DistributedOptions<Message, Log> {
this.networkPartitions = partitions
return this
Expand All @@ -73,7 +79,7 @@ class DistributedOptions<Message, Log> : Options<DistributedOptions<Message, Log
actorsPerThread, executionGenerator,
verifier, invocationsPerIteration, isNetworkReliable,
messageOrder, maxNumberOfFailedNodes, supportRecovery,
messageDuplication, networkPartitions, testClasses,
messageDuplication, networkPartitions, asyncRun, testClasses,
requireStateEquivalenceImplementationCheck, false,
chooseSequentialSpecification(sequentialSpecification, testClass), timeoutMs
)
Expand Down