Consistency vs. Availability in
Distributed Real-Time Systems* ^††thanks: ^* This work was supported by the iCyPhy Research Center at UC Berkeley, supported by Denso, Siemens, and Toyota.

It is clear that $\bar{C}_{ij}\geq 0$. If $\bar{C}=0$, we have strong consistency. We will see that this strong consistency comes at a price in availability, and that network failures can result in unbounded unavailability. If $\bar{C}$ is finite, we have eventual consistency, and $\bar{C}$ quantifies “eventual.”

Notice that inconsistency measures the difference between two logical times. We will show how Lingua Franca enables manipulation of the tags of events to relax consistency requirements in order to gain availability. It does so without sacrificing determinacy.

In database systems, unavailability, $\bar{A}$, is a measure of the time it takes for a system to respond to user requests [15]. A user request is an external event that originates from outside the distributed system. We generalize the external events to include sensor inputs, not just user requests, and the responses to include actuations.

Assume that a user request or sensor input triggers a read event in process $i$ with tag $g_{i}$ such that its timestamp $\mathcal{T}(g_{i})$ is the reading of a local clock when the external event occurs. Let $T_{i}$ be the physical time of the read event, i.e., the physical time at which the read is processed. Hence, $T_{i}\geq\mathcal{T}(g_{i})$.

Because we are considering only read events that are triggered from outside the software system, $\mathcal{T}(g_{i})\leq T_{i}$, so $\bar{A}_{i}\geq 0$. If $\bar{A}_{i}=0$, then we have maximum availability (minimum unavailability). This situation arises when external triggers cause immediate reactions.

We require that each process handle events in tag order. This gives the overall program a formal property known as causal consistency, which is analyzed in depth by Schwartz and Mattern. They define a causality relation, written $e_{1}\rightarrow e_{2}$, between events $e_{1}$ and $e_{2}$ to mean that $e_{1}$ can causally affect $e_{2}$. The phrase “causally affect” is rather difficult to pin down (see Lee [21, Chapter 11] for the subtleties around the notion of causation), but, intuitively, $e_{1}\rightarrow e_{2}$ means $e_{2}$ cannot behave as if $e_{1}$ had not occurred. Put another way, if the effect of an event is reflected in the state of a local replica of a variable $x$, then any cause of the event must also be reflected. Put yet another way, an observer must never observe an effect before its cause.

Formally, the causality relation of Schwartz and Mattern is the smallest transitive relation such that $e_{1}\rightarrow e_{2}$ if $e_{1}$ precedes $e_{2}$ in a process, or $e_{1}$ is the sending of a value in one process and $e_{2}$ is the acceptance of the value in another process. If neither $e_{1}\rightarrow e_{2}$ nor $e_{2}\rightarrow e_{1}$ holds, then we write $e_{1}||e_{2}$ or $e_{2}||e_{1}$ and say that $e_{1}$ and $e_{2}$ are incomparable. The causality relation is identical to the “happened before” relation of Lamport [17], but Schwartz and Mattern prefer the term “causality relation” because even if $e_{1}$ occurs unambiguously earlier than $e_{2}$ in physical time, they may nevertheless be incomparable, $e_{1}||e_{2}$.

The causality relation is a strict partial order. Schwartz and Mattern use their causality relation to define a “consistent global snapshot” of a distributed computation to be a subset $S$ of all the events $E$ in the execution that is a downset, meaning that if $e^{\prime}\in S$ and $e\rightarrow e^{\prime}$, then $e\in S$ (this was previously called a “consistent cut” by Mattern [29]).

To maintain causal consistency, the requirement that a process have nondecreasing tags means that, in a trace, a read or write event triggered by an external input may have a physical time $T$ that is significantly larger than its tag’s timestamp $\mathcal{T}(g)$. While $\mathcal{T}(g)$ is determined by the physical clock at the time the external input appears, the physical time at which the event is actually processed may have to be later to ensure that all events with earlier tags have been processed. This motivates the following definition:

The processing offset closely resembles the unavailability of Definition 2, but the former refers to write events and the latter refers to read events. The processing offset, by definition, is greater than or equal to zero.

When a write to a shared variable occurs in process $j$, some time will elapse before a corresponding accept event on process $i$ triggers a write to its local copy of the shared variable. This motivates the following definition:

