Superpixel-based Domain-Knowledge Infusion in Computer Vision

Superpixels are higher-order perceptual groups of pixels in an image, often carrying much more information than raw pixels. There is an inherent relational structure to the relationship among different superpixels of an image. This relational information can convey some form of domain information about the image, e.g. relationship between superpixels representing two eyes in a cat image. Our interest in this paper is to construct computer vision models, specifically those based on Deep Neural Networks (DNNs) to incorporate these superpixels information. We propose a methodology to construct a hybrid model that leverages (a) Convolutional Neural Network (CNN) to deal with spatial information in an image, and (b) Graph Neural Network (GNN) to deal with relational superpixel information in the image. The proposed deep model is learned using a generic hybrid loss function that we call a ‘hybrid’ loss. We evaluate the predictive performance of our proposed hybrid vision model on four popular image classification datasets: MNIST, FMNIST, CIFAR-10 and CIFAR-100. Moreover, we evaluate our method on three real-world classification tasks: COVID-19 X-Ray Detection, LFW Face Recognition, and SOCOFing Fingerprint Identification. The results demonstrate that the relational superpixel information provided via a GNN could improve the performance of standard CNN-based vision systems.

Introduction
Deep learning, especially in the task of image classification and recognition has taken centerstage, mostly due to the introduction of ILSVRC challenge 1 . There have been significant architectural innovations for convolutional neural networks (CNNs). In the last few years, the core approach of basic convolution has been adopted to graph-structured data via the introduction of graph neural networks (GNNs) A graph is a representation of binary relations and GNNs can deal with these relational data. In the case of tasks involving images, binary relations can be easily seen at the level of 'image superpixels'. Superpixels are a higher-order perceptual groups of pixels in an image, often conveying much more information than low-level raw pixels and sharing some common characteristics such as intensity levels.
One can observe that the superpixels share a binary relation with their adjacent neighbours, resulting in a graph structure. Our present work deals with treating the relational information conveyed by the superpixels as domaininformation about an image and providing this information to aid in image classification tasks. It has been observed that incorporating domain knowledge can enhance the performance of deep learning systems [1]. In this work, we leverage spatial information from the image and infuse domain knowledge in the form of binary relations procured from the superpixel graph representation of the image. CNN filters tend to learn parameters based on pixel-level information. We hypothesise that fusing such superpixel-level information can provide a higher-level understanding of the image and aid a CNN in classification tasks. Specifically, we treat the graph resulting from the image superpixels as an input to a GNN and learn a CNN-based vision system together with the GNN. The coupled hybrid CNN+GNN system is expected to be knowledge-rich both at the level of raw pixels and at the level of superpixels.
The major contributions of our paper are as follows: (1) Treating superpixel representation of an image as a graph and allowing a GNN to extract higher-level domain information about an image; (2) We construct an image classification model by coupling the GNN with a CNN-based baseline; (3) We conduct a series of empirical evaluations of our coupled CNN+GNN hybrid system on four different popular image classification benchmarks and three case studies.
The rest of the paper is organised as follows. In Sec. 2 we provide details of our methodology including an introduction to loss suitable for learning the hybrid model. Section 3 provides details of our experiments. Section 4 provides brief description of related work. Section 5 concludes the paper.

Superpixel Graph Construction
Simple Linear Iterative Clustering (SLIC) [2] is a simple and easy-to-use algorithm requiring an input parameter: an approximate number of superpixels along with the input image, and outputs a segmented image. We use SLIC to construct the segmented version of the input image: each segmented patch in the image is now a superpixel. We then treat the centroid of every superpixel as a node in the graph. We link these nodes by building a radius graph [3]. For every pair of nodes, we form an edge between them if and only if the Euclidean distance between them is less than a pre-ordained radius, r. Mathematically, a radius graph is defined as

The Coupled CNN+GNN Model
Our main motive in this work is to learn jointly from the image and from its superpixel representation. This results in a complementary combination of a vision model (CNN) and a relational model (GNN). The CNN takes care of feature extraction (low-level features such as edges in initial layers to complex objects at the latter layers), while the graph-based model takes the superpixelbased radius graph and extracts relational information about the image that can act as domain-knowledge. A block diagram in Fig. 1 Loss Regardless of the detailed architectural specifics, the goal is to construct a representation of the input (image) that consists of both spatial information (extracted by the CNN) and the domain information (extracted by the GNN). This representation can then be used to construct a feed-forward fully-connected neural network that outputs a class label for the input image. In order to train the coupled model in an end-to-end fashion and utilise the information from the combined representation adequately, we propose a simple hybrid loss as follows: Here L C and L G denote the cross-entropy loss for CNN and GNN respectively. The tunable parameter α determines the relative importance of the two models during training, i.e., a value α = 0.5 would mean that both the raw spatial information and the domain information are equally important.
During prediction, we construct a hybrid logits from the logits computed by the CNN and GNN for an input image: where h C and h G are the logits from CNN and GNN respectively.

Aims
Our aim in this study is to integrate superpixel-level domain knowledge into vision systems, specifically those based on CNNs. Our empirical experiments attempt to answer the following questions: Can GNNs construct rich relational representations from superpixels? [RQ1]; Can GNN-constructed knowledge improve CNN-based vision systems? [RQ2]

Materials
We test our hypothesis on four popular benchmarks for image classification: MNIST, FMNIST, CIFAR-10 and CIFAR-100. Each of these datasets are supplied with official train-test splits. Additionally, we perform three case-studies: COVID-19 Chest X-Ray Detection 2 , LFW Facial Recognition 3 and SOCOFing Fingerprint Identification 4 datasets. For the LFW dataset, we discard classes with less than 20 faces. For all the domain-specific datasets, we do a stratified train-validation-test split in 80:10:10. We use the method described in Sec. 2.1 to construct superpixel-based radius graph for each image in these datasets. For convenience, we refer this as a procedure RadiusGraph that takes two inputs: a set of images and the number of superpixels (n), and returns a set of radius graph, each corresponding to an image in the input image-set.
We use the PyTorch library for the implementation of CNN and PyTorch Geometric for GNN models. We conduct all our experiments in the OVHCloud 5 using "AI Training" platform with following configurations: 32GB NVIDIA V100S GPU, 45GB main memory, 14 Intel Xeon 2.90GHz processors and a NVIDIA-DGX station with 32GB Tesla V100 GPU, 256GB main memory, 40 Intel Xeon 2.20GHz processors.

Method
Our method is straightforward. For each dataset D, We use the RadiusGraph(D, n) procedure to get graphs D for all the dataset images, where n is the approximate number of superpixels. Then, we split the dataset into train (D tr , D tr ) and test (D te , D te ) splits, such that D te are made of the images in D te . Then, we train CNN model on D tr , and the coupled CNN+GNN model on D tr , and compare their performances on respective test sets. The following details pertaining to the above steps are relevant: (1) We use n = 75 for MNIST and FMNIST, n = 100 for CIFAR, LFW and SOCOFing and n = 200 for COVID to construct superpixel graphs using RadiusGraph; the number of radial neighbours is set to 5 for MNIST, FMNIST and CIFAR datasets, 27 for COVID, 10 for LFW, and 15 for SOCOfing; This was decided using graph visualisation. (2) The node feature-vector for the radius graphs are: the normalised pixel value and the location of centroid in the image, resulting in 3-length feature-vector for MNIST and FMNIST, and 5-length feature-vector for CIFAR, COVID and LFW; (3) We use 90:10 split on D tr (correspondingly, D tr ) to obtain a validation set useful for hyperparameter tuning; (4) We use the AdamW optimiser [4] for training all our models; (5) The hyperparameters are obtained by a sweep across grids such as batch-size: {128, 256}, learning rate: {1e-3,1e-4,1e-5}, weight-decay parameter: {0, 0.001} for MNIST, FMNIST, CIFAR datasets. For other datasets, we use the best parameters obtained during MNIST/FMNIST/CIFAR grid-search; (6) CNN structure is built with 3-blocks; each block consists of a convolutional layer, a batch-norm layer, ReLU activation and a max-pool layer. The number of channels in each convolution layer is 32, 64 and 64, respectively; (7) The coupled CNN+GNN structure consists of the same CNN backbone as mentioned above; and a GNN structure consisting of three graph-attention layers with 32, 64 and 64 channels, respectively, and the number of heads is 1; (8) The value of α is set to 0.75 for all our experiments; (9) We use accuracy as the metric to measure the predictive performance of the models on D te .

Results
In all our experiments, the primary intention is to show whether relational information provided via a superpixel graph is able to aid in improving the performance of a CNN-based model. One should note that the primary backbone of the CNN in the standalone model (CNN) and that in the coupled model remains the same to draw any meaningful conclusion. The principal results of our experiments are reported in Table 1. The results demonstrate that the higherlevel domain-knowledge extracted by a GNN from the superpixel graph is able to substantially boost the predictive performance of CNNs in a hybrid-learning setting in some cases.

