Decentralized Data Flows for the Functional Scalability of Service-Oriented IoT Systems

Abstract

Horizontal and vertical scalability have been widely studied in the context of computational resources. However, with the exponential growth in the number of connected objects, functional scalability (in terms of the size of software systems) is rapidly becoming a central challenge for building efficient service-oriented Internet of Things (IoT) systems that generate huge volumes of data continuously. As systems scale up, a centralized approach for moving data between services becomes infeasible because it leads to a single performance bottleneck. A distributed approach avoids such a bottleneck, but it incurs additional network traffic as data streams pass through multiple mediators. Decentralized data exchange is the only solution for realizing totally efficient IoT systems, since it avoids a single performance bottleneck and dramatically minimizes network traffic. In this paper, we present a functionally scalable approach that separates data and control for the realization of decentralized data flows in service-oriented IoT systems. Our approach is evaluated empirically, and the results show that it scales well with the size of IoT systems by substantially reducing both the number of data flows and network traffic in comparison with distributed data flows.

1. INTRODUCTION

The Internet of Things (IoT) is penetrating essential domains of our daily life such as healthcare, security or city management. This emerging paradigm promises the seamless interconnection of any physical object (i.e. thing) through innovative distributed services, leading to service-oriented IoT systems.¹ A proper service composition mechanism is thus required for the integration of IoT services into workflows that consist of both control flow and data flow [1]. Control flow refers to the order in which services are executed, whilst data flow defines how services move data over the network.

As of early 2021, there are over 20 billion connected things and it is predicted that this number will exponentially grow in the next few years [2–4]. Hence, as IoT systems may potentially consist of an overwhelmingly large number of services, functional scalability becomes a challenging concern. Unlike vertical and horizontal scalability, functional scalability accommodates growth in terms of the number of services composed in an IoT system [1]. To tackle the functional scalability challenge, a service composition mechanism must provide the means to compose loosely coupled services that exchange data as efficiently as possible over the network.

IoT services can exchange data in three different ways: (i) with a centralized coordinator, (ii) with multiple distributed coordinators or (iii) in a purely decentralized manner. A centralized approach [5] relies on a single coordinator to mediate data streams between services. Although this is viable for enterprise scenarios where small amounts of data are involved, the coordinator would easily become a bottleneck in IoT systems that generate data in the order of Petabytes. To avoid the central bottleneck, a distributed approach [6] can be used for balancing loads over multiple coordinators. However, this would cause network performance degradation as data passes through multiple mediators before reaching the actual data consumers.

A decentralized approach is the most efficient way to exchange data as it enables direct data exchanges from producers to consumers, thereby decreasing latency and maximising throughput [7–14]. However, exchanging data among loosely coupled IoT services is not trivial, especially in resource-constrained environments where things have poor network connection and low-disk space [7]. Furthermore, building data dependency graphs is hard when control flow and data flow are tightly coupled (i.e. when data follows control). To overcome such issues, recent research [1, 8, 15–18] shows that the separation of control and data can be useful since it allows independent reasoning, monitoring, maintenance and evolution of control flow and data flow. Consequently, an efficient data exchange approach can be defined without considering control, so a reduced number of messages can be transmitted over the network.

1.1. Related work

This section presents and analyses related work on decentralized data flows in service-oriented systems. We classify the existing approaches into three major categories, depending on the composition mechanism they are built on: (i) orchestration (with coordinated data exchanges), (ii) P2P dataflows and (iii) P2P choreography.

In orchestration-based approaches [11, 19–21], a central orchestrator coordinates system execution by passing data references alongside control. Although data values do not follow control like in traditional orchestration [22, 23], additional network traffic is introduced since references and acknowledgement messages are routed via the network. This additional network traffic arises from the fact that orchestration-based approaches do not separate data and control.

Dataflows is a composition mechanism that builds a graph of data transformations, where vertices receive data, perform some computation and pass the result(s) to other vertices via data flow edges [24, 25]. Such data exchanges can be done with or without mediators. In P2P dataflows [14, 26–29], services exchange data with no mediators between them [1]. As control flow is implicit in the collaborative exchange of data, P2P dataflows do not separate data and control.

Service choreography describes decentralized interactions among participants using a well-defined public protocol. In P2P choreography, atomic services are participants that exchange data via direct message passing [30]. Some approaches [13, 31] introduce proxies to coordinate the invocation of services and the exchange of data alongside control. In any case, P2P choreography does not separate data and control.

Table 1 summarizes our analysis of related work, where it is clear that there is no approach supporting the separation of control and data for realizing decentralized data flows between atomic services, in order to efficiently support environments that generate huge volumes of data continuously. Furthermore, existing approaches only consider vertical and horizontal scalability. It is important to mention that the separation of concerns does not imply decentralization but provides a number of benefits. Particularly, the separation is necessary to avoid passing references alongside control during system execution, thus reducing the number of messages transmitted over the network. Also, the orthogonality of data and control enables separate reasoning, monitoring, maintenance, reuse and evolution of those concerns, as discussed in other studies [1, 8].

In the analysis above, we did not consider decentralized orchestration, coordinated dataflows and choreographed orchestration, since those approaches do not support decentralized data flows between atomic services. Nevertheless, for completeness, we analyse those categories below.

In approaches built on top of decentralized orchestration, multiple composite services coordinate system execution [9, 10, 12, 32]. In particular, approaches like [32] persist data on distributed data spaces, which may become a bottleneck in IoT environments where services exchange huge volumes of data continuously. Although some works (e.g. [12]) solve the bottleneck issue by persisting references instead of values, they require the maintenance of tuple spaces and databases for moving references and storing data, respectively. Moving references is necessary because decentralized orchestration does not separate data and control. Paradoxically, decentralized orchestration does not support decentralized dataflows between atomic services.

In coordinated dataflows [33], a master composite coordinates data flows between slave composites. As data pass through multiple mediators, this approach introduces unnecessary network hops (like decentralized orchestration). This problem is also present in [34], which introduces the notion of abstract data types for moving data outside services. Discovery Net [35] and Kepler [36] are workflow systems that implement the semantics of coordinated dataflows, which provide mechanisms to coordinate the execution of (disjoint) data flow graphs. Discovery Net allows the definition of a control flow graph where nodes exchange control tokens instead of data values. Nodes can be data flow graphs per se. In Kepler, a director is a semantic entity that controls data exchanges from outside a data flow graph. These systems do not support decentralized data flows because their workflow execution mechanisms are centralized [9].

In choreographed orchestration, data pass through multiple orchestrator participants leading to network degradation [37]. To separate control and data, [8] proposes a choreographed orchestration approach that allows the manual modelling of cross-partner data dependencies. However, there are no decentralized data flows between atomic services, but only between partners.

1.2. Paper contributions

This paper proposes a functionally scalable approach that semantically separates data and control, in order to decentralize data flows between atomic services in IoT systems. Accordingly, this paper makes the following contributions:

