Search

Although the emergence of the programmable smart contract makes blockchain systems easily embrace a wide range of industrial services, how to execute smart contracts efficiently becomes a big challenge nowadays. Due to the existence of Byzantine nodes, existing mature concurrency control protocols in database cannot be employed directly, since the mechanism of executing smart contracts varies a lot. Furthermore, even though smart contract execution follows a two-phase style, i.e., the primary node executes a batch of smart contracts in the first phase and the validators replay them in the second phase, existing parallel solutions merely focus on the optimization for the first phase, rather than the second phase. In this paper, we propose a novel two-phase concurrency control protocol to optimize both phases for the first time. First, the primary executes transactions in parallel and generates a transaction dependency graph with high parallelism for validators. Then, a graph partition algorithm is devised to divide the original graph into several sub-graphs to preserve parallelism and reduce communication cost remarkably. Finally, we propose a deterministic replay protocol to re-execute the primary's parallel schedule concurrently. Moreover, this two-phase protocol is further optimized by integrating with PBFT. Theoretical analysis and extensive experimental results illustrate that the proposed scheme outperforms state-of-art solutions significantly.

Exascale workloads are expected to incorporate data-intensive processing in close coordination with traditional physics simulations. These emerging scientific, data-analytics and machine learning applications need to access a wide variety of datastores in flat files and structured databases. Programmer productivity is greatly enhanced by mapping datastores into the application process's virtual memory space to provide a unified “in-memory” interface. Currently, memory mapping is provided by system software primarily designed for generality and reliability. However, scalability at high concurrency is a formidable challenge on exascale systems. Also, there is a need for extensibility to support new datastores potentially requiring HPC data transfer services. In this article, we present UMap , a scalable and extensible userspace service for memory-mapping datastores. Through decoupled queue management, concurrency aware adaptation, and dynamic load balancing, UMap enables application performance to scale even at high concurrency. We evaluate UMap in data-intensive applications, including sorting, graph traversal, database operations, and metagenomic analytics. Our results show that UMap as a userspace service outperforms an optimized kernel-based service across a wide range of intra-node concurrency by 1.22-1.9 ${\times}$ × . We performed two case studies to demonstrate UMap 's extensibility. First, a new datastore residing in remote memory is incorporated into UMap as an application-specific plugin. Second, we present a persistent memory allocator Metall built atop UMap for unified storage/memory.

Cloud systems suffer from distributed concurrency bugs, which often lead to data loss and service outage. This paper presents CLOUDRAID, a new automatical tool for finding distributed concurrency bugs efficiently and effectively. Distributed concurrency bugs are notoriously difficult to find as they are triggered by untimely interaction among nodes, i.e., unexpected message orderings. To detect concurrency bugs in cloud systems efficiently and effectively, CLOUDRAID analyzes and tests automatically only the message orderings that are likely to expose errors. Specifically, CLOUDRAID mines the logs from previous executions to uncover the message orderings that are feasible but inadequately tested. In addition, we also propose a log enhancing technique to introduce new logs automatically in the system being tested. These extra logs added improve further the effectiveness of CLOUDRAID without introducing any noticeable performance overhead. Our log-based approach makes it well-suited for live systems. We have applied CLOUDRAID to analyze six representative distributed systems: Apache Hadoop2/Yarn, HBase, HDFS, Cassandra, Zookeeper, and Flink. CLOUDRAID has succeeded in testing 60 different versions of these six systems (10 versions per system) in 35 hours, uncovering 31 concurrency bugs, including nine new bugs that have never been reported before. For these nine new bugs detected, which have all been confirmed by their original developers, three are critical and have already been fixed.

In distributed systems, the occurrence of an action can give information about the occurrence of other actions. This can be an unwanted situation when 'high' actions of the system need to be kept secret, while allowing users to observe 'low' actions. If it is possible to deduce information about occurrence of high actions by observing only low actions, then the system suffers from an unwanted information flow. 'Reveals' and 'excludes' relations were introduced for modelling and analysing such an information flow among actions of a distributed system that is modelled via Petri nets. In this paper, we provide a formal basis for computing reveals and excludes relations of 1-safe free-choice Petri nets. We introduce the 'maximal-step computation tree' to represent the behaviour of a distributed system under maximal-step semantics. We define a finite prefix of the tree called 'full prefix' and we show that it is adequate for analysing information flow by means of reveals and excludes relations.

Operating in unlicensed ISM bands, ZigBee devices often yield poor performance due to the interference from ever increasing wireless devices in the 2.4 GHz band. Our empirical results show that, a specific interference is likely to have different influence on different outbound links of a ZigBee sender, which indicates the chance of concurrent transmissions . Based on this insight, we propose Smoggy-Link, a practical protocol to exploit the potential concurrency for adaptive ZigBee transmissions under harsh interference. Smoggy-Link maintains an accurate link model to quantify and trace the relationship between interference and link qualities of the sender’s outbound links. With such a link model, Smoggy-Link can translate low-cost interference information to the fine-grained spatiotemporal link state. The link information is further utilized for adaptive link selection and intelligent transmission schedule. We implement and evaluate a prototype of our approach with TinyOS and TelosB motes. The evaluation results show that Smoggy-Link has consistent improvements in both throughput and packet reception ratio under interference from various interferers.

