Artifact for the paper at OPODIS17

Synthesis of Distributed Algorithms with Parameterized Threshold Guards

This is an artifact that accompanies the paper by Marijana LazićIgor KonnovJosef Widder, and Roderick Bloem, which has been accepted to OPODIS’17. If you have any questions about the artifact or the experiments, feel free to ask Igor Konnov.

1. Virtual machine

You can download the virtual machine (VirtualBox, 64-bit, 1.8 GB) from here.

The virtual machine contains Debian GNU/Linux 3.16 with all necessary packages installed. The packages are installed under the user account named ‘user’ with the password ‘user’. If you have to use the root account, the password is ‘root’. Alternatively, you can also use the ‘sudo’ command.

2. Package structure

The artifact files are located under the directory ‘/home/user/opodis17-submission3’, whose structure is as follows:

  • benchmarks/ contains the benchmarks used in the paper, encoded in generalized threshold automata.
  • bymc/ contains the tool (binaries and source code).

3. Platform requirements

We ran the experiments on two systems:

  • a laptop equipped with 16 GB of RAM and Intel® CoreTM i5-6300U processor with 4 cores, 2.4 GHz, and
  • the Vienna Scientific Cluster (VSC-3) that consists of 2020 nodes, each equipped with 64 GB of RAM and 2 processors (Intel® XeonTM E5-2650v2, 2.6 GHz, 8 cores) and internally connected with an Intel QDR-80 dual-link high-speed InfiniBand fabric.

To run the experiments in your cluster environment, you have to compile the tool according to the instructions found in ~/opodis17-submission3/bymc/README.txt.

4. Installation instructions

This virtual machine already contains all the necessary tools and libraries:

  • ocaml 4.x and ocamlbuild
  • ocaml libraries: batteries, ocamlgraph, sexplib, ocaml_plugin
  • python 2.x
  • Z3 4.3.2

In case you want to install the tool from scratch, please check the file ~/opodis17-submission3/bymc/README.txt.

5. Benchmarks

The benchmarks can be found in the directory ~/opodis17-submission3/benchmarks. They are named after the entries in Tables 1-3 and follow the common pattern: table${i}-${j}.*.ta, where ${i} is a table number and ${j} is a position in the table.

6. Running the individual experiments

In this section, we give the commands to synthesize a threshold automaton ​table1-2bcast-byz-ta-synt.ta. To find the properties, search the code for the section specifications() {...}.

6.1. Single core

The following command runs synthesis on a single CPU core, enumerating all possible solutions:

$ ~/opodis17-submission3/bymc/syntpa-schema \
   ~/opodis17-submission3/benchmarks/table1-2bcast-byz-ta-synt.ta all \   -O synt.all=1

You should see the following line in the output:

> Collected 38 counterexamples in total
 > Found 3 solutions. Check them with grep SOLUTION x/**/synt
 > Finished after 38 refinements

You can check the synthesized unknowns by invoking:  grep SOLUTION x/**/synt

The last command should produce the following:

 > SOLUTION 1: a1 = 0, b1 = 1, c1 = 1, a2 = 0, b2 = 2, c2 = 1
 > SOLUTION 2: a1 = 0, b1 = 1, c1 = 1, a2 = 1, b2 = -1, c2 = 0
 > SOLUTION 3: a1 = 1, b1 = -2, c1 = 0, a2 = 1, b2 = -1, c2 = 0

To see the last synthesized solution, check the file x/**/synt.ta

6.2. Multiple cores (MPI)

The following command runs synthesis with MPI, enumerating all possible solutions:

$ mpirun -n $NUM_NODES --output-filename out ~/opodis17-submission3/bymc/syntpa-schema \
~/opodis17-submission3/benchmarks/table1-2bcast-byz-ta-synt.ta all \
-O synt.all=1 -O

(specify the number of MPI nodes by replacing $NUM_NODES with an actual number)

You can check the log file of the master node in out.0 and the log files of the slave nodes in out.i for i > 0.

Latest News

Florian Zuleger winning WWTF grant

Florian Zuleger was awarded a grant by WWTF for his research project “Automated Program Analysis for Bounds on Resource Consumption”. Florian’s project will develop new methods to extract bounds for loops, memory and bandwidth from imperative programs.

Continue reading

Welcome Georg Weissenbacher

Georg Weissenbacher, leader of a WWTF funded Vienna Research Group, will start his work in our group on July 2. His project “Heisenbugs: From Detection to Explanation” is applying formal methods to identify hard-to-detect errors in computer systems. See a newspaper article on his work in “Der Standard”.

Continue reading

Uni-Finanzierung als Absurdes Theater (Der Standard)

An sieben Universitäten werden in Österreich Informatik-Studien angeboten, aber mehr als 50 Prozent der Studierenden wählen die TU Wien – über 1000 Studienanfänger jährlich. Der gute Ruf der TU Wien wird zum Fluch für das Studium, denn auf 52 habilitierte Professoren kommen fast 7000 Studierende; ein solches Verhältnis wäre bei anderen international führenden Universitäten undenkbar. […]

Continue reading

Full news archive