• We propose an (implementation-independent) service composition model that semantically separates data and control by so-called data forests. The semantics allows the encapsulation of explicit control flow graphs and explicit data dependency graphs. As graphs are orthogonal, the semantics enables a separate reasoning and analysis of data and control.

• We propose an efficient algorithm that leverages the model semantics for a compositional analysis of data forests. The algorithm analyses a data dependency graph, without considering control flow, for the automatic construction of a decentralized mapping between data consumers and data producers. The algorithm reduces both the number of data flows and network traffic of an IoT system.

• Unlike the state-of-the-art on decentralized data flows, we evaluate the proposed approach in terms of functional scalability. The evaluation is implementation-independent and shows that the approach scales well with the number of services by reducing the number of data flows linearly and network traffic logarithmically.

1.3. Paper organisation

The rest of the paper is organized as follows. Section 2 presents a motivating scenario to explain why decentralized data flows are a crucial desideratum in the IoT domain. Section 3 presents an overview of the model semantics and a detailed description of the proposed approach. Section 4 presents the implementation of the proposed solution. Section 5 presents a case study. Section 6 presents a comparative evaluation of decentralized data flows versus distributed data flows in the case study. Section 7 outlines an evaluation of the proposed approach in terms of functional scalability. Section 8 outlines the conclusions. Appendices  A and  B formalise our motivating scenario. Appendix  C describes an example of the deployment-time process. Appendix  D presents a source code fragment of our implementation. Appendix  E presents the notation used throughout the paper.

2. WHY DO WE NEED DECENTRALIZED DATA FLOWS IN IOT?

This section discusses the rationale for enabling decentralized data flows in IoT, with the help of a scenario based on the smart parking system presented in [1] and real-world occupancy data from car parks in Birmingham, UK (Appendix  A). The system is used by drivers who want to find the nearest parking space while they drive around a smart city. The workflow for this scenario is a combination of the reduce and the sequential data patterns and involves the services shown in Figure 1. Although data pass through operations, we consider that it is routed between services as there is a one-to-one relationship between services and operations. For simplicity, we assume that services are deployed on different things, e.g. the Availability Checking Service is deployed on an infostation while the Space Finding Service is deployed on an edge router. An infostation is an urban infrastructure device that collects up-to-date status from all occupancy sensors in range. We assume that all parking spaces are equipped with occupancy sensors whose functionality is abstracted by a Sensor Service.

The workflow of our scenario is triggered by a driver’s request, and it starts with two parallel tasks. In the first one, the Data Reducer 2 receives the driver’s coordinates from the GPS Service. In the second one, the Data Reducer 1 pulls the states from multiple Sensor services to create a list that shows the status of parking spaces. Then, the Availability Checking Service uses the list to determine which parking spaces are free. As some spaces can be reserved in advance, the Reservation Service determines which free parking spaces are unreserved and passes its resulting list to the Data Reducer 2. Once the Data Reducer 2 receives all its inputs, it forwards them to the Mapping Service. The Mapping Service then computes the distance between each (free and unreserved) space and the driver’s location and appends the distances to the list. Finally, the Space Finding Service determines the nearest parking space for the driver, using the calculations from the Mapping Service. The coordinates of the nearest parking space are the final result of the workflow and are passed to the car control application.

As the number of occupancy sensors could be huge, especially in large cities, the services of the smart parking system may potentially exchange vast amounts of data continuously. This is because there is a one-to-one mapping between sensors and services, and occupancy sensors are frequently producing data. Thus, functional scalability becomes a challenging concern. To understand how we can address this problem, we analyse the three existing approaches for passing data between the services of our scenario (Fig. 2). For simplicity, we do not show control flow and we assume that there are no data required for both pulling sensor data and starting the execution of the system (from the car control application).

In our scenario, there are 373 drivers arriving to the car park BHMBCCMKT01 between 07:59:45 and 16:26:47 on a given day (Appendix  A). This car park has 577 occupancy sensors each producing 100 bytes, so there are $577\cdot 100=57.7$ KB of sensor data per driver request. The number of bytes returned by the Availability Checking Service, the Reservation Service and the Mapping Service are computed by the functions $S_A(t)$⁠, $S_R(t)$ and $S_M(t)$⁠, whose definitions are presented in Appendix  B. For simplicity, we assume that the GPS Service and the Space Finding Service always return $40$ bytes for the coordinates of a driver and a nearest space, respectively.

We refer the reader to Appendix  A for details about the data set and the formalisms used in our scenario. Appendix  B presents the calculations for the total data transmitted over the network, considering that there are $373$ drivers between 07:59:45 and 16:26:47. These calculations are presented for each data exchange approach depicted in Figure 2. Below we interpret the results.

A centralized approach [5, 38, 39] depends on a single coordinator for passing data between services. Figure 2(a) shows how a central coordinator mediates data streams for the smart parking system. The main drawback of this approach is that such a coordinator is a potential bottleneck (as huge amounts of data are exchanged) and introduces an extra network hop for passing data. This approach is therefore a threat for scalability as pointed out by many researchers [7, 8, 11, 14]. Furthermore, IoT may potentially require the deployment of coordinators on resource-constrained things (e.g. edge devices), which can lead to bottlenecks due to the presence of low computing power and poor network resources [7]. For instance, the central coordinator of our scenario is deployed on an edge device, which manages $\sim$102.98 MB of data over the network using a poor connection (see Equation 5 in Appendix  B). Certainly, this impacts the overall performance of the system negatively. This is especially true in large cities with multiple drivers requesting a space at the same time.

Although a distributed approach [33, 40, 41] removes the central coordinator, it introduces unnecessary network traffic as data passes through multiple mediators, even if data is unimportant for them. For example, in Figure 2(b) the data generated by the Availability Checking Service goes through Coordinator1 and then through Coordinator2, before reaching the service that really needs the data (i.e. the Reservation Service). These additional network hops negatively impact the overall performance of the system.

For our scenario, the distribution of data load among three coordinators avoids a single bottleneck. However, as coordinators mediate interactions, $\sim$123.36 MB of data is exchanged over the network (see Equation 5 in Appendix  B), leading to $\sim$19.80% more network traffic than the centralized approach (see at the bottom of Appendix  B). In fact, this indicates that the network traffic may increase linearly with the number of coordinators.

The decentralized data exchange approach [7, 8, 11, 13] is the most efficient one, since data are passed directly to the services that actually need it. Particularly, it requires only one network hop to pass data from a data producer to a data consumer, as depicted in Figure 2(c). The decentralized version of our scenario requires a total data transfer of $\sim$51.49 MB over the network (see Equation 7 in Appendix  B), i.e. $\sim$50.00% less network traffic than the centralized approach and $\sim$58.26% less traffic than the distributed one (see at the bottom of Appendix  B).

3. THE DX-MAN MODEL

To realize decentralized data flows, we propose to extend the semantics of DX-MAN [42–44], which is an algebraic model for building IoT systems, where services and exogenous composition operators are first-class semantic entities (Fig. 3).

