什么是分散式算法

liuliuQA2021-05-05 04:56:59阅读(...)

分布式算法是设计用于在由互连处理器构造的计算机硬件上运行的算法。分布式算法用于分布式计算的许多不同应用领域,分布式算法解决的标准问题包括领导者选举,共识,分布式搜索,生成树生成,互斥和资源分配。

分布式算法是设计用于在由互连处理器构造的计算机硬件上运行的算法。分布式算法用于分布式计算的许多不同应用领域,例如电信,科学计算,分布式信息处理和实时过程控制。分布式算法解决的标准问题包括领导者选举,共识,分布式搜索,生成树生成,互斥和资源分配。

什么是分散式算法

介绍

分布式算法是并行算法的子类型,通常同时执行,算法的单独部分在独立处理器上同时运行,并且关于算法的其他部分正在做什么的信息有限。开发和实现分布式算法的主要挑战之一是在面对处理器故障和不可靠的通信链路时成功协调算法的独立部分的行为。选择合适的分布式算法来解决给定问题取决于问题的特征和算法运行的系统特性,例如处理器或链路故障的类型和概率,进程间通信的类型可以执行的,以及单独进程之间的定时同步级别。

为分散式计算而设计,它运行在一群相互连结的处理器所构成的计算机硬件平台上。分散式算法以并行方式执行,是平行算法下的子类别。因为同时运行在不同处理器上,对算法其他部份运行情况的资讯所知有限,使得这类型的算法较为困难。

标准问题

原子提交

原子提交是一组操作,其中一组不同的更改作为单个操作应用。如果原子提交成功,则表示已应用所有更改。如果在完成原子提交之前发生故障,则“commit”将中止,并且不会应用任何更改。

用于解决原子提交协议的算法包括两阶段提交协议和三阶段提交协议。

共识

共识算法试图解决许多同意共同决策的过程的问题。

更准确地说,共识协议必须满足以下四个正式属性。

终止:每个正确的过程决定一些价值。

有效性:如果所有过程提出相同的值 v,则每个正确的过程决定 v。

完整性:每个正确的过程最多决定一个值,如果它决定某个值 v,那么 v 必须由某个过程提出。

协议:如果正确的过程决定 v,那么每个正确的过程决定 v。

解决共识的典型算法是 paxos 算法。

分布式搜索

领导者选举是将单个流程指定为在若干计算机(节点)之间分配的某个任务的组织者的过程。在任务开始之前,所有网络节点都不知道哪个节点将充当任务的“领导者”或协调者。然而,在运行了领导者选举算法之后,整个网络中的每个节点都将特定的唯一节点识别为任务领导者。

可靠的广播

可靠广播是分布式系统中的通信原语。可靠的广播由以下属性定义:

有效性 – 如果正确的进程发送消息,那么一些正确的进程最终将传递该消息。

协议 – 如果正确的流程传递了消息,那么所有正确的流程最终都会传递该消息。

完整性 – 每个正确的流程最多只传递一次相同的消息,并且只有在流程发送了该消息时才会传递。

可靠的广播可以具有顺序,因果或总排序。

收藏0个人收藏
走进科技生活方式

发表评论

本文评论已关闭!