Note that $T_{i}$ and $\mathcal{T}(g_{j})$ are physical times on two different clocks if $i\neq j$, so this apparent latency is an actual latency only if those clocks are perfectly synchronized. Unless the two processes are actually using the same physical clock, they will never be perfectly synchronized. Hence, the apparent latency may even be negative. Note that despite these numbers coming from different clocks, if tags are sent along with messages, this apparent latency is measurable.

The apparent latency is a sum of four components,

where $X_{ij}$ is execution time overhead at node $j$ for sending a message to node $i$, $L_{ij}$ is the network latency from $j$ to $i$, and $E_{ij}$ is the clock synchronization error. The three latter quantities are indistinguishable and always appear summed together, so there is no point in breaking apparent latency down in this way. Moreover, these latter three quantities would have to be measured with some physical clock, and it is not clear what clock to use. The apparent latency requires no problematic measurement since it explicitly refers to local clocks and tags.

The clock synchronization error can be positive or negative, whereas $O_{j}$, $X_{ij}$, and $L_{ij}$ are always nonnegative. If $E_{ij}$ is a sufficiently large negative number, the apparent latency will itself also be negative. Because of the use of local clocks, the accept event will appear to have occurred before the user input that triggered it. This possibility is unavoidable with imperfect clocks.

When $i=j$, $\mathcal{L}_{ij}=O_{j}=O_{i}$. The apparent latency at any node due to itself is just its processing offset.

The above definitions lead immediately to the following theorem:

This can be put in an elegant form using max-plus algebra [3]. Let $N$ be the number of processes, and define an $N\times N$ matrix $\Gamma$ such that its elements are given by

That is, from (5), the $i$, $j$-th entry in the matrix is an assumed bound on $X_{ij}+L_{ij}+E_{ij}$ (execution time, network latency, and clock synchronization error), adjusted downwards by the specified tolerance for inconsistency $\bar{C}_{ij}$.

Let $\bm{A}$ be a column vector with elements equal to the unavailabilities $\bar{A}_{i}$, and $\bm{O}$ be a column vector with elements equal to the processing offsets $O_{i}$. Then the CAL theorem (6) can be written as

where the matrix multiplication is in the max-plus algebra. This can be rewritten as

where $\bm{I}$ is the identity matrix in max-plus, which has zeros along the diagonal and $-\infty$ everywhere else. Hence, unavailability is a simple linear function of the processing offsets, where the function is given by a matrix that depends on the network latencies, clock synchronization error, execution times, and specified inconsistency in a simple way.

The processing offsets $O_{i}$ and $O_{j}$ are physical time delays incurred on nodes $i$ and $j$ before they can begin handling events. Specifically, node $i$ can begin handling a user input (a write event) with tag $g_{i}$ at physical time $T_{i}=\mathcal{T}(g_{i})+O_{i}$. In the absence of any further information about a program, we can use our $\Gamma$ matrix to calculate these offsets. However, the result is conservative because it does not use dependency information that may be present in a program (and is present in the Lingua Franca programs we give in the next section). A less conservative technique is explained below in Section V-B.

First, in the current implementation of LF, by default, logical time “chases” physical time, meaning that logical time never gets ahead of physical time. To model this, define a zero column vector $\bm{Z}$ where every element is zero. With this, we require at least that $\bm{O}\geq\bm{Z}.$ Note that, in general, this vector could be given negative numbers or even $-\infty$, in which case the federate may be able to advance logical time ahead of physical time, but this is not currently supported in LF, so we use a zero vector. In addition, to ensure that node $i$ processes events in tag order, it is sufficient to ensure that node $i$ has received all network input events with tags less than or equal to $g_{i}$ before processing any event with tag $g_{i}$. With this (conservative) policy, $O_{i}\geq\max_{j}(\mathcal{L}_{ij}-\bar{C}_{ij}).$ The smallest processing offsets that satisfy these two constraints satisfy

This is a system of equations in the max-plus algebra. From Baccelli, et al. [3] (Theorem 3.17), if every cycle of the matrix $\Gamma$ has weight less than zero, then the unique solution of this equation is

where the Kleene star is $\Gamma^{*}=\bm{I}\oplus\Gamma\oplus\Gamma^{2}\oplus\cdots.$ Baccelli et al. (Theorem 3.20 [3]) show that this reduces to

where $N$ is the number of processes.