A service  $S\in \mathbb{S}$ is a stateless distributed unit of composition that can be atomic or composite. Its semantics is a workflow space  $W\in \mathbb{W}$⁠, which is a (finite or infinite) set of workflow control flow variants $w_{i\in [1,\mathrm{\infty }]}\in W$ that represent alternative service behaviours:

where $\mathbb{S}$ is the service type and $\mathbb{W}$ is the workflow space type.

An atomic service is syntactically formed by connecting an invocation connector with a computation unit which encapsulates the implementation of multiple operations and it is not allowed to invoke other units (Fig. 3(a)). Semantically, this is equivalent to constructing an atomic workflow space whose variants invoke different operations in the computation unit via the invocation connector. An operation performs some computation and has an input parameter and an output parameter.

The DX-MAN model relies on algebraic composition for defining complex services. Algebraic composition is the process by which a composition operator hierarchically composes multiple services of type $\mathbb{S}$ into a composite service of type $\mathbb{S}$ which, in turn, can be further composed into even more complex composites (Fig. 3(b)) [44]. A composition operator defines control flows exogenously (i.e. outside the composed services) to avoid service dependencies. Formally, it is a function $◯$ for $n$ services with the following type:

A composite service is syntactically formed by connecting a composition operator with multiple (atomic and/or composite) services, which has an input parameter and an output parameter (Fig. 3(c)). Semantically, it is a composite workflow space produced by a composition operator taking sub-workflow spaces as operands. There are composition operators for sequencing (i.e. sequencer), branching (i.e. inclusive selector and exclusive selector) and parallelism (i.e. parallelizer). A sequencer or a parallelizer defines an infinite workflow space, whilst a branching operator defines a finite one.

The control flow structure of a composite service is represented by an abstract workflow tree whose leaves are operations in atomic sub-services, whole composite sub-services or any combination thereof (Fig. 4). An abstract workflow tree allows the definition of a particular variant from a composite workflow space. To do so, a concrete workflow tree must be created, which is a selection function over a set of workflow variants, and it is therefore isomorphic to an abstract workflow tree. The edges of a concrete workflow tree are labelled according to the composition operator used. In particular, the label of a sequencer edge is an ordered list of natural numbers and the label of a parallelizer edge is a natural number (representing the amount of parallel tasks). For the edges of an inclusive selector and an exclusive selector, the labels are conditions and boolean values, respectively. An exclusive selector also has an associated global condition. For further details on workflow selection, see [42, 43].

3.1. Separation of control flows and data flows

IoT service composition can be endogenous or exogenous, depending on control flow origin [45]. Endogenous composition is used by P2P choreographies, which mix service computation (i.e. operations) with control flow constructs (Fig. 5(a)). By contrast, exogenous composition relies on coordinators that define control flow outside the computation of composed services (Fig. 5(b)). This composition approach is used by orchestration and by DX-MAN. Unlike its counterpart, exogenous composition avoids control flow dependencies between services and facilitates reuse at scale [29, 36, 44, 46, 47]. It also avoids application logic being embedded in the computation of multiple atomic services, thereby facilitating tracking and monitoring, which are crucial desiderata of functional scalability [1, 48].

Despite the above advantages, exogenous composition suffers from performance issues when data follow control [11, 14, 49]. This is because coordinators mediate data streams even for data that are unimportant for them (Figs 2(a) and (b)).² To address this problem, we propose to define control flow and data flow as orthogonal dimensions (Fig. 6). The idea is that coordinators (i.e. composition operators) never exchange data during workflow execution, but only control.

In DX-MAN, a workflow is defined by a concrete workflow tree (Fig. 7(b)). It has an input parameter and an output parameter and describes a series of steps for the invocation of operations in atomic services, sub-workflows or any combination thereof.³ Figure 7(c) shows an example of a sequential workflow for the invocation of the operation opA (provided by the atomic service $S_A$⁠) and the operation opB (provided by the atomic service $S_B$⁠). This workflow variant results from the composition depicted in Figure 7(a) where the atomic services $S_B$ and $S_C$ are composed into the composite $S_D$ by the sequencer operator ${◯}_D$⁠. Likewise, the sequencer operator ${◯}_E$ composes $S_A$ and $S_D$ into the top-level composite $S_E$⁠. For each composite, we select a workflow with a different concrete workflow tree. Note that a DX-MAN composition is done in a hierarchical bottom-up manner and, although there are infinite sequential workflow variants, we describe only one of them for the sake of this paper. Also note that the workflow invoking opB is a sub-workflow of the top-level one. This is because $S_D$ is composed into $S_E$⁠.

A workflow execution traverses a control flow tree from top to bottom and then returns backwards (Fig. 8). Thus, the execution of the workflow depicted in Figure 7(c) starts with the activation of ${◯}_E$⁠, which sequentially passes control to the invocation connector $A$ and then to ${◯}_D$⁠. The latter just forwards control to the invocation connector $B$⁠. Once they are triggered, invocation connectors execute an operation in their computation unit.

If data follow control, it passes through the composition connectors ${◯}_E$ and ${◯}_D$ (Fig. 8(a)). Thus, to avoid such inefficient executions, we propose an approach that enables decentralized data exchanges between atomic services by the separation of control and data (Fig. 8(b)). Our approach is described below.

3.2. Design-time: (semantic) data forest definition

A DX-MAN system is a workflow control flow variant with an orthogonal data forest. The latter is a graph of directed data dependency trees defined on service composition at design-time, whose edges define an explicit relationship between parameters. Formally, a data forest is a graph $F:=(V(F),E(F))$ s.t. $V(F)$ is a (finite or infinite) set of parameter vertices and $E(F)$ is a (finite or infinite) set of edges. As a vertex $v\in V(F)$ is of type $\mathbb{D}$⁠, an edge $e\in E(F)$ is a tuple of type $\mathbb{D}\times \mathbb{D}$ where $\mathbb{D}$ is the parameter type.

For a parallelizer, the workflow input is connected to the inputs of all the invoked elements (i.e. operations or sub-workflows) whose outputs are, in turn, connected to the workflow output. In this paper, we only describe how parallel and sequential data forests are formed, since decentralized data flows are only meaningful for parallelism and sequencing. For a sequencer, the connection of vertices forms a data pipeline, so the output of an invoked element is connected to the input of the next invoked element. Additionally, the workflow input is connected to the input of the first invoked element, and the output of the last invoked element is connected to the workflow output.

Figure 9 analyses thoroughly the composition depicted in Figure 7. It shows the sequential workflow variants and the data forests for the composites $S_D$ and $S_E$⁠. Such forests conform to the rules described for a sequencer. The analysis is segmented because every composite in the DX-MAN model is a black box that can have any possible behaviour out of the alternative ones. Thus, as there are no (bridge) connections between data dependency trees of different forests, data are encapsulated in composite services. Therefore, composites (with all their workflows and data forests) are reusable across different IoT systems.

