# 聊聊Election Algorithms

## Election Algorithms

Election Algorithms大致有两类，一类是Garcia-Molina提出的Bully Election，一类是Chang & Roberts's Token Ring Election algorithm；对于大多数的election algorithms通常有如下几个假定：

• 完整的topology，信息可以在topology的nodes之间传递
• 每个node有唯一的id，而且对整个topology其他node可见
• 所有的通信网络是可靠的，只允许node fail，要求消息不丢失，不重复，不损坏
• 要求已经有fail detector机制来处理node fail的情况

## 实例

### Bully Election

```    public void onMessage(String message) {

String messageBody = message.split(":")[1];

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

System.out.println(messageBody + " is the new leader");
if (Integer.parseInt(messageBody.trim()) != Node.getMyID()) Node.sendMsgToNextNode(message);
}
}```
• 可以看到bully算法在看到election request中node id小于自己node id时，直接bully覆盖该node id；当走了一圈发现请求中node id是自己的node id时，则选举自己为leader

### Token Ring Election

```    public void onMessage(String message) {

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

}
}

int maxID = 0;
if (messageBody.size() > 0){
}
}
}
return maxID+"";
}```

## 小结

• Election Algorithms大致有两类，一类是Garcia-Molina提出的Bully Election，一类是Chang & Roberts's Token Ring Election algorithm
• 对于大多数的election algorithms通常有如下几个假定：
• 完整的topology，信息可以在topology的nodes之间传递
• 每个node有唯一的id，而且对整个topology其他node可见
• 所有的通信网络是可靠的，只允许node fail，要求消息不丢失，不重复，不损坏
• 要求已经有fail detector机制来处理node fail的情况

## doc

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

815 篇文章45 人订阅

0 条评论