英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料

匿名系统中的容错广播

摘要 在分布式系统中，广播服务在所有进程之间传播消息m，使每个进程最终都能接收到该消息，达到传递消息的目的。但是在有故障的系统中，基本的广播服务不能保证所有消息都能传递成功。容错广播是分布式系统中一个基本的问题，与基本的广播服务不同，当系统有可能崩溃时，它可以增加消息传递的确定性。

传统意义上，在经典的分布式系统中，当我们对容错广播服务进行研究，每个进程都有一个独特的身份标识。但是最近出现了一些新的分布式系统，如传感器网络，在这些系统中，每个传感器节点并不总是包含独特的身份标识（存储容量小，计算能力降低，要识别大量的元素等）。

在异步系统中，所有进程都有相同的身份，因此它们是无法被区分的（它们可能有相同的代码）。在本文中，我们研究了匿名异步系统中容错广播服务的定义和可实现性。

关键词 分布式计算·容错·可靠、统一；原子广播服务·故障检测器·匿名分布式系统。

1引言

分布式系统最重要的通信概念之一是广播服务，它向系统的所有进程发送消息，但是没有任何容错特性。因此，如果发送方进程在广播消息m时崩溃，m的传递结果就不得而知了。为了避免在进程可能崩溃的情况下，出现交付的不确定性，我们引入了几种类型的容错广播服务。最流行的是可靠广播（reliable broadcast，RB）、统一可靠广播（uniform reliable broadcast，URB）和原子广播（atomic broadcast，AB）服务。

在本文研究的分布式系统中，进程可能会因崩溃而失败（永久停止工作）。进程可能会崩溃，也可能不会。在第一种情况下，我们说这个过程是一个错误的过程，在后一种情况下，是一个正确的过程。此外，本文还重点研究了异步系统，在这种分布式系统中，进程的执行时间和发送消息的传递时间是无限的。

可靠广播（RB）服务要求（a）由正确的进程发送的每个消息m必须由正确的进程传递，并且（b）如果一个正确的进程传递消息m，那么每个正确的进程都传递m。

统一可靠广播（URB）服务是另一种类型的容错广播服务，它具有更强大的传送特性。URB服务要求（a）由正确的进程发送的每个消息m必须由正确的进程传递，并且（b）如果一个进程传递消息m，则每个正确的进程都传递m。请注意，URB服务比RB服务强，因为（a）在两个服务中都相同，并且（b）在URB服务包括所有进程（不论正确与否），而不是RB服务的唯一正确进程。

原子广播（AB）服务也是一种容错广播服务，它规定了传送的总顺序。因此，AB服务要求，如果一个进程在m0之前传送消息m，那么就没有其他进程在m之前传送m0。

文献中有许多论文介绍广播原语，分析硬件和软件如何在可伸缩的多处理器和分布式系统上协同工作，并展示这些原语可以用作更复杂的并行操作的构建块。在这些论文中可以找到一些广播和容错的例子应用。据我们所知，研究容错广播服务的所有工作都依赖于分布式系统，在分布式系统中，进程是可区分的，因为每个进程都有唯一的标识。本文以匿名系统为研究对象。在匿名系统中，进程是不可识别的，因为所有进程的编码都是相同的（即进程没有标识，并且无法区分它们）。

我们可以在文献中找到一些解决计算网络规模问题的著作，其中的进程是匿名的，网络拓扑不断变化。在这些工作中，失败仅限于链接而不是过程。

匿名进程在一些实际的分布式系统中很常见，例如传感器网络，其中每个传感器节点不总是包含唯一的标识（例如，由于存储容量小、计算能力降低或要标识的元素数量巨大）。使用匿名进程的另一个实际问题与隐私有关（例如，在系统中隐藏用户身份）。

我们的工作到目前为止，当每个进程有一个唯一的身份标识时，容错广播服务就在经典的分布式系统中被调用。然而，据我们所知，这是第一篇关于匿名异步系统中具有容错保证的广播服务的论文。

本文提出了几种算法来证明，在匿名异步系统中实现不同类型的容错广播服务的可能性。尤其是RB服务的实现，以及少数进程可能崩溃时URB服务的另外的实现。

本文还讨论了当大多数进程都可能崩溃时，在匿名异步系统中实现URB服务是不可能的。为了避免这种不可能的结果，本文提出了一种实现URB服务的算法，该算法独立于崩溃的进程。为了实现这一目标，我们在匿名异步系统中增加了一个故障检测器。故障检测器是一个oracle（即分布式组件），进程可以调用它来获取有关崩溃进程的信息。