In the era of Internet and big data, contemporary workflows become increasingly large in scale and complex in structure, introducing greater challenges for workflow modeling. Workflows are not with maximized concurrency and block-structuredness in terms of control flow, though languages supporting block-structuredness (e.g., BPEL) are employed. Existing workflow refactoring approaches mostly focus on maximizing concurrency according to dependences between activities, but do not consider the block-structuredness of the refactored workflow. It is easier to comprehend and analyze a workflow that is block-structured and to transform it into BPEL-like processes. In this paper, we aim at maximizing both concurrency and block-structuredness. Nevertheless, not all workflows can be refactored with a block-structured representation, and it is intractable to make sure that the refactored workflows are as block-structured as possible. We first define a well-formed dependence pattern of activities. The control flow among the activities in this pattern can be represented in block-structured forms with maximized concurrency. Then, we propose a greedy heuristics-based graph reduction approach to recursively find such patterns. In this way, the resulting workflow is with maximized concurrency and its block-structuredness approximates optimality. We show the effectiveness and efficiency of our approach with real-world scientific workflows.

Distributed cloud computing environments rely on sophisticated communication and sharing paradigms for ease of access, information processing, and analysis. The challenging characteristic of such cloud computing environments is the concurrency and access as both the service provider and end-user rely on the common sharing platform. In this article, retrieval and storage-based indexing framework (RSIF) is designed to improve the concurrency of user and service provider access to the cloud-stored healthcare data. Concurrency is achieved through replication-free and continuous indexing and time-constrained retrieval of stored information. The process of classifying the constraints for data augmentation and update is performed using deep learning for all the storage instances. Through conditional assessment, the learning process determines the approximation of indexing and ordering for storing and retrieval, respectively. This helps to reduce the time for access and retrieval concurrently, provided the process is not dependent. The simulation analysis using the metrics discontinuous indexing, replicated data, retrieval time, and cost proves the reliability of the proposed framework.

In this article, we propose Failure-atomic Byte-addressable R-tree (FBR-tree) that leverages the byte-addressability, persistence, and high performance of persistent memory while guaranteeing the crash consistency. We carefully control the order of store and cacheline flush instructions and prevent any single store instruction from making an FBR-tree inconsistent and unrecoverable. We also develop a non-blocking lock-free range query algorithm for FBR-tree. Since FBR-tree allows read transactions to detect and ignore any transient inconsistent states, multiple read transactions can concurrently access tree nodes without using shared locks while other write transactions are making changes to them. Our performance study shows that FBR-tree successfully reduces the legacy logging overhead and the lock-free range query algorithm shows up to 2.6x higher query processing throughput than the shared lock-based crabbing concurrency protocol.

Go provides a new concurrency mechanism based on message-passing, which brings a series of new concurrency bugs. The existing tools are highly dependent on model-checking methods in which they take the source program as the input of model-checking tools to detect the potential concurrent bugs. However, these methods can only qualitatively obtain the concurrency of the program but not obtain the exact number of concurrency bugs in the program. Meanwhile, these approaches are not sensitive to dead codes, which are prone to false negatives. Furthermore, few works have been done on detecting WaitGroup-related bugs in Go concurrent programming, which may cause deadlock. To this end, this paper proposes a novel approach GoDetector to detect concurrent bugs. GoDetector uses a detecting algorithm and a pushdown automaton to verify the channel-related concurrent bugs and WaitGroup-related concurrent bugs separately. To support the evaluation of the tool, 30 benchmarks are collected from the existing tools. GoDetector reports 2 channel safety errors, 29 deadlocks, and 11 WaitGroup-related errors. Compared with the existing tool Godel, GoDetector has the capacity to report more concurrency bugs and fewer false positives. GoDetector also offers additional support for the detection of WaitGroup variables. The experimental results indicate that GoDetector is more efficient at detecting the concurrency in regards to accuracy and diversity.

Internet of Things (IoT) is an emerging technology that makes people’s lives smart by conquering a plethora of diverse application and service areas. In near future, the fifth-generation (5G) wireless networks provide the connectivity for this IoT ecosystem. It has been carefully designed to facilitate the exponential growth in the IoT field. Network slicing is one of the key technologies in the 5G architecture that has the ability to divide the physical network into multiple logical networks (i.e. slices) with different network characteristics. Therefore, network slicing is also a key enabler of realisation of IoT in 5G. Network slicing can satisfy the various networking demands by heterogeneous IoT applications via dedicated slices. In this survey, we present a comprehensive analysis of the exploitation of network slicing in IoT realisation. We discuss network slicing utilisation in different IoT application scenarios, along with the technical challenges that can be solved via network slicing. Furthermore, integration challenges and open research problems related to the network slicing in the IoT realisation are also discussed in this paper. Finally, we discuss the role of other emerging technologies and concepts, such as blockchain and Artificial Intelligence/Machine Learning(AI/ML) in network slicing and IoT integration University College Dublin 5GEAR Menot CWCNS 6Genesis Flagship Update citation details during checkdate report - AC

