Distributed Systems Examples
Bully Election Algorithm
The Bully Election algorithm is a well known algorithm created by Garcia-Molina in 1982 that is aimed at providing a decentralised algorithm for electing a leader amongst a set of peers.
The basic idea behind the algorithm is that, when one peer detects the failure of the current coordinator, it begin an election nominating itself to become the new coordinator, sending an election message to all peers it is aware of that have greater importance than it. Importance is based on some agreed measure, such as process id or age. The peer wins the election if no peer of greater importance responds. If a peer with greater importance receives an election message, it responds with “ok” to the peer that sent the message, which tells the peer that it will not be elected. After election, the new coordinator tells all remaining peers that it has been elected.
The code below is an ASTRA version of the bully election algorithm. To use it, you should subclass the agent type and add some mechanism for creating a score belief (this is the measure of importance) and to specify the participants in the coordinated activity. Further, to elect a coordinator, one of the agents must invoke the !bully_election() goal.
agent BullyElection {
types core {
formula score(int);
formula participants(list);
formula holding(string);
formula leader(string);
formula elect(string, int);
formula elected(string);
formula result(string);
formula failed_election(string);
}
module System system;
// this rule starts the election
rule +!bully_election() : score(int score) & participants(list agents) {
// believe that we are holding the election
+holding("election");
// drop the belief about the current leader
if (leader(string X)) -leader(X);
// send an elect message to all participants, passing the agents name and score
forall (string receiver : agents) {
if (receiver ~= system.name() | failed_election(receiver)) {
send(request, receiver, elect(system.name(), score));
}
}
// wait for the deadline (2 seconds)
system.sleep(2000);
// check if we are still holding the election
// this belief will not hold if another agent of higher importance has responded.
if (holding("election")) {
// nobody overrode it, so it is elected...
forall (string agt : agents) {
send(inform, agt, elected(system.name()));
}
}
// drop any beliefs about failed elections
foreach(failed_election(string name)) {
-failed_election(name);
}
}
// we received an elect message from another agent
rule @message(request, string sender, elect(string name, int score)) : score(int my_score) {
if (score < my_score) {
// i am more important than the sender so tell the sender
// to stop and start my own election.
+failed_election(name);
send(inform, sender, result("ok"));
if (~holding("election")) {
!!bully_election();
}
}
}
// i received an "ok" from a more important agent, so stop.
rule @message(inform, string sender, result("ok")) : holding("election") {
-holding("election");
}
// a new coordinator has been elected
rule @message(inform, string N, elected(N)) {
+leader(N);
}
}
Token Ring Election Algorithm (UNDER REVIEW)
This benchmark appears in [1]. The basic idea of the benchmark is to test the performance of the message passing infrastructure by creating a token ring containing WT worker agents, and passing each of T tokens around that ring 500,000 times. The normal value for WT is 500, and T takes the values 1, 250, 500, 750, 1000.
This example is broken up into two parts – a description of the Worker agent design, and a description of the Launcher agent, which creates the token ring and initiates the passing of the tokens.
The Worker Agent
The worker agent implements the token ring. Each agent implements the same basic behaviour: when it receives a message from another agent, check the counter in the message. If the counter is zero, stop, otherwise forward the message onto the next agent in the ring, reducing the counter by one.
package benchmarks.tokenring;
agent Worker {
module Timer timer;
rule @message(inform, string sender, token(int I, 0)) {
timer.shutdown();
}
rule @message(inform, string sender, token(int I, int N)) : next(int X) {
send(inform, ""+X, token(I, N-1));
}
rule @message(inform, "main", init(int X)) {
+next(X);
}
}
This agent consists of three basic rules:
- The first rule handles the case where the agent receives the token and token counter has reached 0. In this case, the agent stops passing the token and calls shutdown on the timer module (see below).
- The second rule deals with the case where the token counter has not reached 0. In this case, the agent forwards the token onto the next agent in the ring, reducing the token count by one.
- The third rule is used to initialize the agent. It receives a message from the “main” agent informing it of the id of the next agent in the ring.
The Launcher Agent
This agent class implements an agent that creates the token ring, sets the shared timer, and sends the initial tokens to the relevant agents.
package benchmarks.tokenring;
agent Launcher {
module Timer timer;
module Console console;
module System system;
rule +!main(list args) {
int WT = 500;
int N = 500000;
console.println("enter number of tokens: ");
console.readInt(int T);
console.println("enter scheduler pool size: ");
console.readInt(int size);
// Create the token ring
int i = 1;
while (i <= WT) {
system.createAgent(""+i, "benchmarks.tokenring.Worker");
send(inform, ""+i, init((i%WT)+1));
i = i + 1;
}
// Start the timer (configuring it for T tokens)
timer.startup(T);
// Send out the initial tokens
i = 1;
while (i <= T) {
send(inform, "" + (i * (WT/T)), token(i, N+1));
i = i + 1;
}
}
}
The Timer Module
The timer module implements a shared resource that is accessed by both the Worker agents and the Launcher agent. The implementation contains two static fields – the last recorded start time and the number of tokens. The two methods implement ACTIONS. The first sets the start time and the number of tokens. The second is used to record when a token has finished being passed.
package benchmarks.tokenring;
import astra.core.Module;
public class Timer extends Module {
private static long startTime;
private static int T = 0;
@ACTION
public boolean startup(int t) {
startTime = System.currentTimeMillis();
T = t;
return true;
}
@ACTION
public boolean shutdown() {
if (--T == 0) {
long duration = System.currentTimeMillis() - startTime;
System.out.println("Duration: " + duration);
System.exit(0);
}
return true;
}
}
References
[1] Cardoso, R. C., Zatelli, M.R., Hubner, J.F., Bordini, R. H., “Towards Benchmarking Actor- and Agent-Based Programming Languages”, Proceedings of the 2013 workshop on Programming based on actors, agents, and decentralized control, pp 115-126, ISBN: 978-1-4503-2602-5, 2013