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.

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

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.