Unlike conventional blockchains, which have a sequential model and restrictive participation rules, DAG-based blockchains offer a flexible structure for enabling concurrency. When all nodes participate actively, the concurrency in block generation naturally creates conflicting branches. Corrective approaches often discard valid blocks to solve conflicts, leading to resource wastage. In preventive approaches, transactions are even separated into groups for parallel processing, complicating transaction processing with outcomes reconciliation, workload balancing, and correctness challenges. This last incurs high communication costs and high confirmation delays. To leverage the whole participant’s capacity to process transaction, the asynchrony in participation and concurrency in block creation must be preserved by resolving the conflicts without arbitrarily wasting resources. This paper introduces a new corrective approach in DAG-based blockchain that identifies discrepancies between conflicting blocks. These differences are classified into concurrency patterns which are useful for resolving conflicts among concurrent blocks maintaining the asynchrony of the system and without discarding, or reversing transactions.

Currently in computer science, there is a new type of emerging system called Cyber-Physical Systems (CPS). CPSs are found in several vital domains. The main characteristic of this type of system, unlike the rest, is that CPSs interact with the environment through sensors and actuators. The latter introduces a new type of spatio-temporal constraints and/or dependencies. Hence, it is necessary to try to understand, identify, and model the intrinsic spatio-temporal behaviors of these systems. In this paper, we present a study that identifies, characterizes, and classifies spatio-temporal phenomena that exist in nature. We claim that such spatio-temporal behaviors exist in CPSs and that we can take advantage of them to design new and better solutions that will be more efficient and effective. Finally, an emergency message system is presented as a case study to illustrate spatio-temporal behaviors in vehicular networks.

Collaborative Cyber-Physical Systems (CCPSs) have gained prominence in Intelligent Transport Systems, Monitoring Epidemic Spreading, and the Industrial Internet of Things. The devices in CCPSs interact with the environment through sensors and actuators. Additionally, these devices collaborate to achieve a specific task. This collaboration and interaction introduces a new set of challenges related to spatio-temporal constraints and dependencies. Therefore, there is a growing need to understand the inherent spatio-temporal behaviors in CCPSs, as well as to identify and model them effectively. In this paper, we present a comprehensive study that focuses on the identification, characterization, and classification of spatio-temporal phenomena observed in social insect societies. By drawing parallels between the spatio-temporal behaviors exhibited by social insects and those prevalent in Collaborate Cyber-Physical Systems, we assert that similar dynamics can be leveraged to design innovative solutions that are more efficient and effective.

As a decentralized system, Bitcoin has earned its reputation as a reliable and secure method for online payments, eliminating the need for a trusted third party. It supports a range of transaction types, such as Multisig, Pay-to-PubKey (P2PK), Pay-to-Script-Hash (P2SH), Pay-to-Public-Key-Hash (P2PKH), SegWit, and Coinbase. These transactions are designed to meet specific user needs, such as throughput and security. For example, the SegWit method modifies the transaction structure and increases the block size to enhance throughput. Similarly, P2PKH reinforces the security of transactions by covering the public key until the funds are used. However, these changes directly affect the growth of blockchain storage, which is one of the main challenges for Bitcoin's adoption. To the authors' knowledge, we found no comparative studies on storage costs between transaction types. To bridge this gap, this paper presents an exhaustive analysis of the storage used by these Bitcoin transaction types. We analyzed 845 million transactions and found that transaction types such as P2SH and SegWit have reduced storage efficiency. This study paves the way for future research to achieve scalable storage solutions in Bitcoin.

Multi-domain federations support shared network services. Many orchestrators manage the service’s lifecycle. For the shared VNF Forwarding Graph (VNF-FG) reconfiguration, orchestrators update the graph’s logical information, ensuring a consistent behavior for replicas. Only one work in the literature considers sharing the VNF-FG. However, it offers weak consistency guarantees, without considering the VNF-FG’s non-functional dependencies. In case of a conflict, while updating the VNF-FG, the orchestrators solve consensus. However, this adds latency, undermining the goal of Network Function Virtualization. This paper introduces the first coordination-free multi-domain orchestration algorithm for consistent shared VNF-FG reconfiguration. Unlike the current state of the art, the proposed algorithm skips the coordination phase, offers strong eventual consistency, and supports non-functional dependencies. We present two variants: the preventive, where transient inconsistent states are prevented; the corrective, where intermediary inconsistent states, during the updating process, are tolerated. We prove the correctness of our algorithm and evaluate it. The variants, unlike the state of the art, reconfigure consistently the shared VNF-FGs without solving consensus. They offer stronger guarantees compared to the literature, like allowing orchestrators to reject ongoing reconfigurations without a high impact on performance.

