sequence

This article will focus on Election Algorithms

Election Algorithms

Election Algorithms can be roughly divided into two categories. One is Bully Election, which was proposed by Garcia-Molina, and the other is Chang & Roberts’ Token Ring Election Algorithm. There are a few assumptions that most Election algorithms generally make:

  • Complete topology. Information can be passed between nodes of the topology
  • Each node has a unique ID that is visible to the other nodes in the topology
  • All communication networks are reliable and only Node fail is allowed, requiring messages not to be lost, repeated or corrupted
  • The Fail Detector mechanism is required to handle node failure

Bully Election

  • When a node detects that the leader fails, it sends an Election Request with its own ID to the other node
  • When a node receives an Election Request, it decides that if its ID is larger than the id in the request, it can “bully” over the ID in the request, and if it is smaller, it does not change the ID, and then sends the Election Request to another node. When a node receives the Election Request id as its own node ID, it is the leader and sends the Leader Request to another node
  • When a node receives a leader request, the local leader ID is set. If the leader ID is not its own node ID, the node forwards the leader request to other nodes

Token Ring Election

  • When a node detects that the leader fails, it sends an Election Request with its own ID to the other node
  • When a node receives an Election Request, it determines whether its node ID is present in the request. If not, it appends its node ID to the Election Request. If its node ID is already in the Election Request, the node ID with the largest id is extracted as the leader, and the leader Request is sent to the other nodes
  • When a node receives a leader request, the local leader ID is set. If the leader ID is not its own node ID, the node forwards the leader request to other nodes

The instance

Here the distributedLeaderElection implementation

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);
		}
	}
Copy the code
  • It can be seen that bully overwrites the node ID directly when it sees that the node ID in the Election Request is smaller than its own. When you find that the node ID in the request is your own node ID, you elect yourself as the 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+"";
	}
Copy the code
  • The ring algorithm appends its node ID to the request. When you go around and find your node ID already in the leaderinBody findLeaderInBody, extract the largest of these node ids and elect that node as the leader

summary

  • Election Algorithms can be broadly divided into two categories. One is Bully Election, which is proposed by Garcia-Molina, and the other is Chang & Roberts’ Token Ring Election Algorithm
  • There are a few assumptions that most Election algorithms generally make:
    • Complete topology. Information can be passed between nodes of the topology
    • Each node has a unique ID that is visible to the other nodes in the topology
    • All communication networks are reliable and only Node fail is allowed, requiring messages not to be lost, repeated or corrupted
    • The Fail Detector mechanism is required to handle node failure
  • The common point between Bully algorithm and Ring algorithm is the comparison of node IDS. In a specific instance, we can see that Bully algorithm, as its name implies, can overwrite the nodes in the request if its node ID is large, and the largest node ID is the leader. The Ring algorithm appends node ids, and finally selects the leader with the largest node ID

doc

  • Election Algorithms
  • The Bully Election Algorithm
  • Bully Election Algorithm Example
  • A Token Ring Election Algorithm
  • Token Ring Election Algorithm Example
  • distributedLeaderElection