Organizations function through the execution of various business processes. Non-conformant behavior in these processes impacts organizations negatively through implications such as reduced eficiency, lower quality, and compliance risks. Thus, it is important to identify non-conformant process behavior rapidly. While this is a challenging problem on its own, it is further complicated by the advent of big data, distributed systems, and a fragmented landscape of cloud- and on-premise tools that all provide data for the analysis of a business process and for determining its conformance. In such a landscape, it is common that events may arrive out of order. This complicates the conformance-checking analysis, which commonly expects events within a process to arrive in a specific sequence allowed by the process model. This paper introduces the first streaming conformance-checking method that incorporates event time awareness, thus having the ability to correct imperfections stemming from the out-of-order arrival of events. The method is scalable, utilizing the Beamline framework built on top of Apache Flink. Furthermore, the method includes an adaptive approach for handling various levels of out-of-order events in event streams. Experiments were conducted to demonstrate the applicability of the method for real-world use cases with diferent levels of out-of-order events. The results indicate that the method is well suited for identifying conformance in business processes that rely on a multitude of underlying systems for aggregating a holistic view of the process.
1 1 2 1 3 2 1
A
B
A
D
A
C
B
of-order data may overcompensate at times when events
arrive mostly on time and undercompensate when out-of- order event arrival [
The contributions of this paper are threefold: (1) a aggregations and joins of multiple streams within spestreaming conformance-checking approach capable of cific timeframes. In the presence of out-of-order events, handling out-of-order events, (2) a novel approach for windows need to be maintained and possibly entirely adaptive handling of event-time progress in business recalculated. An example of out-of-order event arrival process streams, and (3) lifting an existing state-of-the- in the context of windows, and a comparison between art approach to using Apache Flink, allowing for a truly event time and system ingestion time is shown in Figstreaming and scalable conformance checking solution. ure 2. In this example, aggregating based on windows
The rest of the paper is structured as follows: in Sec- would indicate an increasing trend if looking at ingestion
tion 2, we introduce the background, discussing out-of- time (3, 5, 6), while based on the event time, it is actually
order event arrival in data streams, business process char- a downward trend (7, 5, 2).
acteristics, and the current state of the art in streaming Since there is no limit on the potential delay of event
conformance checking. In Section 3, we discuss an ex- arrival, an additional concept called watermarks is used in
isting conformance-checking to be extended to handle data streams to keep track of event time progress and,
esout-of-order event streams. We look at how the method sentially, limit the number of windows [14]. This avoids
would handle out-of-order events and how the solution potential time lag due to outliers or faulty data that could
can adapt based on the frequency of out-of-order event stretch windows indefinitely. While commonly,
waterarrival. Section 4 describes the setting for running the marks are based on event time [
2.1. Out-of-order Event Streams Data analytics answers questions such as what happened
and when [15]. However, traditional data analytics does
Modern stream processing frameworks are designed for not generally consider data from a business process
viewanalytics that build upon recent data stream aggregates, point. Processes have a defined course of action and
especially in cases where real-time results are essential, constitute specific activities [
D B E
C
E
B E
B D C E
C
B
E
such as Petri Nets, Directly-Follows Graphs, and BPMN
models [
An example of the trie sampled from the process model in Figure 1 is shown in Figure 3.
The actual process executions are stored in event data.
Commonly, a single event contains attributes such as the case identifier (Case ID) , activity, and timestamp. All activities having the same case identifier make up a trace – a specific process execution instance. Events can be stored in static logs, called event logs, or in event streams, where each event arrives as it occurs in the real world.
Conformance checking is the examination of process
executions and quantifying the non-conformant
behavior compared to the behavior allowed by a process
model [
Traditional conformance checking is done on event
logs extracted from business systems. While such a static
approach is robust, it has some shortcomings; most
notably, the data is obsolete by design. Thus, several recent
research eforts have made conformance checking on
event streams viable [
log moves model moves
A A ≫ B
D D ≫ E
The work in [
While the initial prefix-alignment-based approaches
ofered guarantees on the exactness of the results, they
sufered from a relatively long latency, rendering the
applicability of the methods challenging for faster event
streams. Thus, new approaches have emerged recently.
In [
The IWS algorithm [
X E decay unprocessed time suffix - 3 | A arriving
events A 3 A
B C D E
A
A prefix alignment
X E 3 - 2 | A,X A 2 | A
B C D E
A X A X A X
X E - 1 | A,X,B A 1 X,B 2 | B
3 B C D E
A X
B A X B A >> B data structure to compare the event data to the expected repurposed to implement out-of-order handling into the process behavior. Due to the nature of business process algorithm, as will be described in the next section. executions, it may sometimes be necessary to re-calculate the optimal route in the trie, and due to erroneous activi- 3.2. Event Time Store ties, the method may end up on a wrong path in the trie.
Thus, the IWS approach uses a state bufer for keeping To handle out-of-order events, the algorithm is extended
some past states available for recalculation and a dis- by an event time store that keeps the event time of each
counted decay time hyperparameter to release old states arrived event. The event time store is an ordered
keyfrom memory. The decay time is calculated based on value pair, with the key denoting the event time and the
the diference between the average length from the root value being an array of events that occurred during this
to a leaf node in the trie, indicating a roughly average time. For simplicity, we assume that if events have the
expected trace length, and the current trace length. The same event time, the arrival order is the correct total
outcome is multiplied with the discounting factor, a value order of these events. In other words, the array denotes
between 0 and 1 to indicate the maximum percentage the arrival time of the events having this event time.
of the average trace length that should be kept in mem- Formally, assume that is the set of timestamps, ℰ is the
ory. For a more detailed explanation and formula, we set of events, and ℰ * is the set of all possible words over ℰ ,
refer to [
An example of the state bufer and the decay time are with a larger timestamp in the event store are considered shown in Figure 4. With the arrival of the first event, , out-of-order events and are piped for a new replay. Furtwo states are initiated, with the state at the root node thermore, any states in the state bufer that have played holding in its unprocessed sufix. The unprocessed out any out-of-order events are removed from the bufer, sufix is used to replay the moves upon the arrival of while the rest of the states remove the unprocessed sufix the next events. Decay time indicates how many events that matches the new sequence of events. within this trace should arrive before the state will be To illustrate, let’s consider an example of allowed becleared from memory. The optimal alignment at each havior as shown by the trie in Figure 3. event arrival is also shown. For event arrival , there Assume we observed events ⟨, , ⟩ with event are actually multiple optimal alignments, but only one timestamps of 1, 3 and 5, respectively. While this trace alignment is shown in the figure for illustrative purposes. could have multiple optimal alignments, for simplicity, Importantly, the state bufer allows the retraction of the assume we have the same alignment as in Table 2. false path traversal to node . This behavior can be If the algorithm now receives event with an event
A
B B ≫ B
D D D D ≫ ≫ E
B B would have events in order. Thus, the formula is applied globally to all traces within the process.
Table 3 In order to be truly scalable, the original algorithm and Comparison of event time aware and non-aware alignments. the extensions introduced in this paper are implemented on top of the Beamline framework [20]. The Beamline timestamp 2, it first checks the event store to see whether framework utilizes Apache Flink as the runtime engine, the events are arriving in order. The event store’s largest allowing the algorithm’s execution to scale across a cluskey (5) is larger than the arrived event timestamp (2). ter of computing nodes. Commonly, each individual trace Thus, all events with timestamps larger than 2 are con- in a business process is looked at separately. Thus, partisidered out-of-order, and all of the states in memory that tioning by the case identifier would theoretically allow have played out the events and are removed. The scaling of the processing to as many nodes as there are resulting alignment of the event time aware solution is cases within the process. shown in Table 3, with a comparison to the original non- The source code for the implementation, together with event time aware version that assumes all events arrive instructions for running the experiments and the datasets in order, leading to a higher conformance cost. used, have been made available on GitHub1.
The arrival of out-of-order events cannot be expected
to be static throughout the life of the stream. Thus, ap- 4.1. Setting
proaches in stream processing have been devised to adapt Several real-life event logs were used to test the handling
the watermarks based on concept drifts – changes in data of out-of-order events. The logs had to be manipulated
arrival frequency and delays [
To adapt to the stream’s frequency of out-of-order Then, events within a trace were swapped with various events, we extend the algorithm with the following settings ranging from no out-of-order events to fully outmethod to modify the discounting factor. With every of-order events (step 2). The settings are described in new event, we check if the event is out of order. If it is Table 4, showing the probability of a swap, i.e., how likely out of order, we assign it a boolean value of 1 and 0 if it a single event is to trade places with another event within is not. Then, we increase (or decrease) the discounting the same trace, and max distance, i.e., how far from the factor using the following formula: current position can an event be swapped to. For example, with the swap_01 setting, each event has a one percent = * + (1 − ) * likelihood of getting swapped with a maximum distance of one, meaning that it will trade places with the event directly before or after.
The unaltered sampled log was used for generating the trie – the process model that describes the expected behavior (step 3). Since the IWS algorithm is capable of streaming conformance checking, the experiments were also conducted in a streaming fashion using an MQTT broker. A Python script published the out-oforder logs to MQTT topics (step 4), and the algorithm
Where is the discounting factor, is the smoothing factor, and is the Boolean value of whether it is an out-of-order event. In our experiments, we found an alpha of 0.005 to represent an appropriate change in the discounting factor.
Intuitively, if the proportion of out-of-order events has increased, then the discounting factor will increase, thus keeping in memory a larger amount of states and allowing for improved out-of-order event handling. If the frequency of out-of-order events decreases, so too will the discounting factor, releasing the memory strain.
We consider it unlikely that any specific trace would start exhibiting out-of-order behavior while other traces 1https://github.com/DataSystemsGroupUT/ StreamingConformanceChecker 2https://doi.org/10.4121/uuid:3926db30-f712-4394-aebc-75976070e91f 3https://doi.org/10.4121/uuid:5f3067df-f10b-45da-b98b-86ae4c7a310b 4https://doi.org/10.4121/uuid:52fb97d4-4588-43c9-9d04-3604d4613b51 MQTT broker
6 Algorithm
Results file Original log 1 Sampled
log is a further order of magnitude slower than the nonadaptive method, with values of 1.89 ms/event for nonaware and 139.32 ms/event for the adaptive methods.
For the other datasets, a similar pattern can be observed. For BPI2017, the diference between non-aware and out-of-order handling methods is clear starting from _50, and for _99 the diference between nonaware and the adaptive method is almost three orders of magnitude. It can be observed that the execution time of the non-aware version of the algorithm does not increase with increased out-of-orderedness – this is because the algorithm does no recalculation for out-of-order event arrival and simply assumes that there is a great deal of non-conformant behavior occurring in the event stream.
For BPI2020 log, the results vary slightly more, with non-aware and non-adaptive versions being roughly equivalent for _50, and the adaptive method is faster than the non-adaptive method for _99. However, this may be due to the fact that this is the smallest of the datasets, as can be seen by the execution time remaining under 1-2ms per event. received the events by subscribing to these topics (step 5). The results of the experiments were outputted to a ifle on an event-by-event basis (step 6), measuring the latency of the algorithm – how long it takes to process an event – and the cost of the latest alignment of the case to where this particular event belongs to.
The method was instantiated with the default settings for the decay time variable: a minimum decay time () of 3 and a discounting factor ( ) of 0.3. The method was run with the adaptive add-on from Section 3.3 turned on (adaptive), turned of ( non-adaptive), and the out-oforder handling turned of ( non-aware, i.e., the original 4.2.2. Cost.
IWS algorithm). A core measure of a conformance checker is the cost. In
All experiments were executed three times and aver- this paper, we measure the cost of an alignment, i.e., simaged to mitigate possible runtime outliers impacting the ilarly to an edit distance diference between the expected results. The experiments were conducted on a machine process behavior and the actual observed behavior. The using Java 11 and Python 3.9. The MQTT broker used benefit of using an alignment is explainability, indicating was EMQX 5.1, which was run using Docker. clearly which part of the process contains the discrepancy. It is important to remember that the non-aware version 4.2. Results naively assumes that the order in which the events arrive is the order in which the events happened, thus nega4.2.1. Latency. tively impacting the alignment cost because the events were actually in the correct order but swapped. The cost results are summarized in Table 5, with color-coding from green (the best result) to red (the worst result) per log and swap variation.
An observation can be made that as the amount of swaps increases, the cost increases. This is true for all executions, except the adaptive algorithm on BPI2012 that slightly decreases cost for _99 compared to _50. This is due to the randomness of the out-oforderedness in the generated event data. In general, the cost increase is due to the fact that with the swaps, we have introduced superficial non-conformant behavior. As was shown in Table 4, the higher swap settings increase the likelihood and distance of an event displacement, thus having an increased amount of non-conformant behavior.
Comparing the diferent versions of the algorithm, it is clear that the non-aware version severely penalizes the out-of-order events. The diference between adaptive and non-adaptive versions is minuscule until _20, when the adaptive versions starts to outperform the nonswap_01 swap_05 swap_10 swap_20 swap_50 swap_99 swap_00 swap_01 swap_05 swap_10 swap_20 swap_50 swap_99 swap_00 swap_01 swap_05 swap_10 swap_20 swap_50 swap_99 adaptive version, and the _50 and _99 variations have an almost double the diference in cost, in favor of the adaptive version.
Based on the results, we can say that we have introduced a streaming conformance-checking approach capable of handling out-of-order events. Furthermore, it seems that the adaptive handling of event-time progress is well suited for adapting to an increased load of out-oforder event arrivals. In general, the introduced methodology seems to work well for handling out-of-order events, even for streams where the portion of out-of-orderedness is relatively high. As expected, higher amounts of out-oforder events impact latency negatively. At the same time, the cost is greatly improved compared to the original IWS algorithm, which is unaware of event time. For smaller business processes, such as BPI2020, the adaptive method has low latency even with extreme out-of-orderedness. However, with more complex business processes, such as BPI2017, the non-adaptive method may be more sensical from the latency perspective.
Some threats of validation include the fact that only a few datasets were used in this comparison. Furthermore, the out-of-orderedness had to be mimicked because no known process mining logs or streams that exhibit outof-order events are publicly available. The swap settings could be further investigated, as the probabilities and max distances could increase orthogonally, not in correlation.
One thing to address in future research would be the fact that if multiple events have the same timestamp, then the method should not blindly assume that the arrival order within the timestamp is correct. This is seen, for example, on the BPI2012 dataset, with many simultaneous timestamps. Having a method that would be able to ifnd the optimal solution from partial order would be a further improvement to the introduced approach.
Ultimately, as the results are positive, and the latencies are generally low for most experiments, we believe this method would be applicable for real-life use cases for running conformance checking on distributed systems.
This paper introduced an approach for handling outof-order event arrival in streaming conformance checking. To the best of our knowledge, this is the first conformance-checking approach that is aware of event time and, thus, is able to handle such stream imperfections. The contribution included a novel approach for adapting the event time progress based on the frequency of out-of-order event arrival. The approach was implemented using the Beamline framework built on top of adap.
non-adap.
non-aw.
adap.
non-adap.
non-aw.
adap.
non-adap.
non-aw. 0.0 1.6 6.0 13.7 24.9 44.9 48.7
This work was supported by the European Social Fund via "ICT programme" measure, the European Regional Development Fund, and the programme Mobilitas Pluss (2014-2020.4.01.16-0024).
Apache Flink, making the method easily scalable and able to handle large data volumes in stream processing.
Future research aims to look at handling partial order in event streams, as the current method assumes the arrival order for events having the same event time is the total order. Furthermore, a more extensive study could be done of the swap settings in event streams and their impact on out-of-order event handling. [18] K. Raun, M. Nielsen, A. Burattin, A. Awad, C-3PA: Streaming conformance, confidence and completeness in prefix-alignments, in: International Conference on Advanced Information Systems Engineering, Springer, 2023, pp. 437–453. [19] P. R. Winters, Forecasting sales by exponentially weighted moving averages, Management science 6 (1960) 324–342. [20] A. Burattin, Streaming process mining with beamline, ICPM Demos (2022).