Related Work
Various graph-based learning approaches for superpixel image classification can be distinguished based on how they perform neighbourhood aggregation. In MoNet [5], weighted aggregation is performed by learning a scale factor based on geometric distances. They also test their model on the MNIST Superpixels dataset. In Graph Attention Networks (GATs) [6], self-attention weights are learned. SplineCNN [7] uses B-spline bases for aggregation, whereas SGCN [8] is a variant of MoNet and uses a different distance metric. Preliminary work on enhancing Semantic Segmentation Vision-based systems using superpixel representations has been done. Mi et al. [9] propose a Superpixel-enhanced Region Module (SRM), which they train jointly with a Deep Neural Forest. The SRM alleviates the noise by leveraging the pixel-superpixel associations. In DrsNet [10], coarse superpixel masking and fine superpixel masking are applied to the CNN features of the input image, particularly for rare classes and background areas.
In our work, we demonstrate that superpixels graphs represent domain knowledge for images and that infusing this knowledge in a standard vision-based training process shows significant gains in accuracy. We are able to conclude that a GNN can deal with relational information conveyed by a superpixel graph and can construct high-level relations that could boost the predictive performance when coupled with a CNN model. A straightforward extension is to employ a pre-trained CNN model for domain-specific tasks and observe how the superpixel information impact the predictive performance. Our code repository is available at: https://github.com/abheesht17/super-pixels.


Traquest Model — A Novel Model for ACID Concurrent Computations∗

Atomicity, consistency, isolation, and durability are essential properties of many distributed systems. They are often abbreviated as the ACID properties. Ensuring ACID comes with a price: it requires extra computing and network capacity to ensure that the atomic operations are done perfectly or they are rolled back. When we have higher requirements on performance, we need to give up the ACID properties entirely or settle for eventual consistency. Since the ambiguity of the order of the events, such algorithms can get very complicated since they have to be prepared for any possible contingencies. Traquest model attempts to create a general concurrency model that can bring the ACID properties without sacrificing a too significant amount of performance.

Introduction
In the case of the microservices architecture [5] when we send a request, it can initiate some modifications in the global state in a transactional way. Microservices are mainly based on the request-response model. When the Request returns with no errors, that means the modifications in the global state are done, and the transaction is over. While if the response is an error, that means there were no modifications in the global state at all. Requests can make other requests, and more complex transactions can be assembled.
In a request-response model, the ACID properties come at a high price. The service which calculates the response has to guarantee that any write operations arising must be synchronized, committed, and persisted before it can reply with a response. Of course, on the other hand, if ACID is not a requirement, the service can be very fast. In this case, the service can just read and write the state of the local server and answer to the client immediately. Later, the server can synchronize the writes if eventual consistency is a requirement, but this does not block or decelerate the original process.
However, it is not just the performance that can cause a problem. It is very challenging to ensure atomicity itself when we nest the services. Figure 1 shows a scenario where we have service A calling two other services, B and C. The order of the network events is marked on the figure. The client sends a request to service A, which sends requests to service B and C. Service B responds correctly, but C responds with an error. In this case, we can assume that C has rolled back correctly, but B should be rolled back as well. There is no mechanism to roll back a request in the request-response model after it has been responded. Therefore it is hard to chain more services properly when atomicity is a requirement. We can be sure to have a proper response if the happy path happens, but if there is an error arising at some of the chained requests, our system can get easily stuck into an invalid intermediate state.
It seems there is a hard dilemma between ACID properties and efficiency. The proposed Traquest model attempts to resolve this dilemma and therefore improve the efficiency of the ACID systems.
The phrase Traquest [28] comes from the words Request and Transaction. The core of the idea comes from the microservices architecture, and the Traquest model is something similar to the request-response model. We can send requests to a Traquest, and the Traquest replies with an answer, but here the answer is not a simple response message, but rather an established parent-child connection between the two Traquests with a temporary response, a so-called Trasponse. When a Traquest gets a request, it can immediately carry out read and write operations on the local server. It can immediately reply with a Trasponse; however, of course, that still might take time to synchronize the effects of the operations with other servers. Therefore Trasponse is only a temporary response.
Before creating the Traquest model, we have examined many of the existing technologies and solutions, including multitier architectures, actor model based systems, different consistency protocols, and different papers discussing the limitations of distributed ACID systems. We have found that the current systems have the strict limitations we described above. We decided to investigate whether it is possible to create a system based on the idea that a response can have a temporary nature. The Traquest model was realized during this research process.
We created the concept of the Traquest model, and we also built an experimental prototype in TypeScript. Adjustments on the model might become necessary later as further, and more comprehensive implementations will be created in different programming languages. However, the current results show that the general concept of the Traquest model is viable. Traquests can provide ACID computations using magnitudes fewer network messages in some concurrency scenarios than the current technologies.
This paper is structured as follows. In Section 2, we give an explanation of the Traquest model. In Section 3, we discuss some state-of-the-art solutions and how the current technologies were used to solve problems related to the ACID properties. We explain further the Traquest model through an exemplary case and compare it to the current technologies. In Section 4, we will highlight the current challenges and further research directions. Finally, this paper concludes in Section 5.

The Traquest model
The request-response model is used on a local level as well and not only between different computing nodes. Asynchronous callback functions can behave equivalently. We can send the request content and the callback function as an argument, and the callback function can contain the response in an argument. This mechanism is often used to wrap network-based request responses, but for local asynchronous operations as well.
However, callbacks can get complicated when they are heavily used, and we want to handle exceptional scenarios. To this end in computer science, Future, Promise, Delay, and Deferred refer to constructs used for synchronizing program execution in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially unknown, usually because the computation of its value is not yet complete. The term Promise was proposed in 1976 by Daniel P. Friedman and David Wise [9] and Peter Hibbard called it Eventual [16]. A somewhat similar concept Future was introduced in 1977 in a paper by Henry Baker and Carl Hewitt [3].
Traquests behave most similarly to Promises; therefore, we use them as a baseline for the explanation. Traquests, just like Promises, are placeholders for a temporarily unknown value. Traquests, just like Promises, can be nested and depend on each other. However, once a Promise returns with a response, this response is final, and it cannot be modified afterwards. On the other hand, Traquests can be strongly bonded together to form a tree structure, a so-called Traquest tree. A Traquest tree creates the transaction, and if any Traquest fails in the Traquest tree, all the Traquests are failing. When the Traquests are failing, they are not just returning an error, but they are ensuring that if they created any modification, it would be appropriately rolled back so that the global state of the system will not be affected by half-done transactions. To be able to achieve this, Traquests are containing some additional mechanisms.

Structure
To understand how Traquests are working, first, we need to see the fundamental structure of the state of art Promises. Figure 2 shows the fundamental structure of Promises. Deferred describes a yet unfinished work which is the asynchronous process that has to be done to get the final value of the Promise. A Promise belongs to a Deferred. When the Deferred finishes, it can call different resolvers depending on whether the execution was successful or some exceptions were arising. If the execution was successful, the Deferred calls the Resolve resolver; otherwise, it calls the Reject resolver. The Promise itself is the placeholder of the yet unknown value. It has two handlers to handle the event when the unknown value becomes known. The Then handler is responsible for handling the successful resolution of the Promise, and the Catch handler is for handling the exceptions. Figure 3 show the fundamentals structure of Traquests. A Traquest also belongs to a Deferred that, similarly to Promises, describes a yet unfinished work. Traquests have handlers just as Promises to handle the event when the Deferred returns. However, Traquests has a third significant component as well, the Binding mechanism. The binding can permanently bind together Traquests in a parent-child tree structure. This binding holds until the whole atomic transaction finishes. Like that, a Traquest tree can act as a single entity, and it can form a complete atomic transaction, which can be distributed to many computing nodes. The Deferred has the following resolvers. The Response resolver is the same as the Resolve resolver at the Promises. This should be executed when the asynchronous Deferred process successfully finishes with the proper value. The Mistake resolver is slightly different from the Reject resolver of the promises. The Mistake is called when a temporary failure happens. If there is a chance that the failure has occurred only because of the wrong order of the asynchronous operations, then Mistake should be triggered. Mistakes can be undone later, and the Traquests might rerun in proper order. The Terminate resolver is used in case of final failures. This resolver terminates the whole Traquest tree and tries to roll back all the Traquests in the Traquest tree.