The requirement that the cycle weights be less than zero is intuitive, but overly restrictive. It means that along any communication path from a node $i$ back to itself, the sum of the logical delays $D_{jk}$ must exceed the sum of the execution times, network latencies, and clock synchronization errors along the path. This implies that we have to tolerate a non-zero inconsistency somewhere on each cycle.

In practice, programs may have zero or positive cycle means. Theorem 3.17 of Baccelli, et al. [3] shows that if all cycle weights are non-positive, then there is a solution, but the solution may not be unique. If there are cycles with positive cycle weights, there is no finite solution for $\bm{O}$ in (10). In this case, the only solution to (10) sets all the processing offsets to $\infty$. Every node must wait forever before handling any user input. This is, of course, the ultimate price in availability.

Equation (11) is conservative because, absent more information about the application logic, we must assume that any network input at node $i$ with tag $g_{i}$ can causally affect any network output with tag $g_{i}$ or larger. For particular applications, it is possible to use the detailed structure of the Lingua Franca program to derive processing offsets that are not conservative, as we do below in Section V-B.

Lingua Franca (or LF, for short) [26] is a polyglot coordination language that orchestrates concurrent and distributed programs written in any of several target languages (as of this writing, C, C++, Python, TypeScript, and Rust). In LF, applications are defined as concurrent compositions of components called reactors [25, 24]. LF borrows the best semantic features of established models of computation, such as actors [2], logical execution time (LET) [14], synchronous reactive languages [5], and discrete event systems [19] including DEVS [36] and SystemC [22]. LF programs are concurrent and deterministic [18] (except when fault handlers are invoked). Given any set of tagged input events, there is exactly one correct behavior.

Fig. 1 gives a simple example that we use to explain the structure of an LF program and how it specifies availability and consistency requirements. This program defines a simple pipeline consisting of a data source, a data processor, and a data sink. The data source could, for example, poll a sensor and filter its readings. The data processor could use the sensor data to calculate a command to send to an actuator. The data sink could drive the actuator.

