容攻击的广域网（III)（100304）
闵应骅
    本文介绍Steward协议和核心算法。
    Steward提供一种分级的拜占庭容错结构，在系统的所有站点间运行一个简明的容错协议。Steward的分级体系结构分为两级：全局和局部，全局管站点，局部管服务器。每一个站点选择一个站点代表，负责散发消息到其他站点代表，接收全局消息，并分发给局部服务器。如果站点代表可疑，站内其他服务器运行局部视图改变协议，取代原有代表，安装新的视图。领袖站点运行全局协议。如果领袖站点出局，则运行非领袖站点全局视图改变协议，选一个新的领袖站点，安装新的全局视图。领袖站点的代表调用为构造在广域网上可传送消息所需要的局部协议，来驱动全局协议。
    在正常情况下，没有领袖站点选举或站点代表选举发生。一次刷新过程如下：
1.用户送一个刷新给局部的某一个服务器。该刷新由一个数据对唯一地标记（用户ID，用户产生的局部时间戳）。一个正常的用户只有接收到对时间戳为i的回复以后，才能送出时间戳为i+1的刷新。用户的局部服务器把该刷新传给局部代表，局部代表再把它传给领袖站点代表。假如用户在一定时限内收不到回答，它将向局部内的所有服务器广播该刷新。
2.当领袖站点代表收到一个刷新，它调用ASSIGN-SEQUENCE协议，给这个刷新分配一个全局序号。该分配压缩于Proposal信息，并根据THRESHOLD-SIGN协议构造门限签名，把签名了的Proposal送给所有其他的站点代表。
3.当代表收到签名了的Proposal以后，转发给其站内所有服务器。服务器收到之后，构造一个站点ACK（即接收消息），调用THRESHOLD-SIGN。站点代表组合这些部分签名，把结果的带门限签名的接收消息送给其他站点代表。
4.站点代表把收到的接收消息转发给本站点的局部服务器。当它收到[S/2]个（多数，S为站点数）从不同站点来的接收消息及其对应的Proposal，它全局性地排序该刷新。该用户所在站点的服务器送回复到该用户。
    正常情况下刷新传送过程就结束了。按理说，我们还要说明THRESHOLD-SIGN和ASSIGN-SEQUENCE这两协议，以及视图如何改变、领袖如何选举、代表如何选举、时限如何确定等等技术细节。但是，博文太长就不像博文了。就此打住。
    下一篇我们要说的是：对于拜占庭问题的这样一个解，我们应该证明什么，才能说明Steward的确是一个解。

转载本文请联系原作者获取授权，同时请注明本文来自闵应骅科学网博客。
链接地址：https://wap.sciencenet.cn/blog-290937-299557.html

上一篇：容攻击的广域网（II）（100303）
下一篇：容攻击的广域网（IV）（100305）