README.md 5.8 KB
Newer Older
1
2
3
4
5
- [Artifact of the article **SASA: a SimulAtor of Self-stabilizing Algorithms** published in TAP 2020](#org8ae01f0)
  - [Using The TAP Virtual Machine](#org06c1764)
  - [Using Docker](#orgc68a614)
    - [Instructions to generate the data contained in Fig.1 of Section 2](#orgb862449)
    - [Instructions to generate the data contained in Table 1 of Section 4](#org31b988d)
erwan's avatar
erwan committed
6
7


8

9
<a id="org8ae01f0"></a>
erwan's avatar
erwan committed
10
11
12

# Artifact of the article **SASA: a SimulAtor of Self-stabilizing Algorithms** published in TAP 2020

13
The objective of this artifact is to show how to replicate the experiments mentioned in [this article](https://hal-cnrs.archives-ouvertes.fr/hal-02521149).
erwan's avatar
erwan committed
14

15
16
<https://doi.org/10.5281/zenodo.3751283>

erwan's avatar
erwan committed
17
18
19
20
21
22
23
24
This artifact contains:

-   instruction to install the necessary tools;
-   instructions to replay the interactive session described in Section 2 of the paper;
-   instructions to generate the data contained in Table 1 of Section 4.

By following the instructions, you should be able to replay the experiments, but for more information on how to use the toolset, please visit:

25
26
-   <https://verimag.gricad-pages.univ-grenoble-alpes.fr/vtt/tags/sasa/>
-   <https://verimag.gricad-pages.univ-grenoble-alpes.fr/synchrone/sasa/>
erwan's avatar
erwan committed
27
28


29
<a id="org06c1764"></a>
erwan's avatar
erwan committed
30
31
32
33
34

## Using The TAP Virtual Machine

All the instructions can be found here <http://www-verimag.imag.fr/reproducible-research/TAP2020_ARTIFACT>

35
They should be executed under a VM that you should find here: <https://doi.org/10.5281/zenodo.3751283>
erwan's avatar
erwan committed
36
37
38
39

cf <https://tap.sosy-lab.org/2020/callforartifacts.php>


40
<a id="orgc68a614"></a>
erwan's avatar
erwan committed
41
42
43

## Using Docker

44
You can mimic one the CI job defined in [.gitlab-ci.yml](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/reproducible-research/sasartifact/blob/master/.gitlab-ci.yml). For instance, if you want to do as in the `expe-dockver` job, you just need to run docker using the `jahierwan/verimag-sync-tools` image (which is available in the cloud) as follows:
erwan's avatar
erwan committed
45
46

```sh
47
git clone https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/reproducible-research/sasartifact.git 
erwan's avatar
erwan committed
48
49
50
51
52
53
54
55
cd expe
docker run --user `id -u` \
    -v "$PWD":/current_dir -w /current_dir \
    -e DISPLAY=$DISPLAY \
    -v /tmp/.X11-unix:/tmp/.X11-unix  \
    -i -t jahierwan/verimag-sync-tools $@
```

56
57
58
59
If the last command has run without problem, you are inside a docker image where:

-   all the necessary tools are installed
-   the `expe` directory (coming from the clone) is accessible
erwan's avatar
erwan committed
60

61
You can thus proceed with the instructions below.
erwan's avatar
erwan committed
62
63


64
<a id="orgb862449"></a>
erwan's avatar
erwan committed
65

66
67
68
### Instructions to generate the data contained in Fig.1 of Section 2

The implementation of Algorithm 1 (top of Page 3) can be found in [expe/async-unison/p.ml](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/reproducible-research/sasartifact/blob/master/expe/async-unison/p.ml)
erwan's avatar
erwan committed
69
70
71

In order to replay the interactive session described in Section 2, you need to type the following commands in a terminal:

72
73
74
75
```sh
cd async-unison
make rdbg4
```
erwan's avatar
erwan committed
76

77
You ought to be prompted to type `<Enter>` or `q` and then `<Enter>` Choose the first proposal and press the `<Enter>` key; this creates a default session using commands defined in [expe/async-unison/Makefile](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/reproducible-research/sasartifact/blob/master/expe/async-unison/Makefile) by the `rdbg4` rule.
erwan's avatar
erwan committed
78
79
80
81

You ought to see:

1.  A pdf view of 4x4 grid with enabled nodes in green, and active ones in orange. This pdf corresponds to the configuration 1 of Fig1 in the article. The active nodes (among the enabled ones) are not necessarily the same as in the article as we did not set the seed of the pseudo-random generator.
82
2.  the `(rdbg)` prompt in your terminal
erwan's avatar
erwan committed
83

84
At the `(rdbg)` prompt, type `sd` and `<Enter>`. This will make the simulation move 1 step forward, and update automatically the pdf view that shows up something equivalent to Configuration 2 in Fig1.
erwan's avatar
erwan committed
85

86
At the `(rdbg)` prompt, type `<Enter>` to replay the last command (i.e., `sd`), and hence move to Configuration 3.
erwan's avatar
erwan committed
87

88
Type `<Enter>` 3 more times to see Configurations 4, 5, and 6 of Fig.1.
erwan's avatar
erwan committed
89

90
Type `q` to exit.
erwan's avatar
erwan committed
91
92


93
<a id="org31b988d"></a>
erwan's avatar
erwan committed
94
95
96

### Instructions to generate the data contained in Table 1 of Section 4

97
In order to run the experiments described in Section 4, type in a terminal, from the [expe](https://gricad-gitlab.univ-grenoble-alpes.fr/verimag/reproducible-research/sasartifact/blob/master/expe) directory:
erwan's avatar
erwan committed
98

99
```sh
erwan's avatar
erwan committed
100
make expe
101
```
erwan's avatar
erwan committed
102

103
It launches the experiments on 2 small graphs (`grid.dot` and `ER.dot`). It should last a few minutes. Once the previous command returns, you can launch:
erwan's avatar
erwan committed
104

105
106
107
```sh
find . -name \*.log
```
erwan's avatar
erwan committed
108
109
110

to see the generated log files. Those files contain the memory usage and the execution time of each individual experiment. If you launch:

111
112
113
```sh
make save_result
```
erwan's avatar
erwan committed
114

erwan's avatar
erwan committed
115
a (sed) script will parse those .log files to generate a `summary.org` file and save generated files in a directory named `results`. The summary.org file ought to contain a summary of all the experiments you have just performed. Table 1 was obtained out of it.
erwan's avatar
erwan committed
116

117
The correspondence between directory names and the Column 1 names is
erwan's avatar
erwan committed
118
119
120
121
122
123
124
125
126
127

-   bfs-spanning-tree : BFS
-   dfs : DFS-a
-   dfs-list: DFS-l
-   coloring : COL
-   unison : SYN
-   async-unison : ASY

The corresponding algorithms are encoded in file p.ml of each directory.

128
If you want to generate the experiment results for the 2 bigger graphs (`biggrid.dot` and `bigER.dot`), you need to be more patient (a few hours) and to launch:
erwan's avatar
erwan committed
129

130
131
132
133
```sh
make bigexpe
make save_result
```
erwan's avatar
erwan committed
134

135
Some remarks, comparing the results announced in the paper and the ones obtained on your machine:
erwan's avatar
erwan committed
136
137

-   The number of seconds (time/step) may differ as the table was obtained using an other machine.
138
-   Some examples may run out of memory on your machine: the dfs algo on `hugeER.dot` and `biggrid.dot`. Indeed, as one can notice in Table 1, those examples require a lot of memory (6.6 and 29 G) that your machine may not have.