最后，在文献中非常清楚，在容易发生故障的经典异步系统中不可能实现AB服务，因此，在其匿名版本中也不可能实现AB服务。本文提出了一种在匿名异步系统中实现AB服务的算法。我们避开了用一致性组件扩充匿名异步系统的不可能结果。一致性是容错分布式计算中最基本的组成部分之一。一致性声明所有进程必须决定一个相同的值v，而这个值v必须由系统的某个进程提出。我们证明了AB服务可以在匿名异步系统中实现，采用了文[19]中提出的解决方案（我们使用RB和一致性的匿名版本作为构建块）。

本文旨在分析匿名系统中主要的容错广播服务的可行性。因此，我们尝试尽可能简单地提出我们的算法来解决每个服务。其他的考虑因素，如性能或效率，超出了我们的论文范围（它是为将来的工作开放的）。

本文的结构如下：匿名系统模型见第2节。匿名系统中容错广播服务的定义包含在第3节中。在第4节中，我们将介绍匿名异步系统中RB服务的实现。在第5节中，我们证明了当大多数进程都可能崩溃时，URB服务不可能在匿名异步系统中实现。第六章研究了匿名异步系统中URB服务的可实现性。具体而言，第6.1节包括在少数进程可能崩溃时在匿名异步系统中实现URB服务，第6.2节提出了一种通过使用故障检测器来规避第5节不可能的结果的算法。第7节介绍了AB服务在匿名异步系统的实现，增加了一致性，RB和URB服务。最后，我们用第8节的结论来结束我们的论文。

2 匿名系统

匿名异步系统（表示为AAS）由一组进程prod;={pi}i=1，hellip;，n，确保其大小prod;为n，i是每个进程pi的索引，1le;ile;n。

进程是匿名的。因此，它们没有标识，并且无法区分系统的两个进程（即进程没有标识，并且执行相同的代码）。匿名性意味着进程索引是虚拟的，因为每个进程pi不知道其索引i。我们只从外部观察者的角度使用进程索引，目的是简化符号。

运行R由每个进程piisin;pi;所采取的一组步骤构成。我们假设时间在每一个运行R中以离散步前进，并且存在一个全局时钟T，其值为正自然数。注意，T是一个辅助概念，我们只用于表示，但进程不能检查或修改。进程是异步的，也就是说，在运行R的过程中，执行一个步骤的时间是无限的。

当进程崩溃时会停止。我们假设崩溃的进程永远不会恢复。进程piisin;pi;如果不崩溃是正确的，那么崩溃就是错误的。把正确的放进正确过程的集合，把错误的放在错误过程的集合。我们用f表示可能崩溃的最大进程数。除非另有说明，否则我们认为这个最大数是n-1（即fle;n-1）。

在AAS中，进程之间通过链接发送和接收消息。每对进程通过一个链接连接。我们假设链接既不复制也不创建虚假消息。我们认为这种联系是可靠的。链路l是可靠的，只要发送者和接收者是正确的进程，就可以保证使用l发送的每一条消息最终都会被接收。请注意，如果发送方或接收方的进程有问题，则消息可能在可靠链接中丢失。除非另有说明，否则链接不会对消息的发送或接收顺序实施任何限制（即不一定保留FIFO顺序）。

AAS系统有两个发送和接收消息的原语：bcast（m）和del（m）。我们说一个进程在调用bcasti（m）时广播消息m。类似地，进程pi在调用deli（m）时会传递消息m。由进程pi传递消息m被视为将消息m传递到该进程pi所在的上层（在顶层的情况下是用户pi）。当调用这些原语的进程pi不重要时，我们省略这些原语中的索引i。

用bcasti（m）进程同步地向每个进程pkisin;pi;发送一条消息m，deli（m）向调用进程pi，m是接收到的传递消息。为了保持系统的匿名性，我们还考虑到传输过程不能识别接收广播消息的链路。

在文献中，人们总是认为广播和传递的信息是唯一的。传统上假定每一广播消息m包括作为m的内容的一部分的不同发送者的处理标识，以将其与其它消息区分开来。因为在AAS中，进程是匿名的，所以我们必须考虑消息不是唯一的。因此，在AAS中，可以广播或传送同一消息m的多个实例。因此，更准确的说法是，在AAS中，当进程调用bcasti（m）时，它向每个进程pkprod;发送消息m的实例，并且当进程调用deli（m）时，它报告消息m的实例的传递。为了简化，我们滥用了符号，只在绝对必要时才区分消息的实例和消息本身。