Reusability is also present in the composite depicted in Figure 10(a), which shows an example where the parallelizer ${◯}_Z$ composes the atomic services $S_X$ and $S_Y$ into the composite $S_Z$⁠. In this example, we define a concrete workflow tree for executing all the sub-service operations in parallel. The resulting workflow has a fork construct to pass control in parallel to opX and opY, and a join construct to synchronise control flow. Choosing this workflow implies that there is a data forest conforming to the rules previously described for a parallelizer (Fig. 10(b)).

Although decentralized data flows are only meaningful for parallelism and sequencing, for completeness we describe how branchial data forests are formed. For both exclusive and inclusive selectors, the corresponding connection scheme is isomorphic to the one defined for a parallelizer in which the workflow input is connected to the inputs of all the invoked elements, and the outputs of the elements are connected to the workflow output (Fig. 10(b)). This connection is done to ensure that there is an output value no matter the execution branch taken.

3.3. Deployment-time: data forest refinement

At deployment-time, a data forest can be (manually) refined in three different ways: (i) by adding or removing edges, (ii) by adding input data into exogenous operators or (iii) by introducing data processors. These refinements are entirely optional with the overall aim of providing extra flexibility for system modellers. To understand them, we consider the data forest of the composite $S_E$ (shown in Fig. 9):

where $iE,oE,iA,oA,iD,oD\in \mathbb{D}$⁠.

For all the scenarios, we show how edges and vertices change with respect to the original data forest (Fig. 11(a)).

3.3.1. Edges refinement

Refining edges is useful for changing data relationships and optimizing data flows. For instance, the edge $(iE,iA)$ can be removed when the operation opA does not need any data to perform computation. Similarly, by replacing $(oA,iD)$ with $(iE,iD)$⁠, the sub-workflow $S_D$ receives data from the top-level input instead of getting it from opA (Fig. 11(b)). Formally, $E(F_E)$ becomes $E(F_E)\setminus \{(iE,iA),(oA,iD)\}\cup \{(iE,iD)\}$⁠.

3.3.2. Exogenous operator refinement

Although they do not perform any computation, exogenous operators might require input values to evaluate boolean conditions at run-time. By default, exogenous operators do not have any parameters, but parameters can be added for a specific workflow. To do so, new vertices are added into the respective data forest and connected manually at the discretion of the modeller. Edge connections must conform to the rules described in [49]. Figure 11(d) shows an example of this kind of refinement, where $iO\in \mathbb{D}$ represents the input parameter of the composition operator that coordinates the execution of the workflow $S_E$⁠. Formally, $V(F_E)$ becomes $V(F_E)\cup \{iO\}$ and $E(F_E)$ becomes $E(F_E)\cup \{(iE,iO)\}$⁠.

3.3.3. Data processor refinement

Data processors can be introduced in a data forest to perform intermediate processing. A data processor is a function that receives at least one input data, performs some custom computation and stores result(s) in at least one output (Fig. 11(c)). By introducing data processors, we avoid tangling with the original workflow control flow of an IoT system. Although the DX-MAN model currently supports the most common data patterns (i.e. map-reduce and filtering), other data processors can be defined using the same semantics. For instance, a replicator could be introduced to copy data to multiple parameters.

Figure 11(e) customises $F_E$ by filtering the data generated by opA before sending it to the sub-workflow $S_D$⁠. Formally, $V(F_E)$ becomes $V(F_E)\cup \{iF,oF\}$ and $E(F_E)$ becomes $E(F_E)\setminus \{(oA,iD)\}\cup \{(oA,iF),(oF,iD)\}$ s.t. $iF,oF\in \mathbb{D}$ are the filter parameters. Figure 11(f) shows another refinement, where a mapper collects data from both opA and the parent workflow to create a list of transformed key-value pairs. The list is then processed by a reducer which produces an output in a suitable format for $S_D$⁠. Formally, $V(F_E)$ becomes $V(F_E)\cup \{iM,i{M}^{\prime },oM,iR,oR\}$ and $E(F_E)$ becomes $E(F_E)\setminus \{(iE,iA),(oA,iD)\}\cup \{(iE,i{M}^{\prime }),(oA,iM),(oM,iR),(oR,iD)\}$ s.t. $iM,i{M}^{\prime },oM\in \mathbb{D}$ are the mapper parameters and $iR,oR\in \mathbb{D}$ are the reducer parameters.

3.4. Deployment-time: data forest analysis

Once data forests have been defined and refined (if needed), a direct mapping between consumer parameters and producer parameters is created. To describe our approach, some formal notations are provided.

 

 

 

 

 

 

 

Our approach analyses the edges of all the data forests of an IoT system, from bottom to top with a complexity of $O(k)$ s.t. $k$ is the total number of edges in a multi-level composition (Fig. 12). As they do not require any data manipulation, workflow parameters (i.e. composite service parameters) are discarded by transforming the binary relations $\varsigma$ and $\rho$ each time an edge is analysed. When all edges have been processed, $\varsigma$ is the result of our approach, i.e. a direct mapping from data consumers to data producers.

We have designed Algorithm 1 to analyse individual data forest edges. The algorithm uses the sets $X_p\subset \mathbb{D}$ and $Y_c\subset \mathbb{D}$ to process the endpoints of an edge $e\in \mathbb{D}\times \mathbb{D}$⁠. The elements of these sets are determined according to two fundamental rules. The first one is shown in lines 4–7. It states that $X_p$ is the set of vertices connected to the tail parameter  ${\mathrm{\Pi }}_1(e)$ if the tail is not a data processor parameter and has incoming connections; otherwise, $X_p$ only contains the tail. The second rule is shown in lines 8–13. It states that if the head parameter  ${\mathrm{\Pi }}_2(e)$ is not in a data processor and has outgoing connections, then (i) $Y_c$ has the vertices connected from the head parameter and (ii) $X_p$ (without the head parameter) is the set of additional producers for each consumer $y\in Y_c$⁠. Otherwise, $Y_c$ just contains the head parameter ${\mathrm{\Pi }}_2(e)$ and the elements of $X_p$ are additional producers of ${\mathrm{\Pi }}_2(e)$⁠. After processing the above rules, the relation $\rho$ is updated to map each producer $x\in X_p$ to each consumer $y\in Y_c$⁠. Appendix  C presents a simple example using this algorithm. A more detailed example is presented in Section 5.

4. IMPLEMENTATION

The DX-MAN platform [50] implements the semantics of the DX-MAN model and provides Java APIs to algebraically compose, deploy and execute IoT systems. Our approach is implemented on top of that platform and uses the Blockchain as the underlying decentralized data space. Please note that a Blockchain platform is just a possible implementation of a decentralized data space. Other possible implementations include OpenLink Data Spaces (ODS), ZeroMQ messaging, a shared memory for IoT or even Apache Storm.⁴ We chose a Blockchain implementation to ensure data ownership for every service and data provenance for discovering data flow histories. Furthermore, we guarantee an extra layer of performance, security and auditability. It is important to note that we do not claim any contributions in terms of implementation. Our implementation is just for validation purposes.

