Leader Election

同步的方式会需要很大的开销：如果如果算法的每个步骤都要去跟集群的每个其他节点通信，我们就遇到一个非常严重的通信负载问题。这在一个大型的分布在多个地理位置的网络中是非常明显的。为了减少同步的开销以及每次做决定时所需的消息通讯数量，有一些算法会使用一个 Leader 领导者 (有时也被称为 Coordinator 协调者) 处理器，负责来执行或者协调分布式算法的各个步骤。

一般来说，分布式系统中的处理器是平等的，任意的处理器都能够接管领导者的角色。处理器们会假设领导权会持有相当长的一段时间，但这并不是一个永久性的角色。通常，处理器会在崩溃之前一直保持领导者的角色。在崩溃之后，其他任意的处理器会启动新的选举轮次，对自身的领导权做出假设，如果他确实被选举了，就会继续负责上一个失效的领导者的工作。

选举算法会保证在大部分的时间里都会有一个存活的领导者，并且选举最终肯定会完成。(也就是整个系统不会一直都处于选举中的状态)

理想情况下，我们对安全性也进行了假设，并且在同一时刻保证了最多只会存在一个领导者，以此来排除 Split Brain 脑裂的情况 (即同时存在两个领导者被选举出来)。但是，在实际中，许多的算法会违背了这个约定。

领导者处理器是非常重要的，举例来说，需要负责实现广播中消息的全序。领导者会收集跟管理全局的状态，接收消息跟将其传播到其他的处理器。他还会被用来在故障恢复后或是刚启动时协调系统进行重建，或者处理一些重要的状态变更。

在系统初始化的时候就会触发选举，这是会首次选出新的领导者，或者在上一个领导者奔溃或无法通信时也会触发选举。选举需要确认的是：从处理器中选出领导者。这个选择需要对所有的参与者都有效。

尽管领导者选举跟分布式锁 (已排他的方式获取共享的资源) 从理论的角度看起来有点像，但实际上是完全不同的。如果一个处理器持有了一个锁来执行关键的节点，对其他的处理器来说谁持有这个锁是不重要的，只要他能够满足锁的存活属性 (锁最终肯定会被释放，并允许其他人再次获取)。相比之下，选举的处理需要一些特殊的属性，还需要让其他所有的参与者都知道，所以被选出的新的领导者需要告知其他人他所扮演的角色。

如果分布式锁的算法对某个处理器或者是某个处理器的组有偏向，他最终会导致那些无偏向的处理器无法获取到所需的共享资源，这就导致跟存活性的属性相矛盾。相比之下，领导者可以在从停止或崩溃前一直保持他的角色，系统会更偏向于长时间存活的领导者。

分布式系统中拥有一个稳定的领导者能够有效避免不同的远程参与者之间的状态同步，减少了需要交换信息的数量，并且驱动计算在单个处理器上进行，而不需要为各个节点进行协调。其中一个隐含的问题是具有领导者的系统中，领导者可能会成为一个瓶颈。为了解决这个问题，许多的系统将数据分区到相互独立的副本集合中 (可以在 Database Partitioning 中了解)。这样可以让整个系统不只持有一个领导者，而是每个独立的副本集合都有其自身的领导者。有一个使用了这种方式的分布式系统是 Spanner (在 Distributed Trasactions with Spanner 中会介绍) 。

因为每个领导者的处理器最终都必然会产生故障，故障需要能够被检测、报告跟做出处理：即系统需要选出一个新的领导者来代替已经失效的那个。

有一些算法，比如 ZAB ( Zookeeper Atomic Broadcast) 中会介绍，Multi-Paxos (本书相应的章节会介绍) 或者 Raft (本书相应的章节会介绍)，使用了临时的领导者来减少参与者之间为了达成一致所需的消息数量。只是，这些算法都使用了自己定义的 Leader Election 领导者选举、Failure Detection 故障检测来解决来处理领导者选举时的冲突。