Home .NET Time fragmented; a bit about the similarity of distributed systems and the weak memory model

Time fragmented; a bit about the similarity of distributed systems and the weak memory model

by admin

Hi all!
Today we would like to touch once again the topic of simultaneous and sequential execution in different programs, especially in distributed systems. Back in September we published an article " Synchronicity is a myth " on the subject, and now publishing a translation of a more serious study that will hopefully help you navigate better with distributed systems.

There is only one real problem in computer science : recognize that cache disablement errors are misnamed. They are merely errors per unit, related to time usage.

– Author unknown
Time is a strange thing.
Time is so strange because we really, really want to think that it is perfectly ordered. It seems to us that any event at 3 p.m. occurs (as we would say) before any event at 4 p.m.–without exception, argument, or compromise.
However, computer science knows a lot of examples when this requirement has to be approached not so strictly. It appears at the level of processors, compilers, and network nodes. Again and again in computing, at different levels of the stack, we find ourselves in situations where we have two events in front of us and we do not know in what order they happened. Time is obviously not total; it is fragmentary.
Why? The fact is that we don’t know it, because the level of abstraction over which we exist does not provide an answer to this question. Accidental or not, our computational abstractions offer no guarantees about the ordering of events. The freedom to reorder events often allows for much more productive and accessible systems.
The processor can act memory ordering model ; it reflects what guarantees the processor does not want to give you during the build phase – for example, which instruction was executed earlier and which was executed later. The processor itself decides exactly how to pipeline instructions and executes them out of order – that is, it uses its chips more efficiently than I would have guessed to use them.
In language can act memory consistency model ("memory model" for short); it reflects what safeguards the language does not give you when generating an assembly, such as distributing instructions across multiple threads. This reordering is, by definition, inherent in the hardware memory model and largely explains why such a "weak" concept of time is provided in compilers. It is within this memory model implemented in the language that you program when you write non-blocking code.
A famous example of a memory model implemented at the language level is with ile and weak memory models in the C++11 standard. By default, C++ provides atomic operations with synchronization, but you can also weaken the memory access model to improve performance. The behavior provided in this way is intended to serve as an abstraction over the major processor architectures in use today (x86, POWER, and ARM).
Finally, a distributed system may have its own consistency model; it reflects what guarantees the system is not going to give you about the order of events on clients and replicas on the WAN. The over-ordering directly related to communication delays or lack of synchronization basically explains why in a distributed system you cannot do without the mentioned weak time model. This is the kind of consistency model you program when you write a distributed application.
In practice, there is a huge zoo consistency models that can be used when programming a distributed system. In all such situations, these models describe the (desired) behavior of the system as observed from outside that system. If I – a particular client or a particular thread – write a value, then immediately read it, is it guaranteed that I will necessarily see a record no older than mine? If time were not fragmented, if we were always clear about the order in which operations occur in our system – naturally, the answer to this question would be in the affirmative. It would be strange to ask such a question at all.
But time is fragmented – so, putting such a question has to be done.

Consistency models – I mean, memory models

Reasoning about this fragmentary order is often difficult and always unpleasant. We would like to assume that time is always absolute at all levels of the stack, whether in ACID transactions or atomic operations/locks. The stricter the guarantees, the easier it is to program with them, of course!
But we all want speed. Whether in distributed systems, where strict consistency has to be sacrificed for availability, or in non-blocking programming, where a weak memory model is adopted to avoid the costs of synchronization, it is usually worthwhile for a programmer working with any level of stack to engage in this complex reasoning.
The consistency of shared-memory models and the consistency of distributed-memory models are both are abstract They describe to the programmer working with a system the interface of that system. They make it clear what kinds of behavior, corresponding to the weak memory model, we can expect, given now that the general properties of the ordering of events in the system, which we take as a given, no longer apply to it. The two models of memory may seem similar, but both communities have developed their own discourses for discussing them. The meanings used in them are different, though they overlap.
We can already imagine how confusing this can be. So what to do?

Description of time as an entity implying anywhere from two to eight kinds of partial order

In His 2014 book. Sebastian Burkhardt attempts an exhaustive characterization of the many variants of consistency models. In this characterization, along with other mathematical structures, two variants of the logical ordering of events apply : "visibility" and "arbitration", previously also mentioned in other works by Burkhardt et al, see e.g, article On specifying and validating replicated data types (2014).
"Visibility" is the partial order inherent in potential conditioning. It allows you to keep track of which events (perhaps in other replicas) are visible to which other events. There are no requirements for visibility other than acyclicity; events in an object may be visible to events in another object, and the operation of reading or writing an event has no effect on its visibility to other events.
"Arbitrariness" is a general order to track how a distributed system in which a choice situation occurs will judge which event to occur earlier and which to occur later.
Since distributed consistency models are analogous to memory models, it turns out that such phenomena of visibility and arbitrariness can also be useful when discussing memory models. In particular, In an appendix to his 2014 article Burkhardt demonstrates "how close" the weak memory model from C++11 is to object-by-object causal consistency, but with some interesting deviations. That’s what the rest of this post is about.
Let’s start by specifying visibility and arbitrariness in terms of "read" and "change order". With "read", visibility between any two objects will only be considered in situations where both reading and writing concern the same object, while with "read" only one entry (or more than one) may be visible.
This corresponds to a situation where a shared-memory processor can write information to just one memory location for any given object at any given time, even though different threads may access it at different causal moments (on the other hand, in a distributed system, a logical object can be written to many separate replicas at once).
"Modification ordering" corresponds to the same step in specifying arbitrariness, it is object-by-object and allows only writes. Again, this specialization is based on the fact that with weak memory specification, categorical guarantees are only given at the single object level.
Next, let’s discuss the consistency axioms formulated by Burkhardt et al. and see how they apply to the weak memory model. Note : even though the word "axioms" is used, these are simply properties that may or may not be enforced in different memory models. Burkhardt’s article focuses on the properties that determine cross-object causal consistency.