Dynamic dataflow scheduling enables effective exploitation of concurrency while making parallel programming easier. To this end, analyzing the inherent degree of concurrency available in dataflow graphs is an important task, since it may aid compilers or programmers to assess the potential performance a program can achieve via parallel execution. However, traditional concurrency analysis techniques only work for DAGs (directed acyclic graphs), hence the need for new techniques that contemplate graphs with cycles. In this paper we present techniques to perform concurrency analysis on generic dynamic dataflow graphs, even in the presence of cycles. In a dataflow graph, nodes represent instructions and edges describe dependencies. The novelty of our approach is that we allow concurrency between different iterations of the loops. Consequently, a set of concurrent nodes may contain instructions from different loops that can be proven independent. In this work, we provide a set of theoretical tools for obtaining bounds and illustrate implementation of parallel dataflow runtime on a set of representative graphs for important classes of benchmarks to compare measured performance against derived bounds.

When mapping C programs to hardware, high-level synthesis (HLS) tools reorder independent instructions, aiming to obtain a schedule that requires as few clock cycles as possible. However, when synthesizing multithreaded C programs, reordering opportunities are limited by the presence of atomic operations (“atomics”), the fundamental concurrency primitives in C. Existing HLS tools analyze and schedule each thread in isolation. In this article, we argue that thread-local analysis is conservative, especially since HLS compilers have access to the entire program. Hence, we propose a global analysis that exploits information about memory accesses by all threads when scheduling each thread. Implemented in the LegUp HLS tool, our analysis is sensitive to sequentially consistent (SC) and weak atomics and supports loop pipelining. Since the semantics of C atomics is complicated, we formally verify that our analysis correctly implements the C memory model using the Alloy model checker. Compared with thread-local analysis, our global analysis achieves a $2.3\times $ average speedup on a set of lock-free data structures and data-flow patterns. We also apply our analysis to a larger application: a lock-free, streamed, and load-balanced implementation of Google’s PageRank, where we see a $1.3\times $ average speedup compared with the thread-local analysis.

Refactoring has become an effective approach to convert sequential programs into concurrent programs. Many refactoring algorithms and tools are proposed to assist developers in writing high-performance concurrent programs. Although researchers actively conduct surveys on refactoring, we are not aware of any survey that summarizes, categorizes and discusses concurrency-oriented refactoring. To this end, this paper presents a survey that investigates how refactoring assists with concurrent programming. To the best of our knowledge, this paper is the first survey that summarizes the state-of-the-art, concurrency-oriented refactoring. First, we design six research questions addressing the concurrent structure, programming language, performance improvement and consistency evaluation. Second, we answer these questions by examining the related papers and then present the results to show how refactoring provides support for concurrent programming after a decade of development, such as transforming the concurrent structures, supporting parallel language, and improving performance. Finally, we summarize the related works and present the future trends.

Comparison of concurrent programming languages and correctness of program transformations in concurrency are the focus of this research. As criterion we use contextual semantics adapted to concurrency, where may -- as well as should -- convergence are observed. We investigate the relation between the synchronous pi-calculus and a core language of Concurrent Haskell (CH). The contextual semantics is on the one hand forgiving with respect to the details of the operational semantics, and on the other hand implies strong requirements for the interplay between the processes after translation. Our result is that CH embraces the synchronous pi-calculus. Our main task is to find and prove correctness of encodings of pi-calculus channels by CH's concurrency primitives, which are MVars. They behave like (blocking) 1-place buffers modelling the shared-memory. The first developed translation uses an extra private MVar for every communication.We also automatically generate and check potentially correct translations that reuse the MVars where one MVar contains the message and two additional MVars for synchronization are used to model the synchronized communication of a single channel in the pi-calculus.Our automated experimental results lead to the conjecture that one additional MVar is insufficient., In Proceedings EXPRESS/SOS 2020, arXiv:2008.12414

System analysis is a crucial activity throughout component-based architecture design. It enables detecting and correcting errors in the early stage of the system development life cycle. In this article, we consider system analysis in UML2.0 component-based architectural design phase. This is done by proposing a model-driven engineering (MDE) tool called UML2Ada. It enables the systematic translation of a UML2.0 atomic and composite component into Ada concurrent language. This, in turn, supports the validation of the source description using an Ada dynamic analysis tools such as GNATprove and ObjectAda. In addition, by using an Ada static analysis tool such as FLAVERS or INCA, the proposed tool enables the detection of the potential behavioral concurrency properties of the Ada concurrent program.

