10 ms·

Clocks and Causality – Ordering Events in Distributed Systems (2022)

397 points by alexzeitler 4y ago

vlovich123 4y ago
> However, because of clock drifts and/or assumptions around network time delays, timestamps from conventional clocks are not always mutually comparable, and therefore events cannot be reliably ordered using timestamps from conventional clocks. This isn’t quite right. CockroachDB and Yuggabyte both use conventional clocks to reliably order events. Spanner uses GPS to do so (conventional time stamp but maybe not technically a conventional clock).
- amelius 4y ago
  I suppose you can always order events by the time it takes for light to (physically or hypothetically) travel to a central server plus the server's local time.
  - diarrhea 4y ago
    Network uncertainties like splits and delays will render that impossible.
- ketzu 4y ago
  Your post made me read this: https://www.cockroachlabs.com/blog/living-without-atomic-clocks/ https://www.cockroachlabs.com/blog/living-without-atomic-clo... on how spanner and cockroadDB do this. And the answes are surprisingly simple, but with consequences attached. * Spanner creates very tight bounds on the clock synchronization (through atomic clocks/GPS) and ... just waits out the length of the bound. * CockroachDB seems to do lamport-clocks-with-real-timestamps for linearizability (track the highest seen timestamp for causality chains). For preventing consistency violations with reads, they also track the bounds on the clock and potentially attempt to read again. So they approve of the overall message (of not just comparing conventional timestamps) but work around those using the uncertainty of the clocks they have available. My professor used to introduce logical clocks with "as we usually can't use atomic clocks on all nodes" because of that.
  - hansvm 4y ago
    The "as we usually can't use atomic clocks on all nodes" constraint is more common than you might think. Even code as simple as ts = get_atomic_time_with_no_delay_because_this_node_has_an_atomic_clock(); do_stuff_with_time(ts); is really broken if you have to wait for garbage collection, wait for your process/thread/coroutine/... to be scheduled, wait for a nearly invisible pause as a cache line is refreshed, .... The time you're using the atomic timestamp is at some future moment, and if that delay matters for your algorithm you need to track your uncertainty just like Spanner/Cockroach do (you just get significant benefits because the uncertainty is low).
    - kurthr 4y ago
      If your get_atomic() isn't also capturing or resetting an internal hardware timer atomically it's kinda broken code anyway. It's important to remember that you're getting data from the firmware of an atomic clock (or GPS receiver) and that they will go to great lengths to compensate for latency variations so not doing it in the sampling code would be nuts (or just not using isochronous coms). Then the local clock/timer can be calibrated from the that and you can have near clock-cycle correct timing. Typically they only send out 1 pulse per second so anything finer than that is locally interpolated. We used 1ms internal intervals with an accuracy of ~1ppm. Last time I worked on something like this was 20 years ago, but it was a Pentium box. The clock firmware to converted a 5MHz sinewave output to 1Pps, but could also output a synthetic UTC through LAN in cases where there was no other connectivity. I guess I'm saying this is really specialized code for whatever hardware/OS you're using. (edit) Here's some documentation for a very similar box: https://www.manualslib.com/manual/1281621/Symmetricom-5071a.html?page=27#manual https://www.manualslib.com/manual/1281621/Symmetricom-5071a....
      - jrockway 4y ago
        The GPS clock is really used to provide long-term stability for the computer's internal oscillator, which provides fine short-term stability. Your calls to gettimeofday() are handled by the internal oscillator, not by asking the GPS unit directly. Additionally, NTP daemons are impressive in their ability to get the "right answer" on current internal oscillator frequency as affected by the entire system. With 86400 very accurate data samples per day, you can do a lot! In a distributed system, the absolute value of the time is important, since that's what your transaction timestamps are based on. There is a lot to do to ensure that your time offset from UTC ends up being correct; antenna cable length compensation, oscillator quantization compensation, etc. These are not strictly necessary for Spanner but can make microsecond-level differences which are quite noticeable. "The API directly exposes clock uncertainty, and the guarantees on Spanner’s timestamps depend on the bounds that the implementation provides. If the uncertainty is large, Spanner slows down to wait out that uncertainty. Google’s cluster-management software provides an implementation of the TrueTime API. This implementation keeps uncertainty small (generally less than 10ms) by using multiple modern clock references (GPS and atomic clocks)." Basically, there is some tradeoff between clock synchronization perfection and transaction processing speed that can be made. You can build dedicated hardware that's clocked by a GPSDO and provide an API to get hardware timestamps, and maybe process transactions a little faster. Your good old C++ program running on Linux with an internal oscillator adjusted by NTP with a GPS PPS input still beats communicating between datacenters to agree on event ordering, though. Light is slow!
