4 ms·

Relativistic effects are irrelevant at the level of precision required for running a system distributed across the surface of Earth, what you are describing is

Relativistic effects are irrelevant at the level of precision required for running a system distributed across the surface of Earth, what you are describing is just due to a lack of properly synchronized clocks. Place an atomic clock at each node and there is no need for any C deciding the ordering of A and B. Alternatively you may also be able to use logical clocks like a Lamport clock or a vector clock to establish an ordering in a distributed system in absence of properly synchronized clocks but that depends on the use case.

EGreg 8y ago
No. Relativity is actually a special case if this general principle. For a large and complex network, events A and B which are very far apart cannot be compared in any canonical way. The larger the network the less they can be compared. However, A can come before B relative to some reference point C. That’s enough to achieve most things. The point is that you shouldn’t have a global and continuous sense of time in distributed systems. Leslie Lamport has developed many things including vector clock over the years to address this. Our PTN is just the latest in a long line of examples. When you say that you have “no need” for C once you have synchronized clocks, not only are you ignoring relativity but you are also ignoring the byzantine generals problem. If Han Solo can benefit from claiming he shot first, why would I trust his clock? If you’re implementing a video game or cryptocurrency in a byzantine resilient way, how exactly would you have a continuous global sense of time? Go ahead the floor is yours.
- danbruc 8y ago
  You are mixing two things up - figuring out the time an event happened and trusting a timestamp that someone attached to an event. Within a single inertial reference frame there is a canonical way to order events, namely by the time coordinate in that reference frame which is the same everywhere. And for all practical purposes of building a distributed system on Earth, Earth is an internal reference frame. Ensuring that nobody cheats when assigning time stamps to events is an entirely different problem. As said, hand an atomic clock to everyone and you can know the order of any two events, relativity plays no role. Making sure that nobody can or will cheat will require some more effort, but again relativity plays no role.
  - EGreg 8y ago
    You didn’t explain how a distributed byzantine system can synchronize a global time that’s continuous. I am saying that you won’t be able to — local time is continuous and you should use that for comparisons. It’s nowhere near as straightforward as you think to make global time work. You will find that “making sure nobody can or will cheat” will require exactly the kind of effort that will make the concept of a global timestamp meaningless. Also, why do you need a global timestamp in the first place? Upon further reflection you will probably realize that all your concepts of time actually require exactly what I said: two paths to the same local reference point, where a comparison is made. Your ideas about global time are an illusion based on simplifying assumptions that are not true.
    - danbruc 8y ago
      I only object your claim that relativity - as in special or general theory of relativity - has any bearing on the design of distributed systems on Earth. In particular, you can order events occurring at different places if you have properly synchronized clocks. The fact that a common solution is to use logical clocks like Lamport clocks is because it is easier to do so than to maintain a network of precisely synchronized clocks. But that does not mean it can not be done with synchronized clocks, see for example Google's Spanner [1] database. I never addressed what else is necessary to make this work in the presence of Byzantine faults. But I am also pretty sure that just sending information about events from A and B to C and asking C about the ordering is not sufficient, after all C may be faulty and give a wrong answer, change its mind after every query, or just not respond at all. Admittedly you did not provide many details, so I may very well totally misunderstand what you had in mind. But, just to repeat, I am not really addressing the requirements of a Byzantine fault tolerant system, I am just saying that the special or general theory of relativity is not relevant for distributed systems on Earth. [1] https://en.wikipedia.org/wiki/Spanner_(database) https://en.wikipedia.org/wiki/Spanner_(database)
      - EGreg 8y ago
        I think you misunderstood my point. I said that relativity is a special case of this principle that time is a local phenomenon.
mannykannot 8y ago
Are Lamport and vector clock mechanisms robust in the presence of nodes controlled by bad actors, who may be colluding through a hidden network?
- danbruc 8y ago
  No, they are just for establishing [partial] orderings of events, they are not designed to be resistent against adversarial behavior.

EGreg 8y ago

No. Relativity is actually a special case if this general principle. For a large and complex network, events A and B which are very far apart cannot be compared in any canonical way. The larger the network the less they can be compared. However, A can come before B relative to some reference point C. That’s enough to achieve most things. The point is that you shouldn’t have a global and continuous sense of time in distributed systems. Leslie Lamport has developed many things including vector clock over the years to address this. Our PTN is just the latest in a long line of examples. When you say that you have “no need” for C once you have synchronized clocks, not only are you ignoring relativity but you are also ignoring the byzantine generals problem. If Han Solo can benefit from claiming he shot first, why would I trust his clock? If you’re implementing a video game or cryptocurrency in a byzantine resilient way, how exactly would you have a continuous global sense of time? Go ahead the floor is yours.

danbruc 8y ago
You are mixing two things up - figuring out the time an event happened and trusting a timestamp that someone attached to an event. Within a single inertial reference frame there is a canonical way to order events, namely by the time coordinate in that reference frame which is the same everywhere. And for all practical purposes of building a distributed system on Earth, Earth is an internal reference frame. Ensuring that nobody cheats when assigning time stamps to events is an entirely different problem. As said, hand an atomic clock to everyone and you can know the order of any two events, relativity plays no role. Making sure that nobody can or will cheat will require some more effort, but again relativity plays no role.
- EGreg 8y ago
  You didn’t explain how a distributed byzantine system can synchronize a global time that’s continuous. I am saying that you won’t be able to — local time is continuous and you should use that for comparisons. It’s nowhere near as straightforward as you think to make global time work. You will find that “making sure nobody can or will cheat” will require exactly the kind of effort that will make the concept of a global timestamp meaningless. Also, why do you need a global timestamp in the first place? Upon further reflection you will probably realize that all your concepts of time actually require exactly what I said: two paths to the same local reference point, where a comparison is made. Your ideas about global time are an illusion based on simplifying assumptions that are not true.
  - danbruc 8y ago
    I only object your claim that relativity - as in special or general theory of relativity - has any bearing on the design of distributed systems on Earth. In particular, you can order events occurring at different places if you have properly synchronized clocks. The fact that a common solution is to use logical clocks like Lamport clocks is because it is easier to do so than to maintain a network of precisely synchronized clocks. But that does not mean it can not be done with synchronized clocks, see for example Google's Spanner [1] database. I never addressed what else is necessary to make this work in the presence of Byzantine faults. But I am also pretty sure that just sending information about events from A and B to C and asking C about the ordering is not sufficient, after all C may be faulty and give a wrong answer, change its mind after every query, or just not respond at all. Admittedly you did not provide many details, so I may very well totally misunderstand what you had in mind. But, just to repeat, I am not really addressing the requirements of a Byzantine fault tolerant system, I am just saying that the special or general theory of relativity is not relevant for distributed systems on Earth. [1] https://en.wikipedia.org/wiki/Spanner_(database) https://en.wikipedia.org/wiki/Spanner_(database)
    - EGreg 8y ago
      I think you misunderstood my point. I said that relativity is a special case of this principle that time is a local phenomenon.

mannykannot 8y ago

Are Lamport and vector clock mechanisms robust in the presence of nodes controlled by bad actors, who may be colluding through a hidden network?

danbruc 8y ago
No, they are just for establishing [partial] orderings of events, they are not designed to be resistent against adversarial behavior.