Traquests
The Then handler is the same as the Then handler of the Promises. The Catch handler is similar to the Catch handler of the Promises, but it is used explicitly for the mistakes. It can also avoid spreading up the Mistake to parent Traquests or let it spread further. The Finally handler is called no matter if the Traquest was properly committing or it was terminated.
The Binding mechanism of the Traquests has the following concepts: Parent-child binding -When a Traquest had been created, the reference to the parent Traquest should be defined. If it is not defined, that means the created Traquest will be the root of the Traquest tree.
Undo -A mistake happens when an exception occurs because the Traquests are executed out of order. However, it can happen that the Traquest has already responded with a seemingly correct response, and an out-of-order conflict turns out only later. In this case, an undoing mechanism can be executed, which rolls back the necessary Traquests on the affected branch of the Traquest tree and re-executes them.
Rollback -A callback is provided for the case when the Traquest needs to revert the changes it has made so far. If the Traquest did not create any changes directly to the global state, just by calling other Traquests, this part could be omitted because the rollbacks spread automatically on the Traquest tree.
Finalizing -It is a mechanism used when all the Traquest in the tree have returned, and the result of the Traquests can be finalized. This happens completely hidden and automatically when all the Traquests in the tree have returned.
Committing -It is a mechanism used when all the Traquests in the tree have been finalized, and a final commit can be initiated. This happens completely hidden and automatically. The Committing mechanism combined with the Finalizing mechanism gives a similar process to the two-phase commit protocol [35]; however, there are differences because the Finalizing and Finalized states are handling the potential rollbacking Tail Traquests as well.

States
Promises and Traquests have different states throughout their life-cycle, which describes their behaviour. Figure 4 is a state diagram that shows the possible states of a Promise. In the case of the Promises, we have three very simple states. We have an Unfulfilled or Pending state while the Deferred process is running, and the Promise value is not known. From this state, the Promise can step only to Fulfilled or Rejected state. This happens when the Deferred process finishes depending on whether an exception was arising or not.   shown here, only the most relevant ones which are necessary to understand the working mechanism of the Traquests. In Figure 5 the explanation for the state transition prefixes are the followings:

Promises
• AC: Automatically triggered by the child Traquest • AP: Automatically triggered by the parent Traquest • AT: Automatically triggered by the current ("this") Traquest • No prefix: Manually triggered in the Deferred process As one can see, Traquests are much more complex and have much more states than Promises have. However, Traquests have only two main manual resolvers, just like the Promises. When we have nested Promises, and an exception occurs, we should ensure manually that the proper Reject resolver is called, and it is handled at the parent Promise [31]. Furthermore, the parent Promise should manually escalate the exception further by calling its own Reject resolver. Traquests, on the other hand, are bound together and escalate the Mistakes automatically. A traditional exception in the Deferred process can be automatically converted into a Mistake, or a Mistake can automatically come from a child Traquest. In either case, no manual intervention is needed. Most of the time, it is enough to define only the happy path in a Deferred process and call the Resolve resolver. Interestingly this means that even though Traquests are more complex than Promises, still using Traquests can be even more convenient. To understand more how Taquests work, let us investigate them state by state in more detail.
Waiting state: The Waiting state is the initialization state of the Traquest. In this state, the Traquest gets initialized by defining the Deferred process belonging to it. The Deferred process is not added automatically to the event-loop like in the case of the Promises [20]; instead, it has to be manually executed. During the execute call, we need to provide the parent Traquest optionally. If the parent Traquest is missing, the current Traquest will be the root of the Traquest tree; therefore, the current Traquest will represent the overall transaction.
Executing state: When the execute method is called on the Traquest, the Traquest begins to execute the Deferred process, and it steps into the Executing state. During this state, the Deferred process can create new child Traquests and bind them to the current Traquest. The transaction can grow this way recursively.
During the execution, the Traquest can be interrupted by parent or child Traquests. The interruption happens if a Mistake arises at the ascending or descending Traquests. If a parent Traquest has a Mistake, that means the current Traquest should be ignored, including its children. Therefore if the parent Traquest triggers an undo operation on the current Traquest, it changes its state to Undoing, and triggers an undo operation on all the descendant Traquests.
If a Mistake is coming from one of the children of the current Traquest, that means that the Mistake is still not escalated to upper levels in the Traquest tree, and the Traquest can try to re-execute itself. In this case, the Traqest steps into the Restarting state.
The Mistake can come not only from the bounded Traquests, but it can also happen locally in the Deferred process of the current Traquest. In this case, the Traquest should roll back its changes; therefore, it has to switch into Undoing state.
Suppose no Mistakes are coming from the bounded Traquests, and the current Traquest is not running into a Mistake either. In that case, the Deferred process should call the resolve operation with the proper resulting value when it finishes. When the resolve operation is called, that means the current Traquest has completed its desired asynchronous task, and it can respond with the required value; therefore, the Traquest should step into the Responded state.
Responded state: The Traquest can get into the Responded state only from the Executing state by the Deferred process calling the Resolve resolver. Before stepping to the Responded state, the Traquest sends the result value coming from the Resolve operation to the handler of the Traquest. The handler executes the callbacks bounded to the Traquest by the Then operation right after the Traquest steps into the Responded state. However, there is one exception. If the current Traquest is the root of the Traquest tree, then no handlers are called, and the Traquest steps into the Finalizing state immediately.
Otherwise, the Traquest waits in the responded state until the parent Traquest asks for a commit, or a Mistake is coming from any of the bounded Traquests. Parent Traquests obviously can still be in execution when the current Traquest responds. However, for synchronization purposes and keeping the system's overall consistency, children Traquests can still be in Executing state as well. We discuss this scenario in more detail in Section 2.6. This means that a Mistake can trigger an undo operation from any direction. When an undo operation is called on a Traquest, which is in a Responded state, it should not be able to commit anymore.
If no Mistakes are coming from any of the bounded Traquests, then the current Traquest waits until it gets a finalize operation from the parent Traquest. The Traquest can and should trigger a finalize on itself only if the current Traquest is the root Traquest.
Finalizing state: When a finalize operation is triggered on a current Traquest by the parent Traquest and the current Traquest is in the Responded state, the current Traquest switches to the Finalizing state and calls the finalize operation on its child Traquests. If there are no child Traquests, the current Traquest steps into Finalized state and sends an ackFinalize operation to the parent Traquest.
If the current Traquest is still in Executing state, it makes no action. In this case, when the Deferred process returns, the parent Traquest calls again the finalize operation on the current Traquest; hence the finalizing mechanism can continue. This scenario happens with the Tail Traquests, which we will discuss later in more detail.
An Undo operation can come from any bounded Traquests during the Finalizing state.
Finalized state: The Traquests step to Finalized state when they get an ackFinalize acknowledgement from all of their children. If the Traqest steps into the Finalized state, it calls an ackFinalize operation on its parent. If it has no parent -meaning that the current Traquest is the root of the Traquest tree -the Traquest steps in to Committing state and sends a commit operation to all of its child Traquests.
Undo operation can come only from a parent Traquest during the Finalized state because this state means that no descendant Traquests are being in Executing state, which could serve as a root for launching the undoing chain.
Committing state: When a Traquest steps into the Committing state, it triggers a commit on its child Traquests and waits until it gets an acknowledgement from them. When all the children have responded with an acknowledgement using the ackCommit operation, the Traquest steps into the Committed state. If the Traquest has no children, it immediately steps to the Committed state without waiting for any other processes or Traquests.
Traquests cannot roll back if the Traquest has already stepped into the Committing state.
Committed state: When a Traquest gets acknowledgements from all the child Traquests, it steps into the Committed state. The Committed state is a final state, meaning that the life-cycle of the Traquest was finished.
At the Response state, we discussed that if the current Traquest is the root Traquest the callbacks bounded to the handlers are not called. The root Traquest calls any handlers only at the end of its life-cycle. Therefore, when the root Traquest enters the Committed state, it calls the callback bounded to the Then handler, responding the final result of the whole transaction.
Undoing state: When a Traquest enters the Undoing state, that means that all the modifications in the global state done by the current Traquest or its descendants should be rolled back. Traquests can enter the Undoing state from almost any state. The exceptional states are the Waiting, Committing, Committed, Ignored, and Terminated states. From Waiting, there would be no point in entering the Undoing state since without executing the Deferred process, there cannot be any modifications to be rolled back.
The Committing state is already part of the committing process. Here all the temporary values are finalized. Suppose any errors are happening at this phase. That means a more serious issue that can affect the consistency. Therefore rolling back cannot be an option from the Committing state.
The Committed, Ignored, and Terminated states are the final states of the Traqest, and they cannot be rolled back. In all the other states, except the five states mentioned above, stepping to the Undoing state is possible.
Stepping to the Undoing state can be triggered manually in the Executing state, during the execution of the Deferred process -we can use the mistake operation for this purpose -or it can be triggered automatically by the bounded Traquests. The bounded Traquests can use the undo operation for initiating a rollback and trigger the current Traquest to step into the Undoing state. However, when the current Traquest is still in Executing state, and an undo operation comes from its child, the Traquest can still be re-executed, and in this case, the Traquest will step into the Restarting state.
Traquests can spread up the undoing chain even if they already have responded. This is important because the undo operation means that the responded value is not valid anymore; therefore, the parent Traquest, which already consumed this value, should be conflicted.
Ignored state: The Traquest steps into the Ignored state from the Undoing state when it has finished calling all the undo operations on its bounded Traquests. The Ignored state is a final state, and it means the life-cycle of the Traquest has ended.
Restarting state: When the current Traquest gets an undo operation from its child Traquest while the current Traquest is still in the Executing state, the Deferred process of the current Traquest should be re-executed. In the Restarting state, an undo operation is called on each of the child Traquests, the rollback callback is called for the current Traquest -if it was defined -to roll back every state change that has been made so far. When the rollbacks are finished, a reExecute operation is called on the current Traquest, which sets back the state of the current Traquest to Executing, and re-executes the Deferred process.
Terminated state: The Terminated state was not discussed in depth so far, and it is missing from Figure 5, because it implies high complexity. Figure 10 in the Appendix shows all the possible states and state transitions a Traquest can have, including the Terminated state. The Terminate state can be initiated by calling the terminate operation of the Traquest. The Terminated state means that an unsolvable error has happened, and the system's consistency cannot be guaranteed.
When a Traquest enters the Terminated state, it tries to roll back itself and calls the terminate operation on all its bounded Traquests.

