13 ms·

Google and Nasdaq Pursuing Nano-Second Precision in Network Time Protocol

236 points by Osiris30 8y ago

wpowiertowski 8y ago
Why not just switch to PTP (IEEE 1588)?
downer68 8y ago
An interesting side-effect of this, is that it would enable a standard of synchronization, across geographic regions, such that one could treat a set of virtual machines as one ultra-wide-bus CPU with a 1 GHz clock speed. All of the local overhead of real system resouces and network synchronization could handled by the remainder of the real CPU clock available to the bare metal, but contribute to the computation of a segment of a virtual bit field, at speed. So, now maybe we get a commodity 4096 bit 1 GHz CPU as a service. Which, is maybe comparable to a 64 core processor, but without the overhead of chunking down to the width of 64 bits.
- dagenix 8y ago
  Are you saying that 64 bit CPU + 64 bit CPU = 128 bit CPU (as long as they are time synced)? 1. It doesn't work this way 2. Why would you want a 4096 bit CPU?
  - tonysdg 8y ago
    For financial transactions, it would certainly allow for fast high-precision floating point math. Imagine IEEE 754 4096-bit floats. Not sure anyone would actually use this, and you'd still have to standardize the rounding precision, but it might be an interesting vein of research. Still, I agree with you -- what the OP described is not a 4096-bit processor. Now highly-synchronized VMs -- that's an entirely different matter. Probably a boatload of use cases for those.
    - lallysingh 8y ago
      Where's that useful? Options pricing? I have no idea.
    - fjsolwmv 8y ago
      Why would you use floating point math for finance?
      - WellOver9000 8y ago
        The alpha calculation can (and should) use floating point math. If the market has a midpoint of $99.99 with a bid/ask of $99.98/$100.00, you could compute a bunch of signals and end up with an alpha-adjusted midpoint of $100.00383736383..., at which point you’d convert it back to fixed-point and then try to buy $100.00
      - danbruc 8y ago
        A floating point representation is not really the issue, the issue is not using base 10, and IEEE 754 specifies base 2 and base 10 floating point formats and operations. But I am of course not sure whether the original comment referred to base 2 or base 10 and given how common the mistake of using base 2 floating point numbers for financial calculations is, you may be correct with the intention of your comment.
        tonysdg 8y ago
        I'm aware of the fact that you don't use floating point math for finance -- for exactly the reason you described -- but the academic in me wonders if you could formally specify a high-enough degree of precision -- and all the corner cases -- to allow FP math for even just a subset of transactions. This would (in theory) allow to programmers to bypass the Decimal classes in your favorite OO language (or GMP if you're a C fan). Again, purely an academic inquiry :-)
        danbruc 8y ago
        My point was more that it is wrong to say that financial calculations should not be done using floating point formats, for example Decimal in .NET and BigDecimal in Java are floating point formats and they are the types you should use for financial calculations. The important difference as compared to formats like IEEE 754 binary32 (formerly single) and binary64 (formerly double) is that the representation is based on base 10 instead of base 2. Fixed point or floating point and base 2 or base 10 are two orthogonal choices. So when you initially mentioned high precision floating point numbers for financial calculations that was not necessarily a bad idea because you might have thought about base 10 floating point numbers. The comment I replied to however assumed you meant base 2 which of course most people do if they say floating point numbers without specifying the base and which of course is a bad idea for financial calculations more often than not. I just pointed out that assuming base 2 is usually but not technically correct. And you can of course use base 2 floating point numbers for financial calculations - 32 bit, 64 bit, or 4096 bit - you just have to keep track of the accumulated errors and stop or correct the result before the error grows into the digits you are interested in. But why would one want to do this? The only thing I can really think of is that you need maximum performance and there is no hardware support for base 10 floating point numbers. And just using integers as base 10 fixed point numbers, which would often be a even better solution, must not be an option.
  - downer68 8y ago
    I don't know how you found your way onto the addition operator (+) on your keyboard, because that's not at all what I was driving at. I think you are... JUMPING! TO CONCLUSIONS! (get it?) Anyway, at it's core, much of the logic within a turing machine winds up being addition in an accumulator. So, you widen the pipeline, and that adds place settings to the numeric values addressed at a location in RAM. I think we both know that each place setting increases the maximum valus of the addressible unit by an exponential factor of the base, which in computing, and so in this instance, is binary. Specifically: 2^4096 instead of 2^64 Golly, did I get my math right? This sure is difficult to for me to understand! Why would anyone want a 4096 bit CPU? Oh, I dunno. I suppose 640K ought to be enough for anyone.
    - downer68 8y ago
      Good job, guys! Nice downvotes! Real nice! I answered substantively, addressing each point carefully, and I was pleasantly rewarded for the time I took to respond. Great incentive system you guys have worked out! Glad to see it being used as intended! Works like a charm!
      - grzm 8y ago
        You were likely down-voted for the snark with which you addressed the points.
    - dagenix 8y ago
      I'm having a hard time trying to figure out if you are serious or if you are masterfully trolling everyone.
- ComputerGuru 8y ago
  I don’t think you understand how memory bus width is calcuslated or what it means. You are an order of magnitude off on the layer in question.
  - downer68 8y ago
    An order of magnitude. Jeepers, that sounds really bad.
- Forge36 8y ago
  How would the math work on that? Simple addition now requires coordination of results across many CPUs. Worst case is N-1 ticks where N is the CPU count. What operation would get faster by such a virtual CPU?
  - downer68 8y ago
    Economy of scale, my dude. An organization seeking to market a product based on any spare slack or wastage of their bare metal could stitch together a niche product like this from enough resources, and price it in the space where it nets them money, and is cheaper than something an individual or small business might be capable of building on their own, with the cheapest possible parts. That's basically the the core principle of every cloud product being sold.
- simias 8y ago
  Suppose you do a simple addition on your 4096bit "CPU", you have to propagate the carry from the first 64bits to the next 64. How do you do that within your clock cycle over the internet? You'd have to pipeline them so that each subsequent 64bit add waits for the previous carry, but then wouldn't it be orders of magnitude faster to just do it on the same CPU rather than taking the time and resources to do a single 64bit add followed by a high latency network transfer? At any rate what does clock synchronization buy you here exactly, data transfer are still high-latency and high-jitter, at best you're isochronous but definitely not synchronous. Either I completely misunderstand what you're proposing or it doesn't make sense at all.
  - twoodfin 8y ago
    I’m not quite sure what GP is getting at, either, but I can sort of see the lockstep synchronization described letting you build something like the original Thinking Machines Connection Machine out of more distributed parts. The original Cray supercomputers also benefitted from a design where every wire in the pipeline was the same length for “free” synchronization courtesy of the speed of light.
- chaboud 8y ago
  "...across geographic regions, such that one could treat a set of virtual machines as one ultra-wide-bus CPU with a 1 GHz clock speed." I'm not entirely sure what you're trying to say here, but I am entirely sure that it's wrong. A precise clock isn't the same thing as the removal of latency, and the operations of a CPU are ordered. That is, I can't start working on the multiplication of A * (B + C) until the addition result is available. Furthermore, if the elements of the operation, B and C, or parts of those elements, were separated by miles (or even feet), the latency of that operation would increase by orders of magnitude. I doubt that even a 1MHz distributed processor would be achievable as a large distributed bit field computer as you've laid out here. If you're worried about overhead in computing, it is critical to remember that a foot is a nanosecond. I'd much rather break my data down to register size (and I often do) than ship my data over a wire or fiber (which I also often do).
  - downer68 8y ago
    Actually, if you marshall all of your addressible units up front (4096 bit sentences, instead of 64 bit words), which aligns well with raw allocation units on many file systems, as an end user of the service, the overhead (to you) is reduced to network I/O if the product is built correctly. The only hard part requiring serialized synchronization is the carry bit, across compute nodes. Share the carry bits between nodes, and while relaying a sentence to a cluster of synchronized nodes, the pipeline can shoot the sentence into the cluster as a unit, proxy and chain together the carry bits with a coordinated execution plan, and on the other side of the pipe, you get your well-timed 4096 bit result, all at 1 GHz, because the service is designed and produced to handle input at nanosecond intervals. What are the advantages? Predictability, and expanded throughput. Now you can look at an entire passage of text and make a determination about it in less time. Or stack many passages and composite them to assess or intuit variation. Designing the product this way makes it easy to reason about, and thus easier to market and sell. Is it possible to make a profitable system that works like this? Gee, great question! There's no obvious answer. But anyway, from the perspective of a subscriber, it's on them to marshall their data, and then, if they have operations for which the scale of 4096 bit chunks improves results, they can get their granular operations done at 1 GHz, which allows them to predict time spent and overall cost more easily. (e.g. I have all these [less-than-but-up-to] 4096 bit toots marshalled in a single data store, from a shit ton mastodon instances (i did all the crawling and retrieving, and saved them in one place, as a standardized data set), and I think this fact might be true about some of them, here is the rule set to interpret, please give me back the members of the toot array that return true when the function of this rule set returns true) BTW, don't get hung up on 4096 as "the best number" I just chose it because it's a nice square number.
bcaa7f3a8bbc 8y ago
It is great news if this algorithm can work directly on the public Internet, without requiring a specialized network - many scientific and engineering applications will be able to get its time reference directly from the Internet! NTP and other protocols currently used are unauthenticated (there is NTP autokey, etc, but its security properties are not ideal, and mostly not deployed) and it is a big security hole, especially more and more cryptographic programs are being putting online, since this protocol is meant for financial applications, hopefully the security issues can also be solved by using digital signature. I guess it's a rare scenario which the finance industry makes a _direct_ contribution to technology.
- makomk 8y ago
  If I'm understanding the Huygens paper linked in one of the other comments correctly, this is strictly in-datacenter only; it relies on properties of datacenter networking that don't apply to the broader internet, in particular that routes are mostly symmetric and mostly low-latency.
  - bcaa7f3a8bbc 8y ago
    Oops.
  - davrosthedalek 8y ago
    Haven't read the paper yet, but even it is data-center only, it is still very relevant for science, e.g. DAQ in nuclear physics, especially if it doesn't need custom hardware.
- simias 8y ago
  I can't imagine how you could hope to reach nanosecond-precision over the internet without changing all the routing hardware in use today. With PTP you can already reach sub-microsecond synchronization but you need full hardware support for every network element on the route if you want to achieve that. The timestamping is done on the network PHY itself, which is how you can remove all jitter introduced by the kernel stack. Anything receiving and re-transmitting the packet along the way must update the timestamps to account for the processing delay. Huygens is a little more clever and uses a statistical approach to sample multiple clocks and correlate them (if I understand correctly) however it still seems designed to work within a datacenter, I assume that over the internet the signal-to-noise ratio for measurements would worsen very significantly and lower the precision dramatically. It could well still outperform NTP however.
geofft 8y ago
This looks like a paper about the Huygens system, with comparison to other protocols like PTP: https://www.usenix.org/system/files/conference/nsdi18/nsdi18-geng.pdf https://www.usenix.org/system/files/conference/nsdi18/nsdi18... Also these slides: https://platformlab.stanford.edu/Seminar%20Talks/retreat-2017/Yilong%20Geng.pdf https://platformlab.stanford.edu/Seminar%20Talks/retreat-201...
- mlichvar 8y ago
  I maintain an NTP implementation. That comparison doesn't seem fair to me. It looks like they are comparing the old reference NTP implementation and not really the protocol itself. An NTP implementation can certainly synchronize clocks with better accuracy than 1 millisecond, or even 1 microsecond with hardware timestamping and good network switches. There are some interesting ideas in the Huygens paper, but I don't see anything that couldn't be done also with NTP.
  - geofft 8y ago
    The other thing I don't understand is that this paper argues against hardware timestamping on the grounds that users won't want to buy expensive hardware, and that Huygens is for "standard hardware ... in current data centers". Expensive, niche hardware is normal for the HFT folks that care about nanosecond precision.
    - justicezyx 8y ago
      The paper did not have hft as its primary use case, but you cannot contain reporters tendency to cherry pick eye catching aspects.
      - acqq 8y ago
        Yes, it seems that the designers tried to make something that would work in the current Google data centers. Which is not surprising as some of the authors work at Google. I'd more want to know: why does Google need even better synchronization of time stamps than what they have now?
amelius 8y ago
How would you use that nano-second precision on a CPU/OS that supports at most microsecond precision?
- dirkgently 8y ago
  Only if the article mentioned it! Oh wait, it did! https://www.usenix.org/conference/nsdi18/presentation/geng https://www.usenix.org/conference/nsdi18/presentation/geng
  - geofft 8y ago
    I don't think the article answers amelius's question, which is not about how you would achieve that precision but how you would use it. On an OS that only supports recording timestamps up to microsecond accuracy, what is the point of synchronizing your clocks within nanoseconds of each other, even if you could?
    - egwor 8y ago
      On linux you can get nanosecond timestamps, and so could record them. This could be useful for capturing certain events. Is that what is meant? IIRC Windows XP didn't support resolving timestamps smaller than 8ms but we've moved beyond this.
chaboud 8y ago
"So-called high frequency trading firms place trades in a fraction of a second, sometimes in a bet that they can move faster than bigger competitors." First off: no. Big money plays in high frequency trading (roughly half of all trading activity), and the smaller traders without instantaneous access are the losers in this game. Secondly, NASDAQ's obsession with precise global sequencing is A) misguided and B) effectively impossible to do right 100% of the time. Given this, I would argue that the appropriate thing to do is change the market requirements. And I'd argue that like this: 1) Temporally quantize the market. Orders come in on an open temporal window that is sufficiently long to account for global latency of non-pathological communication (sorry, tor users) and a bit of computation time. Everyone gets to swim in the same pool. Maybe one second, maybe more. Nobody gets to see the order book until it's resolved. Write-only. 2) Lock the book and fulfill orders from the set of satisfiable orders. If there just contention for a trade (there will always be some), fulfill the contentious trades randomly using random zeedig generated from a pre-announced salt and a hash of some or all of the order book for the window. 3) Return the results and the hashes of the order book, next salt, etc, for verifiability and prep. 4) Re-open the order window. High frequency traders would hate this, because they wouldn't be able to pounce on quick movements, even without fronting slower traders. It would, naturally, increase latency for trades by virtue of having to wait for market resolution. However, mere sequencing doesn't solve the problem of having to resolve and confirm trades (the speed of light is so cruel), so I'm left utterly unsold on the market-efficiency benefit of ultra-high order resolution. Wealthy high frequency traders want to use time to buy an advantage, and the liquidity support they provide to the markets is dubious, at best, since they pull the plug as soon as things get crazy. Quantize the markets.
- qeternity 8y ago
  Most HFT shops are relatively small. HFT is all about latency and turn over. Big quant shops might have HFT elements but lean far more towards systematic/algo strategies that can be relatively high latency (still super low latency, but not HFT) because these are the only strategies that you can deploy serious var with. The guys crushing HFT are not huge hedge funds, and they are solving more engineering problems than building trading models. Also, no, small traders don't lose. Retail traders et al get much tighter spreads, cheaper execution by routing to internalizers, etc. It's big institutionals with size to trade that get front run and have to worry about HFT killing their shortfall. On the institutional side, it's about lit venues preferring HFT w/ special orders types and thin top of book. On the retail side, the issue mostly comes down to direct feed vs. SIP/CQS thanks to NBBO that opened the door for latency arb courtesy of yet more regulation. Blame your regulators folks. This is why dark pools became a thing. > and the liquidity support they provide to the markets is dubious, at best, since they pull the plug as soon as things get crazy This bit is certainly true. Source: hedge fund trader who hates HFT not in principal but because they are good at what they do
