[cpp-threads] Causality on more than two processors, write atomicity

[Doug Lea]

Herb Sutter wrote:

> 
>>The JMM doesn't promise this. Somewhere in the JMM archives is a
>>discussion about this kind of lack of transitivity. It is one
>>ot the reasons that the formal models are more complicated than
>>you'd wish.
> 
> 
> Does that mean I can't always reliably maintain invariants, if I'm using
> unsynchronized updates (no locks) and the variables involved in the
> invariant can be updated by more than one thread over the life of the
> program?

Welcome to the world of lock-free programming :-)

> 
> Can you summarize the issues in that thread, or point to an existing
> summary? I imagine one issue is the cost doing more than pairwise
> (possibly stop-the-system) cache synchronization?
> 

It's actually a decades-old issue, first (to my knowledge)
dealt with by people studying multicast in distributed systems
such as Isis. Globally totally ordered multicast is so expensive
to support that people looked for cheaper protocols; which
were among the ancestors of non-SC memory models.

And historically, almost no algorithms/programs have ever been
found to require such strong guarantees. We once challenged
people to come up with non-toy examples, and never got any.


-Doug