An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 18:12 UTC (Sat) by Wol (subscriber, #4433)
In reply to: An introduction to lockless algorithms by excors
Parent article: An introduction to lockless algorithms

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

to post comments

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'.