A dense metropolis is a complex traffic environment, and autonomous cars with a plethora of attached sensors still have limited situational awareness. Hence, holistic situational awareness of a cloud-connected vehicle is facilitated by 1) timely collection of sensory inputs from different sources (e.g., other vehicles, pedestrians, and smart city infrastructure sensors) , and 2) employing this sensor data to provide timely feedback or decision updates to participating mobile clients. For example, cameras at a smart-city intersection [1] can capture video or images of the intersection and send this data to a processing system at the edge. The system can then analyze the data to identify and inform potential public safety risks such as vehicles running red lights or pedestrians crossing the street outside of designated areas.
Although, it is possible that the system delivers source updates to interested clients using traditional synchronous request/reply communication paradigm, the rigid structure of such interaction renders the system inefficient for realtime decisions [2]. Publish-Subscribe (Pub-Sub) systems are an alternative communication paradigm that enables efficient and scalable communication among various components. The delivery of information from publishers to subscribers is decoupled, meaning that they need not be aware of each other's existence. For example, cameras can publish video frames to the system while a processing system subscribes to this data and uses it to make real-time decisions about intersection safety, such as adjusting the timing of traffic lights or alerting drivers to pedestrians in the area. A middleware (also known as a broker) acts as an intermediary to manage this distribution of information from publishers to subscribers.
The presence of different types of subscribers with varying time scales of operation in an edge computing system allows for flexibility and adaptability to different requirements and use cases. For instance, a real-time subscriber could be an analytics module that processes sensor data in real-time to detect anomalies or trigger immediate actions. On the other hand, a batch processing subscriber could be a processing module that handles a batch of sensor data collected over a certain time window to generate periodic reports or perform long-term trend analysis. Consequently, such heterogeneity requires decoupling subscribers from publishers.
In order to facilitate the required information dissemination, the data is pushed to the middleware from publisher. However, two complementary communication modes between middleware and subscriber exist: push and pull modes. Under the push mode, the subscriber passively receives information from the pub-sub middleware. In a pull-based approach, subscribers request messages from the middleware when they are ready to receive them, rather than waiting for the middleware to push messages to them.
There are pros and cons to both approaches. However, the pull mode is better suited for handling a diverse range of subscribers, without requiring a broker to determine the data transfer rate for each of them. Subscribers have more control over the rate at which they consume messages, making it easier to manage their individual needs [3].
Along with this, a real-time database system, acting as a middleware system, can support information dissemination between publishers and subscribers. With these design choices in mind, we present an analytical framework based on the publish-subscribe interaction paradigm, that is to be used for disseminating source updates to interested clients that process these source updates and arrive at decisions in a timely way.
Considered Problem: The freshness of status information received by subscriber plays an important role in decision making. In this work, we focus on a fundamental problem: What is the average Age of Information (AoI) [4] of decision updates that are computed from time-varying set of sensor data published in the databasefoot_0 ? We model a class of systems (see Fig. 1) in which two independent sources submit time-stamped updates to a writer that is responsible for publishing the source measurements as updates in the memory. A decision process (DP), as a subscriber, reads the pair of source 1 and source Fig. 1. A writer updates shared database with information fetched from two external sources. A decision process (DP) requests a reader process to read the pair of source updates from the memory. Monitors that track the age of source 1 and 2 updates in the memory are denoted •(1) and •(2) respectively; •(x(t)) tracks the age of max-age process in the memory, •(ŷ(t)) tracks the age of sampled max-age process, and •(ẑ(t)) tracks the age of computed decision updates at the external monitor.
2 updates from memory and derives a computational result, a decision update, from this pair that is delivered to a monitor.
Related Work: The issue of update timeliness using Age of Information (AoI) metric has been extensively studied; see the surveys [5], [6] and references therein. A majority of studies focus on analyzing the average AoI of different sources in single-server multi-source queueing models under different service policies [7]- [9].
More recently, there have been efforts to employ age optimization in diverse applications such as edge cloud processing for low-latency edge-assisted applications [10], [11], and timely mobile routing [12], [13]. Authors in [10] discuss a greedy traffic scheduling policy that selects the next processing request (job) that offers maximum age penalty reduction. [11] provides an analytical framework for the problem of optimizing frame rate and lag synchronization of server and player in a real-time cloud-assisted gaming application. Authors in [12], [13] study the effects of concurrency constructs on timely updating of shared data structures used in network software and how this, in turn, affects timely routing of information updates.
In previous works, the system models assumed a tightcoupling between the source and monitor. The primary goal was to maintain the status information of the physical process at the destination nodes. For instance, the just-in-time update policy [4] generated a fresh update instantaneously by the source, which started serving as soon as the current update in service was delivered to the destination node. Many works [14]- [17] have extended upon this idea and aimed to find optimal policies for determining sampling times and updating processes to minimize the Age of Information (AoI) at the destination node.
In publish-subscribe systems with decoupled producers and consumers, where producers use independent status updating policies, and consumers compute on this status information, a key open problem is to study optimal policies for minimizing the Age of Information (AoI) of computed updates. This work aims to study how the decoupling of publishers and subscribers affect the timeliness of updates computed from base set of sensor (source) updates.
In this work, we employ a model that captures the asynchronous operation of the writer and reader of updates in the shared memory Pub-Sub system. There are three aspects to the system depicted in Fig. 1: 1) writing the time-varying data received from two sources into the memory, 2) the arbitration between reader and writer to access memory, 3) reading the source data from memory and generating a decision update. We now give a brief overview of the writing, reading and decision computation processes.
We assume each source i 2 {1, 2} independently submits updates as a rate i Poisson process to the network and that these updates arrive fresh at the writer, i.e. with age 0. The write operations to memory have independent exponential (µ) service times. We model the writer as a buffer-less service facility with blocking discipline. Under this model, a source update arriving at the writer will be served only if the writer is idle; otherwise, the update is discarded.
Remark 1: In the present study, we investigate a computational regime characterized by relatively longer decision update times compared to the write times of any update in the memory. Our focus is not on regimes where writing to the memory is the overloaded process. Instead, we are primarily interested in examining the delays associated with computational processing. Whether we adopt a buffer-less or a queuing model, the impact of queuing at the writer is expected to be minimal.
We assume that arbitration between the reader and writer for the shared memory is facilitated by Read-Copy-Update (RCU) mechanism. RCU is a lock-less concurrency construct that allows concurrent forward progress for both reader and writer. [18]. RCU can be broadly described in two steps [19]: 1) To publish a newer version of a data item, the writer creates a copy of the RCU protected data item, modifies this copy with the newer version of this data item, and atomically replaces the old reference with a reference to this newer version. This publishing process runs concurrently with ongoing read processes that continue to read the old copy/version using the old reference. However, new read requests read the most recent version. 2) Since some readers in progress hold reference to "stale" data, the system defers memory reclamation of old data until after each reader in progress has finished executing its read-side critical section.
Remark 2: RCU read operations can be performed concurrently without any locks, allowing for high concurrency and low contention. This can be particularly useful in systems with multiple subscribers and few publishers. In combination, RCU and Pub-Sub can enable efficient and scalable communication where multiple components need to access and update shared data in a concurrent and asynchronous manner.
We view the decision process (DP) reader as one of many subscribers to the updates in the memory system. The DP reader becomes aware of fresher updates in the memory only when it chooses to query the memory for a fresh sample of the source update pair. We assume a reader can fetch the updates of both source 1 and source 2 from memory in negligible time 2 . With this assumption, the DP reader is an observer that is sampling the pair of source updates from the memory as a point process. Based on this sample, the decision process derives a decision update which is sent to the monitor, as shown in Fig. 1. The reader process fetches the next sample of update pair from the memory only after the computation in progress is completed.
When the DP reader's inter-sample times form a renewal process, this is an example of the model of renewal process sampling of updates introduced in [20]. In this model, the DP reader generates an age process ŷ(t) at the input to the DP that is a sampled version of the max-age process x(t) in the memory. Specifically, in the absence of a read, ŷ(t) continues to grow at unit rate. However, if the DP reader makes a read at time ⌧ , then ŷ(t) is reset to ŷ(⌧ ) = x(⌧ ). This update pair is then processed by the DP for a time T so that at time ⌧ + T a decision update with age ŷ(⌧ ) + T is delivered to the monitor. The age at the monitor, ẑ(t), is then reduced to ẑ(⌧ +T ) = x(⌧ )+T . At this time, the DP reader may choose to fetch a new sample pair from the memory, or it may choose to wait for a time W before fetching the next sample pair. When the DP reader employs non-zero waiting times, we say the DP is using a lazy sampling policy [16]. Fig. 2 illustrates the evolution of age processes x(t), ŷ(t), and ẑ(t).
We divide our AoI analysis into two stages: 1) We analyze the average age of updates in shared memory. 2) We analyze the additional delay induced by the decision process computations. First, section III presents a stochastic hybrid system (SHS) evaluation of the update age processes in the memory. For the system with sources i = 1, 2, we derive the stationary expected ages E[x i (t)] as well as the expected age of the maxage process x(t) = max(x 1 (t), x 2 (t)), .
In section IV, stage two of our analysis, we evaluate the age ẑ(t) of the decision update process at the monitor. The decision process is said to be sampling the source updates from the memory as it holds a sample of updates that were written to the memory. Even though the sampling and computation of the DP makes no attempt to use the age of its sampled updates to optimize its operation, we show that a lazy sampling policy will be able to reduce ẑ(t). Here we will see that analysis of ẑ(t) is separable from the prior SHS analysis of the maxage process x(t) in the shared memory. In particular, the AoI age
. Example AoI evolution of the max-age process x(t) at the memory, the sampled max-age process ŷ(t) with lazy sampling at the input to the DP, and the age process ẑ(t) at the monitor. The DP reader samples updates from the memory at times ⌧1, ⌧2, . . ., marked by H. Yi is the sampling period for sample i, Ti is the computation time for decision update based on sample i 1, and Wi is the waiting time to get the i th sample.
reduction afforded by lazy sampling can be applied to any stationary update age process that is sampled by the DP.
Let U i,1 , U i,2 . . . be the sequence of source i update publication times. At any time t, N i (t) source i updates have been published in the memory, and the most recent update is published at time U i,Ni(t) . It follows that the source i update process has age x i (t) = t U i,Ni(t) in the memory. Under this model, the update age x i (t) is reset to the write time W ⇠ exp(µ) when it is published at time U i,Ni(t) . When the writer writes a fresh source i update at time t 0 , the maxage process x(t) is reset to x(t 0 ) = x j (t 0 ), with j 6 = i. In the following, we use a Stochastic Hybrid System (SHS) to capture the evolution of update age processes in the memory.
To evaluate AoI of source updates, we use a Stochastic Hybrid Systems (SHS) [21] approach, a technique introduced for AoI evaluation in [22] and since employed in AoI evaluation of a variety of status updating systems [20], [23]- [29]. A stochastic hybrid system has a state-space with two components -a discrete component q(t) 2 Q = {0, 2, . . . , M} that is a continuous-time finite-state Markov Chain and a continuous component x(t) = [x 0 (t), . . . , x n (t)] 2 R n+1 . In AoI analyses using SHS, each x j (t) 2 x(t) describes an age process of interest. Each transition l 2 L is a directed edge (q l , q 0 l ) with a transition rate (l) in the Markov chain. The age process vector evolves at a unit rate in each discrete state q 2 Q, i.e., dx dt = ẋ(t) = 1 n . A transition l causes a system to jump from discrete state q l to q 0 l and resets the continuous state from x to x 0 using a linear transition reset map A l 2 {0, 1} (n⇥n) such that x 0 = xA l . For simple queues, examples of transition reset mappings {A l } can be found in [22]. For a discrete state q 2 Q, let
denote the respective sets of incoming and outgoing transitions. Age analysis using SHS is based on the expected value processes {v q (t) : q 2 Q} such that v q (t) = E[x(t) q,q(t) ], with i,j denoting the Kronecker delta function. For the SHS models of age processes considered here, each v q (t) will converge to a fixed point vq . The fixed points {v q : q 2 Q} are the solution to a set of age balance equations. The following theorem provides a simple way to calculate the age-balance fixed point and then the average age.
then the average age vector is
The age of updates in a shared memory system with bufferless service at the writer can be described by the SHS Markov chain and table of state transitions shown in Fig. 3. The continuous age state vector is x = [x 0 , x 1 , x 2 , x], where x 0 is the age of the update being written; x i , i = 1, 2, is the age of the source i update in memory; and x = max(x 1 , x 2 ). The discrete state is Q = {0 1 , 0 2 , 1, 2}. At time t, the system is in state 0 i if the writer is idle and the oldest update belongs to source i. State i 2 {1, 2} corresponds to the writer writing source i update.
We now describe SHS transitions enumerated in the table in Fig. 3. For each collection of transitions, we focus on the age state components that change.
• l = 1, 3, 4, 6: In system idle states 0 1 and 0 2 , the writer receives a new source update and initiates a new write mechanism. x 0 0 = 0 as the writer receives a fresh update, and x 0 1 , x 0 2 , x0 are unchanged as the update is not yet written to the memory.
• l = 2, 5: The writer finishes writing and publishes a new source update. l = 2 : the writer publishes source 1 update: x 0 1 = x 0 as the age of source 1 update in the memory is reset to just written update. The source 2 update becomes the oldest update in the memory; hence, x0 = x 2 . l = 5 : The writer publishes source 2 update: x 0 2 = x 0 , the source 1 update becomes the oldest update, and x0 = x 1 . For the SHS analysis, we employ the normalized rates
(3)
We note that ⇢ = ⇢ 1 + ⇢ 2 is the total offered load of source updates being written to the memory. The Markov chain in Fig. 3 has stationary probabilities ⇡ with normalization constant C ⇡ given by
With the shorthand notation
we now use Theorem 1 to solve for
where
We can now use Theorem 1 to calculate the AoI of source i update in the memory as
. Some algebra yields the following theorem.
Theorem 2.
(a) Source i updates in the memory have average age
(b) The max-age process x(t) = max(x 1 (t), x 2 (t)) in the memory has average age
Not surprisingly, the expected max-age E[x] is symmetric in the load parameters ⇢ 1 and ⇢ 2 . However, since the formula ( 9) is somewhat opaque, a plot of E[x] appears in Fig. 4. A possibly non-obvious observation from the figure is that increasing the overall updating load ⇢ generally improves the average max-age because the writer queues no updates. The figure also reveals that the average max-age is penalized by asymmetry in the update rates of the individual sources. This is in part because a source that updates slowly will have high age and thus cause the max-age to be large. However, it is also true that with asymmetric loads, the high rate source will cause updates of the low rate source to be discarded at the writer. Because the writer is non-selective in offering service, it may be performing updates for the high rate source even when the age of that source is already low.
In section II-C, we observed that the DP reader is sampling the source updates from the memory as a point process. In particular, we assume the inter-sample times Y 1 , Y 2 , . . . that are i.i.d continuous random variables identical to Y . In this case, the update sample times form a renewal process, and in the parlance of [20], the update age process ŷ(t) is sampling the max-age update process x(t) in the shared memory.
At time t, the most recent read from memory occurred at time t Z(t). That is, Z(t) is the age of the sampling renewal process. When the renewal process is in equilibrium, Z(t) is stationary with first moment [30,Theorem 5.7.4]
Next, following the approach in [20], we observe that the DP reader does not fetch any update in the interval (t Z(t), t]. Hence, at time t, the update age ŷ(t) satisfies
Further, Z(t) is independent of x(t) because the inter-sample times Y i are independent of the age processes in the shared memory. Thus stationarity of
. It then follows from (10) and (11) that ŷ(t) has expected value 3
3 A stronger distributional result is derived in [20,Theorem 6] that is not needed for the average AoI analysis here.
When the DP reader samples the shared memory, the DP then computes a decision update based on this sample. On delivery of a decision update to the monitor, the update age ẑ(t) is reset to the age of the oldest source update that was read and used to compute the decision update. This means that an arrival of decision update at the monitor at time t resets ẑ(t) to ŷ(t).
In this work, we assume that the decision computation times are i.i.d continuous random variables T 1 , T 2 , . . ., each identically distributed to T . We will consider a DP that performs lazy sampling: after delivering the computation to the output monitor, the DP reader waits for a random time W before reading again. The alternative to being lazy is the zero-wait policy, a special case of lazy when W = 0.
Fig. 2 depicts the evolution of the max-age process x(t) = max(x 1 (t), x 2 (t)), the status-sampling process ŷ(t), and the age at the monitor ẑ(t). with i.i.d inter-sample intervals Y 1 , Y 2 , . . . such that samples are taken at times ⌧ i = P i j=1 Y j . Under lazy sampling, we admit the possibility that the ith computation time T i and the ith waiting time W i are correlated. However, in order for the ŷ(t) process to be sampling the shared memory with independent inter-sample times Y i = T i +W i , we require that the pairs (T 1 , W 1 ), (T 2 , W 2 ), . . . to be i.i.d., identical to (T, W ). Under this assumption, it follows directly from (12) that the average update age at the input to the DP is
Curiously, (13) reveals that the problem of minimizing the average age at the input to DP appears to be isomorphic to the timely updating problem that was originally formulated in [16], [17], where the suboptimality of zero-wait policies was first identified. However, in this system, our objective is not to minimize E[ŷ] but rather to minimize the average age E[ẑ] at the monitor. Since ẑ(t) is penalized by the waiting time W , choosing W to minimize E[ŷ] may not be good for E[ẑ]. Fortunately, the following claim verifies this is not the case. Theorem 3. If x(t) is a stationary process, then for any waiting policy such that W i depends only on T i , the average age at the monitor satisfies
The proof appears in the Appendix. We observe that Theorem 3 can give one the mistaken impression that E[ẑ] is insensitive to the waiting time W . In fact, the theorem says that the waiting time W affects E[ŷ] and E[ẑ] identically. A hand-waving intuition is that ẑ(t) lags ŷ(t) only during the computation time T but, once the computation is complete, ẑ(t) = ŷ(t) during any waiting period.
Combining ( 13) and ( 14), we obtain an end-to-end characterization of the average age in the system:
Since the computation time T is given, (15) shows that the choice of a waiting function W as a function of T is the same problem formulated in [16], [17]. Hence the solution is the same, namely the -minimum waiting policy
where the parameter is chosen by numerical line search. With this policy, T + W = max( , T ) and it follows from (15) that the policy achieves end-to-end average AoI
For completeness, the effectiveness of waiting is demonstrated in section V by some numerical evaluations of the lazy sampling policy. We will see that lazy sampling becomes important when the variance of the computation time T becomes large. Before presenting these results, we comment on the connection of this lazy sampling model to the lazy updating model in [16], [17].
In [16], [17], the random variable T represented the delivery time of a fresh update (say through a network) to the monitor. Fresh updates were generated at will and W represented the waiting time prior to generating the next fresh update. A key element of this system was the tight coupling of waiting and update generation. In this setting, the intuition behind -minimum waiting was that if the prior delivery time was small, the age at the monitor would be small and it would be a waste of network resources to deliver an update when the age reduction afforded by the update would be small.
In this work, updates are generated by an exogenous process that is beyond the control of the DP. Moreover, because updates are disseminated through a shared memory publication process, the age processes of updates in shared memory are essentially uncoupled from the update sampling/processing policy implemented by the DP. In particular, any time the DP reader fetches a sample pair from the memory, the update age of that pair has expected value E[x], which is just the average age in the shared memory. Nevertheless, even though DP operation is uncoupled from the age process in shared memory, the -minimum waiting policy is effective. In particular, it reduces the expected value of ŷ(t), the age process at the input to the DP. What is happening is that the waiting policy mitigates the deleterious effect of high-variance computation times T on the sampling policy at the DP reader. We note that Theorem 3 went unrecognized in [16], [17]. Specifically, Theorem 3 shows that no matter what policy is used, the output always lags the input by E[T ] in terms of average age.
In this section, we examine some numerical examples of the performance -minimum waiting policy, simply to remind the reader of the benefits of waiting. Fig. 5 illustrates age performance with respect to variance in the computation time with probability distributions exp(1) (Fig. 5 Normal(1, e 2 1) (Fig. 5(b)). The log-normal distributed computation times T has PDF [31], f T (t) = e (ln(t) b) 2 /2 2 p 2⇡ t , t>0,
with free parameters b and > 0. In our numerical evaluations, we consider a given distribution on T such that the computation time is normalized to E[T ] = 1. In this regard, for Log-Normal distribution, for each , we set b = 2 /2 so that E[T ] = 1. By varying , we vary Var[T ] = e 2 1. These numerical results are largely similar to those in [16], [17]. In particular, the results remind the reader that zero-wait becomes increasingly sub-optimal when the computation time T has high variance. The choice of specifies a sampling rate
at the DP reader. We then plot the average age at the monitor as a function of . Because E[T ] = 1, the maximum update sampling rate is = 1, which corresponds to the zero-wait policy. As ! 0, the average age is increasingly dominated by the average inter-read time 1/ , because updates become too infrequent.
VI. CONCLUSION In this work, we focused on the problem of timely processing of updates from multiple sources. Specifically, we considered a model of a publish-subscribe system where a writer publishes updates from two independent sources in a shared memory and decision updates are derived by a decision process by reading from the memory. The decision processing is a subscriber that works independently of how the source updates are recorded in the memory. Even though the decision processing operates without knowledge of the ages of updates in the shared memory, its reading policy is still able to improve the end-to-end decision update timeliness.
We recognize that there could be other DP reading policies that exploit knowledge of the update age processes in shared memory to further reduce decision update age at the monitor; identifying such policies would be an interesting avenue for future research.
Another drawback of our system model is that when stale values are read from the shared memory, the DP will still perform its computations, even though the resulting DP update is not age-reducing. Effectively, the DP is waiting for a computation time before attempting to retrieve new updates from memory. Instead, it would be better for the DP to discard the stale updates and wait for an optimized time before reading the memory again. Analyzing such a model also remains as future work.
Going forward, we refer to the database as shared memory, or simply as memory.
This assumption is consistent with RCU reads being lightweight and fast, so that the heavier load is indeed induced by actual decision computation. Further, our model assumes that the DP reader fetches updates from the memory at some finite average rate such that the combined read request process of all subscribers does not overload the shared memory system.