Timestamps
Traquests contain a logical timestamp of their creation to be able to resolve conflicts. The timestamp of a Traquest inherits all the timestamps of the ascendant Traqests. This means that the timestamp of a parent Traquest represents the logical time of its whole branch when compared with Traquests from other branches. The timestamp of an ascendent Traquest is always earlier than the timestamps of descendant Traquests. The order of the sibling Traquests is decided in the order of their creation.
To clarify how the order of the Traquests should be considered, Figure 6 shows two Traquest trees, and on the horizontal axis, their physical time of creation is represented. In this case, the physical order of the Traquests is the following: T1; T2; T3; T4; T5; T6; T7; T8; T9. However, since Traquests trees represent atomic operations, and the branches of the trees represent atomic sub-operations, the logical order of the Traquests cannot be equivalent to the physical order. The logical order of the Traquests in this particular case is the following: T1; T3; T6; T8; T4; T7; T2; T5; T9.

Current logical timestamps
There are already several solutions for creating timestamps and clocks in a distributed environment when more processes are running parallelly. The Lamport timestamp [27] algorithm or the Vector clocks [37] algorithm are designed to handle timing issues when more processes are existing at the same time which can interact with each other. In the case of the Lamport timestamp, creating the timestamp is very fast and easy but compare two timestamps is very hard and costs a lot of computation time. For the comparison, we also must decide if there is a joining path between the processes. It is not possible to use it for the Traquests. With the vector clocks, the result is similar. However, at the vector clocks, creating the timestamp is highly costly because we need as many dimensions for the clock as many processes we have. In our case, every Traquest is a process, and there can be millions of them or even more. Furthermore, Traquests can be created in realtime, which means at the point where we should give a timestamp for a Traquest, we do not even know how many processes should we consider to create a Vector Clock based timestamp. Therefore, the Vector clock works neither for the Traquest model.

Hierarchical timestamp
We need a hierarchical time stamping mechanism which is a more special case. The naive algorithm for creating a required hierarchical timestamp would be simply using an array with integers. All the Traquest can count how many children they have already, and whenever a child is created, they increase the counter; therefore, each child knows where they are in the queue of the order. The root Traquests can get their number from a global counter, from the Unix time, or a combination of the two. The array used as a timestamp can store all the ancestor's order numbers and also its own order number in the last record. Figure 7 shows the naive algorithm timestamps for the Traquest tree example presented in Figure 6. In the example, we supposed that all the Traquests were created very close in physical time; therefore, they all have the same Unix time in the first record. After the global timestamp, all the timestamps contain their ancestors' timestamps; they are just extending it with their own order number. For flat hierarchies, it works well because there are only a few levels, and the length of the timestamp is short. However, the timestamps can get very long when the hierarchy is tall.
To address this issue, we have created a new timestamp algorithm that can reduce the necessary size of the timestamp drastically. Explaining our research on the optimized timestamps in more detail would be complex, and it is out of the scope of the current paper. Therefore, we rely on the naive timestamps for the explanation of the Traquest model.

Data protectors
We introduced that Traquests are forming a tree structure. However, a tree structure by itself would never result in any conflicts, which would be the core of the Traquest model to handle them effectively. Conflicts are happening when two different processes are trying to read or write the same part of the global state. To this end, Data protectors were constructed. Data protectors are entities responsible for managing a given segment of the global state. They protect the given global state particle from conflicting reads and writes.
The goal of each branch of the Traquest tree is to interact somehow with the global state. Therefore, each branch, at some point, ends up in a Data protector. Traquests can call CRUD [33] operations on the Data Protectors. When a Traquest calls a CRUD operation to a Data protector, the Data protector generates a new Traquest containing the operation and replies with the generated Traquest. This new Traquest can be bounded to the original Traquest as a child; therefore, it becomes part of the Traquest tree.
When more Traquests are using the same Data protector, the Data protector can use the logical timestamps of the Traquests to decide which read or write operation should be answered first. If a Traquest with an earlier timestamp comes after a Traquest with a later timestamp has been already responded to, the Data protector can call the undo mechanism of the already responded Traquest and serve the newly requesting Traquest. Therefore, the Data protector can efficiently resolve any conflicts.
Furthermore, because all the conflicts are recognized and resolved at the Data protectors, most of the conflict resolving features of the Traquests are used only by the Data protectors themselves. Data Protectors can trigger a Mistake if they have conflicting Traquests, and they can define the callback for the Rollback. This way, the increased complexity of the Traquests can be mostly hidden from the developers, and they do not need to care about the failure handling parts at all, except taking care of the Finally handler of the root Traquest. As a result, using Traquests can be as straightforward as using Promises or even more.
Data Protectors are the only entities who can contact directly to the global state storage. Therefore, the way we physically store the data can be abstracted away. Data Protectors can store the state using any databases, the local storage, the memory, or even any mixture of these solutions. Using traditional databases can be helpful to provide compatibility with other systems; however, in this case, we should be aware of the risk of corrupting the consistency of the global state. The most efficient solution is to use the local storage or memory for storing the state.

Consistency and Fault tolerance
Traquests interact with each other using serializable data constructs only. Therefore, Traquests can be located on different computing notes as well, and they still can interact. Fault tolerance requires the replication of the different particles of the global state to several computing nodes. Traquests are perfect for creating replicas of a desired global state particle and consistently managing them. It is enough to add new Traquest tree branches to each write operation that replicates the operation on different computing nodes. Thanks to the atomic property of the Traquest tree, the state will always remain consistent. For the read operations, we do not need such replication since the writes are already ensuring consistency.

Tail Traquests and network buffering
Tail Traquest is not a new separate feature in the Traquest model; it is instead a useful design pattern. Tail Traquests are simply Traquests where the Then handler of the Traquest is not defined. This implies that the parent Traquest of a Tail Traquest can finish its Deferred process without waiting for the current Traquest to finish with its task. This also means that the resulting value of a Traquest is independent of its child Tail Traquests.
Tail Traquests are primarily helpful for synchronizing the modifications in the global state made by the Traquest tree with other servers in a consistent way for reaching fault tolerance. Because Tail Traquests are not blocking the execution of the core logic of the Traquest tree, the overall Traquest tree can run very fast. Suppose every part of the global state that needs to be used is replicated locally. In that case, the whole logic of the Traquest tree can even execute in-memory time, and the network messages for the synchronizations are buffered automatically. They can be synchronized lazily in only two round trip messages for finalizing and committing. This optimization can happen even in the case of very complex algorithms, when there are many global state reads and writes depending on each other.
The communication of the Traquests between different computing nodes and the buffering can be separated and managed automatically. Therefore, the protocol for communication is abstracted away. The background implementation can use TCP [17], UDP [39], REST [21], WebSocket [8], WebRTC [18], long polling [19], SSE [36] or any other technologies what the infrastructure allows. This leaves many possibilities for optimizations. For example, if two nodes are communicating less frequently, they can use REST calls. However, if there are two nodes with frequent communication between them, they can switch to WebSocket. This way, the Traquest model attempts to create a new layer on top of the OSI layers [14], where the network communication itself can be abstracted.

A basic exemplary case
We have discussed how the basics of the Traquest model are working. To have a deeper understanding, let us examine how we can increment a simple integer value in the global state.

Basic scenario with no conflicts
To examine a basic scenario with no conflicts, let us discuss a simple incrementation of a value in the global state. In the Appendix Figure 11 illustrates such an example of an incrementation. The incremented global state variable is named i. The global process creates a Traquest for the transactional incrementation. A "T" prefix marks the Traquests, and their postfix is their logical timestamp. "DP i" is the Data Protector of the i variable, and "Storage i" is the physical location of the i variable. The "Storage i" can be a local storage, it can be stored directly in the memory, or it can represent any kind of database as well. The sequence diagram notes are marking the actual states of the Traquests. The global process creates the "T1" Traquest, and the other two Traquests are generated by the Data Protector, one for reading the i variable and one for updating it. The diagram shows the operations between the entities. The initial value of the i variable is 10.