Our approach uses Hyperledger Fabric 1.2 as the underlying Blockchain infrastructure and Hyperledger Composer 0.20.0 to define a Blockchain model based on three smart contracts (Fig. 13). CreateParameters initialises the consumer parameters of an IoT system, whereas UpdateParameters and ReadParameters change and retrieve a list of parameter values from the data space, respectively. The implementation logic of the contracts is written in JavaScript and it is shown in Appendix  D.

The DX-MAN platform provides the programming abstractions for composing IoT services (at design-time) and selecting IoT workflows (at deployment-time). When a workflow is selected, a data forest is automatically created for the respective control flow. Workflow selection is out of the scope of this paper; on this matter, we refer the reader to [42]. Also, to guarantee openness and replicability, the source code of the DX-MAN platform is available at https://github.com/damianarellanes/dxman.

Once workflows have been selected, Algorithm 1 analyses the edges of all the data forests involved to build a Java Hashmap (i.e. a binary relation $\varsigma$⁠) with a consumer parameter UUID as the key and a list of producer parameter UUIDs as the value. The entries of the map are stored as Parameter assets in the Blockchain using the transaction CreateParameters. In particular, the field parameterId is the hashmap key and the field producers is the hashmap value (see lines 7 and 12 in Fig. 13).

At run-time, exogenous operators coordinate an IoT system execution by passing control only via CoAP messages.⁵ When an exogenous operator receives control, it performs one of the processes shown in Figure 14(b and c) only if input data are needed; otherwise, steps 1–2 are omitted. When control triggers an invocation connector, the latter performs the process shown in Figure 14(a). Firstly, the connector executes the transaction ReadParameters to retrieve the necessary inputs from the data space. For each input, the Blockchain directly consumes values from the producer list.

Producer data are stored in the Blockchain as soon as it is available, even before control reaches consumer services. To avoid run-time synchronisation problems, control flow blocks in an invocation connector until all needed input values are retrieved. Next, the connector executes the computation of an operation by passing it the respective data. The result is stored in the Blockchain via the transaction UpdateParameters.

UpdateParameters raises an UpdateParameterEvent after changing a parameter value. This is useful for data processor instances that subscribe to events notified by producer parameters. Thus, a data processor instance performs a user-defined computation after receiving all the events for its inputs. Currently, our implementation supports mappers, reducers and filters, but further processors (e.g. a replicator) can be implemented conforming to the semantics presented in Section 3.3.

Consumer parameters are unaware of data producers, and vice versa, since data references are stored in the Blockchain. Furthermore, the mapping generated by Algorithm 1 avoids the inefficient approach of passing data values through exogenous operators at run-time. Therefore, as consumer parameters read data directly from producers and they are unaware of each other, our approach enables a (transparent) decentralized data exchange.

5. CASE STUDY

This section describes how to enable decentralized data flows in the smart parking scenario presented in Section 2, by covering the three phases of a DX-MAN system life-cycle.

5.1. Design-time

At design-time, we use the syntactic constructs presented in Section 3 to define a multi-level composition structure for our smart parking application (Fig. 15). This process is done in a hierarchical bottom-up manner, starting with the composition of Sensor Services into SensorNet, via the parallelizer operator ${◯}_N$⁠. Afterwards, we use the sequencer operator ${◯}_C$ to compose the SensorNet composite, the Availability Checking Service and the Reservation Service into CityManagement. In the next level, the GPS Service and CityManagement are composed into Information via the parallelizer operator ${◯}_I$⁠. Finally, we use the sequencer ${◯}_T$ to compose Information, Mapping Service and Space Finding Service into CarControlApp (i.e. the top-level composite). Note that, according to the semantics presented in Section 3, each composite service is a workflow space with a (finite or infinite) set of workflow variants and a (finite or infinite) set of data forest variants. For clarity and conciseness, we do not present them. Instead, we refer the reader to our previous work on this matter [42, 43].

5.2. Deployment-time

For each composite, we define a concrete workflow tree to explicitly choose a workflow and a data forest from the respective space (Section 3). In particular, for SensorNet there is a workflow that executes all sensor operations in parallel. For CityManagement, there is a workflow that sequentially invokes the SensorNet sub-workflow, the getFree operation and the getUnreser operation, in that order. For Information, there is a workflow that synchronises the execution of the getLocation operation and the CityManagement sub-workflow. Finally, in the top-level composite, the Information sub-workflow, the computeDis operation and the getNearest operation are triggered sequentially. The concrete workflow trees for each composite are shown in Figure 16 and the whole workflow of our scenario is depicted in Figure 17(a). The latter is just a concatenation of individual workflows.

In Section 3, we mentioned that data forests are implicitly selected when workflows are chosen. On that basis, the resulting data forests for each composite service are shown in Figure 16 and the complete concatenation of data forests is illustrated in Figure 17(b). Note that both workflows and data forests are not manually created, but just selected using the syntactic representation of concrete workflow trees.

Once data dependencies are in place, some data forests are refined (Fig. 18(a)). In particular, we remove the edges between the inputs of the parallel composites (i.e. SensorNet and Information) and the inputs of their respective sub-services. Similarly, we remove the edges connecting the inputs of the sequential composites (i.e. CarControlApp and CityManagement) and the inputs of the parallel composites. Note that this does not mean that edges are always refined. In some scenarios, refinement never takes place.

After refinement, Algorithm 1 analyses the edges of each data forest from the bottom-level composite (i.e. SensorNet) to the top-level one (i.e. CarControlApp). The resulting binary relation between consumer parameters and producer parameters is illustrated in Figure 18(b).

5.3. Run-time

At run-time, composition operators coordinate the execution of the selected workflow by passing control only (Fig. 19(a)), while atomic services exchange data directly (Fig. 19(b)). In particular, when a driver requests a nearest parking space, ${◯}_T$ passes control to the ${◯}_I$ operator which, in turn, forks control towards the invocation connector $G$ and the ${◯}_C$ operator. When $G$ is triggered, it activates the getLocation operation before passing control back to ${◯}_I$⁠. Meanwhile, ${◯}_C$ forwards control to ${◯}_N$ for activating the invocation connectors of all the sensors. After receiving control from all of them, ${◯}_N$ notifies the ${◯}_C$ operator for executing the operations getFree and getUnreser via their invocation connectors. Once control returns from $R$⁠, ${◯}_C$ sends control back to ${◯}_I$⁠. If the latter has received control from $G$ and ${◯}_C$⁠, it notifies ${◯}_T$ for invoking the operations computeDis and getNearest via $M$ and $S$⁠, respectively. The execution of the smart parking app terminates when ${◯}_T$ receives control from $S$⁠.