viburnum 8y ago
This is a huge waste of effort. HFT should be banned so smart people work on solving real problems instead.
- JumpCrisscross 8y ago
  > so smart people work on solving real problems instead Like making people click on ads?
- throwaway37585 8y ago
  > HFT should be banned What do you mean by this?
SEJeff 8y ago
IEEE 1588 v2 + rubidium decay grandmaster time sources do this quite nicely. Source: have worked as a software / Linux monkey for two of the biggest US HFT firms the past 10 years.
ShiftAce 8y ago
This is a bad move on their part. They should be pursuing Nano-First precision. Duh.
NelsonMinar 8y ago
HFT aside, this also has interesting applications in distributed databases. Spanner, for instance, has consistency guarantees directly related to how synchronized the clocks are (keyword: TrueTime). It seems plausible that Huygens could make a significant improvement on performance of this kind of distributed database. This looks like a very impressive result. NTP has been doing its thing well for years but a factor of 100 improvement on time accuracy would be amazing,
partycoder 8y ago
I think this is no longer about NTP but all the stack below it including hardware.
drumttocs8 8y ago
Confusing title. Perhaps better to say "successor to Network Time Protocol", which, like IRIG or PTP, is a pretty common timekeeping protocol.
amenod 8y ago
From [0]: > In this paper, we present HUYGENS, a software clock synchronization system that uses a synchronization network and leverages three key ideas. First, coded probes identify and reject impure probe data—data captured by probes which suffer queuing delays, random jitter, and NIC timestamp noise. Next, HUYGENS processes the purified data with Support Vector Machines, a widely-used and powerful classifier, to accurately estimate one-way propagation times and achieve clock synchronization to within 100 nanoseconds. Finally, HUYGENS exploits a natural network effect—the idea that a group of pair-wise synchronized clocks must be transitively synchronized— to detect and correct synchronization errors even further. Not an expert, but this seems quite a complex system. Since HF traders have huge incentive to game the system, my fear is that the next headline about Huygens will be about a new exploit found in the wild. [0] https://www.usenix.org/conference/nsdi18/presentation/geng https://www.usenix.org/conference/nsdi18/presentation/geng
jrockway 8y ago
This technology will also be excellent for games. Right now, the server has to decide how it's going to break ties, and that results in confusing moments. For example, Overwatch favors the shooter, so you might see someone in a position to shoot you, use a defensive ability, and die even though you used it, because the server decides that if two events are close in time, the shooter wins. With a trusted time reference, you can actually order events from the perspective of the client instead of the server; so if you actually used that defensive ability before the shooter clicked the mouse, you don't die. I actually think NTP might be good enough for this (despite what people say their reaction times are, milliseconds don't actually matter), but I guess game developers don't think of games as globally-distributed transaction processing systems (which is what they are, just a lot more write conflicts to resolve than your average database), and haven't experimented with ideas that are still only a few years old in that field. (The game industry also doesn't reward experimentation. If you're Google and you try to replace Bigtable with Spanner and it fails, it doesn't matter, you just keep using Bigtable. If you're a game company and your netcode is janky, you launch late, a competitor releases a similar game before you, and all the money you spent on development is gone.) With games there is always the trust issue; can someone write a client that lies about the time they took an action? The answer is yes. But if we have technology that relies on similar client trust working in high-frequency trading, it should be safe enough for games. The stakes are a lot lower in a computer game than the financial markets. So I think good things are on their way.
- throwaway2048 8y ago
  You still cant trust the client here, no matter how precisely synced your clocks are, because it could maliciously reorder events/tamper with time (always claim you activated first, with a certain fudge factor to prevent detection) and it would be undetectable within the bounds of internet latency.
  - jrockway 8y ago
    I'm not completely convinced that cheating would not be detectable after aggregating some statistics over time. (Similar to how you can extract encryption keys from server processes, simply by timing how long certain operations take.)
red75prime 8y ago
It's interesting, that time synchronization in a rotating reference frame is path dependent ([0], for example). [0] https://tycho.usno.navy.mil/ptti/1974papers/Vol%2006_26.pdf https://tycho.usno.navy.mil/ptti/1974papers/Vol%2006_26.pdf
jfoutz 8y ago
I wonder if the next wave of hft will be a geostationary space station over New York, to get the extra occasional nanosecond.
- chaboud 8y ago
  Uh, I know it's a joke, but isn't geostationary orbit almost 36K km over the equator? The round trip time to NYC would be over a quarter of a second... Hence, drones. With lasers... Laser drones...
aswanson 8y ago
Seems sad so much technical effort to be exerted towards something so venal, trivial, and fleeting.
- txdv 8y ago
  If there is money in it, it will get solved!
cordite 8y ago
What value does this add to the world?

236 points by Osiris30 8y ago

Why not just switch to PTP (IEEE 1588)?

An interesting side-effect of this, is that it would enable a standard of synchronization, across geographic regions, such that one could treat a set of virtual machines as one ultra-wide-bus CPU with a 1 GHz clock speed. All of the local overhead of real system resouces and network synchronization could handled by the remainder of the real CPU clock available to the bare metal, but contribute to the computation of a segment of a virtual bit field, at speed. So, now maybe we get a commodity 4096 bit 1 GHz CPU as a service. Which, is maybe comparable to a 64 core processor, but without the overhead of chunking down to the width of 64 bits.

dagenix 8y ago
Are you saying that 64 bit CPU + 64 bit CPU = 128 bit CPU (as long as they are time synced)? 1. It doesn't work this way 2. Why would you want a 4096 bit CPU?
- tonysdg 8y ago
  For financial transactions, it would certainly allow for fast high-precision floating point math. Imagine IEEE 754 4096-bit floats. Not sure anyone would actually use this, and you'd still have to standardize the rounding precision, but it might be an interesting vein of research. Still, I agree with you -- what the OP described is not a 4096-bit processor. Now highly-synchronized VMs -- that's an entirely different matter. Probably a boatload of use cases for those.
  - lallysingh 8y ago
    Where's that useful? Options pricing? I have no idea.
  - fjsolwmv 8y ago
    Why would you use floating point math for finance?
    - WellOver9000 8y ago
      The alpha calculation can (and should) use floating point math. If the market has a midpoint of $99.99 with a bid/ask of $99.98/$100.00, you could compute a bunch of signals and end up with an alpha-adjusted midpoint of $100.00383736383..., at which point you’d convert it back to fixed-point and then try to buy $100.00
    - danbruc 8y ago
      A floating point representation is not really the issue, the issue is not using base 10, and IEEE 754 specifies base 2 and base 10 floating point formats and operations. But I am of course not sure whether the original comment referred to base 2 or base 10 and given how common the mistake of using base 2 floating point numbers for financial calculations is, you may be correct with the intention of your comment.
      - tonysdg 8y ago
        I'm aware of the fact that you don't use floating point math for finance -- for exactly the reason you described -- but the academic in me wonders if you could formally specify a high-enough degree of precision -- and all the corner cases -- to allow FP math for even just a subset of transactions. This would (in theory) allow to programmers to bypass the Decimal classes in your favorite OO language (or GMP if you're a C fan). Again, purely an academic inquiry :-)
        danbruc 8y ago
        My point was more that it is wrong to say that financial calculations should not be done using floating point formats, for example Decimal in .NET and BigDecimal in Java are floating point formats and they are the types you should use for financial calculations. The important difference as compared to formats like IEEE 754 binary32 (formerly single) and binary64 (formerly double) is that the representation is based on base 10 instead of base 2. Fixed point or floating point and base 2 or base 10 are two orthogonal choices. So when you initially mentioned high precision floating point numbers for financial calculations that was not necessarily a bad idea because you might have thought about base 10 floating point numbers. The comment I replied to however assumed you meant base 2 which of course most people do if they say floating point numbers without specifying the base and which of course is a bad idea for financial calculations more often than not. I just pointed out that assuming base 2 is usually but not technically correct. And you can of course use base 2 floating point numbers for financial calculations - 32 bit, 64 bit, or 4096 bit - you just have to keep track of the accumulated errors and stop or correct the result before the error grows into the digits you are interested in. But why would one want to do this? The only thing I can really think of is that you need maximum performance and there is no hardware support for base 10 floating point numbers. And just using integers as base 10 fixed point numbers, which would often be a even better solution, must not be an option.
- downer68 8y ago
  I don't know how you found your way onto the addition operator (+) on your keyboard, because that's not at all what I was driving at. I think you are... JUMPING! TO CONCLUSIONS! (get it?) Anyway, at it's core, much of the logic within a turing machine winds up being addition in an accumulator. So, you widen the pipeline, and that adds place settings to the numeric values addressed at a location in RAM. I think we both know that each place setting increases the maximum valus of the addressible unit by an exponential factor of the base, which in computing, and so in this instance, is binary. Specifically: 2^4096 instead of 2^64 Golly, did I get my math right? This sure is difficult to for me to understand! Why would anyone want a 4096 bit CPU? Oh, I dunno. I suppose 640K ought to be enough for anyone.
  - downer68 8y ago
    Good job, guys! Nice downvotes! Real nice! I answered substantively, addressing each point carefully, and I was pleasantly rewarded for the time I took to respond. Great incentive system you guys have worked out! Glad to see it being used as intended! Works like a charm!
    - grzm 8y ago
      You were likely down-voted for the snark with which you addressed the points.
  - dagenix 8y ago
    I'm having a hard time trying to figure out if you are serious or if you are masterfully trolling everyone.
ComputerGuru 8y ago
I don’t think you understand how memory bus width is calcuslated or what it means. You are an order of magnitude off on the layer in question.
- downer68 8y ago
  An order of magnitude. Jeepers, that sounds really bad.
Forge36 8y ago
How would the math work on that? Simple addition now requires coordination of results across many CPUs. Worst case is N-1 ticks where N is the CPU count. What operation would get faster by such a virtual CPU?
- downer68 8y ago
  Economy of scale, my dude. An organization seeking to market a product based on any spare slack or wastage of their bare metal could stitch together a niche product like this from enough resources, and price it in the space where it nets them money, and is cheaper than something an individual or small business might be capable of building on their own, with the cheapest possible parts. That's basically the the core principle of every cloud product being sold.
simias 8y ago
Suppose you do a simple addition on your 4096bit "CPU", you have to propagate the carry from the first 64bits to the next 64. How do you do that within your clock cycle over the internet? You'd have to pipeline them so that each subsequent 64bit add waits for the previous carry, but then wouldn't it be orders of magnitude faster to just do it on the same CPU rather than taking the time and resources to do a single 64bit add followed by a high latency network transfer? At any rate what does clock synchronization buy you here exactly, data transfer are still high-latency and high-jitter, at best you're isochronous but definitely not synchronous. Either I completely misunderstand what you're proposing or it doesn't make sense at all.
- twoodfin 8y ago
  I’m not quite sure what GP is getting at, either, but I can sort of see the lockstep synchronization described letting you build something like the original Thinking Machines Connection Machine out of more distributed parts. The original Cray supercomputers also benefitted from a design where every wire in the pipeline was the same length for “free” synchronization courtesy of the speed of light.
chaboud 8y ago
"...across geographic regions, such that one could treat a set of virtual machines as one ultra-wide-bus CPU with a 1 GHz clock speed." I'm not entirely sure what you're trying to say here, but I am entirely sure that it's wrong. A precise clock isn't the same thing as the removal of latency, and the operations of a CPU are ordered. That is, I can't start working on the multiplication of A * (B + C) until the addition result is available. Furthermore, if the elements of the operation, B and C, or parts of those elements, were separated by miles (or even feet), the latency of that operation would increase by orders of magnitude. I doubt that even a 1MHz distributed processor would be achievable as a large distributed bit field computer as you've laid out here. If you're worried about overhead in computing, it is critical to remember that a foot is a nanosecond. I'd much rather break my data down to register size (and I often do) than ship my data over a wire or fiber (which I also often do).
- downer68 8y ago
  Actually, if you marshall all of your addressible units up front (4096 bit sentences, instead of 64 bit words), which aligns well with raw allocation units on many file systems, as an end user of the service, the overhead (to you) is reduced to network I/O if the product is built correctly. The only hard part requiring serialized synchronization is the carry bit, across compute nodes. Share the carry bits between nodes, and while relaying a sentence to a cluster of synchronized nodes, the pipeline can shoot the sentence into the cluster as a unit, proxy and chain together the carry bits with a coordinated execution plan, and on the other side of the pipe, you get your well-timed 4096 bit result, all at 1 GHz, because the service is designed and produced to handle input at nanosecond intervals. What are the advantages? Predictability, and expanded throughput. Now you can look at an entire passage of text and make a determination about it in less time. Or stack many passages and composite them to assess or intuit variation. Designing the product this way makes it easy to reason about, and thus easier to market and sell. Is it possible to make a profitable system that works like this? Gee, great question! There's no obvious answer. But anyway, from the perspective of a subscriber, it's on them to marshall their data, and then, if they have operations for which the scale of 4096 bit chunks improves results, they can get their granular operations done at 1 GHz, which allows them to predict time spent and overall cost more easily. (e.g. I have all these [less-than-but-up-to] 4096 bit toots marshalled in a single data store, from a shit ton mastodon instances (i did all the crawling and retrieving, and saved them in one place, as a standardized data set), and I think this fact might be true about some of them, here is the rule set to interpret, please give me back the members of the toot array that return true when the function of this rule set returns true) BTW, don't get hung up on 4096 as "the best number" I just chose it because it's a nice square number.

bcaa7f3a8bbc 8y ago

It is great news if this algorithm can work directly on the public Internet, without requiring a specialized network - many scientific and engineering applications will be able to get its time reference directly from the Internet! NTP and other protocols currently used are unauthenticated (there is NTP autokey, etc, but its security properties are not ideal, and mostly not deployed) and it is a big security hole, especially more and more cryptographic programs are being putting online, since this protocol is meant for financial applications, hopefully the security issues can also be solved by using digital signature. I guess it's a rare scenario which the finance industry makes a _direct_ contribution to technology.

makomk 8y ago
If I'm understanding the Huygens paper linked in one of the other comments correctly, this is strictly in-datacenter only; it relies on properties of datacenter networking that don't apply to the broader internet, in particular that routes are mostly symmetric and mostly low-latency.
- bcaa7f3a8bbc 8y ago
  Oops.
- davrosthedalek 8y ago
  Haven't read the paper yet, but even it is data-center only, it is still very relevant for science, e.g. DAQ in nuclear physics, especially if it doesn't need custom hardware.
simias 8y ago
I can't imagine how you could hope to reach nanosecond-precision over the internet without changing all the routing hardware in use today. With PTP you can already reach sub-microsecond synchronization but you need full hardware support for every network element on the route if you want to achieve that. The timestamping is done on the network PHY itself, which is how you can remove all jitter introduced by the kernel stack. Anything receiving and re-transmitting the packet along the way must update the timestamps to account for the processing delay. Huygens is a little more clever and uses a statistical approach to sample multiple clocks and correlate them (if I understand correctly) however it still seems designed to work within a datacenter, I assume that over the internet the signal-to-noise ratio for measurements would worsen very significantly and lower the precision dramatically. It could well still outperform NTP however.

geofft 8y ago

This looks like a paper about the Huygens system, with comparison to other protocols like PTP: https://www.usenix.org/system/files/conference/nsdi18/nsdi18-geng.pdf https://www.usenix.org/system/files/conference/nsdi18/nsdi18... Also these slides: https://platformlab.stanford.edu/Seminar%20Talks/retreat-2017/Yilong%20Geng.pdf https://platformlab.stanford.edu/Seminar%20Talks/retreat-201...

mlichvar 8y ago
I maintain an NTP implementation. That comparison doesn't seem fair to me. It looks like they are comparing the old reference NTP implementation and not really the protocol itself. An NTP implementation can certainly synchronize clocks with better accuracy than 1 millisecond, or even 1 microsecond with hardware timestamping and good network switches. There are some interesting ideas in the Huygens paper, but I don't see anything that couldn't be done also with NTP.
- geofft 8y ago
  The other thing I don't understand is that this paper argues against hardware timestamping on the grounds that users won't want to buy expensive hardware, and that Huygens is for "standard hardware ... in current data centers". Expensive, niche hardware is normal for the HFT folks that care about nanosecond precision.
  - justicezyx 8y ago
    The paper did not have hft as its primary use case, but you cannot contain reporters tendency to cherry pick eye catching aspects.
    - acqq 8y ago
      Yes, it seems that the designers tried to make something that would work in the current Google data centers. Which is not surprising as some of the authors work at Google. I'd more want to know: why does Google need even better synchronization of time stamps than what they have now?

amelius 8y ago

How would you use that nano-second precision on a CPU/OS that supports at most microsecond precision?

dirkgently 8y ago
Only if the article mentioned it! Oh wait, it did! https://www.usenix.org/conference/nsdi18/presentation/geng https://www.usenix.org/conference/nsdi18/presentation/geng
- geofft 8y ago
  I don't think the article answers amelius's question, which is not about how you would achieve that precision but how you would use it. On an OS that only supports recording timestamps up to microsecond accuracy, what is the point of synchronizing your clocks within nanoseconds of each other, even if you could?
  - egwor 8y ago
    On linux you can get nanosecond timestamps, and so could record them. This could be useful for capturing certain events. Is that what is meant? IIRC Windows XP didn't support resolving timestamps smaller than 8ms but we've moved beyond this.

chaboud 8y ago

"So-called high frequency trading firms place trades in a fraction of a second, sometimes in a bet that they can move faster than bigger competitors." First off: no. Big money plays in high frequency trading (roughly half of all trading activity), and the smaller traders without instantaneous access are the losers in this game. Secondly, NASDAQ's obsession with precise global sequencing is A) misguided and B) effectively impossible to do right 100% of the time. Given this, I would argue that the appropriate thing to do is change the market requirements. And I'd argue that like this: 1) Temporally quantize the market. Orders come in on an open temporal window that is sufficiently long to account for global latency of non-pathological communication (sorry, tor users) and a bit of computation time. Everyone gets to swim in the same pool. Maybe one second, maybe more. Nobody gets to see the order book until it's resolved. Write-only. 2) Lock the book and fulfill orders from the set of satisfiable orders. If there just contention for a trade (there will always be some), fulfill the contentious trades randomly using random zeedig generated from a pre-announced salt and a hash of some or all of the order book for the window. 3) Return the results and the hashes of the order book, next salt, etc, for verifiability and prep. 4) Re-open the order window. High frequency traders would hate this, because they wouldn't be able to pounce on quick movements, even without fronting slower traders. It would, naturally, increase latency for trades by virtue of having to wait for market resolution. However, mere sequencing doesn't solve the problem of having to resolve and confirm trades (the speed of light is so cruel), so I'm left utterly unsold on the market-efficiency benefit of ultra-high order resolution. Wealthy high frequency traders want to use time to buy an advantage, and the liquidity support they provide to the markets is dubious, at best, since they pull the plug as soon as things get crazy. Quantize the markets.

qeternity 8y ago
Most HFT shops are relatively small. HFT is all about latency and turn over. Big quant shops might have HFT elements but lean far more towards systematic/algo strategies that can be relatively high latency (still super low latency, but not HFT) because these are the only strategies that you can deploy serious var with. The guys crushing HFT are not huge hedge funds, and they are solving more engineering problems than building trading models. Also, no, small traders don't lose. Retail traders et al get much tighter spreads, cheaper execution by routing to internalizers, etc. It's big institutionals with size to trade that get front run and have to worry about HFT killing their shortfall. On the institutional side, it's about lit venues preferring HFT w/ special orders types and thin top of book. On the retail side, the issue mostly comes down to direct feed vs. SIP/CQS thanks to NBBO that opened the door for latency arb courtesy of yet more regulation. Blame your regulators folks. This is why dark pools became a thing. > and the liquidity support they provide to the markets is dubious, at best, since they pull the plug as soon as things get crazy This bit is certainly true. Source: hedge fund trader who hates HFT not in principal but because they are good at what they do

viburnum 8y ago

This is a huge waste of effort. HFT should be banned so smart people work on solving real problems instead.

JumpCrisscross 8y ago
> so smart people work on solving real problems instead Like making people click on ads?
throwaway37585 8y ago
> HFT should be banned What do you mean by this?

SEJeff 8y ago

IEEE 1588 v2 + rubidium decay grandmaster time sources do this quite nicely. Source: have worked as a software / Linux monkey for two of the biggest US HFT firms the past 10 years.

ShiftAce 8y ago

This is a bad move on their part. They should be pursuing Nano-First precision. Duh.

NelsonMinar 8y ago

HFT aside, this also has interesting applications in distributed databases. Spanner, for instance, has consistency guarantees directly related to how synchronized the clocks are (keyword: TrueTime). It seems plausible that Huygens could make a significant improvement on performance of this kind of distributed database. This looks like a very impressive result. NTP has been doing its thing well for years but a factor of 100 improvement on time accuracy would be amazing,

partycoder 8y ago

I think this is no longer about NTP but all the stack below it including hardware.

drumttocs8 8y ago

Confusing title. Perhaps better to say "successor to Network Time Protocol", which, like IRIG or PTP, is a pretty common timekeeping protocol.

amenod 8y ago

From [0]: > In this paper, we present HUYGENS, a software clock synchronization system that uses a synchronization network and leverages three key ideas. First, coded probes identify and reject impure probe data—data captured by probes which suffer queuing delays, random jitter, and NIC timestamp noise. Next, HUYGENS processes the purified data with Support Vector Machines, a widely-used and powerful classifier, to accurately estimate one-way propagation times and achieve clock synchronization to within 100 nanoseconds. Finally, HUYGENS exploits a natural network effect—the idea that a group of pair-wise synchronized clocks must be transitively synchronized— to detect and correct synchronization errors even further. Not an expert, but this seems quite a complex system. Since HF traders have huge incentive to game the system, my fear is that the next headline about Huygens will be about a new exploit found in the wild. [0] https://www.usenix.org/conference/nsdi18/presentation/geng https://www.usenix.org/conference/nsdi18/presentation/geng

jrockway 8y ago

This technology will also be excellent for games. Right now, the server has to decide how it's going to break ties, and that results in confusing moments. For example, Overwatch favors the shooter, so you might see someone in a position to shoot you, use a defensive ability, and die even though you used it, because the server decides that if two events are close in time, the shooter wins. With a trusted time reference, you can actually order events from the perspective of the client instead of the server; so if you actually used that defensive ability before the shooter clicked the mouse, you don't die. I actually think NTP might be good enough for this (despite what people say their reaction times are, milliseconds don't actually matter), but I guess game developers don't think of games as globally-distributed transaction processing systems (which is what they are, just a lot more write conflicts to resolve than your average database), and haven't experimented with ideas that are still only a few years old in that field. (The game industry also doesn't reward experimentation. If you're Google and you try to replace Bigtable with Spanner and it fails, it doesn't matter, you just keep using Bigtable. If you're a game company and your netcode is janky, you launch late, a competitor releases a similar game before you, and all the money you spent on development is gone.) With games there is always the trust issue; can someone write a client that lies about the time they took an action? The answer is yes. But if we have technology that relies on similar client trust working in high-frequency trading, it should be safe enough for games. The stakes are a lot lower in a computer game than the financial markets. So I think good things are on their way.

throwaway2048 8y ago
You still cant trust the client here, no matter how precisely synced your clocks are, because it could maliciously reorder events/tamper with time (always claim you activated first, with a certain fudge factor to prevent detection) and it would be undetectable within the bounds of internet latency.
- jrockway 8y ago
  I'm not completely convinced that cheating would not be detectable after aggregating some statistics over time. (Similar to how you can extract encryption keys from server processes, simply by timing how long certain operations take.)

red75prime 8y ago

It's interesting, that time synchronization in a rotating reference frame is path dependent ([0], for example). [0] https://tycho.usno.navy.mil/ptti/1974papers/Vol%2006_26.pdf https://tycho.usno.navy.mil/ptti/1974papers/Vol%2006_26.pdf

jfoutz 8y ago

I wonder if the next wave of hft will be a geostationary space station over New York, to get the extra occasional nanosecond.

chaboud 8y ago
Uh, I know it's a joke, but isn't geostationary orbit almost 36K km over the equator? The round trip time to NYC would be over a quarter of a second... Hence, drones. With lasers... Laser drones...

aswanson 8y ago

Seems sad so much technical effort to be exerted towards something so venal, trivial, and fleeting.

txdv 8y ago
If there is money in it, it will get solved!

cordite 8y ago

What value does this add to the world?