Conflict resolving
To examine how Traquests behave in a conflicting scenario, let us continue with a similar incrementation, but in this case, we have two conflicting global processes (e.g., two threads). In the Appendix Figures 12a and 12b illustrate such an example of a conflicting incrementation. The first global process begins an incrementation on variable i, and the second process begins a read on the same i variable only a little later. In this case, we have two Traquest trees with T1 and T2 Traquests at the root. The T1 tree performs a read on variable i, next the T2 tree performs a read, and after that, T1 performs the write with the incremented value. This is a conflicting scenario because the T2 tree should read the value of i only after the T1 has completely finished with the incrementation. Figures 12a and 12b in the Appendix show that despite the conflict, the global processes get only the correct result at the end, and the correct final global state value is persisted on the storage. Examining more the "DP i" Data Protector, it is also visible that the Data Protector reads and writes to the storage only once. It is interesting if we consider that it had to serve several CRUD operations coming from the Traquests. Data Protectors can effectively aggregate those CRUD operations and reduce the number of CRUD operations necessary to call on the storage itself. This has higher importance if we consider that the storage is a component that can be located on different computing nodes; therefore, calling an operation on the storage can be the slowest element of the overall process.

Related work 3.1 Current technologies
There are many technologies for providing ACID concurrent systems. Hereby we discuss the most relevant and most widely used directions.

Multitier architectures
The "Layers" architectural pattern has been described in various publications [6], and it is the most widely used pattern in the case of enterprise web applications. When the Business layer executes the desired algorithm, it continuously has to access the Data access layer to read the global state and write back the changed state. When the algorithm requires only a few iterations depending on each other with the Data access layer, this causes no problem. On the other hand, each read and write requires a roundtrip on the network when there are several depending steps. Although many databases -e.g., most of the SQL databases -can easily handle atomic transactions, the number of the necessary roundtrips implicates a massive limitation in the overall performance. This is a strict limitation in any architecture where we separate the location where we execute the business logic from the location where we store the global state.
To give an example, one might select any use cases where there are several dependent reads or writes to any databases to compare the multitier architectures. One of those examples is the Geographical Information System using large point clouds. For this purpose traditional PostgreSQL [23] is often used. Using space partitioning algorithms is a necessity to be able to manage the point cloud. Octree [22] is such an algorithm that can let us manage the points efficiently and easily. Figure 8 shows an example when a new point is added to an Octree. We assumed that adding the new point requires searching down the Octree structure for ten levels. We assumed that the whole data set is replicated to two servers.
Database servers cannot execute algorithms in multitier architectures. They are only responsible for storing the data. The application is executed by the application server. Therefore, each node has to be first read to the application server from one of the database servers. Each node refers to its children; therefore, all the parents should be read before the child can be reached, and pipelining [29] cannot be used. Furthermore, to ensure atomicity and consistency, each node must be checked and locked on both servers. The example showed in Figure 8 is a simplified one. In real life, there can be much more and complex network messages between the servers. Still, even in this simplified case, we can count up to 44 network messages between the servers. This example shows that any solutions built on using databases can have strict performance limitations if the operations sent to the database are depending on each other. If they are independent, buffering and pipelining can be used, and many queries can be sent within a single RTT (Round Trip Time) over the network. In this case, the number of network messages can be O(1). However, in many cases, we need to know the result of a query to be able to send the following query to the database. In such cases, the number of network messages grows on a O(n) scale.

Serverless architecture
Serverless is one of the most trending architecture types nowadays. Serverless computing has emerged as a new compelling paradigm for the deployment of applications and services. It represents an evolution of cloud programming models, abstractions, and platforms and is a testament to the maturity and wide adoption of cloud technologies [4].
The serverless architecture is built on using stateless cloud functions in a managed way. The developer does not need to manage any server-side infrastructures. The number of cloud functions can scale horizontally automatically. These cloud functions can call other managed database systems to reach out to the application's global state. Serverless is getting more and more traction, and all the leading cloud providers are offering their serverless solutions: AWS Lambda [2], Google Cloud Functions [11], or Azure Functions [24].
However, in serverless architectures, the cloud functions have strict performance limitations thanks to the stateless nature of the cloud functions. The cloud functions cannot store any part of the global state. They need to call a database, a distributed file system, or other external services for that purpose. Therefore the cloud functions cannot be executed in-memory time, and they need to communicate on the network to finish their task. This means that from a performance perspective, they share the same limitations with the multitier architectures.

Actor model
Carl Hewitt first described the actor model in 1973 [15]. Actors can execute business logic and store state simultaneously; therefore, they do not share the limitations of the classical multitier architectures. Actors are excellent for solving problems where we have many independent processes that can work in isolation and only interact with other Actors through message passing. This model fits many problems. However, unfortunately, the actor model is not a favorable model for implementing truly shared state [34], when we need to have a consensus and a stable view of state across many components. Actors can get information about each other only through messages; therefore, it is hard to maintain atomicity.
The Actor model is a more general concept. Many algorithms can be implemented using Actors. Therefore we cannot directly compare the Actor model itself with the Traquest model because it depends on the algorithm that we create using the Actor model. However, there are standardized solutions for creating atomic transactions using the Actor model. The Akka toolkit suggests Transactors [34] for creating transactions. Under the hood, it uses a CommitBarrier, similar to a Java CountDownLatch [26] which is a blocking mechanism. Therefore, Transactors also have no specific timestamping mechanism. They have to lock and await each change in the global state; therefore, we would not have fewer network messages with the Transactors than what multitier architectures have.

Consistency protocols
The Traquest model can ensure atomicity and is also a promising way to ensure consistency. Therefore, hereby we take the most relevant consistency protocols [32] under investigation respective to the Traquest model.
Continuous consistency: Continuous consistency ensures that the numerical deviation of a specific global state particle does not go above a certain threshold on the different computing nodes. This can be applied only in the case of numerical values, and it ensures only an approximate consistency; therefore, it is out of scope for the Traquest model.
Primary-Based Protocols: Primary-Based protocols provide proper consistency for an arbitrary type of data. To keep the data consistent, they have to synchronize each write at least with the primary server. For instance, in such a case, the algorithm has to be blocked until a read it depends on gets a confirmation from the primary server. This requires many iterations of roundtrip messages; therefore, Primary-Based Protocol implies a strict limitation in the performance.
Quorum-Based Protocols: Quorum-Based Protocols have very similar limitations to Primary-Based Protocols. Each read and write operation must be confirmed by other computing nodes before the executed algorithm can rely on the operation and step forward. The only exception is the Read-One, Write-All scheme. In this case, it is enough to read the local state of the data; however, it requires even more messages to write synchronizations. This scenario can only be suitable in the case of very read-heavy applications.
The mentioned Primary-Based and Quorum-Based protocols share the same problems with the Transactors and multitier solutions. Each read or write should be crosschecked with other servers before we can rely on the locally stored data, and the locks are blocking the process. Therefore, these protocols cannot reduce the necessary network messages either.

