Bully Election Algorithm

Agents elect a coordinator using a score that represents their importance. A higher-scoring agent can override a lower-scoring candidate. This example demonstrates message events, concurrent goals and beliefs that track an election.

Run the example

Use an ASTRA 2.6.1 project from the Quick Start. Save the reusable agent below as src/main/astra/BullyElection.astra.

This example provides an election component, rather than a complete launcher. Create a subclass for each participant, give it a distinct score(int) belief and a participants(list) belief containing the participating agent names, and create those agents through a launcher. Start an election by invoking !bully_election() on one participant. Add a plan reacting to +leader(string Name) if you want to print the result.

BullyElection.astra

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 plan starts the election
    plan +!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
    plan @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.
    plan @message(inform, string sender, result("ok")) : holding("election") {
        -holding("election");
    }

    // a new coordinator has been elected
    plan @message(inform, string N, elected(N)) {
        +leader(N);
    }
}

Expected output

The component does not print console output. After a successful election, participants receive elected(Name) and store leader(Name). With distinct scores and responsive participants, the intended outcome is that the highest-scoring participant becomes coordinator.

The two-second deadline assumes timely message delivery. This example has not been checked for repeated elections or participant failures.

How it works

A candidate adds holding("election"), removes its existing leader belief and sends election requests. A receiver with a higher score replies result("ok") and starts its own election if necessary. Receiving ok removes the candidate’s holding belief, preventing it from announcing itself when its deadline expires.

A candidate still holding the election after the deadline broadcasts elected(...). The receiving plans record the new coordinator as a belief. The implementation sends requests to the participant list and lets receivers compare scores.

Try a change

Add console messages for election requests, replies and coordinator announcements. Try three distinct scores and start an election at the lowest-scoring agent. Then start a second election and inspect the election-state beliefs; record any unexpected behaviour before extending the component to handle failures.

See Creating Multiple Agents, Agent Communication and Beliefs and Inference.