An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 0:18 UTC (Sat) by pebolle (guest, #35204)
Parent article: An introduction to lockless algorithms

> [...] if event P happens before event Q and event Q happens before event R, then event P happens before R.

I'm still dumb: what makes this insightful?

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 0:56 UTC (Sat) by gus3 (guest, #61103) [Link] (48 responses)

Not dumb at all. It's an axiom, like this one for mathematics:

"For any op <, =, >, if A op B, and B op C, then A op C." That is to say:

-- If A < B, and B < C, then A < C
-- If A = B, and B = C, then A = C
-- If A > B, and B > C, then A > C

Referring to the statement you quoted, it could be re-stated thus:

"Given an action A, the time tA at which action A takes place, and any op <, =, >:
If tP op tQ, and tQ op tR, then tP op tR."

That may seem thick, but instead of just A, B, and C, I've just substituted locations on a time-line instead of a number line.

It may seem obvious, and it kind of is. But stating applicable axioms explicitly is standard practice in rigorous maths discussions.

An introduction to lockless algorithms

Posted Feb 20, 2021 2:55 UTC (Sat) by excors (subscriber, #95769) [Link] (5 responses)

It's also important what rules *aren't* stated. There's no requirement e.g. that for any two events P and Q, you can always determine either that P happens before Q or that Q happens before P. It's perfectly acceptable for there to be no ordering between them (except where the axioms say there must be an ordering).

That's contrary to the everyday human concept of time, where you would say every event happens at a precise number of seconds past midnight and you can always work out which happened first. That concept is problematic to implement in computers, because it's simply impractical for physically separated processors to have perfectly synchronised nanosecond-precision clocks and to attach timestamps to every message they share. So we throw away that concept of time and time-lines and define a brand new concept (called "happens before", but could equally be called "op" or "→") from scratch.

The axioms are trying to define that new concept with the minimal set of requirements on where there must be a well-defined ordering between events, so it's just barely strong enough to achieve the goal (in this case to define some useful kind of synchronisation between concurrent threads). And in this particular case, transitivity is one property that is required else the mathematical proofs stop working, so it has to be stated explicitly in the definition.

An introduction to lockless algorithms

Posted Feb 20, 2021 18:12 UTC (Sat) by Wol (subscriber, #4433) [Link] (3 responses)

This is where relativity helps :-)

Whether two things are sequential or not depends on whether one occurs INSIDE the light-cone of the other. These acquire-release semantics force the two light cones to intersect, so anything after the intersect is visible inside both light cones so you can conclude they are sequential.

And the light-cone thing also explains why things can only be simultaneous if they occur at the same 4-dimensional co-ordinates, because otherwise they are not in each other's light cone, and therefore there is no mutual concept of time.

Cheers,
Wol

An introduction to lockless algorithms

Posted Feb 20, 2021 19:14 UTC (Sat) by pbonzini (subscriber, #60935) [Link] (2 responses)

I don't think it's really about relativity; anything that you can model as a directed graph function just as well as a representation of a partial ordering.

For example think of two cars going from A to B along two different roads. Any time a junction joins the two roads you *might* be able to say who is ahead at that moment. However while the roads are running parallel it's possible (but not certain) that you cannot say that. That is because the points along the two routes form a partial ordering.

An introduction to lockless algorithms

Posted Feb 21, 2021 12:36 UTC (Sun) by Wol (subscriber, #4433) [Link] (1 responses)

No I didn't mean to say it was relativity. It's just that if you understand light cones and all that, it's the same problem in a different domain :-)

The send-receive creates a new light cone for which the origin is visible in both the previous two cones :-)

Cheers,
Wol

An introduction to lockless algorithms

Posted Feb 21, 2021 13:00 UTC (Sun) by pebolle (guest, #35204) [Link]

I'll file this under 'Disagreeing what "work" means'.

An introduction to lockless algorithms

Posted Feb 23, 2021 1:06 UTC (Tue) by rgmoore (✭ supporter ✭, #75) [Link]

It's perfectly acceptable for there to be no ordering between them (except where the axioms say there must be an ordering).

From a practical standpoint, it's not just acceptable for there to be no ordering; it's actually desirable for performance. If you can divide up your program into separate tasks that don't have ordering constraints between them, you can run those tasks however makes the best performance sense. This has been the key to all kinds of modern performance advances, like out of order execution, multiprocessing, and what have you. Those things all depend on being able to break up tasks into parts that can be run in different orders. It's the need to synchronize that slows things down.

Axioms

Posted Feb 21, 2021 6:22 UTC (Sun) by tialaramex (subscriber, #21167) [Link] (41 responses)

Right.

Not explicitly stating such an assumption can get you in serious trouble if we want to prove things about a system.

For example: As an IoT developer thinking about how two devices you manufacture can securely communicate over an IP network, you might seize upon the Pre-shared Keys (PSKs) in TLS 1.3 (RFC 8446) as a good approach that avoids worrying about certificates or a PKI. It might seem like a common sense assumption that if device #1 ("Alice"), and device #2 ("Bob") share the same key K, that's going to be secure against any attacker that doesn't know K, the document (as published) doesn't suggest there would be any unexpected problems. And indeed mathematical proofs of TLS 1.3 say it does deliver on the claims in its introduction.

Unfortunately those proofs assume something different from you. They assume your two devices would each need their own key, K1 and K2. If you don't use separate keys you need countermeasures not described in the protocol, because of the "Selfie attack". The attack goes like this, Alice asks Bob something (using key K of course), but Mallory (who doesn't know K) just redirects Alice's message back to Alice. Alice thinks this question came from Bob (after all it uses key K which they share) and answers it, now Alice also thinks that answer came from Bob. Mallory has successfully confused Alice despite being unable to either read or forge messages from either Alice or Bob. Under the proof scenario Alice asks using K1, when the message is redirected back to her Alice is puzzled because it isn't encrypted with key K2 from Bob, so that message is rejected and everything is fine.

If this assumption had been made into an explicit _axiom_ that could have highlighted that the TLS document doesn't explain the problem with just having a single key K and likely its authors would have drafted a section explaining why you might need more keys than seem necessary at first glance, and what alternative strategies would work if you must have one key.

A more broadly famous missing assumption is the Axiom of Choice. In the 1800s mathematicians were confident they understood the Theory of Sets - they had established Axioms stating how it works - but alas they'd actually without making it explicit been assuming that in a set of sets (like the set of sets of integers) you can always choose one of the members of each set. This is definitely true for finite sets. But for infinite sets we can't prove it, so, we ought to explicitly make it an Axiom and say so, if we're wrong any results depending on that assumption may be wrong too. Today most mathematicians will choose ZFC, axioms for set theory which include the Axiom of Choice, because it does after all _feel_ intuitively as though you could choose one from each set. But at least you've written down this specific assumption you're making in case it matters some day.

Axioms

Posted Feb 21, 2021 12:25 UTC (Sun) by ale2018 (subscriber, #128727) [Link] (40 responses)

A possibility could be to assimilate any exchange of information as a message transmission. There may always be entities with witch you don't exchange any information at all. They may exist or not, you never know. Like the set of all sets, if you cannot ping it, you may consider it doesn't exist.

Thus, among "existing" things you have defined a partial time order. Can one obtain relativity from Newtonian physics by just introducing information exchange?

Axioms

Posted Feb 21, 2021 12:47 UTC (Sun) by Wol (subscriber, #4433) [Link] (39 responses)

> Thus, among "existing" things you have defined a partial time order. Can one obtain relativity from Newtonian physics by just introducing information exchange?

Almost certainly not. Newtonian Physics assumes time IS constant from all vantage points - if you see time move ten seconds so will I. Relativity says time APPEARS constant from all vantage points.

If we assume I travel to Alpha Centauri and back at 0.9c, you on Earth will see me take about 9 years to do so. Newton says that means I must experience the same 9 years. But relativity says time will run slower for me, I may only experience 1 year passing.

It's like a multi-core CPU with each core having a different clock ... and time is measured in ticks ...

I don't see how exchanging information will alter anything.

Cheers,
Wol

Axioms

Posted Feb 22, 2021 13:04 UTC (Mon) by ale2018 (subscriber, #128727) [Link] (38 responses)

> I don't see how exchanging information will alter anything.

For one thing, introducing information and the ability to process it breaks time symmetry. You can easily call "past" the side you remember and "future" the side you predict. Time reversal doesn't work any more. At this point you've already left the classical, Newtonian vision, and dropped those misconceptions about time.

Special relativity was introduced as an attempt to account for the speed of light being a universal constant. As a speed limit, it entails that information cannot travel faster than light either. My question was whether it's possible to derive some kind of relativity the opposite way around. That is, assuming that things exists only if you can exchange information with them, and then assuming the partial ordering principle outlined in the article, is it possible to derive a concept similar to the light cone?

Of course, it is not possible to compute the actual speed of light based on pure logic... Or is it?

Axioms

Posted Feb 22, 2021 13:46 UTC (Mon) by mathstuf (subscriber, #69389) [Link] (37 responses)

> Of course, it is not possible to compute the actual speed of light based on pure logic... Or is it?

AFAIR, it's not possible to compute a one-way speed at all. You can only get a round-trip speed (light could be traveling at some factor based on its angle with a "universal axis" and we'd never be able to tell) because you can't communicate back about any time synchronization without being affected by the same limits. So, no, without an axiom that "the universe has no preferred axis for light travel", you get an infinite number of possible solutions for a speed-of-light gradient.

Axioms

Posted Feb 22, 2021 18:44 UTC (Mon) by ale2018 (subscriber, #128727) [Link]

That's right.

Let me quote Leslie Lamport, from the 1978 article cited by Paolo Bonzini:

This definition will appear quite natural to the reader familiar with the invariant space-time formulation of special relativity, as described for example in [1] or the first chapter of [2]. In relativity, the ordering of events is defined in terms of messages that could be sent. However, we have taken the more pragmatic approach of only considering messages that actually are sent. We should be able to determine if a system performed correctly by knowing only those events which did occur, without knowing which events could have occurred.

The references [1] and [2] are two introductory texts on relativity of those times.

Axioms

Posted Feb 23, 2021 0:03 UTC (Tue) by Wol (subscriber, #4433) [Link] (31 responses)

Well, as far as light is concerned, the speed of light ... ISN'T. No time passes whatsoever between a photon leaving wherever it was created, and being absorbed by whatever it hits ...

Oh, and I believe it IS possible to calculate the speed of light based on pure logic ...

You'll have to look it up for yourself, but if you take a bunch of mathematical constants like e, pi, ln and so on, I think they somehow dictate a set of possible values for c, g, and other physical constants. It's too long ago, but I'm sure I've seen the physical constants defined in terms of the mathematical constants. And that's why astronomers are so unhappy with the cosmological constant. Because they can't define it in terms of anything else, it shouldn't exist ...

Cheers,
Wol

Axioms

Posted Feb 23, 2021 0:38 UTC (Tue) by mathstuf (subscriber, #69389) [Link] (26 responses)

Eh, that sounds like numerology to me. Which is "more fundamental", e or pi? Is the Feigenbaum constant important? Gamma? The golden ratio? Silver ratio?

It'd also lay a blow to various theories of multiple universes which differ in the physical constants. Also, what is a "fundamental constant"? Is the radius of a proton a constant or a derived value? The size of a helium-4 nucleus? Ratio between the lepton sizes? Even physics is a *bit* arbitrary here.

Axioms

Posted Feb 23, 2021 1:19 UTC (Tue) by Wol (subscriber, #4433) [Link] (25 responses)

> Eh, that sounds like numerology to me. Which is "more fundamental", e or pi? Is the Feigenbaum constant important? Gamma? The golden ratio? Silver ratio?

Who said anything about fundamental? Both e and pi are mathematical constants, as is the golden ratio. They're all of equal importance.

Things like c, g, permittivity, that stuff, are all physical constants, which should be explainable in terms of maths.
Cheers,
Wol

Axioms

Posted Feb 23, 2021 13:10 UTC (Tue) by mathstuf (subscriber, #69389) [Link] (7 responses)

> Things like c, g, permittivity, that stuff, are all physical constants, which should be explainable in terms of maths.

But…why? What is this assumption based upon? Is it a bit of Platonic idealism?

Axioms

Posted Feb 24, 2021 0:27 UTC (Wed) by Wol (subscriber, #4433) [Link] (6 responses)

I don't know why, I just remember coming across it somewhere that most of the physical constants could be defined in terms of other things, and the reason they had the values they did was because the maths didn't make sense otherwise.

Cheers,
Wol

Axioms

Posted Feb 24, 2021 21:58 UTC (Wed) by mathstuf (subscriber, #69389) [Link] (5 responses)

Sure, but (as stated elsewhere) your numerical values are limited to our arbitrarily defined units. A mole is a number of atoms of a substance in a number of grams equal to its molecular weight. A meter is basically an arbitrary nice length, Seconds are based on a breakdown of the rotational speed of Earth. Sure, we've rebased them onto more stable footing now, but the counts of those things into the units are "arbitrary" based on what we had before.

If we wanted, we could say that the speed of light is pi/e Wol_lengths/Wol_time intervals. Doesn't mean that those units are any more useful than our numerical value in m/s.

Axioms

Posted Feb 25, 2021 7:48 UTC (Thu) by jem (subscriber, #24231) [Link] (4 responses)

One fun fact about the base unit for mass, kg, is that it is derived (indirectly) from the size of the Earth. On a bigger Earth, we would have a different "kilogram", with a bigger mass. (And I'm not talking about the gravitational force, which would increase even more, because of the bigger mass of both a kilogram and the Earth.)

Axioms

Posted Mar 16, 2021 21:09 UTC (Tue) by nix (subscriber, #2304) [Link] (3 responses)

Not any more it isn't. In 2019 it was redefined in terms of the Planck constant -- though, of course, its *actual value* comes down to the original French Revolutionary definition: but even that was the mass of a cubic centimetre of water at the melting point of ice. This, of course, depends on atmospheric pressure (since they didn't use the triple point), and thus indirectly on the mass of the Earth and a bunch of other contingent values -- but the current definition depends on no such things.

Axioms

Posted Mar 17, 2021 10:37 UTC (Wed) by jem (subscriber, #24231) [Link]

>Not any more it isn't. In 2019 it was redefined in terms of the Planck constant

Well, I said derived, not defined.

Axioms

Posted Mar 18, 2021 10:14 UTC (Thu) by mgedmin (guest, #34497) [Link] (1 responses)

> mass of a cubic centimetre of water

a cubic *deci*meter (which is also one liter) of water.

Axioms

Posted Mar 20, 2021 1:24 UTC (Sat) by nix (subscriber, #2304) [Link]

I changed that repeatedly before posting... and picked the wrong one, despite the metric system being the only system I actually know. Sigh.

(And obviously you're right, unless water has suddenly become much, much denser than lead :) )

Axioms

Posted Feb 23, 2021 15:24 UTC (Tue) by rschroev (subscriber, #4164) [Link] (16 responses)

π² m/s² is an approximation for g, but only because of our definitions for the meter and the second, and because we happen to live on Earth. I really don't see why there should be any connection between mathematical constants and the values of constants that govern physical phenomena. Mathematics is purer than that: it can with equal ease describe a universe with completely different constants or even different physical laws.

Axioms

Posted Feb 24, 2021 0:23 UTC (Wed) by Wol (subscriber, #4433) [Link] (1 responses)

Are you confusing g and G, or am I?

I think the equation is G=g.m1.m2/d^2

G is 9.8m/s^2, while g is the gravitational constant, which is believed to be the same everywhere in the universe.

Cheers,
Wol

Axioms

Posted Feb 24, 2021 0:47 UTC (Wed) by rschroev (subscriber, #4164) [Link]

G is the gravitational constant (or indeed the universal gravitational constant), approximately 6.674×10^−11 m³/(kg⋅s²).
g is the gravity of earth, approximately 9.81 m/s².
The equation is F = G⋅m1⋅m2/r². In case of Earth, that's F = G⋅m⋅m_earth/r_earth², with g = G⋅m_earth/r_earth². So in that case we get F = m⋅g.

Axioms

Posted Feb 24, 2021 0:31 UTC (Wed) by Wol (subscriber, #4433) [Link] (11 responses)

> Mathematics is purer than that: it can with equal ease describe a universe with completely different constants or even different physical laws.

It can *de*scribe it, yes. But I think you'll find it also *pre*scribes it and says "completely different constants and laws doesn't make logical sense".

Cheers,
Wol

Axioms

Posted Feb 24, 2021 1:01 UTC (Wed) by rschroev (subscriber, #4164) [Link] (10 responses)

I think you're mistaken in this, but I would be happy to be proven wrong because that would lead to very interesting insights in physics and the relationship between physics and mathematics.

BTW there's a video of Richard Feyman's lecture about that relationship here: https://youtu.be/obCjODeoLVw
And some comments about it: https://medium.com/cantors-paradise/richard-feynman-on-th...

Interesting stuff, if you're interested in that kind of stuff.

Axioms

Posted Feb 24, 2021 18:28 UTC (Wed) by Wol (subscriber, #4433) [Link] (9 responses)

Whoops. I didn't mean to say there aren't other solutions for the equations. Just that the possible universes are seriously constrained by the maths.

Cheers,
Wol

Axioms

Posted Feb 24, 2021 21:54 UTC (Wed) by mathstuf (subscriber, #69389) [Link] (3 responses)

That we had such a firm grasp on physics at that level to tell a "broken" from a "working" universe given a set of "knob settings" is news to me. That we even know all of the relevant knobs is news even. I thought we were still at the "we have a working universe on our hands…what makes it tick" stage about the fundamentals. Do you have any journal papers about this you could cite?

Axioms

Posted Feb 24, 2021 23:22 UTC (Wed) by Wol (subscriber, #4433) [Link] (2 responses)

How many dimensions does the Universe have? We know it's not three, Einstein proved that.

We think it may be four - that's what Einstein thought but that has a whole bunch of problems. If it *is* four, I believe that means string theory is correct as it's the explanation for relativistic singularities.

Or it could be ten or eleven. Anything betwen five and nine inclusive just doesn't work because we get an explosion of infinities - infinity itself isn't a problem, but there are different sorts of infinity and for reality to work they need to cancel out. For those dimensions they don't. (These universes, if I remember correctly, define mass as the fifth dimension ...)

(That's why I was moaning about computers crashing when you divide by zero. If you declare zero and infinity as non-numbers for which arithmetic doesn't work, you're in trouble. If you say "to make arithmetic work, they swap places on division", then you can do this sort of maths and come up with something that makes sense.)

At the end of the day, we have loads of maths that describes what we see. And that *constrains* what is a plausible universe. We have a local maximum or minimum, don't know which. By adjusting some values, we can force others to impossible values. Plausible universes must have all these values at maximum or minimum, not off the scale or impossible or at some non-equilibrium value.

Cheers,
Wol

Axioms

Posted Feb 24, 2021 23:36 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link]

> Or it could be ten or eleven. Anything betwen five and nine inclusive just doesn't work because we get an explosion of infinities - infinity itself isn't a problem, but there are different sorts of infinity and for reality to work they need to cancel out. For those dimensions they don't. (These universes, if I remember correctly, define mass as the fifth dimension ...)
You can construct a universe with multiple time axes, with many more dimensions, and so on. The math will be internally consistent.

Axioms

Posted Feb 25, 2021 0:05 UTC (Thu) by nybble41 (subscriber, #55106) [Link]

> That's why I was moaning about computers crashing when you divide by zero.

To say that division by zero is undefined is mathematically correct and not just an arbitrary computer limitation. There is no proper answer to the question "What number, when multiplied by zero, gives the non-zero product X?", at least not in any system that would uphold basic idioms such as the product of a number and its reciprocal being equal to one. "Infinity" times zero is not equal to any particular finite number X, so that isn't a solution. Depending on the particular forms of the equations which gave rise to the infinity and the zero (or infinitesimal) the product could be another infinity or any real number; it depends on how you phrase the question. $\lim_{x \to 0+} x ln \frac{1}{x} = 0$, but $\lim_{x \to 0+} x \frac{1}{x} = 1$. In both cases you're multiplying an infinitesimal ($\lim_{x \to 0+} x$) by an infinity ($\lim{x \to 0+} ln \frac{1}{x}$ or $\lim{x \to 0+} \frac{1}{x}$, respectively) but the specific form of the equation changes the result.

Axioms

Posted Feb 24, 2021 22:24 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link] (4 responses)

Not really. Math is just a language, it basically restricts nothing.

If you want to read something mind-blowing, try the "Clockwork Rocket" series by Greg Egan. It's accompanied by a thesis-sized exploration of its (fictional) physics: http://www.gregegan.net/ORTHOGONAL/ORTHOGONAL.html

Axioms

Posted Feb 24, 2021 23:26 UTC (Wed) by Wol (subscriber, #4433) [Link] (3 responses)

Maths is just a language, true. But if we try to define a - six-dimensional universe, say - the maths just doesn't add up. So yes the maths does restrict our universes - it says six dimensions just won't work.

Cheers,
Wol

Axioms

Posted Feb 24, 2021 23:34 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link]

> Maths is just a language, true. But if we try to define a - six-dimensional universe, say - the maths just doesn't add up. So yes the maths does restrict our universes - it says six dimensions just won't work.
Who told you that? A six-dimensional classic (Newtonian) universe works just fine. Sure, you won't have stable orbits but apart from that it's OK.

You can also construct a quantum field theory for such a universe, it also would work just fine.

Axioms

Posted Feb 25, 2021 15:16 UTC (Thu) by mathstuf (subscriber, #69389) [Link]

I think you're confusing the physics of our universe versus those of any possible universe. Sure, *ours* might not make sense with 5-9 dimensions, but that makes no conclusion about *any possible universe* having such a number of dimensions. Maybe you're just being imprecise with your language in places?

Axioms

Posted Mar 8, 2021 14:59 UTC (Mon) by LtWorf (subscriber, #124958) [Link]

I think you are very confused about the dimensions thing in physics.

Physics tries to model measurements.

So for example you measure a planet that is orbiting, make an equation, and see if tomorrow the equation and the position are the same (within a certain range of precision).

Before Galileo saw that Jupiter had satellites, they had perfectly fine equations that predicted where everything would be in the sky. The problem arose because new data could not fit the model.

You can absolutely model an orbit of a planet using 3 dimensions, or you can model it in an higher space with an equation of a lower degree. Both work. We can't really know which is "exact" if both work.

You can keep adding dimensions and make equations that work, but we don't really know what the "truth" is.

Axioms

Posted Feb 24, 2021 1:24 UTC (Wed) by SiB (subscriber, #4048) [Link] (1 responses)

The earliest definition of a meter is the length of a seconds pendulum. By that definition, g=π² m/s² exactly.

Axioms

Posted Feb 24, 2021 8:53 UTC (Wed) by mpr22 (subscriber, #60784) [Link]

Jean Picard's proposed toise universelle was twice the length of a seconds pendulum. Unfortunately, if you set up a seconds pendulum in (say) Cayenne, French Guiana, you would find that it was 0.3% longer than one set up in the Paris Observatory, because the acceleration due to gravity at sea level varies with a number of factors including latitude.

The first formally adopted definition for the metre itself, proposed in 1791 by the French Academy of Sciences and adopted in 1793 by the National Assembly, was one ten-millionth of the distance from the North Pole to the Equator along the Paris meridian.

Axioms

Posted Feb 23, 2021 1:06 UTC (Tue) by mpr22 (subscriber, #60784) [Link] (3 responses)

It is not possible to calculate the speed of light by pure logic, because the numerical value of the speed of light is a consequence of your units of measurement.

There is one particular physical constant, µ_0 (the permeability of free space) which was historically defined (as a consequence of the relationship between electrical current and induced magnetic fields) as exactly 4π × 10^-7 H/m ... but that value is no longer strictly valid (although it's close enough for the vast majority of practical purposes), because the ampere has been redefined in terms of the elementary charge and the second.

Axioms

Posted Feb 24, 2021 1:00 UTC (Wed) by SiB (subscriber, #4048) [Link] (2 responses)

Physical constants that carry units do not carry any physics. The universe does not care about the value of the speed of light.

Some years ago in our coffee room at the institute there was a discussion about the possibility that the fine-structure constant α may not have been constant in the past after all. The question was raised, which of the constituents of α=e²/(4πε₀ħc) may be the reason. Well, the answer is e, if at all. α is a constant without units. It is pure physics. It defines the strength of electromagnetic interactions. The universe cares a lot about the value of the fine-structure constant α. In our experimental units it is the charge of the electron e that represents that strength, but in the end, it also just defines units of measure.

Theoretical physics defines the units differently than experimental physics. They mostly use c=4πε₀=ħ=k=1. Everything is measured in eV or eV¯¹.

From a theoretical point I am a bit unhappy about the new definition of the SI units. They fixed the value of e, although it indirectly represents a quantity the universe cares about. The cost is that µ₀ and ε₀ are now _not_ fixed by definition in the SI, as they were before, like Wol said.

Ideally, all units were defined by fixing the value of some fundamental constant. We are now almost there. The second is still defined by an artifact. At least it is an atom, so it can be reproduced everywhere in the universe. To fix that we need to fix the gravitational constant. But metrology defines units by what they can measure with the best precision. The gravitational constant does not apply, it has to catch up at least eight orders of magnitude in precision.

Axioms

Posted Feb 24, 2021 1:16 UTC (Wed) by SiB (subscriber, #4048) [Link]

s/Wol/mpr22/

Axioms

Posted Feb 25, 2021 3:46 UTC (Thu) by NYKevin (subscriber, #129325) [Link]

> Physical constants that carry units do not carry any physics. The universe does not care about the value of the speed of light.

The universe may not care about the speed of light, but the stuff in the universe surely does. To borrow from your "theoretical physics normalizes everything to 1" example, the mass of the proton is much, much (numerically) smaller than the charge of the proton, and surely there's some physical significance of that? Or, alternatively, we can say that there's nothing wrong with the proton, and instead it's gravity which is too weak, but that's just reframing the same question in different units. I'm not sure you can ask that question without using units at all.

Ultimately, I suppose the "proper" framing of this question is some nonsensically complicated question about why the relevant quantum fields happen to interfere in exactly the way that they do to give the proton the properties that it has. But you can't even ask that question until you know what gravity is, at a quantum level, and to the best of my knowledge, nobody does.

Axioms

Posted Feb 25, 2021 4:35 UTC (Thu) by NYKevin (subscriber, #129325) [Link] (3 responses)

Another way of thinking about it: The one-way speed of light is operationally ill-defined.

Ultimately, science is about predicting the outcomes of experiments and observations. If you can't observe it, directly or indirectly, it is beyond the realm of scientific inquiry. The one-way speed of light falls into this hole. Speed is normally defined as distance divided by time, but when we're talking about relativistic speeds, we need to be clear about which time we mean.

So, let's imagine a specific setup. We'll send a pulse of light from point A to point B. So, what is the one-way velocity of the light? It is the distance between A and B, divided by the time it takes for the signal to arrive. But whose time?

It turns out that, not only is there no reasonable way for the scientists at A and B to communicate the fact that the pulse has arrived (short of sending a second pulse and thereby measuring the round-trip time instead), it is actually not meaningful for an event at A and an event at B to happen "simultaneously." There will always be an observer who thinks that A's event happened first, and an observer who thinks that B's event happened first, unless the events are in each others' light cones, in which case everyone will agree that one comes before the other. But you can't get everyone to agree that both events happen simultaneously.

This creates a problem, because no matter where you put the clock, it has to be synchronized with respect to two distant events:

1. The pulse being sent from A.
2. The pulse arriving at B.

You cannot synchronize a clock with respect to an event unless the clock is physically present at that event, because simultaneity is otherwise relative to one's choice of reference frame. So the clock has to be at both A and B. You could imagine two clocks, synchronized with each other, but then you have to decide what you mean by "synchronized," because simultaneity is still relative. There is always a reference frame in which the clocks are not synchronized.

If the pulse were traveling slower than light, then you could move the clock with the pulse. This would give you a metric called the "proper time," and that actually does have some useful properties in this context. In particular, it is independent of reference frame or choice of coordinates, so that the one-way velocity of any slower-than-light object is perfectly well-defined and even measurable. But you can't do that with a pulse of light, because the pulse is traveling at the speed of light, and the clock can't go that fast if it has any mass. If the clock doesn't have any mass, then it cannot function as a clock in the first place, because massless particles do not experience the passage of time.

As a result, there is no operational definition of the one-way speed of light that is compatible with the laws of physics. This is why Einstein, for example, describes it as a "convention" in his special relativity paper, rather than asserting it as fact. It's not fact, it's just a convenient way of labeling the diagram.

Having said all that, there is one thing we can experimentally verify (and have done so): The time it takes for light to travel along a closed inertial path of length L is L/c, as measured at the start/endpoint of the path, regardless of what the path looks like or how it is shaped. So, if there are any variations in the one-way speed of light that depend on angle, they *always* cancel each other out. As a result, if you simply assume that the one-way speed of light is a constant, then you can use that assumption to "synchronize" distant clocks by sending light pulses between them and adjusting for the speed of light delay. Although this "synchronization" is ultimately just a convention, it behaves a lot like you would expect "true" synchronization to behave (at least with respect to the clocks' reference frames, anyway). Einstein describes how this works in his paper, and others have elaborated on the details (in short, the clocks should be in inertial reference frames and not in relative motion).

Axioms

Posted Feb 25, 2021 22:39 UTC (Thu) by apoelstra (subscriber, #75205) [Link] (2 responses)

> So the clock has to be at both A and B.

Could you entangle two clocks?

Axioms

Posted Feb 25, 2021 22:47 UTC (Thu) by mathstuf (subscriber, #69389) [Link] (1 responses)

You could, but you wouldn't know if they disentangled in the meantime without communicating. Entanglement still doesn't allow information to travel faster than light. Part of the problem is that if they're at the same place to sync with each other, to then be at A and B they'll need to travel outside of an intertial reference frame causing time dilation for them.

Axioms

Posted Feb 25, 2021 22:56 UTC (Thu) by apoelstra (subscriber, #75205) [Link]

Ah, ok, I see. To make meaningful use of the entanglement you'd have to bring the clocks back together (or communicate between them, but that's essentially the same -- there is frame-switching no matter what). But this is exactly the setting of the twin paradox [1] which is a more well-known example of trying to equivocate between events in distinct frames.

[1] https://en.wikipedia.org/wiki/Twin_paradox

An introduction to lockless algorithms

Posted Feb 20, 2021 4:04 UTC (Sat) by itsmycpu (guest, #139639) [Link] (4 responses)

Practically it means that if (step1) the first thread updates data, and then (step2) does a store-release of a value that indicates that the data was written, and then (step3) the second thread does a load-acquire of that value, it will (step4) see all the updates that the first thread has done before step2.

As long as the value read in step3 is the value written in step2 (or a value written after that). Because then you know that step3 > step2, and because of that, step4 > step1.

An introduction to lockless algorithms

Posted Feb 20, 2021 6:15 UTC (Sat) by itsmycpu (guest, #139639) [Link] (3 responses)

>Practically it means that if (step1) the first thread updates data, and then (step2) does a store-release of a value that indicates that the data was written, and then (step3) the second thread does a load-acquire of that value, it will (step4) see all the updates that the first thread has done before step2.
>
> As long as the value read in step3 is the value written in step2 (or a value written after that). Because then you know that step3 > step2, and because of that, step4 > step1.

To clarify the not-so-obvious part:

From the point of view of the first thread, step2 > step1 is always true, but without using acquire/release, this doesn't transfer to the second thread. Without that, the second thread may not see step4 > step1.

Why not? For example, the compiler is allowed to produce code for step2 that affects memory before step1, as long as that doesn't change the outcome of the first thread's local computations. The compiler does not have to consider the possible side effect on the second thread, which therefore might see the memory affected by step2 before it is affected by step1.

Only the use of acquire/release requires the compiler to produce code where the update of step1 is written to memory, and therefore visible to other threads, before step2. (Memory or shared cache). So without that, the second thread cannot assume step4 > step1, even if it thinks it can assume step3 > step2.

I think this is the same thing as the article says, just highlighting the practical aspects.

An introduction to lockless algorithms

Posted Feb 20, 2021 7:24 UTC (Sat) by pbonzini (subscriber, #60935) [Link] (2 responses)

Yes, it's exactly the last ASCII art graph. Thanks for explaining it in words; even if a picture is worth a thousand words, sometimes writing them down still helps!

An introduction to lockless algorithms

Posted Feb 20, 2021 9:47 UTC (Sat) by pebolle (guest, #35204) [Link]

> Thanks for explaining it in words

And that goes for everyone taking time to answering my grumpy questions.

When you're not versed in the vocabulary and habits of a certain field it is very to hard determine whether you're reading something profound, something trivial or just plain nonsense. (I've just finished a book of nearly 300 pages explaining that even physicists can be happily employed while apparently only producing hot air.)

I'll restart the article and hope that I won't get stuck on one of my many, many pet peeves again.

An introduction to lockless algorithms

Posted Dec 10, 2021 9:48 UTC (Fri) by Lurchi (guest, #38509) [Link]

    a.x = 1;                            datum = message;
       |                                    |
       |   happens before                   |
       v                                    v
    message = &a;                       datum->x

I think the left "happens before" arrow should not be there (the right one of course is correct, due to the data dependency).