分布式互斥与领导者选举

互斥和领导者选举是经典的协调问题：确保至多一个进程访问关键资源，并在对等进程中选择一个单一的指定协调者。

Definition

分布式互斥保证在任何给定时间只有一个进程持有共享资源，同时确保所有请求者最终都能访问；领导者选举确定性地选择一个进程作为协调者，所有进程都认同这一结果。

Scope

本主题涵盖了基于许可的互斥算法（Lamport时间戳算法、Ricart-Agrawala算法、Maekawa的法定人数方法）和基于令牌的算法，以及它们的通信复杂度和公平性特性；还包括环形网络（Chang-Roberts算法）和通用网络（Bully算法）的领导者选举算法，包括它们对标识符和同步性的假设。这些原语在协调服务和复制系统中反复出现。

Core questions

• 进程如何仅通过消息来序列化对共享资源的访问？
• 基于许可和基于令牌的方案在消息复杂度与公平性之间有何权衡？
• 如何选择唯一的领导者，以及在领导者失败后如何重新触发选举？

Key theories

基于许可的互斥

Ricart-Agrawala等算法通过逻辑时间戳对请求进行排序，并在请求者收到所有（或法定人数的）对等进程的许可后授予进入权限，从而在每次进入临界区时以有限的消息成本实现公平性。

基于令牌的互斥

一个唯一的令牌循环或按需请求，只有持有者才能进入临界区，这减少了消息流量，但需要在故障后有机制来重新生成丢失的令牌。

领导者选举

环形网络（如Chang-Roberts算法）和通用网络（如Bully算法）的选举算法利用进程标识符来收敛于一个所有正确进程都认可的优先级最高的协调者。

Clinical relevance

每当复制系统必须选择一个主节点或协调器时，就会调用领导者选举；分布式锁定是互斥的泛化；两者都作为核心服务由云基础设施中使用的协调系统提供。

History

Lamport于1978年发表的逻辑时钟论文引入了一种基于时间戳的互斥算法；Ricart和Agrawala在1981年对其进行了优化，Maekawa不久后引入了法定人数方法，Garcia-Molina在1982年的Bully算法形式化了领导者选举，为该领域提供了规范的协调算法。

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

分布式互斥与单机上的锁有何不同？

分布式互斥不能依赖共享内存或中央锁管理器，因此进程必须纯粹通过交换消息进行协调，并且必须明确处理消息延迟和故障，而单机锁可以假定这些问题不存在。