- pookah 4y ago
  When a system overheats the CPU can speed up and the clocks drift and if you're producing volumes of events you will get corruption. Wouldn't ever use a system clock... You can write a hybrid logical clock in about forty lines of code that can scale as much as these wildly expensive appliances that these big tech companies shill.
- lanstin 4y ago
  This is why reading the original Lamport paper is useful. This distributed nature of things isn’t due to bad clocks or software or anything. It is an irreducible part of the physics of our world, with relativity. Perfect clocks won’t help with space like separations and different velocities or gravitational force. You have to build communication into it. The causality relationship is inherently a partial order.
  - cleansingfire 4y ago
    Original Lamport paper here https://lamport.azurewebsites.net/pubs/time-clocks.pdf https://lamport.azurewebsites.net/pubs/time-clocks.pdf
    - lanstin 4y ago
      thanks. this is a profoundly useful paper to help one being able to think about distributed systems.
  - libraryofbabel 4y ago
    This isn’t really true: it’s not got anything to do with relatively specifically, it’s just because of the finite and varying time for messages to travel between points in a distributed system. So it’s about physics but not about relativistic physics. A Newtonian universe with finite speed of light would have the same phenomenon. That said, the analogy with causality in relativity and light cones etc is useful, and it’s no coincidence that Lamport wrote a book on general relativity before he turned to distributed systems.
    - magicalhippo 4y ago
      > A Newtonian universe with finite speed of light would have the same phenomenon. Isn't the whole point of special relativity that a Newtonian universe with a finite speed of light isn't Newtonian?
      - libraryofbabel 4y ago
- dikei 4y ago
  It really depends on how you define "reliability". If a system never orders events wrong but will immediately stops processing events when enough number of nodes have their clocks out-of-synced, which is the case with all systems using conventional clocks, can it still be considered reliable?
  - lanstin 4y ago
    only if you have a good ops team on 24x7 pager duty
ketzu 4y ago
Huh, this is a really nice writeup of the logical time part of the foundations of distributed systems lecture I used to assist in. I always wondered how much they are actually used in real systems.
- dboreham 4y ago
  I haven't seen basic Lamport Clocks used much but sequence numbers and various kinds of vector clock are widely used in eventually consistent systems (fashionable to call this CRDT nowadays). Edit: perhaps git uses a kind of lamport clock, but with linked lists of hashes not numbers as the values.
  - thoughtlede 4y ago
    Right. The flavors of Lamport clocks I stated in the article are used in CRDTs designs I studied. While CRDTs are eventually consistent, I wouldn't dismiss them as such without qualification. They are causal-consistent when offline and sequential-consistent when online. (This duality is why CRDTs have been hard for me to wrap my head around them).
    - preseinger 4y ago
      the properties of CRDTs are invariant to the concept of "online" or "offline" i think you may be making things harder for yourself by thinking in these terms
      - thoughtlede 4y ago
        Indeed, certain properties of CRDT are invariable to network state. However, it is worth pointing out that in ops-based CRDT “implementations”, you deal with local ops case differently from remote ops case. That is, while the properties are invariant, how you produce them are different. So I was on a my quest to understand the “essence” of CRDTs, not just understand them to be able to practically use them. Atomic broadcast and Raft were easy enough for me to wrap my head around (although quite challenging to implement). But not CRDTs. I found common statements about CRDTs that they ensure ops to be commutative to be superficial. A slightly deeper characteristic was that ops-based CRDTs are just causally-linked ops (aka causal tree). But what about state-based? Finally, when I realized CRDTs are dual-consistent and that’s what makes any data structure a CRDT, that was a moment of epiphany for me.