The diagram at the bottom of the figure is automatically generated by the LF tools given the source code at the top.¹¹1The diagram synthesis feature was created by Alexander Schulz-Rosengarten of Kiel University using the graphical layout tools from the KIELER Lightweight Diagrams framework [32] (see https://rtsys.informatik.uni-kiel.de/kieler). In later examples, we will show the diagram only and not the source code because the diagram contains sufficient information. The chevrons in the figure represent reactions, which process events, and their dependencies on inputs and their ability to produce outputs is shown using dashed lines.

Line 1 in the source code defines the target language, which is the language in which reactions are written, and the language into which the entire LF program is translated. This example uses the C target, which means that the bodies of reactions are written in C.

Line 2 declares a reactor class named Sense, which has an output port (line 3), a timer (line 4), a state variable (line 5), and a reaction (line 6). The output port has name out and type int. The timer has name t, offset 0 (meaning it should start when the program starts), and period 10 ms. The state variable has a name, type, and initial value. Each of these properties of the reactor is represented in the diagram at the bottom.

A reaction, like that on line 6, is defined with a syntax of the form

reaction($L_{1}$) $L_{2}$ -> $L_{3}$ {= code body =}

where $L_{1}$ is a list of triggers, which are inputs, timers, and actions (we will discuss actions later); $L_{2}$ is an optional list of observables, which are inputs and actions that do not trigger the reaction but may be read by the reaction; and $L_{3}$ is an optional list of effects, which are outputs, actions, and modes (which are not used in this paper).

The particular reaction on line 6 is triggered by the timer every 10 ms. When it is triggered for the $n$-th time, its logical time will be $t=s+n\times 10$ ms, where $s$ is the logical start time, typically set using the local physical clock when the program starts. The runtime system attempts to align logical time with physical time, so this reaction will be invoked roughly every 10 ms, but this cannot be done perfectly. By default, logical time “chases” physical time in a program execution, so that reactions with a logical time $t$ are invoked close to (but never before) physical time $T=t$.

A reaction may optionally have a deadline, as shown in the Actuate reactor class on line 14. This gives a time value and a code body to execute instead of the reaction if the deadline is violated. The time value may be a parameter of the reactor class but here is shown as the constant 10 ms. A deadline with time value $d=10$ms is violated for an event with tag $g$ if the reaction is invoked at a physical time $T$ where $T>\mathcal{T}(g)+d$. Such a deadline explicitly specifies an availability requirement. The deadline violation handler (line 15) is a fault handler. The LF runtime system uses an EDF scheduler to attempt to avoid violating this deadline, as usual in real-time systems.

The top-level (main) reactor is defined on line 25. Within it, reactor instances are created as on line 26 using the new keyword. If the main keyword is replaced with federated, then a separate C program is generated for each reactor instantiated within the federated reactor. Otherwise, a single multi-threaded C program is generated for the entire program. For the federated case, each instance is called a federate, and tagged inputs will arrive from the network at the input ports and be handled in tag order.

The routing of messages is specified by connections, as shown on line 29, which connects the output of i1 to the input of i2. Such a connection may optionally alter the timestamp of the message using the after keyword. The connection on line 29 specifies that the timestamp of the input event at i2 should be 10 ms greater than the timestamp at the output of i1. Such a logical delay explicitly relaxes the consistency requirements because it explicitly states that i2 can use information that is 10 ms out of date relative to i1.

We can see immediately that use of logical delays improves availability for this example, as expected from the CAL theorem. Suppose that this program is federated and that the three instances are mapped to distinct processors on a network. Were it not for the logical delays, intuitively, the Actuate reactor i3 would be unable to react until the message from the Sense reactor i1 had flowed through the network to i2, i2 had completed its reaction, and the result from i2 had flowed over the network to i3. If these delays add up to more than 10 ms, the i3’s deadline will be missed. With the logical delays, however, as long as the delays add up to less than 30 ms, the deadline will not be missed. If the delays add up to less than 20 ms, then i3 can react to its input with timestamp $t$ as soon as physical time $T$ matches or exceeds $t$. The specified tolerance for inconsistency improves availability.

This intuition can be made rigorous using the CAL theorem.

For the program in Fig. 1, the $\Gamma$ matrix is given by

where

• •

  $\Gamma_{21}=X_{21}+L_{21}+E_{21}-10\mbox{ms}$,

• •

  $\Gamma_{32}=X_{32}+L_{32}+E_{32}-10\mbox{ms}$,

and

• •

  $X_{21}$ is the execution time for the reaction in Sense,

• •

  $L_{21}$ is the network latency from Sense to Compute,

• •

  $E_{21}$ is the clock synchronization error from i1 to i2,

• •

  $X_{32}$ is the execution time for the reaction in Compute,

• •

  $L_{32}$ is the network latency from Compute to Actuate, and

• •

  $E_{32}$ is the clock synchronization error from i2 to i3.

The $-\infty$ entries in the matrix are a consequence of a lack of communication.

On the communication path from i1 to i2, there is a logical delay of 10 ms, which is an explicit declaration of an inconsistency $\bar{C}_{21}=10$ ms. The Compute reactor’s view of the data from the Sense reactor is 10 ms behind. We can now determine that this allowance of 10 ms of inconsistency improves availability compared to what we would get without it.

First, we can use the analysis of Section III-F to evaluate the processing offsets. For this example, $N=3$, so (12) reduces to

It is straightforward to evaluate this to get

Intuitively, this matrix captures the fact that the Actuate reactor indirectly depends on the Sense reactor, something not directly represented in the $\Gamma$ matrix.

We can now evaluate (11) to get

Next, we evaluate (9) to get the unavailability at each node,

In this simple case, the unavailability is equal to the processing offsets, which means that the processing offsets capture all the waiting that needs to be done to realize the semantics of the program.

These unavailability numbers are intuitive. First, note that the Sense can react to external stimulus immediately. It has no network inputs to worry about, so $\bm{A}_{0}=0$. The Compute reactor, however, can react to an input stimulus with timestamp $t$ immediately when physical time $T=t$ only if $X_{21}+L_{21}+E_{21}\leq 10\mbox{ms}$. Otherwise, in order to ensure that it processes events in timestamp order, it may need to wait until $T=t+X_{21}+L_{21}+E_{21}-10\mbox{ms}$. Similarly, the Actuate reactor can respond immediately if $\Gamma_{32}\leq 0$ and $\Gamma_{21}+\Gamma_{32}\leq 0$. These conditions occur if the 10 ms logical delay is larger than the apparent latencies in communication.

If we change line 29 to this subtly different version:

then there is no upper bound on the inconsistency between these two instances. The subtle change is to replace the logical connection -> with a physical connection $\small\mathtt{\sim}$>. In Lingua Franca, this is a directive to assign a new tag $g_{i}$ at the receiving end $i$ based on a local measurement of physical time $T_{i}$ when the message is received such that $\mathcal{T}(g_{i})=T_{i}$. The original tag is discarded. Such connections, therefore, have no effect on availability, but they completely abandon consistency.

Lingua Franca offers two coordination strategies for federated execution, centralized and decentralized [4]. The centralized coordinator is an extension of the High-Level Architecture (HLA) [12], a distributed discrete-event simulation standard. The decentralized coordinator is an extension of PTIDES [38], a real-time technique also implemented in Google Spanner [10], a globally distributed database. This coordinator is also influenced by Lamport [16] and Chandy and Misra [9, 30].

For the purposes of this paper, we only need to know how these coordination mechanisms relate to processing offsets and availability. The centralized coordinator is the easiest to understand. It does whatever is necessary to ensure that events are processed in tag order. In particular, execution in a federate will be delayed when such a delay is needed to ensure tag order semantics. As a consequence, the processing offsets and unavailability bounds emerge from an execution of the program. As network latencies vary, the offsets and unavailability vary. The CAL theorem tells what to expect these numbers to be, given network latencies. The programmer, therefore, can use the CAL theorem to determine whether deadlines will be met, given specific latencies.

The processing offsets and unavailability bounds play a bigger role when using the decentralized coordinator. In particular, with this coordinator, the programmer is required to specify a safe-to-advance (STA) offset for each federate. The choice of STA at federate $i$ can be guided by processing offset $\bm{O}_{i}$ for federate $i$, with the caveat that $\bm{O}_{i}$ is a property of a trace, whereas STA is a property of a program (a family of traces). The STA specified for a federate $i$ enforces $O_{i}$ during execution for all the traces produced by federate $i$. For particular reactions, the programmer can also give an additional safe-to-assume-absent (STAA) offset. STAA gives an additional time beyond the STA to wait before assuming that the absence of a message on a particular input means that there will be no message on that port with the current tag or less. The availability bound for any shared state read by that reaction can similarly guide the choice of STAA. Such guidance is much better than guesswork.

Both coordinators will deterministically execute the LF program identically, yielding the same behavior as an unfederated execution, under certain assumptions. For the centralized coordinator, the assumptions are that the network latencies are sufficiently low that no deadlines are missed. For the decentralized coordinator, the assumptions are that the network latencies are sufficiently low that events are seen by each reactor in tag order. In both cases, violations of the assumptions are detectable and can be handled by fault-handling code provided by the programmer.

The key difference between the two coordinators, therefore, is in their fault handling. When network latencies get large (or the network gets partitioned), the centralized coordinator sacrifices availability, whereas the decentralized coordinator sacrifices consistency. Which of these is the right choice is application dependent.

Note also that for both coordinators, the CAL theorem can be used to derive the requirements on network latencies, and therefore provides a principled guide for choosing networking technology and can guide refactoring designs to move computations between embedded, edge, and cloud computing.

Any assumptions about network latency may be violated in the field. In centralized coordination, such violations will manifest as deadline violations, whereas in decentralized coordination, they will manifest as consistency violations. In both cases, LF allows the programmer to specify exception handlers to be invoked when such violations occur.

Hence, for safety-critical CPS applications, the proposed framework promises some astonishingly attractive properties. First, a programmer can explicitly decide when and how much to give up consistency and when and how much to give up availability to accommodate execution times, network latency, and clock synchronization error. Second, the programmer’s specification will imply explicit constraints on the technology (networking, processing, and clock synchronization) that can be used to guide selection of parts to use and mapping of software components onto resources (embedded, edge, or cloud). Third, to allow for (inevitable) possible failures in the field, where specifications are not met due to unforeseen circumstances such as hardware failures, the programmer can explicitly give code to execute when the fault occurs.

We will show next how these principles can be applied through two complementary practical examples.

Consider an Advanced Driver Assist Systems (ADAS), as shown in Fig. 2. Such a system uses a camera with a computer vision system that analyzes images for pedestrians and applies braking when a pedestrian is detected, as shown in the photo. The figure shows the diagram synthesized from an LF program that shows the structure of this system. In this structure, there are two federated reactors, a Vision subsystem and a Braking subsystem. The structure is a pipeline similar to that of Fig. 1, except with a twist. Inside the Braking subsystem is a second sensor, which senses when a driver presses on the brake pedal. Both the camera and the pedal can affect the same actuator, which is driven by the Brake reactor.

The Vision federate has a time-triggered periodically invoked reaction that captures and analyzes an image. It then sends the results over the network to the Braking federate. The Braking federate has a local interface to a sensor on the brake pedal, represented in the diagram by the triangle with a “P” (which represents a physical action in LF). When the brake pedal is pushed, an event is generated that is assigned a time stamp from the local clock and triggers invocation of the reaction labeled “2” within the BrakePedal reactor.

Let the Vision federate be process 1 and the Braking federate be process 2. Then the $\Gamma$ matrix is similar to (13):

where

• •

  $\Gamma_{21}=X_{21}+L_{21}+E_{21}-10\mbox{ms},$

and

• •

  $X_{21}$ is the execution time in Vision to prepare the data to send to Braking,

• •

  $L_{21}$ is the network latency from Vision to Braking, and

• •

  $E_{21}$ is the clock synchronization error.

The logical delay of 10 ms on the communication path from 1 to 2 is an explicit declaration of an inconsistency $\bar{C}_{21}=10$ ms. The Braking system’s view of the sensor data from the Vision system is 10 ms behind. Using the same methods, the processing offsets and unavailability are similar to (14) and (15):

The allowance of 10 ms of inconsistency improves availability compared to what we would get without it. In particular, if $X_{21}+L_{21}+E_{21}\leq 10\mbox{ms},$ then the processing offsets and unavailability are all zero.

In Fig. 2, notice that the first reaction of Brake has a deadline of 3 ms. This deadline is as an explicit requirement for availability, stating, effectively, that we require

where $X_{22}$ is the execution time of reaction 2 in BrakePedal.²²2Note that LF implements an EDF scheduling policy, and that deadlines are inherited upstream, so reaction 2 of BrakePedal will have high priority. The requirement becomes

This requirement almost certainly means that the vision processing cannot be done in the cloud. If it is, then the deadline is likely to be violated. In principle, this analysis can be automated, so that a system designer simply enters the requirements (by specifying deadlines, communication paths, and consistency requirements), and the system provides feedback on the realizability of the requirements.

If the system designer really wants to do the vision processing in the cloud, then these results can be used to negotiate a service-level agreement, for example, with the 5G network vendor and the cloud service provider. Alternatively, the 10ms tolerance for inconsistency could be increased, although this would require an evaluation of whether the ADAS system continues to be able to do its job safely.

Once the requirements and assumptions are specified, then the next key decision is what to do when those assumptions are violated. For this application, missing the deadline could be disastrous, so we should emphasize availability over consistency. To accomplish that in Lingua Franca, we just have to specify to use decentralized coordination. With this coordination mechanism, if messages fail to arrive on time from the network, each local runtime system assumes there are no messages and continues accordingly. This will ensure that the brake pedal event gets handled as long as the Braking federate’s host computer is still working.

Consider autonomous or semi-autonomous vehicles that leverage communication with a roadside unit (RSU) to mediate access to a four way intersection. There are many projects working on such automation to improve traffic flow [31, 34]. A prototype is depicted in Fig. 3. This prototype uses a popular open-source vehicle simulator called Carla, which generates the animated image in the figure that gets updated as the program runs. The prototype is implemented using the Python target in LF, which enables easy integration of large legacy subsystems, such as Carla, that have Python APIs.

The LF program depicted in Fig. 3 consists of nine top-level components, four vehicle simulators, four vehicle controllers, and one roadside unit. The program uses a compact LF notation for banks of reactors and a multiplicity of communication channels. In this program, as a vehicle approaches the intersection, it communicates with the RSU, sending its kinematic state (position and velocity). The RSU handles competing requests for access to a single shared resource, the intersection, by granting time windows to particular vehicles during which they may use the intersection. This application represents a common pattern that occurs whenever distinct agents contend for access to a shared resource.

A key property of this application is that, very much unlike the ADAS example in Section V-A, consistency is far more important. All vehicles and the RSU must have a consistent view of the state of the intersection before any vehicle can enter the intersection. In other words, we prefer that vehicles stop (making the intersection unavailable) over having them enter the intersection without a consistent view on the state of the system, which could lead to a collision.

In LF, if we choose centralized coordination for the federated execution, the system will emphasize consistency over availability in the event of faults (violations of the assumptions and requirements). If messages from the network do not arrive on time, each federate stops progressing, which will prevent a vehicle from entering the intersection.

The contrast between the requirements of the intersection and ADAS examples demonstrates that tradeoffs between availability and consistency are application dependent. System designers should be able to make such tradeoffs in system requirements, and software needs to be designed so it responds to faults in coherence with the stated requirements. For the ADAS example, we need to sacrifice consistency, whereas for the intersection example, we need to sacrifice availability.

A second key difference between this intersection example and the ADAS example is that the program has communication cycles without logical delays. This changes how we do the analysis because we will no longer be able to use (11) to determine the processing offsets. Instead, we have to derive the processing offsets using more detailed information about the program structure. We now show how to do that.

The simpler LF program depicted in Fig. 4 has the essential structure of the intersection example reduced to the minimum that illustrates the issues. The $\Gamma$ matrix is

The finite non-zero entries are defined as before,

where, in this case, $\bar{C}_{ij}=0$ because none of the connections has a logical delay. To find the processing offsets, we use information that is evident in the LF program but not in the matrix. Specifically, note that any inputs that arrive at the inputs of the Sim reactors will have the same tag as an output produced by one of the two Sim reactors. Moreover, the two Sim reactors’ outputs are driven by timers with the same offset and period (zero and 16 ms), so these outputs are logically simultaneous. We now make a key assumption:

With this assumption, each Sim reactor will have completed processing all events with timestamp $t$ before it needs to advance to logical time $t+p$, where $p$ is the timer period. Recall that we are assuming that logical time chases physical time, so physical time has to advance to $t+p$ before the federate will even attempt to advance its logical time. At this point, it can safely advance its logical time immediately. Hence, the processing offset for both Sim reactors is zero if our assumption 1 is true.

The processing offset for the two Vehicle is easier to derive. It simply depends on the communication latencies, clock synchronization errors, and execution time bounds. The resulting processing offset vector is

We can now use (9) to calculate the unavailability:

We can now see that if the clock period is less than that top two entries in this vector, then assumption 1 will be violated, so this becomes a requirement.

These results are intuitive and correspond with observation when we run the federated LF program. Assumption 1 asserts that the period of the clocks is large enough that each period begins fresh without an accumulated backlog of unprocessed events. The execution will begin each period by advancing the logical time of each Sim federate to the next period as soon as physical time matches that logical time. The zeros in the first two entries of (18) tell us this is done without delay. The logical time of the two Vehicle federates, however, cannot be advanced until enough physical time has elapsed to allow for propagation of events from both Sim federates. This delay is represented by last two entries in (18).

As shown in (19), the unavailability of the two Vehicle federates matches their processing offset. This is not surprising because they each have only one reaction and that reaction reacts to both network inputs. However, the unavailability at the Sim reactors is larger than their processing offset. This reflects the fact that reaction 2 in each of the Sim reactors has to wait for the upstream Vehicle reactors to execute and for their results to propagate over the network. In other words, strong consistency—which lets actuation be logically simultaneous with the acquisition of sensor inputs—comes at the cost of a penalty in availability. The actuation is delayed in physical time, and, more fundamentally, the period with which sensing and actuation can be done has a lower bound that depends on the network delays.

Under centralized coordination, the actual values of all the $\Gamma_{ij}$ latencies are determined automatically at runtime as apparent latencies. If the program fails to keep up for any reason (e.g. network failures), then the centralized coordinator will preserve consistency; unavailability will rise and deadlines (if any are specified) will be missed. Fault handlers provided by the programmer can adapt the system accordingly. Moreover, in this case, assumption 1 becomes invalid, so the derived unavailability bound becomes invalid. Unavailability will exceed our calculated bound for such a trace and, in the event of total network failure, will grow without bound.

Under decentralized coordination, the programmer chooses numbers to the $\Gamma_{ij}$ latencies based on assumptions about network behavior and derives processing offsets (18) and unavailability (19). These then guide the choices of STA and STAA numbers specified in the program. At runtime, each federate proceeds on the assumption that the network latencies will be respected. If these assumptions are violated, then a reactor may see events out of timestamp order, in which case a fault handler will be invoked. If the network fails altogether, however, no reactor will see events out of timestamp order, and no fault handler will be invoked. Instead, each vehicle will act based on inconsistent information. Hence, with decentralized coordination, availability is prioritized over consistency when a fault occurs, which is the wrong choice for this application.