Network Function Virtualization (NFV) enables running Virtualized Network Functions (VNF) on top of any generic, commercial off-the-shelf hardware. VNFs rely on the VNF-Forwarding Graph (VNF-FG) concept to describe and implement network topologies. VNF-FGs are provisioned and managed by appropriate orchestrators. In the multidomain approach, and for complex and sophisticated network topologies, VNF-FGs are managed by multiple orchestrators. Despite being a key task in the lifecycle of network services, the reconfiguration of VNF-FGs under multi-domain orchestration has not been thoroughly explored in the literature, focused mostly on the initial VNF-FG placement and embedding. Reconfiguration enables the providers to answer to unforeseen changes in the environment. However, such distributed orchestration might lead to inconsistencies, and thus partial or total failure of network services. In turn, such inconsistencies increase the cost for providers. This paper proposes the use of causal dependencies among orchestrators to provision consistent VNF-FG reconfiguration in distributed multi-domain environments under asynchronous communication channels. The proposed model is implemented and compared with the current ETSI VNF-FG reconfiguration algorithm. Results indicate that, with this proposal, the inconsistencies are reduced compared to the reconfiguration algorithm according to the ETSI standard for VNF-FGs in multi-domain orchestration.

Several works in the literature have proposed migration mechanisms for VNFs, however they only consider the migration of isolated Virtual Network Functions (VNFs) instead of the migration under a shared and chained scenario. Reconfiguration of VNFs, like in the case of migration, is necessary to handle dynamic requirements for the service. However, it is not a straightforward operation. On one hand, it is necessary to coordinate VNFs to achieve migration while maintaining the end-to-end service availability. On the other hand, the new deployment can disrupt the chain and violate predefined services constraints. Moreover if there is no access to global references, migration can introduce inconsistent services due to a lack of knowledge from orchestrators. This paper focuses on the problem of coordinating orchestrators in a NFV federation to achieve migration of shared VNFs with only local domain information. It introduces a novel coordination algorithm that relies on ETSI/MANO specifications. The proposed algorithm is implemented and evaluated for validation purposes. Results show that migration satisfies the constraints for seamless migration and the algorithm obtains better performance compared to state of the art solution with a slight overhead cost when considering the shared VNFs instead of isolated VNFS.

High Performance Computing (HPC) has seen prodigious growth over the past few years and fault tolerance solutions have been incorporated into HPC systems. The most commonly used technique for fault tolerance in HPC is checkpointing. Processes achieve fault tolerance by saving local checkpoint periodically during execution. When a failure occurs, the previously saved global checkpoint can be used to restart the computation from an intermediate state. Quasi-Synchronous Checkpointing (QSC) is attractive because it allows finding consistent global checkpoints without an extra message overhead. QSC algorithms are classified into: Strictly Z-Path Free, Z-Path Free and Z-Cycle Free. Z-paths and Z-cycles are undesirable patterns that can give rise to inconsistent system states. QSC algorithms are often evaluated with regard to performance, generally through simulation. However, few works have been designed to validate their correctness. Our approach validates if a QSC algorithm is correct by modeling its execution into a graph and then verifying over this graph if the algorithm is exempt from undesirable patterns. QSC is based on the Happened-Before Relation (HBR) introduced by Lamport. One main problem linked to the HBR is the combinatorial state explosion. Nevertheless, for a HPC system modeled with a HBR graph, the computational cost for the identification of such patterns becomes prohibitively high. In this paper, we define a set of transformation rules oriented towards the detection of the undesirable patterns over a graph derived from the causal order set abstraction (CAOS) which is equivalent to a HBR graph, but it drastically reduces the statespace of a system.

