Can a logical clock protocol provide a full ordering of events?
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.
精彩评论