Figure 19 illustrates the execution of the smart parking scenario, where it is clear that data never passes alongside control, but it flows in a decentralized manner according to the binary relation shown in Figure 18(b). It is important to note that control blocks in an invocation connector until all producer values become available (Section 4). For instance, $A$ waits until all sensor data have been produced, before executing the getFree operation; thereby, guaranteeing synchronisation between the Availability Checking Service and all Sensor Services. Situations like this can be common since control generally travels faster than data over the network, and they may happen even in sequential workflows. This implies that an operation can be executing while control waits in the invocation connector of the next service in a pipeline.

6. DISTRIBUTED DATA FLOWS VERSUS DECENTRALIZED DATA FLOWS IN THE SMART PARKING SCENARIO

This section presents a quantitative comparison between the proposed approach (when data are separated from control) and distributed data flows (when data follow control), in terms of network traffic generated and response time perceived. Our evaluation is based on two OMNET++ simulations in which composition operators and invocation connectors are OMNET++ modules, whereas control flow and data flow are channels between modules.⁶ For fairness, we assume ideal wireless channels communicating over IEEE 802.11a links at a rate of $54$Mbps, with no delay and no bit error rate. The configuration of our simulations is shown in Figure 20.

An OMNET++ experiment simulates drivers using the smart parking application between 07:59:45 and 16:26:47 (Appendix  A). In all the experiments, we assume that there is no network traffic for invoking operations, since invocation connectors reside in the same device as their connected operations. Also, composition operators and invocation connectors do not incur any processing time since they only forward data or control. The latter is just a 1-byte signal that activates an operator or a connector.

For simplicity and clarity, we also assume that IoT devices hosting atomic services have a fixed data processing time of $100\mu$ seconds. This assumption is valid since having equal data processing rates does not influence the network traffic generated by atomic services.

Considering the above assumptions, the first experiment simulates decentralized data flows in the smart parking system. Here, control is exchanged among composition operators and invocation connectors, while data are passed between producer connectors and consumer connectors via ideal OMNET++ channels (Fig. 20). These channels simulate read-write operations on a decentralized space (regardless its implementation). These actions are performed by invocation connectors on behalf of their connected operations. In this experiment, the total network traffic from 07:59:45 to 16:26:47 is $51.93$MB (Table 2). The additional traffic with respect to the calculation described in Appendix  B corresponds to the bytes required for control exchange (i.e. $0.44$MB).⁷ This extra traffic is minimal since control is just a 1-byte signal that does not carry any additional data.

The second simulation considers a distributed version of the smart parking scenario, in which data pass alongside control through invocation connectors and composition operators. The only exception is when control traverses from ${◯}_T$ to $G$⁠, and from ${◯}_I$ to the invocation connectors $1$ and 577 (Fig. 21(b)). This is because the GPS Service and the Sensor Services do not require any input data from the CarControlApp composite (Fig. 18(a)). Using distributed data flows, the total network traffic from 07:59:45 to 16:26:47 is $140.63$MB (Table 2).

Although our approach requires 50% more control messages than its counterpart, the network traffic is dramatically minimized by a rate of $2.71$ times, i.e. $(1-\frac{51.93}{140.63})\cdot 100\approx 63.07\mathrm{\%}$ less network traffic than the distributed version. Particularly, the main benefit occurs when data are passed directly from the Reservation Service to the Mapping Service, since the distributed approach requires four network hops whereas our approach requires only one (Fig. 21).

Reducing network traffic improves the overall response time of the smart parking system by an average factor of $4$⁠. This factor is computed as follows:

where ${\psi }_i^{\alpha }$ is the response time perceived by driver $i$ when requesting a parking space under distributed data flows and ${\psi }_i^{\beta }$ is the response time perceived by driver $i$ when requesting a parking space under decentralized data flows. The response times (in seconds) are individually collected from our simulations for the 373 drivers arriving between 07:59:45 and 16:26:47.⁸

As an example, Figure 21 shows the time window for the driver’s request at 08:26 (i.e. 1621 seconds after 07:59:45), where it is clear that the system is executed in 0.08 seconds using the distributed approach and in $0.02$ seconds with the decentralized version. This improvement is due to the fact that data and control travel independently over the network when decentralized data flows are used, so that control arrives before data in certain cases (e.g. see the timeline of $R$⁠) and data arrives before control in others (e.g. see the timeline of $M$⁠).

Table 2 presents the results of a quantitative evaluation that considers a few services. However, the benefit of our approach becomes more evident as the number of services increases. To evaluate this property, known as functional scalability, we conducted an experiment in which we gradually increase the data being processed by the smart parking application through the continuous addition of sensor services (up to 100 000). The aim of this experiment is to analyse network traffic in the order of Gigabytes. The results are shown in Figure 22.

Figure 22 shows that our approach outperforms distributed data flows in terms of data traffic, whereas the distributed version outperforms our approach in terms of control traffic. Despite this, the total network traffic is linearly improved by our approach since control messages are minimal (i.e. they always oscillate below $0.08$ GB). Consequently, the total traffic and the data traffic are almost identical (cf., Fig. 22(a) and (c)).

The next section presents a generic evaluation of functional scalability that is independent of any implementation or specific case studies. In this evaluation, we do not only increase services horizontally (for the same composite) but also vertically (by increasing the number of composition levels).

7. EVALUATION OF FUNCTIONAL SCALABILITY

This section presents a comparative evaluation between decentralized data flows (when control flow and data flow are separated—Fig. 8(b)) and distributed data flows (when data follows control—Fig. 8(a)), in terms of functional scalability. To do so, two major research questions are studied: (RQ1) Does the proposed approach scale with the number of services? and (RQ2) Under which conditions are decentralized data flows beneficial?

To answer the above questions, we conducted a series of experiments based on the following statements.

 

 

 

 

 

 

 

 

 

We assume that ${\mathrm{\Omega }}_{\alpha }$⁠, $\mathrm{\Gamma }$ and $\omega$ include all network communication factors, such as marshalling, unmarshalling, latency and bandwidth, just to name a few.

7.1. Initial experimental setting

The worst performance of a distributed approach occurs when all composite services are sequential. So, for our evaluation we consider the DX-MAN composition shown in Figure 23, which has four hierarchy levels, four atomic services and three composites. The sequential workflow variants selected for each composite and their respective data forests are also presented in the figure.

Figure 24 shows the resulting workflow control flow and the data exchange approaches that we use in our experiments. For the distributed approach (Fig. 24(b)), we consider the graph $G_{\alpha }$ in which data follows control and passes through workflow parameters via nine data flow edges with a ${\mathrm{\Omega }}_{\alpha }(e_j)$ cost each s.t. $e_{j\in [1,9]}\in E_{\alpha }$⁠. Particularly, $G_{\alpha }$ has five data flow walks since the number of producer parameters is directly proportional to the number of walks: $M_{iG}=⟨e_1⟩\in M$⁠, $M_{oA}=⟨e_2,e_3⟩\in M$⁠, $M_{oB}=⟨e_4,e_5⟩\in M$⁠, $M_{oC}=⟨e_6⟩\in M$ and $M_{oD}=⟨e_7,e_8,e_9⟩\in M$ s.t. $iG,oA,oB,oC,oD\in (V_{\alpha }\cap V_p)$ and $e_{j\in [1,9]}\in E_{\alpha }$⁠.