Service composition is fundamental in the SOA paradigm. It is oriented to build complex applications from smaller components. The design of composing service-based applications is mainly carried out throughout two composition techniques namely choreography and orchestration. Although these two composition models are different in nature, they are complementary. Choreography presents an abstract description of protocols. It offers a top view of the management rules which govern the interactions between the services involved in a decentralized application. On the other hand, orchestration provides details of the executable process at single peers which are necessary for the implementation of choreography. In this context, one open research problem, is the correct transformation of choreography specifications to orchestration specifications since orchestration provides more details to choreography specification. The choreography transformation has been the subject of several research works. Nevertheless, the existing works have considered that the choreography, on which their transformations are based, is correct by default. So, they have not sought to verify whether it is free of any error or not. Actually, due to the message passing nature of web services interaction, many subtle errors can occur. So, it is crucial to implement a checking process oriented to identify eventual incompatibilities that may arise. For this purpose, we present a formal verification approach based on the SPIN model-checker. The approach automatically transforms WS-CDL choreography specifications to Promela code for verification purposes. We verify non-functional properties that are expressed with linear temporal logic.

Distributed systems have undergone a very fast evolution in the last years. Large-scale distributed systems have become an integral part of everyday life with the development of new large-scale applications, consisting of thousands of computers and supporting millions of users. Examples include global Internet services, cloud computing systems, "big data" analytic platforms, peer-to-peer systems, wireless sensor networks and so on. The recent research addresses questions related to the way of how to design, build, operate and maintain large-scale distributed systems. Another question associated to it is how to represent and ensure causal dependencies in such systems in a optimal way. Causal dependencies have been established according to the Happened-Before Relation (HBR), which was introduced by Lamport. The HBR establishes a strict partial order among the events in a system, and therefore, one main problem linked to it is the combinatorial state explosion. To attack this problem the Causal Order Set Abstraction (CAOS) theory arises. CAOS attains the optimal representation at the set level of the causal dependencies of events in a distributed system. In this paper, we propose a mechanism based on the HBR and the Immediate Dependency Relation to automatically model any large-scale distributed system execution into the CAOS form. The resultant CAOS model, expressed in the form of a graph, drastically reduce the state-space of a system. In general, the resultant CAOS graph can be used for different purposes, such as for the design of more efficient algorithms, validation, verification, and/or the debugging of the existing ones, among others. In this paper, we illustrate how the CAOS graph can be used for validation purposes. The mechanism is implemented in C++. The results of its execution shows the viability to support large-scale systems.

Service-oriented architectures (SOA) are hugely adopted. Within the SOA, service composition is fundamental. The design of composing service-based applications is mainly carried out throughout two composition techniques namely choreography and orchestration. Although these two composition models are different in nature, they are complementary. Choreography presents an abstract description of protocols. It offers a top view of the management rules which govern the interactions between the services involved in a decentralized application. On the other hand, orchestration provides details of the executable process at single peers which are necessary for the implementation of choreography. In this context, one open research problem, is the correct transformation of choreography specifications to orchestration specifications since orchestration provides more details to choreography specification. The choreography transformation has been the subject of several research works. Nevertheless, the existing works have considered that the choreography, on which their transformations are based, is correct by default. So, it is crucial to implement a checking process oriented to identify eventual incompatibilities that may arise. For this purpose, we present a formal verification approach based on the SPIN model-checker. The approach automatically transforms WS-CDL choreography specifications to Promela code for verification purposes. We verify non-functional properties that are expressed with linear temporal logic.

Autonomic Computing Systems are oriented to prevent the human intervention and to enable distributed systems to manage themselves. One of their challenges is the efficient monitoring at runtime oriented to collect information from which the system can automatically repair itself in case of failure. Quasi-Synchronous Check pointing is a well-known technique, which allows processes to recover in spite of failures. Based on this technique, several check pointing algorithms have been developed. According to the checkpoint properties detected and ensured, they are classified into: Strictly Z-Path Free (SZPF), Z-Path Free (ZPF) and Z-Cycle Free (ZCF). In the literature, the simulation has been the method adopted for the performance evaluation of check pointing algorithms. However, few works have been designed to validate their correctness. In this paper, we propose a validation approach based on graph transformation oriented to automatically detect the previous mentioned check pointing properties. To achieve this, we take the vector clocks resulting from the algorithm execution, and we model it into a causal graph. Then, we design and use transformation rules oriented to verify if in such a causal graph, the algorithm is exempt from non desirable patterns, such as Z-paths or Z-cycles, according to the case.