分布式系统分类
SMP (symmetric multiprocessor) 对称多处理机
PVP (parallel vector processor) 并行向量机
MPP (Massively parallel processor) 大型并行机
COW (cluster of workstation) 工作站集群
Internet 广域分布式
而针对并行机(耦合/松散类型)有DSW (Distributed Shared Memory) 专用分布式共享存储
分布式系统的优势
可用性: 比如保证可靠性, 多个处理机计算同一个任务, 对比结果分析是否正确
高性能: 多个处理机分担大型任务, 提高计算复杂任务的效率
分布式系统的困难:
异质性: 软硬件不同
异步性: 事件发生的绝对/相对时间不能精准得知
局部性: 每个计算实体只有全局情况的一个局部信息
故障: 每个计算实体可能独立出现故障, 影响其他计算实体的工作进度
目标: 针对分布式系统完成类似顺序式计算中对算法的研究.
对分布式情况进行抽象, 精确陈述问题
设计和分析有效算法
证明算法最优性
计算模型:
通信: 信息传递 / 共享变量
计时信息和行为
容错
复杂性度量:
时间 / 空间
通信成本
故障 / 非故障数目
分布式系统通常会出现一些不可解的问题, 需要给出不可解证明
(分布式的 NP-hard 问题, 在多项式时间复杂内无确定性解法的问题
(NPC问题, 如果对该类中的某一个问题设计出多项式时间复杂性的电子计算机算法, 那么该类中的每一个问题也都存在多项式时间复杂性的电子计算机算法; 反之, 如果证明了该类中的某一个问题不存在多项式时间的电子计算机算法, 那么该类中的所有问题也不可能存在多项式时间复杂性的电子计算机算法
实际中: 在弱情况下求解问题
侧重研究:
可计算性
计算复杂度
按 通信介质 和 同步程度 分类
主要考虑两个模型: 异步 / 同步
网络拓扑图: 默认为无向图, 结点表示处理机, 边表示双向信道
算法: 由每个处理机上的局部算法的构成
形式化: 一个算法由
{
p
0
,
p
1
,
.
.
.
,
p
n
−
1
}
\{p_0, p_1, ..., p_{n-1}\}
{p0,p1,...,pn−1}n个处理机组成, 并且对于处理机
p
i
p_i
pi可以抽象为状态集为
Q
i
Q_i
Qi的状态机(可以为无限); 对于结点i, 具有输入输出缓冲区, 定义为
i
n
b
u
f
i
[
1
,
2
,
.
.
.
,
r
]
inbuf_i [1, 2, ..., r]
inbufi[1,2,...,r] 和
o
u
t
b
u
f
i
[
1
,
2
,
.
.
.
,
r
]
outbuf_i [1, 2, ..., r]
outbufi[1,2,...,r], 下标i表示靠近结点i的缓存区
因此, 处理机
p
i
p_i
pi的状态由2r个信息集构成
i
n
b
u
f
i
[
l
]
inbuf_i [l]
inbufi[l]: 在
p
i
p_i
pi的第
l
l
l条信道上已传递给
p
i
p_i
pi但尚未经过
p
i
p_i
pi内部计算处理的消息
o
u
t
b
u
f
i
[
l
]
outbuf_i [l]
outbufi[l]:
p
i
p_i
pi经过第
l
l
l条信道发送给邻结点, 但尚未抵达的消息
初始状态
对于每个
Q
i
Q_i
Qi包含一个特殊的初始状态子集, 每个
i
n
b
u
f
i
[
l
]
inbuf_i[l]
inbufi[l]必须为空,
o
u
t
b
u
f
i
[
l
outbuf_i[l
outbufi[l可能不空
转换函数(transition)
处理器
p
i
p_i
pi的转换函数是一个局部程序
配置
这个配置是指, 在某个时间点下整个算法的全局状态, 即所有处理机结点的状态集合
定义为向量
(
q
1
,
q
2
,
.
.
.
,
q
n
−
1
)
(q_1, q_2, ..., q_{n-1})
(q1,q2,...,qn−1),
q
i
q_i
qi 为
p
i
p_i
pi 的一个状态; 一个配置里outbuf变量则是每个信道正在传输的信息; 一个初始配置则是所有处理机的初始状态.
转移系统: 状态按离散步骤变化的系统
定义1: 三元组
S
=
(
C
,
→
,
I
)
S = (C, →, I)
S=(C,→,I)可以表示一个转移系统. C是配置集, →是C上的一个二元关系(比如配置
C
x
C_x
Cx 转移到
C
y
C_y
Cy), I是初始配置的一个子集
定义2:
S
=
(
C
,
→
,
I
)
S = (C, →, I)
S=(C,→,I)是转移系统, S的一次执行的最大序列为
E
=
(
r
0
,
r
1
,
.
.
.
)
E = (r_0, r_1, ...)
E=(r0,r1,...)其中
r
0
∈
I
r_0 \in I
r0∈I. 且对于
∀
i
≥
0
,
r
i
→
r
i
+
1
\forall i \geq 0, r_i → r_{i+1}
∀i≥0,ri→ri+1. 终止配置: 不存在
σ
\sigma
σ满足
r
→
σ
r → \sigma
r→σ, 则称r为终止配置
最大序列E可以无限长 / 以终止配置结束
定义3:
S
=
(
C
,
→
,
I
)
S = (C, →, I)
S=(C,→,I)是转移系统, 如果S的一次执行存在序列
r
→
r
1
→
.
.
.
→
r
k
=
σ
r → r_1 → ... → r_k = \sigma
r→r1→...→rk=σ且对
∀
i
≥
0
&
i
≤
k
−
1
\forall i \geq 0 \& i \leq k - 1
∀i≥0&i≤k−1, 满足
r
i
→
r
i
+
1
r_i → r_{i+1}
ri→ri+1, 则称配置
σ
\sigma
σ是由配置r可达. 如果配置S是由初始配置可达, 则统一称为可达的.
事件
系统发生的动作被模型化为事件
comp(i) ---- 计算事件, 处理机
p
i
p_i
pi的一个计算步骤, 每次计算事件会清空
i
n
b
u
f
i
inbuf_i
inbufi
del(i, j, m) ---- 传递事件, 消息m由处理机
p
i
p_i
pi传递到
p
j
p_j
pj
执行
系统在时间上的行为被模型化为执行, 是一个由配置和事件交错的序列. 需要满足两个条件:
(1 safety: 某个性质在每次执行中每个可达的配置里都需要成立, 在序列的每个有限前缀里必须成立(简单来说就是序列的有限个之前的执行不出错, 或者说一个性质在所有全局状态(配置)下均成立
形式化: 断言P, Q需要满足, 在
S
=
(
C
,
→
,
I
)
S = (C, →, I)
S=(C,→,I)转移系统中, 对于任意一次转移
r
→
σ
r → \sigma
r→σ, 断言P在配置r下成立: P( r )成立, 则转移后
Q
(
σ
)
Q( \sigma )
Q(σ)成立
定义4:
∀
r
∈
I
\forall r \in I
∀r∈I,
P
(
r
)
P(r)
P(r)成立且
{
P
}
→
{
P
}
\{P\} → \{P\}
{P}→{P}, 断言P总是成立, 则称P为不变式
定理1: 如果P是S的不变式, 则对于S的每一个执行和任意配置P都成立
定理2: 设Q是S的不变式, 且
Q
⇒
P
Q \Rightarrow P
Q⇒P(对于
∀
r
∈
C
\forall r \in C
∀r∈C成立). 那么P在S的每次执行和任意配置中均成立(但是注意, P依然不一定是不变式
证:
∀
r
∈
C
\forall r \in C
∀r∈C的每一个执行,
Q
(
r
)
Q(r)
Q(r)成立, 则
P
(
r
)
P(r)
P(r)成立
定义5: S是转移系统, P,Q为断言, 对于
∀
r
∈
I
\forall r \in I
∀r∈I满足
Q
(
r
)
⇒
P
(
r
)
Q(r) \Rightarrow P(r)
Q(r)⇒P(r)且{
Q
∩
P
Q \cap P
Q∩P} → {
Q
⇒
P
Q \Rightarrow P
Q⇒P}(Q且P成立能在转移之后让Q推出P成立), 则称P为Q导出的
定理3: 如果Q是不变式, 且P是Q导出的, 则
Q
∩
P
Q \cap P
Q∩P 为不变式
证明: 需要证两个条件1.
∀
r
∈
I
,
Q
∩
P
(
r
)
\forall r \in I, Q \cap P(r)
∀r∈I,Q∩P(r)成立; 2.{
Q
∩
P
Q \cap P
Q∩P} → {
Q
∩
P
Q \cap P
Q∩P}成立
已知条件: Q是不变式, P是Q导出所以有
(1)
∀
r
∈
I
,
Q
(
r
)
\forall r \in I, Q(r)
∀r∈I,Q(r)成立
(2) {Q} → {Q}
(3)
∀
r
∈
I
,
Q
(
r
)
⇒
P
(
r
)
\forall r \in I, Q(r) \Rightarrow P(r)
∀r∈I,Q(r)⇒P(r)成立
(4) {
Q
∩
P
Q \cap P
Q∩P} → {
Q
⇒
P
Q \Rightarrow P
Q⇒P}
由(1)(3)可以推出
∀
r
∈
I
,
Q
∩
P
(
r
)
\forall r \in I, Q \cap P(r)
∀r∈I,Q∩P(r)成立
证明{
Q
∩
P
Q \cap P
Q∩P} → {
Q
∩
P
Q \cap P
Q∩P}即证明
Q
∩
P
(
r
i
)
Q \cap P(r_i)
Q∩P(ri) →
Q
∩
P
(
r
i
+
1
)
Q \cap P(r_{i+1})
Q∩P(ri+1)成立
由(2)(3)(4), 已知
Q
(
r
i
)
→
Q
(
r
i
+
1
)
Q(r_i) → Q(r_{i+1})
Q(ri)→Q(ri+1)成立,
Q
∩
P
(
r
i
)
→
Q
(
r
i
+
1
)
⇒
P
(
r
i
+
1
)
Q \cap P(r_i) → Q(r_{i+1}) \Rightarrow P(r_{i+1})
Q∩P(ri)→Q(ri+1)⇒P(ri+1)成立
则
P
(
r
i
+
1
)
P(r_{i+1})
P(ri+1)成立, 所以
Q
∩
P
(
r
i
+
1
)
Q \cap P(r_{i+1})
Q∩P(ri+1)也成立, 归纳法即可证明{
Q
∩
P
Q \cap P
Q∩P} → {
Q
∩
P
Q \cap P
Q∩P}
(2 liveness条件 (活跃性条件
某个性质在每次执行中某些可达配置里必须成立, 比如"
p
1
p_1
p1必须终止"
这个条件限制了执行的合法性, 不至于达不到目标计算结果
形式化:
safety条件: 在算法每次执行的每个可达配置中, 断言p始终为真
liveness条件: 在算法每次执行的某些配置中, 断言p最终为真
定义5: 如果谓词(term ⇒ \Rightarrow ⇒ p)在S中总为真, 则系统S正常终止(无死锁性
定义6: 给定转移系统S和断言P, 称C到良基集W的函数f为关于p的范函数. 当且仅当对于任意一次转移r →
σ
\sigma
σ, 有
f
(
r
)
>
f
(
σ
)
f(r) > f(\sigma)
f(r)>f(σ)或
p
(
σ
)
p(\sigma)
p(σ)成立
(良基集: 称一个偏序集(W, <)是良基的, 如果集合中不存在无穷递减序列, 也就是需要存在一个最小元素)
定理4: 给定转移系统S, 和断言p, 如果S正常终止, 且关于p的范函数f存在, 那么p在S的每一次执行的某些配置中, p为真
定理5: 如果S正常终止, 且存在数k满足算法的每一次执行至多包含k步转移, 那么在算法每次执行的某些配置中, p为真
应用: 由定理5, 可以通过证明算法可以正常终止且为有限数目步, 那么就可以证明liveness条件成立