8 ms·

Fun stuff: "What time is it ?" is a question that a vector clock can't answer, since it does not provide total ordering.

by dikei 3y ago

catlifeonmars 3y ago
Time isn’t totally ordered either whenever there are multiple observers with differing inertial frames.
- 3cats-in-a-coat 3y ago
  Funny how computer algorithms reinvented General Relativity, because they happen to operate in a universe ruled by it.
  - frutiger 3y ago
    > reinvented General Relativity Special relativity.
    - 3cats-in-a-coat 3y ago
      Time isn't totally ordered in both, though?
      - Filligree 3y ago
        Correct. Special relativity is the special case where there's no gravity, but for the most part adding in gravity just complicates things.
        3cats-in-a-coat 3y ago
        I mean, if the goal is to keep it simple and wrong we can remove even more things then. JK. What Special Relativity was, is work in progress, General Relativity is the whole model, it makes sense together, it’s cohesive, and it’s cohesive because it has gravity in. Without it, this universe does not exist. Although it is slightly off-topic here, I would actually suggest that without gravity there is no time, but this is another story.
        BoiledCabbage 3y ago
        Yes but the parts related to GR are irrelevant. That's like if CS needed a Newtonian Physics model for something seeing it and saying "ah ha, computers invented GR Because they exist in a universe that uses it." Just because newtonian physics is a sub part of GR, doesn't mean "GR" is the best way to describe basic F=ma. The smallest subset theory that incorporates the need for vector clocks, and the most unique part that introduced and required vector clocks is special relativity - which is what thats what's most appropriate to discuss and not GR.
      - frutiger 3y ago
        Yes, but the reason to bring in vector clocks in computer science is because information does not propagate instantaneously. This is also the key insight of Special Relativity. The key insight of General Relativity is that in addition to, tidal effects of gravity cannot be transformed away even in arbitrarily accelerating reference frames. This is not particularly related to vector clocks.
  - myk9001 3y ago
    This isn't a coincidence. Vector clocks, roughly speaking, build upon the idea of Lamport Clocks. This isn't to say that one type of clock is better than the other. The choice between them depends on the task at hand and involves a set of trade-offs. Anyway, Leslie Lamport, who is considered the founding father of distributed systems as we know them today, introduced the concept of Lamport Clocks in his 1978 paper "Time, clocks, and the ordering of events in a distributed system" (for which he later won the Turing Award). According to Lamport, that paper was directly inspired by the special theory of relativity. In his own words [^1]: "[...] special relativity, in particular, the four-dimensional space-time view developed by Minkowski in the famous 1908 paper. I realized that the problems in distributed systems are very much analogous to what's going on in physics [...]" So, I don't know if these algorithms were reinvented or (re)discovered because, as you rightly say, they happen to operate in our universe. [^1]: https://www.youtube.com/watch?v=nfRouGH0oMg https://www.youtube.com/watch?v=nfRouGH0oMg"
dboreham 3y ago
Vector clocks are typically used to provide total order by using the node id as a tie break on concurrent sequence numbers.
- josephg 3y ago
  If you want a total order over a bunch of events, you don’t need vector clocks. A simple sequence number that everyone increments is usually enough. (Eg each event has max(seen)+1 and tie break on content or agent id or something). Vector clocks are valuable precisely because you can tell when concurrent events occur. Eg [1,2] and [2,1] are concurrent but [1,2] and [2,2] are ordered. You need this info for things like MVRegister CRDTs.
  - catlifeonmars 3y ago
    I’m assuming you mean total order in a synchronized system. As soon as you introduce concurrency, max(seen) followed by a tie break is no longer guaranteed to be eventually consistent. Nodes can disagree on the order of past events; to put it another way, their histories will have diverged.

Fun stuff: "What time is it ?" is a question that a vector clock can't answer, since it does not provide total ordering.

by dikei 3y ago

Fun stuff: "What time is it ?" is a question that a vector clock can't answer, since it does not provide total ordering.

catlifeonmars 3y ago

Time isn’t totally ordered either whenever there are multiple observers with differing inertial frames.

3cats-in-a-coat 3y ago
Funny how computer algorithms reinvented General Relativity, because they happen to operate in a universe ruled by it.
- frutiger 3y ago
  > reinvented General Relativity Special relativity.
  - 3cats-in-a-coat 3y ago
    Time isn't totally ordered in both, though?
    - Filligree 3y ago
      Correct. Special relativity is the special case where there's no gravity, but for the most part adding in gravity just complicates things.
      - 3cats-in-a-coat 3y ago
        I mean, if the goal is to keep it simple and wrong we can remove even more things then. JK. What Special Relativity was, is work in progress, General Relativity is the whole model, it makes sense together, it’s cohesive, and it’s cohesive because it has gravity in. Without it, this universe does not exist. Although it is slightly off-topic here, I would actually suggest that without gravity there is no time, but this is another story.
        BoiledCabbage 3y ago
        Yes but the parts related to GR are irrelevant. That's like if CS needed a Newtonian Physics model for something seeing it and saying "ah ha, computers invented GR Because they exist in a universe that uses it." Just because newtonian physics is a sub part of GR, doesn't mean "GR" is the best way to describe basic F=ma. The smallest subset theory that incorporates the need for vector clocks, and the most unique part that introduced and required vector clocks is special relativity - which is what thats what's most appropriate to discuss and not GR.
    - frutiger 3y ago
      Yes, but the reason to bring in vector clocks in computer science is because information does not propagate instantaneously. This is also the key insight of Special Relativity. The key insight of General Relativity is that in addition to, tidal effects of gravity cannot be transformed away even in arbitrarily accelerating reference frames. This is not particularly related to vector clocks.
- myk9001 3y ago
  This isn't a coincidence. Vector clocks, roughly speaking, build upon the idea of Lamport Clocks. This isn't to say that one type of clock is better than the other. The choice between them depends on the task at hand and involves a set of trade-offs. Anyway, Leslie Lamport, who is considered the founding father of distributed systems as we know them today, introduced the concept of Lamport Clocks in his 1978 paper "Time, clocks, and the ordering of events in a distributed system" (for which he later won the Turing Award). According to Lamport, that paper was directly inspired by the special theory of relativity. In his own words [^1]: "[...] special relativity, in particular, the four-dimensional space-time view developed by Minkowski in the famous 1908 paper. I realized that the problems in distributed systems are very much analogous to what's going on in physics [...]" So, I don't know if these algorithms were reinvented or (re)discovered because, as you rightly say, they happen to operate in our universe. [^1]: https://www.youtube.com/watch?v=nfRouGH0oMg https://www.youtube.com/watch?v=nfRouGH0oMg"

dboreham 3y ago

Vector clocks are typically used to provide total order by using the node id as a tie break on concurrent sequence numbers.

josephg 3y ago
If you want a total order over a bunch of events, you don’t need vector clocks. A simple sequence number that everyone increments is usually enough. (Eg each event has max(seen)+1 and tie break on content or agent id or something). Vector clocks are valuable precisely because you can tell when concurrent events occur. Eg [1,2] and [2,1] are concurrent but [1,2] and [2,2] are ordered. You need this info for things like MVRegister CRDTs.
- catlifeonmars 3y ago
  I’m assuming you mean total order in a synchronized system. As soon as you introduce concurrency, max(seen) followed by a tie break is no longer guaranteed to be eventually consistent. Nodes can disagree on the order of past events; to put it another way, their histories will have diverged.