# 袖珍分布式系统（三）

## Time and order

What is order and why is it important?

the art of solving the same problem that you can solve on a single computer using multiple computers.

## Total and partial order

Total 和 partial order 都满足 自反性和传递性。

If a ≤ b and b ≤ a then a = b (antisymmetry); If a ≤ b and b ≤ c then a ≤ c (transitivity);

total order还满足：

a ≤ b or b ≤ a (totality) for all a, b in X

a ≤ a (reflexivity) for all a in X

communication is expensive, and time synchronization is diﬃcult and fragile

## What is time?

Time is a source of order - it allows us to deﬁne the order of operations- which coincidentally also has an interpretation that people can understand (a second, a minute, a day and so on).

Timestamps really are a shorthand value for representing the state of the world from the start of the universe to the current moment - if something occurred at a particular timestamp, then it was potentially inﬂuenced by everything that happened before it.

• Order
• Duration
• Interpretation

• we can attach timestamps to unordered events to order them【通过给事件安排一个时间戳，从而给事件排序】
• we can use timestamps to enforce a speciﬁc ordering of operations or the delivery of messages (for example, by delaying an operation if it arrives out of order)【我们可以通过时间戳给操作重新排序】
• we can use the value of a timestamp to determine whether something happened chronologically before something else【通过时间戳知道哪个事件发生在前】

Interpretation - time as a universally comparable value.

Duration - durations measured in time have some relation to the real world.

## Does time progress at the same rate everywhere?

• "Global clock": yes
• "Local clock": no, but
• "No clock": no!

• the synchronous system model has a global clock,
• the partially synchronous model has a local clock, and
• in the asynchronous system model one cannot use clocks at all

### Time with a "Local-clock" assumption

events on each system are ordered but events cannot be ordered across systems by only using a clock.

## How is time used in a distributed system?

1. Time can deﬁne order across a system (without communication)
2. Time can deﬁne boundary conditions for algorithms

• where correctness depends on (agreement on) correct event ordering, for example serializability in a distributed database【正确性依赖于事件的顺序】
• order can be used as a tie breaker when resource contention occurs, for example if there are two orders for a widget, fulﬁll the ﬁrst and cancel the second one【当发生资源争用的时候可以用来做裁决】

## Failure detectors (time for cutoﬀ)

A failure detector is a way to abstract away the exact timing assumptions. Failure detectors are implemented using heartbeat messages and timers. Processes exchange heartbeat messages. If a message response is not received before the timeout occurs, then the process suspects the other process.

78 篇文章18 人订阅

0 条评论

## 相关文章

31660

273100

37750

22260

38270

55620

662120

50660

### 那些神奇的一行 Python 代码

Python 这门语言非常的有趣，不仅可以做高大上的人工智能、大数据、机器学习。还可以用来做 Web、爬虫。还有其它很多的应用。今天我就给大家展示下一行 Pyt...

19040

### 《一个陌生同学的留言》-- “老尚，你一定要讲设计模式”

image.png 以前就曾经有人问过我，“老尚，你说是不是有的面试官以虐新人为乐？”，，，我说，“传说中，据说有”，，，他说，“我觉得这应该不是传说。” //...

20880