As the performance gap between processors and storage devices keeps increasing, I/O performance becomes a critical bottleneck of modern high-performance computing systems. In this paper, we propose a pattern-directed and layout-aware data replication design, named PDLA, to improve the performance of parallel I/O systems. PDLA includes an HDD-based scheme H-PDLA and an SSD-based scheme S-PDLA . For applications with relatively low I/O concurrency, H-PDLA identifies access patterns of applications and makes a reorganized data replica for each access pattern on HDD-based servers with an optimized data layout. Moreover, to accommodate applications with high I/O concurrency, S-PDLA replicates critical access patterns that can bring performance benefits on SSD-based servers or on HDD-based and SSD-based servers. We have implemented the proposed replication scheme under MPICH2 library on top of OrangeFS file system. Experimental results show that H-PDLA can significantly improve the original parallel I/O system performance and demonstrate the advantages of S-PDLA over H-PDLA.

An increasing concern that curbs the widespread adoption of KV-SSD is whether or not offloading host-side operations to the storage device changes device behavior, negatively affecting various applications’ overall performance. In this paper, we systematically measure, quantify, and understand the performance of KV-SSD by studying the impact of its distinct components such as indexing, data packing, and key handling on I/O concurrency, garbage collection, and space utilization. Our experiments and analysis uncover that KV-SSD’s behavior differs from well-known idiosyncrasies of block-SSD. Proper understanding of its characteristics will enable us to achieve better performance for random, read-heavy, and highly concurrent workloads.

The increasing use of cloud and HPC systems put more pressure on the efficient utilization of hardware resources to keep costs low. Many dynamic concurrency throttling (DCT) techniques have successfully used to tune the number of executing threads to better balance a parallel application according to its available scalability. Similarly, boosting frequency strategies have been used to speed up the sequential parts’ execution. Given that, we propose Poseidon, the first transparent and automatic approach that cooperatively exploits both techniques to rebalance OpenMP applications without any preprocessing, with no code transformation, recompilation, or OS modification.

Much recent research has been devoted to modeling effects within type theory. Building on this work, we observe that effectful type theories can provide a foundation on which to build semantics for more complex programming constructs and program logics, extending the reasoning principles that apply within the host effectful type theory itself. Concretely, our main contribution is a semantics for concurrent separation logic (CSL) within the F* proof assistant in a manner that enables dependently typed, effectful F* programs to make use of concurrency and to be specified and verified using a full-featured, extensible CSL. In contrast to prior approaches, we directly derive the partial-correctness Hoare rules for CSL from the denotation of computations in the effectful semantics of non-deterministically interleaved atomic actions. Demonstrating the flexibility of our semantics, we build generic, verified libraries that support various concurrency constructs, ranging from dynamically allocated, storable spin locks, to protocol-indexed channels. We conclude that our effectful semantics provides a simple yet expressive basis on which to layer domain-specific languages and logics for verified, concurrent programming., ICFP 2020 camera-ready version

Reliability and real-time are extremely important indicators in the aerospace field. With the increasing complexity of nano satellite missions, research on the reliability and real-time of on-board computers has become very important. This paper uses AM5748 chip manufactured by Texas Instruments as the processor, which is equipped with RT-Linux for the software design of on-board computers. Aiming at the reliability of on-orbit data storage of on-board computers, this paper proposes a loading method combining U-BOOT and N-modular redundant (NMR), which can solve the static operating system’s single event upset (SEU) problem well; aiming at the concurrency problem of on-board computer OS drivers, a priority-based serialized driver framework is designed to solve the possible concurrency problems in the driver layer to a certain extent. Finally, the system's five-mode redundancy is verified by the fault injection, the driver framework is tested by Multi-process concurrency. The results shows that the system can resist the single event upset rate of up to 10-5/(bit∙day), and the driver framework can complete on-orbit multi-task scheduling, which solves the concurrency problems. Thus, the work is of great significance for the reliability and real-time research of nano satellites and on-board computers in orbit applications.

Positioning plays an important role in many IoT applications. Ultra-wideband (UWB)-based positioning is an alternative to GPS in indoor environments due to its multipath resilience and its accuracy and precision. In the presence of a large number of targets to localize, conventional UWB localization fails to provide a practical location update rate. UWB concurrency in conjunction with self-localization has been used in both time-based and phase-based localization making the targets to localize (tags), a relatively passive device with the sole role of receiving wireless packets and calculating its own location. More recently, phase-based concurrent angle estimation also offloaded the hardware complexity and cost to the anchors instead of the tags. In this work, our anchor-oriented approach combines inter-anchor and intra-anchor concurrency for phase-based localization but also allows time-based localization. Our experimental evaluation on a testbed consisting of Decawave platform shows that our technique is not only practical but also performant.

