Election

• 每个进程都能开启leader election，多个election可以同时被开启

• 每个进程维护两个boolean类型的变量：

  • done：当leader election算法结束之后置为true

  • is_leader：当进程知道自己是leader之后置为true

• 算法要满足两个条件

• ring的定义

• leader election不能在anonymous ring中进行，因为每个node必须有个标识，不然不知道哪个是leader

  • uniform ring: 知道ring的大小

  • non-uniform ring：不知道ring的大小

  • symmetric：

  • asymmetric：

  • synchronous：

  • asynchronous：

• node的identifier必须是unique的，并且可排序的

• LeLann-Chang-Roberts (LCR) algorithm：选id最大的那个node

  • 假设是一个单向顺时针的ring

  • 任意一个node可以开始leader election：把自己的id发给下一个node

  • 如果收到的id比自己的id大，那么就直接把收到的id发给下一个node

  • 如果收到的id比自己的id小，那么把自己的id发给下一个node

  • 最后，如果一个node收到了自己的id，说明自己是这个ring中id最大的，那么声明自己是这个ring的leader

  • 评价：id降序排列的时候是worst case，别忘了最后广播自己是leader还要发送一轮消息

  • 但是平均时间复杂度是nlogn

    • 每个id发送一个消息，总共有n！个消息，因为有n！种组合情况

    • 每个id在他的后k个邻居中有1/k的概率是最大的，所以发送1/k个消息

    • 所以总消息数是，n个节点*（各个节点发送消息之和+最后的leader通知消息）/ n！种情况

• 为了减少消息复杂度，使用HS算法：

  • 是bidirectional ring

  • 每个node向自己的邻居发送自己的id，只有自己的id是最大的时候才扩展邻居*2（注意不是+2）

  • 最后只有一个winner就是leader

  • 信息复杂度：

  • 在asynchronous rings， ring的大小不知道的情况下，message complexity不可能比nlogn更低