withinboredom 4y ago
Things like this are interesting for a couple of reasons. Synchronizing clocks in the network and even attaching the current time to packets is supported with the correct hardware (PPS). This is extremely reliable (when ordering is important, not necessarily for keeping time). What makes solutions like this article interesting is that this is at the application level, while there are synchronization problems you can solve at the hardware level when you control the hardware. Since moving things to the cloud, it’s as though we’ve forgotten about these technologies that have been around for over 20 years.
- deleted 4y ago
  [deleted]
vrglvrglvrgl 4y ago
[dead]
noiv 4y ago
Given Einstein proved time is relative and not absolute I wonder at what time resolution all attempts to assume time as an absolute fall apart? The maximum distance of two surface nodes on this planet is about 20_000 km translating to about 67 milli seconds as speed of information. All discussion here assumes 17th century Newton's physics.
- hinkley 4y ago
  Much of the rule of law is based on cause and effect. Most of the people who get hung up on time stamps are trying to reconstruct a chain of events over time. And like a lot of concurrency problems, the solution seems to be to solve a different problem instead. Such as causal chaining. We made an error here because we were aware of three facts but not aware of a fourth. The answer is wrong but the data is consistent. That’s important for finding bugs. It’s also important for establishing intent. If I bonk you with a bat, it might be an accident. If I had just found out you’ve been sleeping with my wife, people should be asking a lot more questions. If I don’t know that, then there’s no causal link between these events.
  - noiv 4y ago
    > Such as causal chaining. Doesn't that imply knowing which of two events happened first? Imagine, after your bat accident I took liberties with your wife as a revenge? Please pardon my 17th century's line of thought :)
    - Rhapso 4y ago
      It really depends on how fast both of you are going relatively to each other and who is asking the questions (and how fast they are going...)
    - hinkley 4y ago
      Which happened first can be in the eye of a third party observer versus a first party. it doesn’t matter which happened first, it matters what the observers saw and whether they can agree. The relativistic example here says that observers will never agree. If an event that I didn’t observe happened first, it didn’t influence my decisions. It might influence yours though, but when things get grey we give benefit of the doubt.
hinkley 4y ago
I’ve been wondering off and on if the end game for borrow checkers is a language that can mode causality in data operations. This withdrawal was predicated on checking records A and B at point X in the timeline and approving it. Meanwhile auto withdrawal happened 20 ms later and that’s why we let him overdraft.
MPSimmons 4y ago
> However, because of clock drifts and/or assumptions around network time delays, timestamps from conventional clocks are not always mutually comparable, and therefore events cannot be reliably ordered using timestamps from conventional clocks. I don't think that this distributed logical clock solution isn't worth working on, but some combination of a low-stratum NTP server combined with PTP is good enough for most people, I would think, but cloud solutions are mixed. - Azure Time Sync uses PTP - https://learn.microsoft.com/en-us/azure/virtual-machines/linux/time-sync https://learn.microsoft.com/en-us/azure/virtual-machines/lin... - AWS time sync uses NTP - https://aws.amazon.com/about-aws/whats-new/2017/11/introducing-the-amazon-time-sync-service/ https://aws.amazon.com/about-aws/whats-new/2017/11/introduci... - Google Cloud also uses NTP - https://developers.google.com/time/faq https://developers.google.com/time/faq
thoughtlede 4y ago
Author here. Pleasantly surprised to see the article here. Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven't seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference. (To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).
- riemannzeta 4y ago
  Curious to know whether, in your opinion, the use of verifiable delay functions and proof of history represents a more reliable and scalable approach to decentralized time-ordering. https://solana.com/news/proof-of-history---a-clock-for-blockchain https://solana.com/news/proof-of-history---a-clock-for-block...
  - lostcolony 4y ago
    Can't speak for op, but can speak as just an observer - probably not. Blockchains are ultimately CP systems, not AP. From that link - "Data can be inserted into the sequence by appending the data to the previous generated state. The state, input data, and count are all published. Appending the input causes all future output to change unpredictably." Meaning there is a single source of truth. That single source is decentralized (because blockchain), but it still requires a quorum to agree to accept a bit of data, and to treat the new state as the valid state. I.e., multiple competing parallel writes must be serialized across a network of computers, which is always more expensive than if they multiple competing parallel writes can be done in parallel. Lamport clocks and etc are AP. It fully expects nodes to make decisions autonomously, and to synchronize after the fact. And data can be lost without realizing it. (The above is all a bit of a simplification, but fundamentally, they're solving different problems)
    - riemannzeta 4y ago
      Yup. Different problem space! Thanks for laying it out clearly.