Distributed systems are inevitable part of an IT infrastructure as they offer several benefits over centralized systems. However, designing a distributed system is a very complex and challenging task as it requires a complex infrastructure comprising several components and properties to realise these benefits for users. The properties of a distributed system are the most crucial for its design, implementation and debugging purposes. The inclusion of different types and levels of properties results in different types of distributed systems. However, it is very difficult to understand and analyse all the properties of distributed systems due to their types, levels, complexities, and variations in different application areas. Additionally, some properties are very similar to the properties of other types of systems, which requires a system-specific understanding. Therefore, this paper will analyse the following important properties of distributed systems: resource sharing, openness, concurrency, consistency, idempotency, scalability, availability, reliability, fault tolerance and transparency. It will explain their meaning, types, levels, requirements and compromises in distributed systems.

Concurrency and consistency are the two inherent and complex characteristics of distributed systems. Their types, levels and implementation procedures determine the nature and efficiency of a distributed system. Concurrency and consistency are difficult concepts to understand, moreover, without a comprehensive understanding a complete system cannot be designed and built. Applying a comprehensive understanding of concurrency and consistency to the design of a distributed system will generate a system that is more closely aligned with the desired outcomes. This paper analyses both concurrency and consistency in distributed systems to present a comprehensive understanding of their requirements, types, levels, benefits and limitations. Initially, it analyses concurrency and compares it with parallelism to distinguish the two related but distinct terms. Subsequently, it analyses consistency and different consistency models including a comparative analysis of strong consistency and weak consistency models, and data-centric consistency and client-centric consistency models.

Modern serverless orchestrations are based on either simple step chaining or function invocations. This raises the challenges of implementing high-performance systems. In the context of this, the paper explores how a system can be structured to scale across cross-platform infrastructures by design. This research work has proposed a framework that can be used under circumstances where heavy computation with data consistent results are demanded from the serverless networks, in which the instances depend upon multiple nested servers and the flow of the data is unprecedented without worrying about concurrency and function invocation limitation resulting in zero throttling of requests on the service. This means that the function that needs to be triggered next will be decided by the present function which can demand multiple arguments to run that are to be provided by some other functions. The algorithm is based on the Gaffer Framework which is designed to take care of resource allocation, maintaining the function(servers) level order dependency also sub-level dependency, and resource integration using event-driven semaphore signals. The framework proposed in this paper demonstrates high coordination-free consistency along with the performance that exceeds the current orchestrations. Gaffer Framework run-time system also takes care of distributed data partitioning and efficient handling of machine failures. This makes it simple for programmers with little or no expertise with serverless and distributed systems to create and maintain large interconnected serverless containers.

A decentralized application involves multiple autonomous principals, e.g., humans and organizations. Autonomy motivates (i) specifying a decentralized application via a protocol that captures the interactions between the principals, and (ii) a programming model that enables each principal to independently (from other principals) construct its own protocol-compliant agent. An agent encodes its principal's decision making and represents it in the application. We contribute Deserv, the first protocol-based programming model for decentralized applications that is suited to the cloud. Specifically, Deserv demonstrates how to leverage function-as-a-service (FaaS), a popular serverless programming model, to implement agents. A notable feature of Deserv is the use declarative protocols to specify interactions. Declarative protocols support implementing stateful agents in a manner that naturally exploits the concurrency and autoscaling benefits offered by serverless computing.

In order to understand the relative expressive power of larger concurrent programming languages, we analyze translations of small process calculi which model the communication and synchronization of concurrent processes. The source language SYNCSIMPLE is a minimalistic model for message passing concurrency while the target language LOCKSIMPLE is a minimalistic model for shared memory concurrency. The former is a calculus with synchronous communication of processes, while the latter has synchronizing mutable locations - called locks - that behave similarly to binary semaphores. The criteria for correctness of translations is that they preserve and reflect may-termination and must-termination of the processes. We show that there is no correct compositional translation from SYNCSIMPLE to LOCKSIMPLE that uses one or two locks, independent from the initialisation of the locks. We also show that there is a correct translation that uses three locks. Also variants of the locks are taken into account with different blocking behavior., In Proceedings EXPRESS/SOS 2021, arXiv:2108.09624. Author version at 2107.14651

This paper presents an optimal decision-making strategy for a self-driving car using a game-theoretic approach. To ensure the safety of the decision, Stackelberg game's maximin reward strategy, which considers concurrency, is applied. The receding horizon is included to increase the accuracy of the decision, but the computational burden is high. We assume that the follower takes only one prediction time, not the receding horizon, to relieve the computational burden. For an accurate prediction of interacting vehicles, the intention estimation model is suggested. We demonstrate the efficiency of our approach in a simulation environment and various traffic conditions.