For the decentralized approach (Fig. 24(c)), we consider the graph $G_{\beta }$ in which data are separated from control and passes from producer parameters to consumer parameters directly. In this case, there are five data flows each with a network cost of ${\mathrm{\Omega }}_{\beta }(e_j)$ s.t. $e_{j\in [1,5]}\in E_{\beta }$⁠. For example, the cost of routing the data produced by oA is ${\mathrm{\Omega }}_{\beta }((oA,iB))=\omega (oA)+\mathrm{\Gamma }(iB)$⁠. As $G_{\beta }$ is constructed with Algorithm 1 and does not consider any data exchanges through workflow parameters, the number of edges is directly proportional to the number of producer parameters (i.e. $|E_{\beta }|=|V_{\beta }\cap V_p|=5$⁠) and the number of vertices is twice the number of producers (i.e. $|V_{\beta }|=2|V_{\beta }\cap V_p|=10$⁠). Therefore, $|V_{\beta }|<|V_{\alpha }|\wedge |E_{\beta }|<|E_{\alpha }|\because |V_{\alpha }|=14\wedge |E_{\alpha }|=9$⁠.

7.2. RQ1: does the proposed approach scale with the number of services?

We conducted an experiment to dynamically increase the number of composites in the (four-level) composition shown in Figure 23. The experiment is carried out in $\tau =200000$ steps with $|E_{\alpha }|\in (\mathbb{N}\cap [9,f(\tau )])$ and $|E_{\beta }|\in (\mathbb{N}\cap [5,g(\tau )])$ s.t. $f(c)=4c+9$ is the total number of distributed data flows and $g(c)=2c+5$ is the total number of decentralized data flows, when there are $c\in (\mathbb{N}\cap [0,\tau ])$ new composites in $S_F$⁠.

At each step of the experiment, we compose a replica of $S_E$ into $S_F$ and define a sequential workflow variant for the invocation of the operations opC and opD (Fig. 23). At the end of the experiment, there is a data pipeline in $G_{\alpha }$ for $\tau +1$ composites in $S_F$⁠. In the case of $G_{\beta }$⁠, there are additional data flows between the parameters of the atomic services added.

As they capture the growth pattern of data flows, we use the functions $f(c)$ and $g(c)$ to analytically compare $|E_{\alpha }|$ and $|E_{\beta }|$ as the number of composites increases. Figure 25 shows the result of our analysis under the assumption that the weight functions of $E_{\alpha }$ and $E_{\beta }$ are ${\mathrm{\Omega }}_{\alpha }:E_{\alpha }\to \{1\}$ and ${\mathrm{\Omega }}_{\beta }:E_{\beta }\to \{1\}$⁠. On that basis, it is clear that the number of data exchanges grows linearly with the number of composite services and that the number of distributed data flows grows twice faster than its counterpart. The latter can be strictly explained by the average rate of change $\frac{\mathrm{\Delta }f}{\mathrm{\Delta }g}=2$ in the interval $[0,\tau ]$⁠.

7.3. RQ2: under which conditions are decentralized data flows beneficial?

We conducted two experiments to determine if there is a benefit of decentralized data flows as the number of levels increases in a DX-MAN composition. To do so, we consider the total network costs of passing the output oD (of the atomic service $S_D$⁠) to an output oT (of a top-level composite), using both the distributed approach and the decentralized one s.t. $oT\in V_c$⁠. For both experiments, we assume that $im({\mathrm{\Omega }}_{\alpha }),im(\omega ),im(\mathrm{\Gamma })\in \mathbb{R}\cap (0,1]$⁠.

For each experiment, we compute ten samples over 100 levels each. At each sample, we increase the number of composition levels by $1$ and define random network costs for $E_{\alpha }$ and $E_{\beta }$ using ${\mathrm{\Omega }}_{\alpha }$ and ${\mathrm{\Omega }}_{\beta }$⁠, respectively. The decentralized approach yields a graph with the same number of edges no matter the composition levels, whereas the distributed approach increases the number of edges by $1$ at every level. Thus, $|M_{oD}|$ also increases by $1$⁠. The improvement rate of the decentralized approach is given by $1-\frac{\beta ((oD,oT))}{\alpha (M_{oD})}$⁠.

Figure 26 shows the result of our experiments, where it is clear that the benefit of decentralized data flows is logarithmic and, as such, it becomes more evident as the number of levels of a DX-MAN composition increases. This is because $|M_{oD}|$ increases at every level and so $\alpha (M_{oD})$⁠. In the experiments, we allocate network costs using random values uniformly distributed in $(0,1]\in \mathbb{R}$⁠. However, if the cost of performing operations on a data space (i.e. $\beta ((oD,oT))$⁠) is more expensive than the total cost of routing data through composite coordinators (i.e. $\alpha (M_{oD})$⁠), the decentralized approach is outperformed by the distributed one. Thus, a DX-MAN composition only benefits from the proposed approach iff $\beta ((oD,oT))<\alpha (M_{oD})$⁠.

8. CONCLUSIONS

In this paper, we presented a functionally scalable approach that semantically separates control and data in DX-MAN compositions for the realization of decentralized data flows in service-oriented IoT systems. At design-time, the algebraic semantics of the model allows the definition of data forests that denote data dependencies between service operation parameters. At deployment-time, data forests are (manually) refined and (automatically) analysed by an algorithm that leverages the separation of control and data. The algorithm works for any workflow in a composite workflow space and produces a direct mapping from consumer parameters to producer parameters. Thus, preventing coordinators (i.e. exogenous operators) from passing data at run-time. In fact, exogenous operators coordinate an IoT system execution by passing control only. To realize our approach, we implemented it on top of the DX-MAN platform, which uses the Blockchain as the underlying data space for persisting direct mappings and managing data at run-time. It is important to mention that our approach is not exclusive to a specific data space implementation (e.g. Blockchain or ODS). For that reason, we evaluated the benefits of the proposed approach rather than the benefits of a particular implementation.

Unfortunately, as other composition models have their own constructs and do not define composition operators like DX-MAN, it is not possible to extend other composition model semantics using our proposed approach. Instead, a custom extension per model would be required to enable the semantic separation of data and control. Another interesting future direction is to explore the possibility of incorporating stateful services into the semantics of DX-MAN.

DX-MAN is a service composition model that semantically separates data, control and computation for separate reasoning, monitoring, maintenance and evolution of such dimensions. More concretely, this separation allows passing data from producer parameters to consumer parameters directly and enables the use of distinct technologies to manage control flows and data flows separately. For example, in our implementation we use CoAP to pass control between exogenous operators and the Blockchain for handling data flows.