imoe 4y ago
[flagged]
HyperSane 4y ago
Active Directory is the most wildly used multi-master distributed database in the world and it uses update sequence numbers. An update sequence number (USN) is a 64-bit number in Active Directory that increases as changes occur. Local counters on every domain controller assign USNs. Whenever an object is changed, its USN is incremented. When replication occurs, only the version of the object with the greatest USN is retained. Local counters for USNs are considered reliable because they never decrease or "run backward." USNs are also always unique, making it easier for domain controllers to never use the same USNS at the same time.
- deleted 4y ago
  [deleted]
- preseinger 4y ago
  conflict resolution for concurrent modifications of the same object on different domain controllers are resolved first by local timestamp (unreliable) and then by GUID order (arbitrary) and in both cases mean that it's possible for someone to make a change to an object that is reflected in local reads for a period of time, but then "erased" and forgotten after replication, tl;dr: this approach provides basically no meaningful consistency at all
  - HyperSane 4y ago
    my understanding is that conflict resolution is done by all domain controllers comparing the USN of each object and replicating the object with the highest USN. https://www.techtarget.com/searchwindowsserver/definition/update-sequence-number-USN https://www.techtarget.com/searchwindowsserver/definition/up...
    - preseinger 4y ago
      yes. this is my point. "highest usn" is arbitrary.
      - HyperSane 4y ago
_3u10 4y ago
I find most of this stuff is an attempt to apply a mental model of the universe that is not logically consistent with the way the universe actually works. Basically, what I'm saying is if the universe can live without strict ordering of events as a distributed system, chances are whatever thing you are designing can also live without ordered events. For some reason people always point to financial transactions yet, there's absolutely no ordering to financial transaction events. eg. If I buy something on the weekend usually my statement says I bought it on Monday, and sometimes a day later the transaction might be visible, but might also say it occurred on Monday even though it's Sunday. Instead banks have a better solution, if your bank account goes below zero, they charge you extra money to go extra below zero.

397 points by alexzeitler 4y ago

> However, because of clock drifts and/or assumptions around network time delays, timestamps from conventional clocks are not always mutually comparable, and therefore events cannot be reliably ordered using timestamps from conventional clocks. This isn’t quite right. CockroachDB and Yuggabyte both use conventional clocks to reliably order events. Spanner uses GPS to do so (conventional time stamp but maybe not technically a conventional clock).

amelius 4y ago
I suppose you can always order events by the time it takes for light to (physically or hypothetically) travel to a central server plus the server's local time.
- diarrhea 4y ago
  Network uncertainties like splits and delays will render that impossible.
