Search for worst-case initial configurations
A simulator is useful to study the time complexity of algorithms, e.g., to experimentally check whether existing theoretical bounds are correct or tight. Once the topology is fixed, there remains two sources of non-determinism: one coming from the daemon (cf potential-function), and one coming from the choice of the initial configuration.
In this tutorial, we demonstrate how sasa
can be used to search for
“bad” initial configuration (in terms of steps).
Preliminaries
Let’s download an example available in the git repository (if you haven’t
already done this clone in other vtt posts) and go to the async-unison
directory.
[ -d "sasa" ] || git clone https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/synchrone/sasa.git
cd sasa/test/async-unison
make er20.dot # generate a random topology with 20 nodes
make er20.cmxs # compile what's needed
sasa -sd er20.dot
sasa -sd er20.dot # run it several times with a synchronous daemon
In this directory, the configuration initialization function
is such that a new configuration is chosen at random at each new
simulation. If we run it with a deterministic daemon, such as the
synchronous one, we can observe that indeed, the number of moves/steps
differs from run to another. Since sasa
outputs the seed that has
been used to chose the configuration, one can run several
simulations, and remember the seed that led to the
worst-case. However, sasa
also has an option to perform this
process more easily.
Global search
sasa -cd er20.dot --global-init-search 100 # or -gis 100, for short
[...]
Hey, I've found a conf of cost 7! (simu #2)
Hey, I've found a conf of cost 9! (simu #11)
Hey, I've found a conf of cost 11! (simu #26)
100% of the 100 simulations have been tryied so far...
The worst initial configuration costs 11 : (316 221 137 4 17 166 106 379 187 112 224 22 309 26 355 344 76 27 194 174)
er20.dot.log and er20_wi.dot have been generated
This command will run 100 simulations with random configurations, and
generates a er20_wi.dot
file that contains the configuration that
led to the step worst-case (i.e., the simulation that used the bigger
number of steps before stabilizing).
If you have a multicore architecture, you can run those simulations in parallel:
sasa -cd er20.dot -gis 100 --cores-nb 20
Local search
Instead of choosing initial configurations completely at random,
sasa
can also chose initial configurations that are “close” to
the previous one, and can thus perform a local search.
sasa -cd er20.dot --local-init-search 100 # or -is 100, for short
If you want to combine both kinds of searches:
sasa -cd er20.dot -gis 100
sasa -cd er20_wi.dot -is 100
Note that any kind of daemon can be used to “evaluate” the quality if the initial configurations.
sasa --greedy-central-daemon er20.dot -is 100
Cf this article for more details.