Traquest model compared to the current technologies
In the following, we will discuss the exemplary GIS-octree case described in Section 3.1.1 to understand more and compare the Traquests.
With the Traquest model, we do not need a persistence layer because the Traquests themselves can already ensure the ACID properties. The data protectors can store the global state on the local storage or even in the memory. Therefore, there is no need for network communication for the reads in the case of an optimal topology. Moreover, write operations do not need network communication either, only for synchronization, which can be buffered and postponed. This way, all the network events can be done in only three RTTs. This results in O(1) -or even less depending on the proportion of reads and writes -number of network messages even for operations that depend on each other.  Figure 9 shows the same use case that was presented in Figure 8, but it uses the Traquest model. We do not need to use separate application and data servers since the Traquest model has constructions for both processing and storing. We have two servers for storing the replicated data on two different physical computing devices, just like the multitier example. As we discussed earlier, Traquests do not need to synchronize the read operations because if a conflict arises, the responded value can be later undone. Furthermore, the writes can also be aggregated and buffered and be sent in one message on the network. In this particular case, there are only six network messages between the servers. Compared with the optimistic estimation of 44 for the multitier architectures, this is a significant reduction. This difference is even bigger if there are more dependent iterative operations necessary for the database. For example, suppose we would have a graph as an example, and we wanted to find the shortest distance between two points. In that case, there could be thousands of dependent operations to the database, but with the Traquest model, we would still need only six network messages.
Here we need to emphasize that this optimal scenario is valid only if the necessary particles of the global state have replications locally. These numbers also depend on the actual infrastructure topology, the used components, the concrete use case, and many other factors.
However, even if not every data is available locally, the execution of the necessary Traquest tree branches can be delegated to other servers since all the servers are running the Traquest environment. Therefore the location of the processing can move to the data location and not backwards. This means much less communication over the network, even in this case.
Suppose we have a worst-case scenario, where the data stored over the servers is randomly fragmented. In that case, the number of the messages in the Traquest model can grow on a O(n) scale, which is the best-case scenario for the multitier architectures. However, this would mean already an unrealistic and completely randomized worst-case topology. In general, we can say that Traquests has the potential to reduce the network load by magnitudes. Comparing the Traquest model with the existing technologies and models is challenging because there can be many different distributed scenarios. Table 1 shows a more complex comparison of the Traquest model. We showed four different kinds of circumstances that can highly influence the properties of a distributed system. The "Concurrency" column shows whether the examined distributed system has an optimistic or pessimistic concurrency scenario. We consider a scenario optimistic when there are no conflicts or the global state operations are executed in proper order or affect different records of the global state. In a pessimistic scenario, all the global state operations are executed in reverse order on the same global state records; therefore, we have the highest possible amount of conflicts. Realistically, most the distributed systems are much closer to the optimistic scenario.
The "Dependency" column shows whether the global state operations are dependent on each other. They are dependent if a global state operation has to await a previous one to be executed. For instance, incrementing a value is a dependent operation since the value first has to be read to increment it.
The "Topology" column shows whether the topology of global state particles is ideal or not. The topology is ideal if all the corresponding global state particles are stored on the same servers; therefore, the processes can reach them at one step. The topology is random if the global state particles are spread across the servers without considering the probability of them being used together. For instance, consistent hashing used for sharding by many of the most popular databases (AWS DynamoDB [7], Redis [30], etc.) creates such a random topology.
The "Operations" column shows whether the examined processes are writeheavy or they only contain read operations.
There are two "Response type" columns in the table. The Traquest model is built on introducing the temporary responses. As we described earlier, the Traquest model can collect all the conflicts and resolves them lazily in a buffered way. The column "Final" refers basically to all the currently existing technologies (multitier, serverless, actor, etc.) where the response to a request is final; therefore, all the conflict resolution must be finished in advance. It is usually done by using a locking mechanism. The "Temporary" column refers practically to the Traquest model as it introduces the temporary responses. However, we do not exclude the possibility that later new models or concepts will arise and utilize this idea as well.
The limitation in the performance of a distributed system is usually coming from the overall time needed to get network messages from one computing node to the other. A larger amount of data can be sent over the network relatively fast in a buffered way, but when there are more messages, each message has a roundtrip time and an overhead. Also, in-memory calculations are magnitudes faster than network communication. Therefore, to compare the Traquest model, we choose the necessary number of messages compared to the number of global state operations as the primary indicator for the performance of the distributed system.
The rows in the table describe different cases respective to the different circumstances. The last two columns show how the necessary number of network messages is growing as we increase the global state operations. The cells with green background mean easier circumstances or better performance, and the red background table cells have the opposite meaning. Table cells with white background mean no significant difference between traditional architectures and the Traquest model. The exclamation marks at the end of Case 5,9,and 13 highlight that the Traquest model performs better not only by one but also by two magnitudes.
When the global state operations come strictly in order, they are independent, and the topology is ideal, the traditional databases can use pipelining. In this ideal scenario, the read and write operations can be sent over one single network message. This implies that at Case 1 and 2, the number of messages can scale on a O(1) level ideally. In all the other cases, there is at least one network message per global state operation necessary. When the operations come entirely out of order and have a pessimistic concurrency scenario, traditional architectures using final responses still need only O(n) messages. However, they also need to use locking mechanisms actively. This slows down the execution significantly. We did not show this effect in the table because we assumed that the servers could utilize this freed resource for other tasks or processes.
With the Traquest model, the processing and storing of the data can be performed on the same server, supposing we have read operations only and the topology is ideal. Therefore, in Case 1,5,9,and 13, there is no need for messages on the network at all. This means the number of the messages scales on a O(0) scale. In an ideal case, when there are writes, the Traquest model can immediately process the writes in-memory time and postpones the conflict resolving and data replication lazily to buffer them to one single message. The committing mechanism runs in a buffered way as well, meaning that Case 2 and 6 can scale on a O(1) level. In the worst cases, the Traquest model needs O(n) network messages, except when we need to consider pessimistic concurrency. When we have pessimistic concurrency, random topology, and write-heavy global state operations, the Traquest model can require O(n 2 ) number of messages. There is a big difference between read and write operations because reads do not generate conflicts thanks to the ability of the Data protectors to store the history of the global state records and serve the read operations, respectively.
We can conclude that the Traquest model performs better than the traditional architectures when considering some level of topology optimization and a more optimistic concurrency scenario. In this case, the advantage can reach several magnitudes. The Traquest model is not ideal when there is a limited amount of global state records getting many concurrent, and conflicting writes or the topology of the global state records is random.

Consistency Choices in Distributed Systems
Gotsman et al. [12] give a comprehensive overview of the consistency issues and the compromises that should be considered when designing a distributed system. It argues that only the necessary level of consistency should be used to avoid unnecessary loss in the performance. Using different levels of consistency in the same distributed system in such a mixed way is called hybrid consistency. The authors have designed a modular methodology to help developers decide the necessary level of consistency, and they presented proof for the methodology.
Despite the comprehensiveness of the paper, the different consistency issues are all discussed on the database level. All the consistency issues are discussed as database-related issues. This pattern can be recognized in the literature in general since consistency problems are associated with the consistency of the global state, and most of the distributed systems are managing the global state in the persistence layer. On the other hand, Traquests can ensure consistency -and atomicity -on the data processing level, not only on the data storage level. This is a major difference that allows a significant leap forward in the potentially reachable performance.
The authors of the paper also discuss the usefulness of hybrid consistency strategies. Through the enhanced performance, the Traquest model can highly reduce the consistency level dilemma and reduce the necessity of using hybrid strategies. Nevertheless, the Traquest model still supports hybrid consistency implicitly. When we wish to create strong consistency, we can build a fully bound Traquest tree as an atomic operation, and all the state changes and replica synchronization steps will remain strongly consistent.
However, we are not always restricted to define the parent of a Traquest. This way, we can separate different branches from the Traquest tree, and we can create less consistent operations to gain more performance. Although, in the Traquest model, it can rarely have clear benefits because strong consistency can already perform equally fast. Separating Traquest trees can be beneficial when we need to face highly conflicting use cases. In such a pessimistic concurrency case, the continuous rollbacking of the branches could slow down the execution of the Traquest tree, and hybrid consistency can be an effective solution.

Performance of Transactional Distributed Systems
Eric Brewer introduced the idea that there is a fundamental tradeoff between consistency, availability, and network partition tolerance. This tradeoff, known as the CAP [10] theorem, has been widely discussed ever since. Some of the interest in CAP derives from the fact that it illustrates a general tradeoff in distributed computing: the impossibility of guaranteeing both safety and liveness in an unreliable distributed system.
Ahsan et al. [1] discuss the CAP theorem in more depth. The authors highlight some of the limitations in the practical usage of the CAP theorem, and they propose a new impossibility theorem called the CAT theorem.
The paper refers to Jim Gray's paper from 1996 [13] which showed that the rate of transaction aborts increases at least proportional to the square of the TPS (throughput) of the system, and the third to the fifth power of the number of actions in the transaction.
The Traquest model cannot violate the CAP theorem either, but it can provide a workaround. The Traquest model can inherently provide consistency and partition tolerance. Transaction availability is also basically provided thanks to the Tail Traquests. Availability is provided for the whole transaction as well; just the final commit of the root Traquest has to be awaited. We will have the correct result, and only the response time can be higher for the final commit if the writes need to be synchronized.
The workaround nature of the Traquest model for the CAP theorem confirms that alternative and more practical impossibility theorems can be essential. The CAT theorem stands for Contention, Abort Rate, and Throughput. The Traquest model tries to keep the abort rate minimal, thanks to introducing the temporary mistakes. If an exception arises, that would typically trigger the abortion of the whole transaction. Instead, in the Traquest model, only the affected Traquest tree branch gets aborted, rolled back, and re-executed. Therefore the Traquest model balances between Contention and Throughput.
In the Traquest model, resolving a conflict is relatively expensive, thanks to the undoing mechanism. Therefore, the Traquest model shows the most significant potential in the case of optimistic concurrency cases. This refers to cases where we can assume that most of the operations are not conflicting. We can say that regarding the CAT theorem, the Traquest model prefers Contention and low Abort Rate over Throughput. However, this decision is not architecturally predefined. When the system gets fewer conflicting concurrent operations, it automatically achieves higher throughput. To be able to verify the Traquest model, we have built an experimental prototype in TypeScript. The Traquest model itself has no language dependencies. It can be implemented practically in almost any programming language. However, using TypeScript gave us more benefits in the current phase of the research. The concept of Promises is highly used in JavaScript. Typescript is a superset of JavaScript [25]; therefore, it simplified the experimentation process with Promises and Traquests. The flexibility of JavaScript and the strong typing, the strictness, and the expressivity of TypeScript made it an ideal solution. Furthermore, TypeScript compiles to JavaScript, which can be executed on the client and server side, enabling the experimentation with hybrid architectures balancing between cloud, edge, and peer to peer.
Building this experimental prototype helped clarify that the general concept of the Traquest model is feasible and viable. We could try the different state transitions, callbacks and write unit tests and integration tests to verify whether the Traquests behave as expected. The functional tests have worked as they were expected, and they gave a positive result. However, the non-functional tests gave a slower execution time than we were expecting. The complete correctness of the final version of the model can be verified only after more tests at a larger scale or a complete formalization of the model. This requires further research and optimization. However, we expect no significant changes in the general concept. Only slight modifications are expected for edge cases we could not consider in advance. These edge cases also might vary slightly depending on the programming language used for the implementation.