设Bibe为进程pi广播的所有消息实例的多集，设Dibe为进程pi传递的所有消息实例的多集。设B为系统中所有广播消息实例的多集，即B=[piisin;prod;B i。类似地，D=[piisin;prod;Diis系统中传递的所有消息实例形成的多集。因此，例如，如果我们有以下五个具有相同消息m的原语：bcasti（m）、bcastj（m）、deli（m）、delj（m）和delk（m），那么多集B有m的两个实例，D有三个实例（即B={m，m}，D={m，m}）。

我们假设，如果进程崩溃，AAS的广播和传递原语不会提供任何容错保证。具体地说，如果一个进程在执行bcast（m）时崩溃，则m可以由任何进程子集接收，因此，del（m）只能由该进程子集调用。因此，系统AAS，使用这两个通信原语，提供不可靠的广播服务。

在完成本节之前，我们将解释本文中要使用的系统的名称。如前所述，AAS是先前定义的匿名异步系统的表示法。正如我们将在本文后面看到的那样，只有约束或增强系统AAS，才能获得一些结果。我们用符号中的括号来表示它。例如，如果我们将错误进程的数量限制在少数，我们使用AAS[f lt; n/2]。在其他情况下，我们必须使用另一个组件来丰富系统，例如，使用故障检测器。因此，如果我们使用故障检测器Psi;来增强系统AAS，我们使用AAS[Psi;]。最后，当不需要确定匿名系统是否受到某些组件或条件的增强或约束时，我们使用AAS省略括号。

3 定义

现在，我们定义了包含容错的广播服务。

广播和传递原语必须满足三个属性，才能在匿名系统AAS中提供可靠的广播（RB）服务：

–完整性：进程传递的每个消息m的每个实例im0都必须是广播im的结果。

–有效性：由正确的过程广播的每个消息m，其每个实例必须由正确过程传递。

–协议：所有正确的进程都会传递相同数量的每个消息m的实例。

让我们更正式地定义RB服务。

···略···

4 在AAS中实现RB服务

在本节中，我们将展示图1中的算法在一个匿名异步系统中实现RB服务，而与错误进程的数量无关（即AAS）。

图1的算法描述：回想一下，我们说一个进程pid在AAS中广播消息m的一个实例，如果它执行bcasti（m），pi传递执行deli（m）时广播消息m的一个实例。为了避免歧义，我们假设进程piRB调用RB bcasti（m）（第3行）时广播消息m的实例。类似地，我们说，如果进程piRB调用RB deli（m）（第15行），它将传递消息m的一个实例。

当进程pi调用RB bcasti（m）时，它向系统AAS的每个进程发送一条消息（m，seqi[m]），这样m是要传播的消息的实例，seqi[m]是m（第5行）的pi的序列号。变量seqi[m]允许每个进程pjt区分由进程pi广播的多个m RB实例（最初，seqi[m]是0，第2行）。

当处理pi、提供（m，s）时，即消息m的序列号为s（第6行），它使用count_msgi[m，s]来增加消息m的数量，使其与进程pi（第7行）传递的序列数相同。然后，它发送（ACK，m，s，count msgi[m，s]）到系统AAS（第8行）的每个进程。

当第一次处理pi提供（ACK，m，s，c）时，即具有序列号s和计数器c的m的实例（第9行），它中继此消息（ACK，m，s，c）（第10行）以传播此消息，即使广播消息（ACK，m，s，c）的发送方进程崩溃。为了避免无限期地中继同一消息，第9-11行只在第一次传递同一消息时执行（第9行）。

若要RB根据需要多次传递消息m的实例，进程pi利用execi[m，s]和函数apply msg（m，s，c）。变量execi[m，s]记住由于接收（ACK，m，s，-）而处理piexecuted RB deli（m）的次数（最初execi[m，s]是0，第2行）。函数apply msg（m，s，c）允许进程pito从execi[m，s] 1指示的最后一次开始执行RB deli（m），直到c指示的消息计数器（m，s）的值为止（第14行）。为了避免由于过时的消息传递（ACK，m，s，c）而导致消息m的RB传递实例，c必须大于execi[m，s]（第13行）。

···略···

5 原子吸收光谱法中城市轨道服务的不可能性[fgt;n/2]

在本节中，我们将说明如果大多数进程都可能崩溃，那么在匿名异步系统中就不可能解决URB服务。

····

6 在AAS中实现URB服务

在本节中，我们将介绍一个算法（参见图2），当大多数过程是正确的时候（即AAS[f lt; n/2])在匿名异步系统中实现URB服务。

本节介绍了另一种算法（见图3），该算法使用故障检测器Psi;，在AAS中实现URB服务，见定义3（即AAS[Psi;]）。注意，由于定理1的不可能结果，我们需要使用故障检测器来增强系统并规避这种不可能。因此，在AAS中实现URB服

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[238724]，资料为PDF文档或Word文档，PDF文档可免费转换为Word