Smart contracts present a uniform approach for deploying distributed computation and have become a popular means to develop security critical applications. A major barrier to adoption for many applications is the public nature of existingsystems, such as Ethereum. Several systems satisfying various definitions of privacy and requiring various trust assumptions have been proposed; however, none achieved the universality and uniformity that Ethereum achieved for non-private contracts: One unified method to construct most contracts. We provide a unified security model for private smart contracts which is based on the Universal Composition (UC) model and propose a novel core protocol, KACHINA, for deploying privacy-preserving smart contracts, which encompasses previous systems. We demonstrate the KACHINA method of smart contract development, using it to construct a contract that implements privacy-preserving payments, along the lines of Zerocash, which is provably secure in the UC setting and facilitates concurrency.

The paper deals with a problem of a work scheduling of a fleet of cooperating forklifts. Their cooperation means that they can perform a given interchangeability. Unfortunately, it causes an inevitable concurrency issue, which has to be resolved in an optimal way. Since the vehicles are autonomous, there are no human operators whose experience could be a selection criteria in solving the above problem. Thus, the paper proposes a novel health-aware-based cost function which takes into account predictions concerning current operational ability of vehicle batteries. To obtain these predictions a Takagi-Sugeno approach is proposed and validated using Li-Ion battery data set provided by NASA PCoE. Finally, it is incorporated into the health-aware fault tolerant control scheme, which can tolerate inevitable delays present in such a transportation system.

International audience; A number of simulation platforms allow the validation of advanced driver assistance systems (ADAS) in virtual road environments. However, the development of virtual tests on top of such platforms may face technical issues. Some are related to the management of the modular and configurable architecture of the simulators. Others come from the physical aspects of the simulation. Also, time and concurrency issues may affect the control of dynamic scenarios. This paper shares our experience with the virtual testing of ADAS during a period of time of more than one year. The technical issues yielded simulation crashes, ill-controlled test executions, incorrect verdict assignments, and caused a waste of time in the running and analysis of useless tests. We discuss the issues and provide recommendations for the practitioners.

International audience; Using a combination of automata-theoretic and game-semantic techniques, we propose a method for analysing higher-order concurrent programs. Our language of choice is Finitary Idealised Concurrent Algol (FICA) due to its relatively simple fully abstract game model. Our first contribution is an automata model over a treestructured infinite data alphabet, called split automata, whose distinctive feature is the separation of control and memory. We show that every FICA term can be translated into such an automaton. Thanks to the structure of split automata, we are able to observe subtle aspects of the underlying game semantics. This enables us to identify a fragment of FICA with iteration and limited synchronisation (but without recursion), for which, in contrast to the whole FICA, a variety of verification problems turn out to be decidable.

The efficiency of block lifecycle determines the performance of blockchain, which is critically affected by the execution, mining and validation steps in blockchain lifecycle. To accelerate blockchains, many works focus on optimizing the mining step while ignoring other steps. In this paper, we propose a novel blockchain framework-FastBlock to speed up the execution and validation steps by introducing efficient concurrency. To efficiently prevent the potential concurrency violations, FastBlock utilizes symbolic execution to identify minimal atomic sections in each transaction and guarantees the atomicity of these sections in execution step via an efficient concurrency control mechanism-hardware transactional memory (HTM). To enable a deterministic validation step, FastBlock concurrently re-executes transactions based on a happen-before graph without increasing block size. Finally, we implement FastBlock and evaluate it in terms of conflicting transactions rate, number of transactions per block, and varying thread number. Our results indicate that FastBlock is efficient: the execution step and validation step speed up to 3.0x and 2.3x on average over the original serial model respectively with eight concurrent threads.

This paper aims to study how existing trace mining methods work, and their strengths and weaknesses in the context of communication-centric system-on-chip (SoC) traces. SoC traces are unique because of the inherent concurrency, which makes SoC trace mining very challenging. We select seven well-known trace mining methods both from the hardware and software domains. We perform comprehensive experiments, and offer our understanding of the pros and cons of each mining method. We evaluate the interestingness of the mined outcomes for each tool on a benchmark trace set. This trace benchmark includes sophisticated communication traces generated synthetically and realistically. We provide a comprehensive analysis of the performance of the tools, and release the benchmark trace dataset to facilitate future works in SoC trace mining.

A number of approaches have been developed for analysing information flow in concurrent programs in a compositional manner, i.e., in terms of one thread at a time. Early approaches modelled the behaviour of a given thread’s environment using simple read and write permissions on variables, or by associating specific behaviour with whether or not locks are held. Recent approaches allow more general representations of environmental behaviour, increasing applicability. This, however, comes at a cost. These approaches analyse the code in a forwards direction, from the start of the program to the end, constructing the program’s entire state after each instruction. This process needs to take into account the environmental influence on all shared variables of the program. When environmental influence is modelled in a general way, this leads to increased complexity, hindering automation of the analysis. In this paper, we present a compositional information flow analysis for concurrent systems which is the first to support a general representation of environmental behaviour and be automated within a theorem prover. Our approach analyses the code in a backwards direction, from the end of the program to the start. Rather than constructing the entire state at each instruction, it generates only the security-related proof obligations. These are, in general, much simpler, referring to only a fraction of the program’s shared variables and thus reducing the complexity introduced by environmental behaviour. For increased applicability, our approach analyses value-dependent information flow, where the security classification of a variable may depend on the current state. The resulting logic has been proved sound within the theorem prover Isabelle/HOL.

