Distributed Misc

http://www.cnblogs.com/javanerd/p/6444536.html

第二章 系统模型

描述分布式系统的三种模型

• Physical models : 用机器，网络，硬件等语言去描述整个系统。
• Architectural models : 用计算、计算任务、计算单元等语言去描述整个系统。（比上一中抽象）
• Fundametal models : 用抽象的方式去描述整个系统，主要包括三个方面：interaction models( 系统间的通信)，failure models （描述故障），security models

Architectural models

在这个模型中，考察四个方面：

• 在分布式系统中，通讯的实体（entity）是什么？
• 实体间的通信方式。（ interprocess communication - socket 调用，remote invocation - rpc ，indirect communication - 消息队列）
• 各个实体的在分布式系统的中的角色。
• 各个实体在物理层面，对应的是什么设施。

Fundamental models

用基本的模型主要为了解决两个问题

• 对于分布式系统中的一切假设去建模
• 对于一些假设去证明是否可能，或者不可能。

interaction models

主要影响系统间通信的两个方面：

1. 通信性能受限
2. 没有一个全局时间

failures models

主要关注系统是否故障，故障可以分类

1. Omission failures（无响应，未履行的故障）
2. 1.1 Process omission：进程挂了，在异步分布式系统中，这种故障检测只能靠timeout，但是timeout有可能只是因为系统响应慢了。
3. 1.2 Communication omission failures
4. Arbitrary failures（Byzantine failure）：随机的failures
5. Timing failures： 只在同步的分布式系统中有，指的是各种时间没有在bound中。例如消息延迟了。

https://en.wikipedia.org/wiki/Byzantine_fault_tolerance
在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论^[2]，从而破坏系统一致性^[3]。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假始那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个默认值，若消息（票）没有被收到，则使用此默认值来投票。