# 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.