闵应骅的博客分享 http://blog.sciencenet.cn/u/ymin 一位IEEE终身Fellow对信息科学及其发展的看法

博文

容攻击的广域网(IV)(100305)

已有 3569 次阅读 2010-3-5 09:48 |个人分类:计算机|系统分类:论文交流| 攻击, 广域网

容攻击的广域网(IV)(100305)
闵应骅
    我们已经说明:Steward是一种分级的拜占庭容错结构。怎么从理论上证明Steward的确是拜占庭问题的一个解呢?Yair Amir教授在其文章中用了46个定理来证明,占了全文的大部分篇幅。一篇博文当然无法深入地写出这些证明,但是这正是该论文的精彩之处。现在我们有些学者不爱读证明,“承认它就算了”。我们自己有些文章上的“定理”,常常是两句话就证明完了。这叫什么“定理”?这恰恰是我们搞不出深刻工作的原因。我们喜欢讲大面上的东西,不深入。所以,本文想说明Yair Amir要证明什么?证明的思路是什么?详细证明,读者必须参看全文及其附录。
   一个站点说是对时刻T是稳定的,如果站点里有2f+1(f是被击垮的服务器数)个服务器在任何T'>T时是正确的而且是互相连接的。这些服务器也就称为稳定的。一个系统对时刻T是稳定的,如果该站点集的大多数站点是稳定的。当某个服务器执行刷新时,就说一个全局进展出现了。
   Steward正确性证明包括:
1。安全性(Safety):假如两个正确的服务器执行第i个刷新,则这些刷新是相同的。
   这就是说,两个服务器不能全局性地把不同的刷新赋以相同的序列号。我们证明,任意两个服务器在同一个全局视图下对同一个序列号全局性的排序一个刷新,必然是全局性的排序同一个刷新。一个领袖站点不可能在同一个全局视图下构造矛盾的Proposal。
2。正当性(Validity):只有一个已经由一个用户提出的刷新可以被执行。
   任意两个服务器,如果全局性地在不同的全局视图下对一个刷新排了同一个序列号,那么,这两个刷新是相同的。一个领袖站点不可能在以后的全局视图下构造一个Proposal,与在一个服务器上已经赋予同一序号的刷新相矛盾。正确的服务器不会给不同的刷新赋予相同的序号。由于一个服务器只执行已经赋予序列号的刷新,同样执行第i个刷新的两个服务器必然执行的是同一个刷新。
3。存活性(Liveness):假如系统对于时刻T是稳定的,那么,如果时刻T之后,一个稳定的服务器接收到一个尚未执行的刷新,则全局进展最后必然发生。
   用反证法。如果全局进展不发生。如果系统是稳定的,一个稳定的服务器接收到一个未经执行的刷新,那么,该系统将进入一个状态,使得某个稳定的服务器将执行一个刷新,而且制造全局进展。事实上,如果全局进展不发生,所有稳定的服务器将最后在全局历史上取得一致,即任何稳定服务器都执行了所有刷新,直到最大序列号的刷新。这时,任何服务器执行一个刷新,就制造了一个全局进展。矛盾。因此,稳定的领袖站点的稳定代表将在长时间内保持完成全局改变视图的权威,而且,最后能够全局性地排序和执行那个没有执行过的刷新。
    这些证明思路显得很生涩难懂,欲知详情者需要去看原文。今把该文及其附录附后。完全是公开的,没有版权问题。
容攻击广域网TDSCjan10
文章附录

https://wap.sciencenet.cn/blog-290937-299858.html

上一篇:容攻击的广域网(III)(100304)
下一篇:容攻击的广域网(V)(100306)
收藏 IP: .*| 热度|

3 俞立 张亮生 黄富强

发表评论 评论 (1 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 13:14

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部