ketzu 4y ago
Your post made me read this: https://www.cockroachlabs.com/blog/living-without-atomic-clocks/ https://www.cockroachlabs.com/blog/living-without-atomic-clo... on how spanner and cockroadDB do this. And the answes are surprisingly simple, but with consequences attached. * Spanner creates very tight bounds on the clock synchronization (through atomic clocks/GPS) and ... just waits out the length of the bound. * CockroachDB seems to do lamport-clocks-with-real-timestamps for linearizability (track the highest seen timestamp for causality chains). For preventing consistency violations with reads, they also track the bounds on the clock and potentially attempt to read again. So they approve of the overall message (of not just comparing conventional timestamps) but work around those using the uncertainty of the clocks they have available. My professor used to introduce logical clocks with "as we usually can't use atomic clocks on all nodes" because of that.
- hansvm 4y ago
  The "as we usually can't use atomic clocks on all nodes" constraint is more common than you might think. Even code as simple as ts = get_atomic_time_with_no_delay_because_this_node_has_an_atomic_clock(); do_stuff_with_time(ts); is really broken if you have to wait for garbage collection, wait for your process/thread/coroutine/... to be scheduled, wait for a nearly invisible pause as a cache line is refreshed, .... The time you're using the atomic timestamp is at some future moment, and if that delay matters for your algorithm you need to track your uncertainty just like Spanner/Cockroach do (you just get significant benefits because the uncertainty is low).
  - kurthr 4y ago
    If your get_atomic() isn't also capturing or resetting an internal hardware timer atomically it's kinda broken code anyway. It's important to remember that you're getting data from the firmware of an atomic clock (or GPS receiver) and that they will go to great lengths to compensate for latency variations so not doing it in the sampling code would be nuts (or just not using isochronous coms). Then the local clock/timer can be calibrated from the that and you can have near clock-cycle correct timing. Typically they only send out 1 pulse per second so anything finer than that is locally interpolated. We used 1ms internal intervals with an accuracy of ~1ppm. Last time I worked on something like this was 20 years ago, but it was a Pentium box. The clock firmware to converted a 5MHz sinewave output to 1Pps, but could also output a synthetic UTC through LAN in cases where there was no other connectivity. I guess I'm saying this is really specialized code for whatever hardware/OS you're using. (edit) Here's some documentation for a very similar box: https://www.manualslib.com/manual/1281621/Symmetricom-5071a.html?page=27#manual https://www.manualslib.com/manual/1281621/Symmetricom-5071a....
    - jrockway 4y ago
      The GPS clock is really used to provide long-term stability for the computer's internal oscillator, which provides fine short-term stability. Your calls to gettimeofday() are handled by the internal oscillator, not by asking the GPS unit directly. Additionally, NTP daemons are impressive in their ability to get the "right answer" on current internal oscillator frequency as affected by the entire system. With 86400 very accurate data samples per day, you can do a lot! In a distributed system, the absolute value of the time is important, since that's what your transaction timestamps are based on. There is a lot to do to ensure that your time offset from UTC ends up being correct; antenna cable length compensation, oscillator quantization compensation, etc. These are not strictly necessary for Spanner but can make microsecond-level differences which are quite noticeable. "The API directly exposes clock uncertainty, and the guarantees on Spanner’s timestamps depend on the bounds that the implementation provides. If the uncertainty is large, Spanner slows down to wait out that uncertainty. Google’s cluster-management software provides an implementation of the TrueTime API. This implementation keeps uncertainty small (generally less than 10ms) by using multiple modern clock references (GPS and atomic clocks)." Basically, there is some tradeoff between clock synchronization perfection and transaction processing speed that can be made. You can build dedicated hardware that's clocked by a GPSDO and provide an API to get hardware timestamps, and maybe process transactions a little faster. Your good old C++ program running on Linux with an internal oscillator adjusted by NTP with a GPS PPS input still beats communicating between datacenters to agree on event ordering, though. Light is slow!
pookah 4y ago
When a system overheats the CPU can speed up and the clocks drift and if you're producing volumes of events you will get corruption. Wouldn't ever use a system clock... You can write a hybrid logical clock in about forty lines of code that can scale as much as these wildly expensive appliances that these big tech companies shill.
lanstin 4y ago
This is why reading the original Lamport paper is useful. This distributed nature of things isn’t due to bad clocks or software or anything. It is an irreducible part of the physics of our world, with relativity. Perfect clocks won’t help with space like separations and different velocities or gravitational force. You have to build communication into it. The causality relationship is inherently a partial order.
- cleansingfire 4y ago
  Original Lamport paper here https://lamport.azurewebsites.net/pubs/time-clocks.pdf https://lamport.azurewebsites.net/pubs/time-clocks.pdf
  - lanstin 4y ago
    thanks. this is a profoundly useful paper to help one being able to think about distributed systems.
- libraryofbabel 4y ago
  This isn’t really true: it’s not got anything to do with relatively specifically, it’s just because of the finite and varying time for messages to travel between points in a distributed system. So it’s about physics but not about relativistic physics. A Newtonian universe with finite speed of light would have the same phenomenon. That said, the analogy with causality in relativity and light cones etc is useful, and it’s no coincidence that Lamport wrote a book on general relativity before he turned to distributed systems.
  - magicalhippo 4y ago
    > A Newtonian universe with finite speed of light would have the same phenomenon. Isn't the whole point of special relativity that a Newtonian universe with a finite speed of light isn't Newtonian?
    - libraryofbabel 4y ago
