开发者

Can a logical clock protocol provide a full ordering of events?

开发者 https://www.devze.com 2023-03-12 09:19 出处:网络
Is there a logi开发者_开发知识库cal clock protocol (like Lamport\'s Timestamps or a Vector Clock) that provides a full ordering of events in a distributed system without just breaking ties arbitrarily

Is there a logi开发者_开发知识库cal clock protocol (like Lamport's Timestamps or a Vector Clock) that provides a full ordering of events in a distributed system without just breaking ties arbitrarily? If it's not possible, is there a proof?


No, there is no such algorithm and there is a proof, see, for example, theorem 2.21 in G. Tel, Introduction to Distributed Algorithms, 2nd ed. Roughly speaking the theorem states that given a causal ordering of events, an actual computation can proceed in any way that is compatible with the causal ordering.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号