Talk about Election Algorithms

  distributed-systems

Order

This article mainly studies Election Algorithms.

Election Algorithms

There are roughly two types of Election Algorithms, one is Bully Election proposed by Garcia-Molina, and the other is Chang & Roberts’ s Token Ring Election Algorithm; For most election algorithms, there are usually the following assumptions:

  • Complete topology, information can be passed between nodes of topology.
  • Each node has a unique id and is visible to other nodes in the entire topology.
  • All communication networks are reliable, only node fail is allowed, and messages are required not to be lost, duplicated or damaged.
  • Requires that a fail detector mechanism already exists to handle node fail situations.

Bully Election

  • When a node detects leader fail, it sends the SelectionRequest to other nodes, with its own id in the SelectionRequest.
  • When the node receives the Selectionrequest, it judges that if its id is greater than the id in the request, it can “bully” overwrite the id in the Request, if it is less than, it will not change, and then it will send the SelectionRequest to other Node; When a node receives an election request whose id is its own node id, it indicates that it is a leader and sends the leader request to other nodes.
  • When a node receives a leader request, it sets a local leader id, and at the same time judges that if the leader id is not its own node id, it forwards the leader request to other nodes.

Token Ring Election

  • When a node detects leader fail, it sends the SelectionRequest to other nodes, with its own id in the SelectionRequest.
  • When the node receives the SelectionRequest, it judges whether its own node id is in it, and if not, it adds its own node id to the SelectionRequest; If one’s own noderequest is already in the election request, then extract these noderequests, take out the one with the largest id as the leader, and then send the leader request to other node.
  • When a node receives a leader request, it sets a local leader id, and at the same time judges that if the leader id is not its own node id, it forwards the leader request to other nodes.

Example

It is adopted here.distributedLeaderElectionImplementation of

Bully Election

    public void onMessage(String message) {
        
        String messageHeader = message.split(":")[0];
        String messageBody = message.split(":")[1];
        
        if (messageHeader.equals("Election")){
            if (Integer.parseInt(messageBody.trim()) < Node.getMyID() // If we are a better candidate
                    && !participant){
                System.out.println("I " + Node.getMyID() + " am a better candidate than "+messageBody);
                Node.sendMsgToNextNode("Election" + ":" + Node.getMyID()); // Suggest us for election
            }
            else if (Integer.parseInt(messageBody.trim()) == Node.getMyID())  { // If this is our ID
                System.out.println("I " + Node.getMyID() + " received my own pebble, so I am the new leader");
                Node.sendMsgToNextNode("Leader" + ":" + Node.getMyID()); // Announce us as the new leader
            }
            else { // The current candidate is better
                System.out.println("I " + Node.getMyID() + " am a worse candidate than "+messageBody);
                Node.sendMsgToNextNode(message); // Forward his candidancy
            }
            participant = true;
        }
        
        else if (messageHeader.equals("Leader")){
            System.out.println(messageBody + " is the new leader");
            leaderID = messageBody;
            if (Integer.parseInt(messageBody.trim()) != Node.getMyID()) Node.sendMsgToNextNode(message);
        }
    }
  • It can be seen that the bully algorithm directly bully overwrites the node id when it sees that the node id in the SelectionRequest is smaller than its own NodeId; When you walk around and find that the node id in the request is your node id, you will elect yourself leader.

Token Ring Election

    public void onMessage(String message) {

        String messageHeader = message.split(":")[0];
        List<String> messageBody = Arrays.asList(message.replace(messageHeader+":", "").split(":"));
        
        if (messageHeader.equals("Election")){
            if (!messageBody.contains(Node.getMyID()+"")){ // If we are not contained in the list
                System.out.println("I " + Node.getMyID() + " am not contained in this message "+message);
                Node.sendMsgToNextNode(message + ":" + Node.getMyID()); // Suggest us for election
            }
            else { // If we are in the list
                System.out.println("I " + Node.getMyID() + " am contained in this message");
                String newLeader = findLeaderInBody(messageBody);
                Node.sendMsgToNextNode("Leader" + ":" + newLeader); // Announce the new leader
            }
        }
        
        else if (messageHeader.equals("Leader")){
            String leaderBody = message.split(":")[1];
            System.out.println(leaderBody + " is the new leader");
            leaderID = leaderBody;
            if (Integer.parseInt(leaderBody.trim()) != Node.getMyID()) Node.sendMsgToNextNode(message);
        }
    }

    private String findLeaderInBody(List<String> messageBody) {
        int maxID = 0;
        if (messageBody.size() > 0){
            for (String leaderCandidate : messageBody){
                if (Integer.parseInt(leaderCandidate.trim()) > maxID) {
                    maxID = Integer.parseInt(leaderCandidate.trim());
                }
            }
        }
        return maxID+"";
    }
  • It can be seen that ring algorithm appends its node id; to the request; When you walk around and find that your node id is already in it, take out the largest of these nodeids through findLeaderInBody and elect the node as leader.

Summary

  • There are roughly two types of Election Algorithms, one is Bully Election proposed by Garcia-Molina, and the other is Chang & Roberts’ s Token Ring Election Algorithm
  • For most election algorithms, there are usually the following assumptions:

    • Complete topology, information can be passed between nodes of topology.
    • Each node has a unique id and is visible to other nodes in the entire topology.
    • All communication networks are reliable, only node fail is allowed, and messages are required not to be lost, duplicated or damaged.
    • Requires that a fail detector mechanism already exists to handle node fail situations.
  • The common point between bully algorithm and ring algorithm is to compare node id. In a specific example, we can see that bully algorithm, as its name implies, is that if its node id is relatively large, it can cover node in request, and the largest node id is leader; . While ring algorithm adopts the way of appending node id, and finally selects leader with the largest node id

doc