As applications become increasingly data intensive, conventional computing systems become increasingly inefficient due to data access performance bottlenecks. While intensive efforts have been made in developing new memory technologies and in designing special purpose machines, there is a lack of solutions for evaluating and utilizing recent hardware advancements to address the memory-wall problem in a systematic way. In this study, we present the memory Layered Performance Matching (LPM) methodology to provide a systematic approach for data access performance optimization. LPM uniquely presents and utilizes the data access concurrency, in addition to data access locality, in a memory hierarchical system. The LPM methodology consists of models and algorithms, and is supported with a series of analytic results for its correctness. The rationale of LPM is to reduce the overall data access delay through the matching of data request rate and data supply rate at each layer of a memory hierarchy, with a balanced consideration of data locality, data concurrency, and latency hiding of data flow. Extensive experimentations on both physical platforms and software simulators confirm our theoretical findings, and they show that the LPM approach can be applied in diverse computing platforms and can effectively guide performance optimization of memory systems.

The Internet of Things (IoT) is envisioned as a distributed network formed by many end devices, e.g., the motes of wireless sensor network (WSN). These important IoT end devices enable ubiquitous sensing of environments and provide reliable services for mission-critical applications. However, programs running on WSN devices are typically interrupt-driven and prone to interrupt-induced concurrency bugs, which are primarily caused by erroneous interleavings among interrupt procedure instances (IPIs) (namely, executions of interrupt processing logic). In this paper, we use a set of dynamic bug patterns to characterize the concurrency bugs due to buggy access-interleavings among IPIs to shared resources, including shared memory locations and shared communication channels. By matching the above bug patterns, a dynamic analysis approach called disclosing and locating concurrency bugs of interrupt-driven IoT programs based on dynamic bug patterns (Daemon) is proposed to automatically detect and locate concurrency bugs in WSN programs. A GUI tool of Daemon is developed. As the empirical studies exhibit, the tool can discover concurrency bugs effectively and locate the buggy source lines visually.

This paper focuses on a large class of concurrent data structures that we call pool-like objects (e.g., stack, double-ended queue, and queue). Performance and progress guarantee are two important characteristics for concurrent data structures. In the aspect of performance, weakening the internal order in a pool-like object is an effective technique to reduce the synchronization cost among threads accessing the object, but no objects with weakened internal order provide a progress guarantee as strong as wait-freedom. Meanwhile, wait-free algorithms tend to be inefficient, which is mainly attributed to the helping mechanisms. Based on the philosophy of existing helping mechanisms, a wait-free pool-like object with weakened internal order would suffer from unnecessary process of getting the latest object state and synchronization. This paper takes a state-of-the-art implementation of stacks with weakened internal order as an example, and transforms it into a highly-efficient wait-free stack named WF-TS-Stack. The transformation method includes a helping mechanism with state reuse and a relaxed removal scheme. In addition, we use a simple and effective scheme to further improve the performance of WF-TS-Stack in Non-Uniform Memory Access (NUMA) architectures. Our evaluation with representative benchmarks shows that WF-TS-Stack outperforms its original building blocks by up to 1.45× at maximum concurrency. We also discuss how to yield an efficient double-ended queue (deque) variant of WF-TS-Stack, because deque is a more generalized pool-like object.

In the Internet of Things (IoT) community, Wireless Sensor Network (WSN) is a key technique to enable ubiquitous sensing of environments and provide reliable services to applications. WSN programs, typically interrupt-driven, implement the functionalities via the collaboration of Interrupt Procedure Instances (IPIs, namely executions of interrupt processing logic). However, due to the complicated concurrency model of WSN programs, the IPIs are interleaved intricately and the program behaviours are hard to predicate from the source codes. Thus, to improve the software quality of WSN programs, it is significant to disentangle the interleaved executions and develop various IPI-based program analysis techniques, including offline and online ones. As the common foundation of those techniques, a generic efficient and real-time algorithm to identify IPIs is urgently desired. However, the existing instance-identification approach cannot satisfy the desires. In this paper, we first formally define the concept of IPI. Next, we propose a generic IPI-identification algorithm, and prove its correctness, real-time and efficiency. We also conduct comparison experiments to illustrate that our algorithm is more efficient than the existing one in terms of both time and space. As the theoretical analyses and empirical studies exhibit, our algorithm provides the groundwork for IPI-based analyses of WSN programs in IoT environment.