dikei 4y ago
It really depends on how you define "reliability". If a system never orders events wrong but will immediately stops processing events when enough number of nodes have their clocks out-of-synced, which is the case with all systems using conventional clocks, can it still be considered reliable?
- lanstin 4y ago
  only if you have a good ops team on 24x7 pager duty

ketzu 4y ago

Huh, this is a really nice writeup of the logical time part of the foundations of distributed systems lecture I used to assist in. I always wondered how much they are actually used in real systems.

dboreham 4y ago
I haven't seen basic Lamport Clocks used much but sequence numbers and various kinds of vector clock are widely used in eventually consistent systems (fashionable to call this CRDT nowadays). Edit: perhaps git uses a kind of lamport clock, but with linked lists of hashes not numbers as the values.
- thoughtlede 4y ago
  Right. The flavors of Lamport clocks I stated in the article are used in CRDTs designs I studied. While CRDTs are eventually consistent, I wouldn't dismiss them as such without qualification. They are causal-consistent when offline and sequential-consistent when online. (This duality is why CRDTs have been hard for me to wrap my head around them).
  - preseinger 4y ago
    the properties of CRDTs are invariant to the concept of "online" or "offline" i think you may be making things harder for yourself by thinking in these terms
    - thoughtlede 4y ago
      Indeed, certain properties of CRDT are invariable to network state. However, it is worth pointing out that in ops-based CRDT “implementations”, you deal with local ops case differently from remote ops case. That is, while the properties are invariant, how you produce them are different. So I was on a my quest to understand the “essence” of CRDTs, not just understand them to be able to practically use them. Atomic broadcast and Raft were easy enough for me to wrap my head around (although quite challenging to implement). But not CRDTs. I found common statements about CRDTs that they ensure ops to be commutative to be superficial. A slightly deeper characteristic was that ops-based CRDTs are just causally-linked ops (aka causal tree). But what about state-based? Finally, when I realized CRDTs are dual-consistent and that’s what makes any data structure a CRDT, that was a moment of epiphany for me.

withinboredom 4y ago

Things like this are interesting for a couple of reasons. Synchronizing clocks in the network and even attaching the current time to packets is supported with the correct hardware (PPS). This is extremely reliable (when ordering is important, not necessarily for keeping time). What makes solutions like this article interesting is that this is at the application level, while there are synchronization problems you can solve at the hardware level when you control the hardware. Since moving things to the cloud, it’s as though we’ve forgotten about these technologies that have been around for over 20 years.

deleted 4y ago
[deleted]

vrglvrglvrgl 4y ago

[dead]

noiv 4y ago

Given Einstein proved time is relative and not absolute I wonder at what time resolution all attempts to assume time as an absolute fall apart? The maximum distance of two surface nodes on this planet is about 20_000 km translating to about 67 milli seconds as speed of information. All discussion here assumes 17th century Newton's physics.

hinkley 4y ago
Much of the rule of law is based on cause and effect. Most of the people who get hung up on time stamps are trying to reconstruct a chain of events over time. And like a lot of concurrency problems, the solution seems to be to solve a different problem instead. Such as causal chaining. We made an error here because we were aware of three facts but not aware of a fourth. The answer is wrong but the data is consistent. That’s important for finding bugs. It’s also important for establishing intent. If I bonk you with a bat, it might be an accident. If I had just found out you’ve been sleeping with my wife, people should be asking a lot more questions. If I don’t know that, then there’s no causal link between these events.
- noiv 4y ago
  > Such as causal chaining. Doesn't that imply knowing which of two events happened first? Imagine, after your bat accident I took liberties with your wife as a revenge? Please pardon my 17th century's line of thought :)
  - Rhapso 4y ago
    It really depends on how fast both of you are going relatively to each other and who is asking the questions (and how fast they are going...)
  - hinkley 4y ago
    Which happened first can be in the eye of a third party observer versus a first party. it doesn’t matter which happened first, it matters what the observers saw and whether they can agree. The relativistic example here says that observers will never agree. If an event that I didn’t observe happened first, it didn’t influence my decisions. It might influence yours though, but when things get grey we give benefit of the doubt.

hinkley 4y ago

I’ve been wondering off and on if the end game for borrow checkers is a language that can mode causality in data operations. This withdrawal was predicated on checking records A and B at point X in the timeline and approving it. Meanwhile auto withdrawal happened 20 ms later and that’s why we let him overdraft.

