星球日报
搜索
手机客户端
iPhone · Android
微信公众号
微信公众号

iPhone · Android

微信公众号

经典重读 | 拜占庭将军问题

2019-03-12

一个可靠的计算机系统必须具备处理故障的能力,以免出现故障的组件向系统其他部分传递信息时出现错误。在拜占庭问题中,一个叛变的将领会迷惑两位忠诚的将领。如果使用不可伪造的书信交流,不论有多少将领和潜在的叛变将领,此问题也有解。

原作者:L Lamport, R Shostak, M Pease    翻译:TLAB李炼炫

一个可靠的计算机系统必须具备处理故障的能力,以免出现故障的组件向系统其他部分传递信息时出现错误。该情况可以用以下语境抽象地表述:一群拜占庭军队的将军率兵驻扎在敌城附近。在只能依靠信使联系彼此的情况下,将军们必须就同一个作战方案达成共识。然而,他们中的一位或多位有可能是叛徒,试图混淆其他人的视听。解决该问题的关键在于找到一种算法来确保忠心耿耿的将军之间能够达成共识。研究显示,如果仅靠口信交流,当且仅当忠诚的将领人数超过三分之二时,此问题便可解决;因此,一个叛变的将领会迷惑两位忠诚的将领。如果使用不可伪造的书信交流,不论有多少将领和潜在的叛变的将领,此问题有解。文章随后讨论了这些解法在建立可靠计算机系统中的运用。

分类和关键词:C.2.4[计算机通信网络]:分布式系统——网络操作系统; D.4.4[操作系统]:通信管理——网络通信; D.4.5[操作系统]:可靠性——容错

通用术语:算法,可靠性

其他关键词:交互一致性

一、引言

一个可靠的计算机系统必须能够处理一个或多个故障组件。故障组件可能会表现出一类常常被忽视的行为——即向系统的其他组件发送冲突信息。处理这类故障的问题可以抽象地表述为拜占庭将军问题。本文着重讨论了这一问题,并在结论中指出如何利用这类解法使可靠的计算机系统成为可能。

我们假设有几个师的拜占庭军队在一座敌城外扎营,每个师都由一名将军统率。将军们彼此之间只能通过信使联系。观察敌情后,他们必须商讨出一个一致的作战

经典重读 | 拜占庭将军问题经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题经典重读 | 拜占庭将军问题经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题经典重读 | 拜占庭将军问题

经典重读 | 拜占庭将军问题

本文翻译自https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf。如若转载请注明出处。

参与讨论

登录后参与讨论

TLABResearch

特邀作者

TLABResearch

致力于做区块链行业里最权威的数字券商

总文章数: 7


分享至

微信扫一扫分享

0