Our experimental results confirm that our approach scales well with the number of services, by reducing the number of data flows by an average factor of two with respect to a distributed approach (where data follows control). They also show that our approach scales well with the number of levels of a DX-MAN composition. From our results, we found that the proposed approach provides the best performance when the cost of performing operations on a data space is less than the cost of exchanging data over the network. Thus, our solution is potentially beneficial for large-scale IoT systems in which loosely coupled services exchange huge amounts of data continuously.

DATA AVAILABILITY

The data underlying this article are available in UCI Machine Learning Repository at https://archive.ics.uci.edu/ml/datasets/Parking+Birmingham#.

FUNDING

This work was partially supported by the I-BiDaaS project, funded by the European Union's Horizon 2020 Research and Innovation programme under grant agreement No. 780787.

CONFLICT OF INTEREST

The authors declare that they have no known conflict of interest.

Footnotes

REFERENCES

A. APPENDIX

This appendix presents the notation required for the analysis of the IoT scenario described in Section 2. This scenario considers a real-world data set publicly available at https://archive.ics.uci.edu/ml/datasets/Parking+Birmingham#, which collects occupancy status in car parks operated by the Birmingham City Council, from 07:59:45 to 16:26:47 on October 22, 2016 [52]. Table A3 presents the data obtained for the car park BHMBCCMKT01 whose total capacity is $577$⁠. It particularly shows the measurement time, the $t$ seconds elapsed after 07:59:45, the number of occupied spaces $O(t)$ and the rate of available parking spaces (calculated by $1-\frac{O(t)}{577}$⁠).

 

Considering the columns 2 and 4 from our data set, we performed a cubic regression to approximate a function $A(t)$ for the rate of available parking spaces at $t$ seconds. The resulting equation has an average relative error of $1.98\mathrm{\%}$ and it is defined as follows:

where $0\le t\le 30422$⁠.

The probability of a parking space being unreserved at $t$ seconds is then $A(t)$⁠. Following the same trend of demand for parking spaces, the rate of parking spaces that are both free and unreserved at $t$ seconds is given by the function $U(t)$ as follows:

where $0\le t\le 30422$⁠.

B. APPENDIX

This appendix presents the result of the calculations for the total data transmitted over the network in our IoT scenario (Section 2 and Appendix  A). The calculations are presented for each data exchange approach, i.e. centralized data flows, distributed data flows and decentralized data flows. For all of them, we assume that:

1. There are 577 occupancy sensors near a driver, corresponding to each space in the car park BHMBCCMKT01.

2. Each Sensor Service is hosted in an occupancy sensor and produces 100 bytes.

3. Once all sensor data are collected by a reducer, it is processed by the Availability Checking Service.

4. The Mapping Service appends 20 bytes to each parking space that is both free and unreserved. These extra bytes correspond to the distance between the driver’s location and each occupancy sensor.

5. The Space Finding Service produces 40 bytes for the coordinates of the nearest parking space.

6. There is a driver requesting a nearest parking space every $\frac{t_{i+1}-t_i}{\mathrm{\Delta }O(t_i,t_{i+1})}$ seconds between $t_i\in T$ and $t_{i+1}\in T$ (Notation  .15 and Equation 4).

7. The GPS service produces 40 bytes for the coordinates of the driver.

8. The driver always finds a nearest parking space, since the car park is never full (see $O(t)$ in Table A1).

 

For the sake of clarity and conciseness, we use the functions below to compute the number of bytes returned by the Availability Checking Service, the Reservation Service, the Mapping Service and the Space Finding Service, respectively.

 

 

 

 

 

A centralized approach for exchanging data requires two data flows for moving data from a service producer to a service consumer. Therefore, $B_{\gamma }$ denotes the total data exchanged over the network from 07:59:45 to 16:26:47 when a centralized approach is used:

For the distributed approach, each coordinator requires two data flows for passing data between a service producer and a service consumer. In addition, Coordinator1 requires a data flow for moving data to the Coordinator2 which, in turn, requires another data flow for passing data to the Coordinator3. Thus, the exchanges between the Availability Checking Service and the Reservation Service are done with three data flows. Likewise, there are three data flows for passing data from the Reservation Service to the Mapping Service. The symbol $B_{\alpha }$ denotes the total data exchanged over the network from 07:59:45 to 16:26:47 when a distributed approach is used:

A decentralized approach is the most efficient since it requires only one data flow for moving data from a service producer to a service consumer. Based on this premise, $B_{\beta }$ denotes the total data exchanged over the network from 07:59:45 to 16:26:47 when a decentralized approach is used:

Taking into account the above calculations, the distributed approach leads to $(\frac{B_{\alpha }}{B_{\gamma }}-1)\cdot 100\approx 19.80\mathrm{\%}$ more network traffic than the centralized approach. Likewise, the decentralized approach produces $(1-\frac{B_{\beta }}{B_{\gamma }})\cdot 100\approx 50.00\mathrm{\%}$ less network traffic than the centralized approach and $(1-\frac{B_{\beta }}{B_{\alpha }})\cdot 100\approx 58.26\mathrm{\%}$ less traffic than the distributed one.

C. APPENDIX

This appendix presents an example of how data forests are analysed in a bottom-up fashion using the Algorithm 1 at deployment-time. Our example considers the three-level data forest depicted in Figure C.2, which obeys the connection rules described in Section 3.2. Here, G is the forest of a parallel workflow that simultaneously executes the corresponding workflow for F and an atomic operation (with input iD and output oD). The workflow for F sequentially executes the workflow for E and then an atomic operation (with input iC and output oC). To pre-process data, F has a filter that takes the data produced by E before sending it to the corresponding operation. In our example, E is the lowest-level data forest defined by a branchial workflow that uses the input parameter iS to choose an operation to execute (out of two possible ones).

As described in Section 3.4, the deployment process begins at the bottom-level. So, we first analyse the edges of the branchial data forest E via the Algorithm 1. The resulting binary relation is shown in Figure B.1.(a).

In the next step, we analyse the edges of the sequential data forest F to yield the binary relation described in Figure B.1.(b). Here, we can notice that the relations from the output oE are now the relations from iP. This is because the filter input does not require to read from oE. Instead, the filter reads data directly from any of the actual producers, viz. the operation output oA or the operation output oB. Likewise, the input parameters iA, iB and iS do not read data from iE since a new (intermediate) top-level data producer has been found (i.e. iF). Complementarily, the operation input iC reads data directly from the filter output, whereas the (intermediate) top-level output oF reads data from oC.

Finally, in the last deployment step, the edges of the data forest G are analysed to yield the binary relation depicted in Figure B.1.(c). As iG is the new top-level data producer, the relations from consumers iA, iB and iS are updated accordingly. Similarly, as G is a parallel forest, the top-level output oG takes both the data source from oF (i.e. oC) and the output oD. At the end of the deployment process, we have a mapping scheme that discards unnecessary relations to allow data consumers read values directly from data producers.

D. APPENDIX

Figure D.3. presents the JavaScript source code of the three smart contracts used in our implementation. The source code follows the contract model definition described in Section 4.

E. APPENDIX

This appendix presents the notation used throughout the paper.