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 {
    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);
    }
}