Consistency in the long run

For any particular event, there cannot be an indefinitely large number of events that do not see it. That is, any event eventually is visible to the system.
Logically constructing such conditions in a system with a weak memory model should be somewhat more difficult : one has to argue that for any particular record there cannot be an infinite number of read operations which do not read that record or earlier records (in order of modification).
The C++11 specification does not guarantee compliance with this axiom, although it is difficult to find a counterexample in practice.

Etheric coherence

When tracking "potential conditioning" at the flow/client level, and as far as visibility/readability is concerned, it must be understood that there is no backtracking time. This is why it is required that closures when ordering threads that involve reads be acyclic. As a rule of thumb, you can be sure that this property will be respected in distributed systems, but it is the property that prevents user visibility in some speculative execution options if the system has a weak memory model.
Burkhardt et al. point out that this axiom is "not validated" in the C++11 specification, and it is unclear whether "does not validate" can in practice observe "satisfying cycles".

Axioms of Conditionality

In order to specify exactly what the phenomenon of conditioning under the weak memory model refers to, we must determine exactly which events can influence the outcomes of which other events. First, consider our standard causal axioms : session guarantees These are four interrelated qualities reflecting the coherence properties of read and write operations occurring in different threads, and, moreover, they must be instantiated at the level of each object (cf. Fig. 23 in Burkhardt et al. ).

  • RYW (Read your notes): a read operation following a write operation, done in the same cell, within the same thread/replica/session, should read data no less relevant than a write. A variant of this property for distributed systems is specified solely in terms of visibility, whereas a variant for a weak memory model must rely on both read order and change order.
  • MR (monolithic reads): subsequent reads (within the same flow, in the same cell) must also see no less relevant data in the future.
  • WFR (read first, then write): if a write follows a read within the flow, in the same cell, it should go later than the read operation in the order of change.
  • MW (Monolithic writes): later writes (within a stream, to the same cell) must go later in the modification order.

Source versions of WFR and MW exist in two versions, for randomness and visibility; but this is only important when dealing with more complex data cells than registers for integers.
These properties reflect notions of conditionality consistent with our common sense; however, they leave out the most interesting part. In particular, when analyzed in a weak memorymodel, such conditioning phenomena are limited to the limits of the stream/replica/session and the particular cell/object where the recording is made : In the article by Burkhardt et al. .here refers to "object-by-object conditional visibility" and "object-by-object conditional arbitrariness, " also see Fig. 23. These phenomena do not limit the system behavior at all when different threads write information to different cells.
The axioms of cross-object conditionality then describe the effect of causality at the level of different objects/memory cells.

  • COCV (Cross-Object Conditional Visibility): same case as RYW, but without the condition that the final read must be done in the same thread/replica/session. Reads from an object, objectively later than writes to that object, must take data at least as up-to-date as what was written.

The C++11 specification reflects these properties. Note : they are defined in such a way that restrictions on write visibility and arbitrariness of the modification order do not affect these definitions too much.
But this does not apply to the last property.

  • COCA (Cross-Object Conditional Arbitrariness): similar to monolithic records, but applies to different threads, similar to how COCV is RYW for different threads. However, since the order of modification only affects single-object writes, the formulation for the weak memory model allows inconsistent distribution of write acts to different objects in the system, and writes may not correspond to either reads or order within a thread.

Specifically, COCA in a weak memory model is a much weaker property. This is why with a weak memory model, the following code can return {x ≡ 0, y ≡ 0}
Thread A: y := 0; x := 1; return x
Thread B: x := 0; y := 1; return y

The order within each thread can be inconsistent with the object-by-object order and the modification order. Note : with RYW there is no x := 0 → x := 1 In order of modification and for y – similarly; thus, the modification order must contain x := 1 → x := 0 and y := 1 → y := 0 Thus, the order of modification obviously forms a loop in the order of the threads.
Such a loop is allowed in COCA when the memory model is weak. It is not that the order of threads/reads contradicts the order of modification, but that each thread sees a consistent record history. These histories are consistent with the histories of other threads only if we object-bound their scope.

What does it all mean?

Time is fragmented.
Even though it seems to us that time flows in a perfectly orderly fashion, the study of distributed systems and the weak memory model demonstrates to you with all clarity that it does not. This is why, in both of these situations, our standard over-approximation, according to which time is total, limits performance–which we cannot afford.
Then, recognizing that time is indeed fragmentary, we discover many small but important differences between the varieties of such partiality. Even the two aforementioned fields, which seem so similar at first glance, in a multitude of subtle nuances allow us to distinguish what kinds of events under them are considered mutually influential.
It is necessary to go into more detail about the technical details of the various properties after someone has been able to express the properties of one field in the language of another.
Time is fragmented. Perhaps we just need to get used to it.

You may also like