MPSimmons 4y ago

> However, because of clock drifts and/or assumptions around network time delays, timestamps from conventional clocks are not always mutually comparable, and therefore events cannot be reliably ordered using timestamps from conventional clocks. I don't think that this distributed logical clock solution isn't worth working on, but some combination of a low-stratum NTP server combined with PTP is good enough for most people, I would think, but cloud solutions are mixed. - Azure Time Sync uses PTP - https://learn.microsoft.com/en-us/azure/virtual-machines/linux/time-sync https://learn.microsoft.com/en-us/azure/virtual-machines/lin... - AWS time sync uses NTP - https://aws.amazon.com/about-aws/whats-new/2017/11/introducing-the-amazon-time-sync-service/ https://aws.amazon.com/about-aws/whats-new/2017/11/introduci... - Google Cloud also uses NTP - https://developers.google.com/time/faq https://developers.google.com/time/faq

thoughtlede 4y ago

Author here. Pleasantly surprised to see the article here. Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven't seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference. (To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).

riemannzeta 4y ago
Curious to know whether, in your opinion, the use of verifiable delay functions and proof of history represents a more reliable and scalable approach to decentralized time-ordering. https://solana.com/news/proof-of-history---a-clock-for-blockchain https://solana.com/news/proof-of-history---a-clock-for-block...
- lostcolony 4y ago
  Can't speak for op, but can speak as just an observer - probably not. Blockchains are ultimately CP systems, not AP. From that link - "Data can be inserted into the sequence by appending the data to the previous generated state. The state, input data, and count are all published. Appending the input causes all future output to change unpredictably." Meaning there is a single source of truth. That single source is decentralized (because blockchain), but it still requires a quorum to agree to accept a bit of data, and to treat the new state as the valid state. I.e., multiple competing parallel writes must be serialized across a network of computers, which is always more expensive than if they multiple competing parallel writes can be done in parallel. Lamport clocks and etc are AP. It fully expects nodes to make decisions autonomously, and to synchronize after the fact. And data can be lost without realizing it. (The above is all a bit of a simplification, but fundamentally, they're solving different problems)
  - riemannzeta 4y ago
    Yup. Different problem space! Thanks for laying it out clearly.

imoe 4y ago

[flagged]

HyperSane 4y ago

Active Directory is the most wildly used multi-master distributed database in the world and it uses update sequence numbers. An update sequence number (USN) is a 64-bit number in Active Directory that increases as changes occur. Local counters on every domain controller assign USNs. Whenever an object is changed, its USN is incremented. When replication occurs, only the version of the object with the greatest USN is retained. Local counters for USNs are considered reliable because they never decrease or "run backward." USNs are also always unique, making it easier for domain controllers to never use the same USNS at the same time.

deleted 4y ago
[deleted]
preseinger 4y ago
conflict resolution for concurrent modifications of the same object on different domain controllers are resolved first by local timestamp (unreliable) and then by GUID order (arbitrary) and in both cases mean that it's possible for someone to make a change to an object that is reflected in local reads for a period of time, but then "erased" and forgotten after replication, tl;dr: this approach provides basically no meaningful consistency at all
- HyperSane 4y ago
  my understanding is that conflict resolution is done by all domain controllers comparing the USN of each object and replicating the object with the highest USN. https://www.techtarget.com/searchwindowsserver/definition/update-sequence-number-USN https://www.techtarget.com/searchwindowsserver/definition/up...
  - preseinger 4y ago
    yes. this is my point. "highest usn" is arbitrary.
    - HyperSane 4y ago

_3u10 4y ago

I find most of this stuff is an attempt to apply a mental model of the universe that is not logically consistent with the way the universe actually works. Basically, what I'm saying is if the universe can live without strict ordering of events as a distributed system, chances are whatever thing you are designing can also live without ordered events. For some reason people always point to financial transactions yet, there's absolutely no ordering to financial transaction events. eg. If I buy something on the weekend usually my statement says I bought it on Monday, and sometimes a day later the transaction might be visible, but might also say it occurred on Monday even though it's Sunday. Instead banks have a better solution, if your bank account goes below zero, they charge you extra money to go extra below zero.