Algorithms

Trivial examples

  • hello-world: a simple trigger that prints “hello world” on the stdout.
  • ping-pong: each process broadcasts a ping and reply with a pong any ping received (even from itself).

Benchmarks

  • tput: two processes (0 and 1) measure the maximal possible throughput.
  • rtt: two processes (0 and 1) measure the round-trip-time at application level.
  • bbench: a sender (process 0) sends broadcasts messages to all other processes and measures several metrics: latency to receive the first reply, latency to receive a quorum of replies, latency to receive all replies and throughput. bbench stands for broadcast bench and serves as an indication of how the peformance of an “optimal” replication would be in our framework.

Useful algorithms

Rotating leader election

The algorithm follows the rotating leader election algorithm suggested in “Stable leader election” by Aguilera et al. This algorithm is the simplest version of the rotating leader election, ie, it is not stable!

Failure detector

A simple push failure detector.

Fail-aware datagram service

Implementation of the “Fail-aware Datagram Service” by Fetzer and Christian.

FADS provides a layer above the ztas messaging service which calculates an upper-bound in the transmission delay of each message. The message delay upperbound can be used to discard late messages.

Complex algorithms

Highly-available election service

Implementation of the “Highly-available local leader election service” by Fetzer and Christian.

This algorithms is a strong leader election algorithm: at any point in time, there are at most one leader for each partition.

The algorithm relies on FADS.

Stable Rotating leader election

Implementation of the (n+4)-stable leader election with message loss from Aguilera’s Stable Leader Election Paper (2000).

Instead of implementing expiring links with their approach, we use FADS.

State machine replication

Implementation of Paxos and a State Machine Replication library based on the algorithms in “Paxos Made Moderately Complex” by Robbert van Renesse.