Bachelor Thesis for Arvy Heuristics

This is the repository for my bachelors thesis on Arvy heuristics for distributed mutual exclusion. It contains all the work that was done as part of it, including the implementation of all heuristics, the framework for writing and testing them, the thesis itself, slides used for the final presentation and the simulation used for demonstration.

This work was done as part of my Computer Science bachelor at ETHZ in the department of Distributed Computing, advised by Pankaj Khanchandani and András Papp Pál and under the direction of Prof. Dr. Roger Wattenhofer.

The dependencies are managed by Nix, the code is written in Haskell and the thesis and slides are written in LaTeX.

The thesis can be found pregenerated at thesis/Thesis.pdf and the slides can be found at slides/presentation.pdf.

Building and Running

This project uses Nix to manage dependencies and is fully reproducible. To install Nix, visit https://nixos.org/nix/. Only Linux has been tested but macOS might work too.

Demo

To build the interactive demo:

nix-build -A arvy

Note that this will take a long time to build

Then you can run the demo with e.g.

result/bin/arvy-demo -a pairmin

Or there is a demo controller with the parameters used in the presentation:

demo/controller

The implemented controls are:

• Click a node to send a request from it
• Scroll to decrease/increase simulation speed
• Press A to enable/disable automatic random requests
• When automatic requests are on, press C to switch enable/disable concurrent automated requests
• Press R to reset to the initial state
• Press Q to quit

Thesis and Slides

To build the thesis and slides:

nix-build -A thesis
nix-build -A slides

Then they will be in result/Thesis.pdf and result/presentation.pdf respectively. Alternatively they can be found pregenerated at thesis/Thesis.pdf and slides/presentation.pdf.

All the evaluation data used for the thesis and slides is in the pregenerated data folder. This data can be generated by running the arvy executable:

nix-build -A arvy
result/bin/arvy

Note that this will take a long time and requires about 16GB of RAM at least, swap recommended.

What is Arvy?

What is a distributed directory algorithm?

This is an algorithm that manages a single resource in a graph of distributed nodes. Only one node can have the resource at any given time. Nodes that don’t have the resource can request it, after which they should receive it eventually.

What is Arvy and how does it work?

The Arvy algorithm, introduced in a paper by Pankaj Khanchandani and Roger Wattenhofer (The Arvy Distributed Directory Protocol), is a generalization of Arrow and Ivy. Both Arrow and Ivy have the same underlying idea: All nodes in the graph point towards the node currently holding the token (the root node) in a spanning tree. If a node needs the token, it sends a request to the node it points to, which will get forwarded on the path towards the root node. Once arrived at the root node, the token can be sent to the node that requested it.

In order for the rooted spanning tree to persist, the node pointers need to be adjusted: If node 3 is the root node and node 1 requested it by sending a request to node 2, which forwarded the request to node 3, which then sent the token to node 1, the new root node needs to be 1 because that’s where the token now is. In addition, the node pointers in node 2 and 3 need to be changed so they point towards the new root node 1 again. This is where Arrow and Ivy diverge in behavior: Arrow works by inverting the edges the request travels through, while Ivy adjusts all nodes in the path to point at the new root directly.

Arvy is the generalization of that, in that when a request travels through a path with nodes 1, 2, … n, nodes can choose to point to any previously traveled through node, so node 4 can newly point to either 1, 2 or 3, node k can newly point to 1, 2, …, (k-1). Arrow is the special case of always choosing (k-1), while Ivy is the special case of always choosing 1.

Errata and Notes

• Errata: In section 2.4 of the thesis, it was pointed out that the Edge Cost Minimizer heuristic converges to a static MST tree. However that is not the case as can be seen by comparing spanning trees from running `demo/controller`
• Note: In section 4.1.2 of the thesis, the Uniformly Random Tree line in the plot previously showed the expected average tree edge distance in a completely random tree (from points in a unit square), by calculating the value to be 0.521. This was done in order to see that the random and Ivy heuristics hover around the area of such a random tree. However for simplicity of data generation, the current version shows the average edge distance of exactly the initial random tree used for all heuristics in the plot. By chance, this random tree happens to be a bit above the expected value, which is why the line is higher than one would expect.