Local boilerplate
One of the main disadvantages of the Traquest model is that it increases the computing power necessary on a local level. Managing all the Traquests, calculating the timestamps, maintaining all the states can consume significant computing. The non-functional tests of the Traquest model clearly showed this issue. When we created only simple standalone Traquests, then 100,000 Traquests could be executed in 460 msec. However, when we had a more complex Traquest tree where we created a binary tree from the Traquests, we measured 990 msec to execute only 5,998 Traquests which means less than one Traquest/msec.
Thanks to the results of the non-functional tests, the current focus of our research is to optimize the Traquests performance.
Some parts of this increased computing resource consumption come from the programming language used for the prototype implementation. Namely, if we dynamically change the schema of an object in runtime, the V8 JavaScript engine changes to a much slower general implementation in the background. We measured that this deceleration can be even on a 100X times slower level. We have built many new concepts to mitigate this issue. To describe them in detail would be out of scope for the current paper, but we mention the most important ones. We have created a custom Promise implementation which we measured to be 30X times faster than the standard JavaScript Promise implementation. We also created a custom callback mechanism which we measured to be around 14X times faster than the standard JavaScript anonymous callbacks. We also prepared a second prototype of the Traquest model, avoiding object schema changes. With these optimizations, we could significantly accelerate the Traquests and execute 100,000 standalone Traquests in 54 msec.
Some parts of the increased computing resource are coming from a more general algorithmic level. We have also conducted more research that would be out of scope to discuss in more detail, but we mention the most significant achievements. One of the most resource-consuming parts of the Traquest model is the hierarchical timestamping mechanism. We highlighted this issue in Section 2.3.2. To address this, we created a new timestamp algorithm what we named Interval Timestamp, which uses a logical time interval to define inheriting timestamp relations instead of arrays used by the naive algorithm.
We plan to expand the research on aggregating the Traquests that can be executed sequentially. If a group of Traquests is executed by one single thread, that means there can be no conflicting operations from elsewhere; therefore, they could be handled as one aggregated Traquest. This optimization could reduce the execution boilerplate of the Traquests almost completely. Only the Traquest communicating on the network would break this aggregation and end up in physically new Traquests.
After this research phase, we will have a final Traquest implementation, and we will be able to test Traquests in larger quantities. This will let us create a more rigorous validation of the Traquest model and make more definitive performance tests comparing Traquests with architectures based on the currently existing technologies.
The Traquest model in its current status is already a unique approach utilizing the idea that a response to a request can contain temporary information. A general system can be built based on this principle. This system can postpone synchronization and conflict resolution phases lazily, enabling us much more buffering on the network and in-memory time speed even in the dependent operations where network communication is inevitable using the current technologies.

Formalizing
We tried to model every possible scenario that can happen with a Traquest tree to be sure about the correctness of the model. However, the Traquest model is a new concept, and in the future, building formal semantics and reasoning for the Traquest model using tools like the Coq [38] formal proof managing system would give us an absolute certainty about the correctness of the model.

Conclusion
Providing ACID properties can be crucial for many applications, but it requires a massive compromise in performance. The Traquest model is a proposed potential solution for this problem. We have discussed in detail the general concept of the Traquest model.
Traquests are unifying the location of the data storing and processing; they are using specialized timestamps and history tracking of the global state changes that can potentially cause conflicts. By creating temporary responses and building up a mechanism for rolling back the conflicting parts of a running distributed algorithm, Traquests can ensure atomicity in a very efficient way. The synchronization steps over the network for replication and fault tolerance do not block the business logic executed in the Traquests, giving a massive advantage in the performance. Furthermore, this lazy synchronization allows an effective buffering of the network messages; therefore, the number of the necessary network messages can be decreased by magnitudes.
In our investigated concrete use case, the classical multitier architecture required 44 messages between the servers, where the Traquest model only needed six. The difference can grow magnitudes as the complexity of the algorithm grows. We showed that classical architectures require at least O(n) network messages as the number of operations grows in the case of depending operations. Simultaneously, the Traquest model can scale with only a O(1) factor.


s2fieldsofstudy:
Computer Science
Biology

text:
Web Application for Statistical Tracking and Predicting the Evolution of Active Cases with the Novel Coronavirus ( SARS-CoV-2 )

Since February 2020, when the first case of infection with SARS COV-2 virus appeared in Romania, the evolution of COVID-19 pandemic continues to have an ascending allure, reaching in September 2020 a second wave of infections as expected. In order to understand the evolution and spread of this disease over time and space, more and more research is focused on obtaining mathematical models that are able to predict the evolution of active cases based on different scenarios and taking into account the numerous inputs that influence the spread of this infection. This paper presents a web responsive application that allows the end user to analyze the evolution of the pandemic in Romania, graphically, and that incorporates, unlike other COVID-19 statistical applications, a prediction of active cases evolution. The prediction is based on a neural network mathematical model, described from the architectural point of view.

I. INTRODUCTION
First cases of COVID-19 on the Romanian territory were confirmed on 26 February 2020. In 19 March there were already 277 cases reported by the authorities. The first case of COVID-19 pandemic, originated from the city of Wuhan of China in December 2019 and since then it spread and the coronavirus outbreak evolved into a pandemic [ 1], declared in 11 March 2020 by the WHO (Word Health Organization).
The COVID-19 pandemic has highly affected the health, socio-economic and financial matters of the different countries of the world [2].
Since then, local authorities took a bunch of restrictive actions to prevent the spread of COVID-19 (corona virus disease caused by SARS-CoV 2) (severe acute respiratory syndrome coronavirus 2). From 16 March to 14 May there was a national lockdown, that decreased the number of active cases in our country, thus on 15 May 2020 the President of Romania promulgated the law on the establishment of the state of alert on the territory of Romania, a state that is Manuscript  However, as can be observed from analyzing the red line in Fig. 1, the number of cases reported each day as COVID-19 positive, continue to have an ascending allure, reaching in September 2020 a much higher infection rate than at the beginning of the pandemic. In Fig. 1, the red line corresponds to the number of new cases reported every day, the green line represents the number of cured cases each day while the black line denoted the number of reported daily deaths due to infection.
In order to understand the evolution of this disease over time and space, more and more research is focused on obtaining prediction models [2]- [4]. Such models could help primarily the authorities to manage and content the spread of COVID-19, since they could test and observe the effect of different actions, or restrictions that can be imposed in order to decrease the number of active cases in their country. Having a prediction model, could mean that different scenarios or practices can be carried out in simulation and thus the scenario that proves to have the best outcome can be selected and implemented. The aim being to limit the intra-community spread, thus reducing the pressure put on the health care department [5]. The fewer the cases reported every day (smaller number of diseases), means more time and resources allocated to threat the most vulnerable and the most severe cases of corona virus disease [6], [7]. Even more, decreasing the number of cases and limiting the spread, means that the health care system is not overwhelmed and can threat all active cases of COVID-19, regardless of the severity. The aim of this paper is to present a web application, design in order to show statistical information on the reported active cases in our country, based on the official reported and The developed application must be web responsive so that it is as pleasing to the eye as possible, regardless of the viewing environment or the resolution of the used device. We want the application to be easy to follow, and for each user to quickly find the information they are interested in.
Most of the presented information is in the form of diagrams for ease of analysis and perception of data, which is easier to assimilate than in the case of tables (that would be very large for this type of application/data). In order not to have a monotony of the application, the daily information displayed on the country map is also used, for a spatial distribution, and the main data are given by counties, represented with colors of different intensity depending on the severity.
Currently, there are some web applications like the one we made, but they are only informative about the situation of the spread of COVID-19 disease. The novelty introduced by the developed web application is the part dedicated to predicting the evolution of the number of cases. Datelazi.ro is a pro-bono project developed by Code for Romania that presents the data provided by the Romanian Government in a graphic form that can be easily traversed. Graphs.ro is a personal project, made by Dragoș Vână. The data is collected from the Romanian Ministry of Health and can be accessed in the form of a json, provided the source is credited. Covid19.geo-spatial.org, is an application that has a team of about 32 volunteers, so the data are quite numerous and complex. The collected data can be accessed using a dedicated API (Application Programming Interface) and can be found in json format. Fig. 2 shows the use cases diagram of any client, which uses the application developed by the authors. No authentication is required to access all the information available in the interface. One can note from this diagram the main structure of the web application, as well as the arrangement of the information.