Concurrency bugs widely exist and severely threaten system availability. Techniques that help recover from concurrency-bug failures during production runs are highly desired. This paper proposes BugTM, an approach that applies transactional memory techniques for concurrency-bug recovery in production runs. Requiring no knowledge about where are concurrency bugs, BugTM uses static analysis and code transformation to enable BugTM-transformed software to recover from a concurrency-bug failure by rolling back and re-executing the recent history of a failure thread. BugTM is instantiated as three schemes that have different trade-offs in performance and recovery capability: BugTM$_H$H uses existing hardware transactional memory (HTM) support, BugTM$_S$S leverages software transactional memory techniques, and BugTM$_{\mathrm{HS}}$ HS is a software-hardware hybrid design. BugTM greatly improves the recovery capability of state-of-the-art techniques with low run-time overhead and no changes to OS or hardware, while guarantees not to introduce new bugs.

Scaling complex distributed systems such as e-commerce is an importance practice to simultaneously achieve high performance and high resource efficiency in the cloud. Most previous research focuses on hardware resource scaling to handle runtime workload variation. Through extensive experiments using a representative n-tier web application benchmark (RUBBoS), we demonstrate that scaling an n-tier system by adding or removing VMs without appropriately re-allocating soft resources (e.g., server threads and connections) may lead to significant performance degradation resulting from implicit change of request processing concurrency in the system, causing either over- or under-utilization of the critical hardware resource in the system. We build a concurrency-aware model that determines a near optimal soft resource allocation of each tier by combining some operational queuing laws and the fine-grained online measurement data of the system. We then develop a dynamic concurrency management (DCM) framework that integrates the concurrency-aware model to intelligently reallocate soft resources in the system during the system scaling process. We compare DCM with Amazon EC2-AutoScale, the state-of-the-art hardware only scaling management solution using six real-world bursty workload traces. The experimental results show that DCM achieves significantly shorter tail latency and higher throughput compared to Amazon EC2-AutoScale under all the workload traces.

More than 75% of recent Java projects include some form of concurrent programming. Due to complex interactions between multi-threads, concurrent programs are often harder to understand and test than single threaded programs. To facilitate understanding and testing of concurrent programs, we developed a new profiling method called TCP (Thread Control Profiling). Outputs of TCP presents frequencies of control dependence, which includes thread creation, thread synchronization, interruption, and so on, of the executed thread. TCP first performs static analysis of detailed concurrency syntax and semantics of Java to construct the profiling graph model TCDG (Thread Control Dependence Graph). TCDG is then used for instrumentation and for generating profiles. We have evaluated TCP using a case study and a few experiments. The case study shows that TCP method can effectively prioritize test cases for testing concurrent programs. One experiment shows that outputs from TCP facilitate developers’ understanding of concurrent code. Other experiments evaluate various possible overheads introduced by the TCP method. Results show that TCP can provide rich and useful information with reasonable costs.

Process models are used to describe or verify the correctness of business processes before their implementation by enterprise information systems. With the development of data mining technologies, a lot of event logs generated from such systems can be used to check conformance of business processes and process models. For models containing a choice with concurrency structure, although the model repaired by the existing method can replay the event log, it is quite different from the business process. Therefore, we propose a model repair method based on logic Petri net. First, we give an algorithm to find the position of the deviation. Then, we add directed arcs from a place to a transition or from a transition to a place via logic Petri nets. Finally, we repair the model by adding logic transitions with logic functions. The repaired model can efficiently enhance conformance dimensions, such as simplicity and precision. The correctness and effectiveness of the method are verified by experimental results.

Parallelizing performance-critical applications are of critical importance for harnessing the power of multicore processors, which are now ubiquitous. Even though wait-free algorithms offer the appeal of completing each operation of a parallelized application in a finite number of steps, high-performance wait-free algorithms at high levels of concurrency are still rare. In this paper, we demonstrate one primary reason for this inefficiency: existing wait-free algorithms are not optimized for processors’ caches and write buffers, two key components in modern hardware to accelerate memory accesses. As an example, a wait-free multi-producer-single-consumer queue algorithm, which faces common performance problems of wait-free algorithms, is studied in this paper. We accelerate the queue algorithm by (1) allowing producers to buffer enqueue requests in their local buffers and to write them into the shared queue in batch, to exhibit the spatial locality of the program, and (2) eliminating expensive atomic operations, by giving up some degree of internal consistency to avoid write buffers being drained frequently. The outcome is a write-buffer and cache-friendly queue algorithm which is wait-free and efficient on off-the-shelf multicore processors. The experiments show that the optimized queue algorithm outperforms prior queue algorithms on three different architectures ( $\times $ 86, Power8, and ARMv8). On $\times $ 86, it outperforms WFQueue, the state-of-the-art solution, by 2–3 $\times$ , and outperforms CCQueue, the representative of combining solution, by 4–12 $\times $ . Applying the techniques presented in this paper to other wait-free algorithms is straightforward; our queue example demonstrates that these techniques can be applied to other wait-free algorithms while maintaining the control flow of the original algorithms without dramatic changes.