A. Application Design and Implementation
The aspects related to the implementation of the application will be presented in the following.
To create the desired application the authors used on the front end and stylization: Razor, Bootstrap, HTML and CSS. For the implementation of the application back-end part, the server and its connection to the database were made, the language used was C#. The authors also worked with Dapper, Syncfusion.Blazor, System.Json, System.Data.SqlClient packages.
Net is an open source platform developed by Microsoft, with which one can build applications for desktop, web, mobile, IoT and games. They can be written in F#, C# or Visual Basic, but no matter what language is used, the code runs natively on any compatible operating system [8]. Blazor is a free and open-source framework used in creating interactive web applications, which uses C# instead of JavaScript. It uses open web standards without plugins. The code running in the browser runs in the same security sandbox as the one used by the JavaScript framework. Blazor applications are based on components, which are elements of the user interface [9]. The MainLayout of our application is the basic one of all Razor components, here all the pages and the navigation menu are inserted. Its use is efficient since there is no need to insert the navigation menu part into each page.
Syncfusion.Blazor is a library that offers a multitude of UI (User Interface) components for Blazor applications, having a high performance and being able to work with a large volume of data. This library was chosen to create all the diagrams in the project, and for creating the country map. Diagrams are the best way to visualize information since they can be compared more easily with each other, and we used their layout over time since we want to emphasize the evolution and development of cases (tendency to increase or decrease). Both the diagrams and the map have different labels added, for better and more aesthetic interaction.
Both relational and non-relational databases were used in this project, combining them for the best possible data management. Because some data had a very large volume of information and manipulation could be done very easily using the non-relational database, and others had a small volume at the beginning and were much easier to manipulate and organize with the help of the relational database. Adding data to the database is done automatically, thus no administrator role is needed.
To populate the relational database with the current values, a request is used to the file available on graphs.ro, it is saved locally in a json file, and then its deserialization is performed. The actual insertion in the database is done automatically when the application is run, depending on the time of day when it is run and depending on when the last update was made (reporting data for the last 24 hours is done daily at the same time). The non-relational database used was of the json document type. It was used to implement the map type statistical view since it requires a very large volume of data and was an easier way to manage.

B. The Web Responsive Application Interface
Since the current application is developed for the statistical analysis of COVID-19 evolution in Romania, the text on many pages is in Romanian language. The first time the application is run, the browser opens with the Home Page where one can see all the functionalities that the customer has available. This page also contains data about the latest updates and a small preview for the data that can be found in the application, as shown in Fig. 3 [10].
The Mobility page has a built-in graph from the Graphs.ro page, regarding Google's mobility in Romania as a percentage. An interesting aspect is that it is very easy to see the moments when measures have been taken to relax the restrictions in the country (see Fig. 4).
The Romanian Map page, as can be seen in fig. 5, presents statistics for the current day for each county of Romania. The user being able to select the data set according to which to stain the map.
In the County Statistics page (Fig. 6) one can view for each county a diagram with the statistics of new cases over the last 7 days, or if one of the counties is selected it redirects the user to the page of the respective county.   When one clicks on the menu on Diagrams, a dropdown submenu opens (as shown in Fig. 2 diagram), and on the Diagrams page two graphics are displayed over time (from March 2020 to present). The first graph shows the daily number of new cases, healings (cured cases) and deaths, and the second illustrates the statistics for active cases in Romania.
If we enter the submenu at Tests, an important statistic will be graphically accessible on the Tests page as depicted in Fig.  7, which is somewhat avoided when presenting official data: the number of daily tests performed nationally. If we were presented with this data, we could more easily understand what percentage of the number of tests performed, came out positive.
The Prediction page is under development, since it must be linked with the prediction model described further, and it must incorporate a menu for selecting different scenarios (that influence the input signals for the prediction model). However, an example of a predicted scenario diagram, that shows the evolution of COVID-19 cases, is given in Fig. 8.

III. COVID-19 PREDICTION MODEL
The elaboration of a prediction mathematical model [11] represents a task of high difficulty due to the high complexity of the virus transmission dynamics. International Journal of Modeling and Optimization, Vol. 11, No. 3, August 2021 The process of virus transmission is a biological process which has the particularities of having large number of input and output signals, respectively the input-output interdependencies being strong nonlinear ones. Consequently, this process is a strong nonlinear MIMO (Multiple Input Multiple Output) process.
The identification of this type of processes is based on processing of large databases containing information about past cases. In this context, the usage of neural networks represents an opportunity. In order to prove the neural networks capacity of learning the behavior of complicated mathematical functions with applications in COVID-19 problem, the case of the signal from Fig. 9 is considered. In Fig. 9, the variation of the new daily cases of infections with SARS-CoV-2 virus, on the territory of Romania, is presented. The considered time interval is from 15 February 2020 to 28 October 2020, more exactly covering 257 days of the pandemic. The source of the input data, graphically presented in Fig. 9, is the https://www.worldometers.info/coronavirus/ web page.
From Figure 9, the strong variation of the considered signal is highlighted due to the consistent variation of the infection's cases from a day to the next one and due to the consistent variation of COVID-19 performed tests during the weeks and during the weekends.
In order to learn the behavior of the signal considered as an example in Fig. 9, a fully feed-forward neural network, having many hidden layers of significant high sizes, is used. After training the neural network and simulating it, the comparative graph between the experimental curve from Fig.  9 and the response of the solution generated by the neural network is presented in Fig. 10. The high accuracy of the obtained neural model results both directly from Fig. 10, the two responses being almost superposed, and through the insignificant value of the quality indicator (the considered quality indicator is MSE (Mean Square Error) and by computing its value, considering 257 pairs of samples of the two curves presented in Fig. 10, the value of 5.9028 cases results). These aspects prove the viability of using neural networks in modelling the virus transmission dynamics. This remark is, also, strengthened by the fact that neural networks have a parallel structure [12], aspect which allows them to process large number of data.
The general architecture of the proposed prediction model for the virus transmission dynamics is presented in Fig.11.   As it is highlighted in Fig. 11, the future proposed model for the virus transmission dynamics will be a MIMO type one. Also, it will be implemented using neural structures which will contain different types of neural networks, depending of the types of the input-output dependences associated to the model. The main sets of the model input signals are: SAIS -Set of Active Input Signals (for example the treatment procedures or the legislation in the domain of the COVID-19 problem; SEIS -Set of Exogenous Input Signals (for example the climatic conditions); SENIS -Set of Endogenous Input Signals (for example the approach of the pandemic by the population). The proposed model will provide the prediction of the SOS (Set of Output Signals) as for example: the future daily cases of infections; the future daily active cases; the future number of cures.
As the main future research activity and direction, we will approach the problem of determining the prediction model for the virus transmission, based on large sets of different types of data, containing information about past cases.

IV. CONCLUSION
The aim of the research carried out by the authors is to develop a statistical web application, with prediction of new active cases of coronavirus disease (COVID-19) integrated. The first step is to develop a statistical web application that is tracking the evolution of coronavirus disease pandemic, using graphical representation, since it is more easily to interpret large amount of data this way, to emphasize the current situation. The web responsive application described in this paper is in the early stages of implementation. Others can be added to the presented functionalities. A more detailed development of this application will be made on the part regarding the evolution prediction of COVID-19 cases.
The main step is to implement a mathematical model using neural networks to predict the pandemic evolution on Romanian territory based on different scenarios, thus giving for example the local authorities a tool of analyzing how different measures and actions to prevent the further speared of this virus work, and act accordingly.
The research team from which the authors take part, too, works hardly, in present, to obtain a functional prediction model, based on multiple and consistent data, containing information about past cases.
As future research, the model and the web application can be extended to predict the evolution of active cases at European level. For further development the authors will also add an option to change the language of the displayed text.

CONFLICT OF INTEREST
The authors declare no conflict of interest.

AUTHOR CONTRIBUTIONS
I. Clitan performed the state of the art and described the web responsive application on COVID-19 evolution. A. Puscasiu elaborated the web responsive application. V. Muresan developed the prediction model's architecture. M. Unguresan contributed in analyzing and processing the experimental data. M. Abrudean proofread the paper and contributed to the development of the prediction model.