Recent Linux memory-management interfaces make it practical to revisit distributed shared memory (DSM) as a deployable runtime substrate for conventional multithreaded software. We present Stretch, a userspace fault-driven page-granularity DSM runtime that combines userfaultfd-based fault interception, centralized MSI-style coherence (i.e., Modified, Shared, or Invalid), and CRIU-based thread placement to extend a process across multiple machines. Missing-page and write-protection faults are translated into fetch, invalidation, and ownership-transfer operations, while distributed barriers and coarse-grained mutexes reuse the same mechanism. Stretch supports both automatic tracking of anonymous regions and an explicit tracked-region mode that focuses coherence on genuinely shared memory.

This work introduces StageSAT , a new approach to solving floating-point satisfiability that bridges SMT solving with numerical optimization. StageSAT reframes a floating-point formula as a series of optimization problems in three stages, each with increasing precision. It begins with a fast, projection-aided descent objective to efficiently guide the search toward a feasible region, then proceeds to bit-level accuracy with units-in-the-last-place (ULP) 2 optimization and a final n -ULP lattice refinement to ensure correctness. By construction, the final two stages use a representing function that evaluates to zero if and only if a candidate satisfies all constraints. Thus, whenever optimization drives the bit-precise objective to zero, the resulting assignment is a valid solution, providing a built-in guarantee of soundness (no spurious SAT results). To further improve the search, StageSAT introduces a partial monotone descent property on linear constraints via an orthogonal projection technique, which prevents the optimizer from stalling on flat or misleading objective landscapes. Critically, this solver requires no heavy bit-level reasoning or specialized abstractions of floating-point arithmetic; it treats complex arithmetic as a black box, using runtime evaluations to navigate the input space. We implement StageSAT and evaluate it on extensive benchmarks, including the SMT-COMP’25 floating-point suites and difficult cases from prior work. In our experiments, StageSAT proved both more scalable and more accurate than state-of-the-art optimization-based alternatives. It solved strictly more formulas than any competing solver under the same time budget – in fact, StageSAT found most of the satisfiable instances in our benchmarks and never produced a spurious model for an unsatisfiable formula. This amounts to 99.4% recall on satisfiable cases with 0% false SAT in our benchmarks, exceeding the reliability of prior optimization-based solvers we tested. StageSAT also delivered significant speedups (often 5–10× faster) over traditional bit-precise SMT solvers and earlier numeric solvers. These results demonstrate that our staged optimization strategy can significantly improve both the performance and correctness of floating-point satisfiability solving.

We live in the world of heterogeneous computing. With specialised elements reaching all aspects of our computer systems and their prevalence only growing, we must act to rein in their inherent complexity. One area that has seen significantly less investment in terms of development is heterogeneous-ISA systems, specifically because of complexity. To date, heterogeneous-ISA processors have required significant software overheads, workarounds, and coordination layers, making the development of more advanced software hard, and motivating little further development of more advanced hardware. In this paper, we take a fused approach to heterogeneity, and introduce a new operating system (OS) design, the fused-kernel OS, which goes beyond the multiple-kernel OS design, exploiting cache-coherent shared memory among heterogeneous-ISA CPUs as a first principle -- introducing a set of new OS kernel mechanisms. We built a prototype fused-kernel OS, Stramash-Linux, to demonstrate the applicability of our design to monolithic OS kernels. We profile Stramash OS components on real hardware but tested them on an architectural simulator -- Stramash-QEMU, which we design and build. Our evaluation begins by validating the accuracy of our simulator, achieving an average of less than 4% errors. We then perform a direct comparison between our fused-kernel OS and state-of-the-art multiple-kernel OS designs. Results demonstrate speedups of up to 2.1× on NPB benchmarks. Further, we provide an in-depth analysis of the differences and trade-offs between fused-kernel and multiple-kernel OS designs.

We present two system services - the storage service and the file system service designed for private cloud environments to facilitate file sharing across different virtual machines (VMs). Our services are scalable, fault-tolerant, and deliver excellent performance. These system servers are implemented as unikernels running atop of the Xen hypervisor. Additionally, our storage service can leverage NetBSD code, enabling support for a wide range of both legacy and modern storage devices, such as NVMe. Furthermore, the storage service addresses the challenge of transparent fault recovery for storage, a complex task for stateful subsystems, without incurring significant overhead - a well-known challenge in storage systems. Our file system service is designed to be copy-free, enhancing overall performance. We have also designed an inter-VM communication (IVMC) mechanism that fosters scalability and reliability by leveraging lock-free concurrent ring buffers. Since this mechanism is lock-free, our system services communicate with application VMs in a more scalable manner compared to traditional ring buffers used in hypervisors such as Xen. Our lock-free design also aids in restoring storage states during the fault recovery process of the storage server. Our evaluation results demonstrate that our system services achieve performance comparable to that of Linux.

An emerging trend in the heterogeneous computing space is instruction-set-architecture (ISA) heterogeneity. Data center providers are increasingly incorporating ARM-based hardware into their high-end computing installations which are traditionally made up of x86-based servers. Another interesting trend is the emergence of “smart” I/O devices such as SmartNICs [2] and SmartSSDs which include full-featured SoCs.

Binary-level pointer analysis can be of use in symbolic execution, testing, verification, and decompilation of software binaries. In various such contexts, it is crucial that the result is trustworthy, i.e., it can be formally established that the pointer designations are overapproximative. This paper presents an approach to formally proven correct binary-level pointer analysis. A salient property of our approach is that it first generically considers what proof obligations a generic abstract domain for pointer analysis must satisfy. This allows easy instantiation of different domains, varying in precision, while preserving the correctness of the analysis. In the trade-off between scalability and precision, such customization allows “meaningful” precision (sufficiently precise to ensure basic sanity properties, such as that relevant parts of the stack frame are not overwritten during function execution) while also allowing coarse analysis when pointer computations have become too obfuscated during compilation for sound and accurate bounds analysis. We experiment with three different abstract domains with high, medium, and low precision. Evaluation shows that our approach is able to derive designations for memory writes soundly in COTS binaries, in a context-sensitive interprocedural fashion.

This paper studies an extension of O’Hearn’s incorrectness logic (IL) that allows backwards reasoning. IL in its current form does not generically permit backwards reasoning. We show t at this can be mitigated by extending IL with underspecification. The resulting logic combines underspecification (the result, or postcondition, only needs to formulate constraints over relevant variables) with underapproximation (it allows to focus on fewer than all the paths). We prove soundness of the proof system, as well as completeness for a defined subset of presumptions. We discuss proof strategies that allow one to derive a presumption from a given result. Notably, we show that the existing concept of loop summaries- closed-form symbolic representations that summarize the effects of executing an entire loop at once- is highly useful. The logic, the proof system and all theorems have been formalized in the Isabelle/HOL theorem prover.

Analysis of binary software plays a critical role in software security. Reverse engineers analyze binaries to discover vulnerabilities, patch legacy software, and detect malware. Most of the reverse engineering tools have been developed from a practical point of view, and do not provide any guarantees with their results. Recently, formally verified reverse engineering and decompilation have gained traction. These formal tools are for the most part proof-of-concept systems not yet suitable for real-world reverse-engineering tasks. In this poster, we explore the idea of formalizing part of an existing decompilation tool instead. We focus on the lifting from assembly to the IR P-Code in one of the most popular decompilers, Ghidra. This step occurs immediately after disassembly. We are developing a proof system inside the Isabelle theorem prover, to automatically prove semantical equivalence between the assembly and P-Code instructions. We leverage machine-learned x86-64 semantics, to stay as close as possible to actual CPU behavior. This approach has uncovered several shortcomings in Ghidra's P-Code and the lifting it performs. By using a theorem prover, we obtain guarantees that our system of formal semantics and lifting is internally consistent. This work brings the powerful guarantees that formal methods provide in reverse engineering research to the real world.

We present an approach to lift position-independent x86-64 binaries to symbolized NASM. Symbolization is a decompilation step that enables binary patching: functions can be modified, and instructions can be interspersed. Moreover, it is the first abstraction step in a larger decompilation chain. The produced NASM is recompilable, and we extensively test the recompiled binaries to see if they exhibit the same behavior as the original ones. In addition to testing, the produced NASM is accompanied with a certificate, constructed in such a way that if all theorems in the certificate hold, symbolization has occurred correctly. The original and recompiled binary are lifted again with a third-party decompiler (Ghidra). These representations, as well as the certificate, are loaded into the Isabelle/HOL theorem prover, where proof scripts ensure that correctness can be proven automatically. We have applied symbolization to various stripped binaries from various sources, from various compilers, and ranging over various optimization levels. We show how symbolization enables binary-level patching, by tackling challenges originating from industry.

We present Dapper, a lightweight system that transforms the execution state of a live process into a new process state in a secure and extensible manner. Dapper checkpoints a live process into a process image using Linux's CRIU mechanism, rewrites the image with an updated execution state, and restores program execution. In particular, Dapper can restore the program execution on a CPU with a different architecture by rewriting the process's architecture-specific execution state. Dapper transforms the process externally and only requires inserting a small amount of compile-time metadata to guide the state transformation. Therefore, Dapper brings a smaller attack surface for the transformed program and can be extended for different scenarios in contrast to existing techniques. We build and evaluate a prototype of Dapper using server applications and benchmark suites. Our evaluation shows that Dapper can be extended and used in many different scenarios, such as improving servers' energy efficiency by live program migration on heterogeneous processors and enhancing program security with dynamic randomness of the program states.

Multi-Variant Execution (MVX) is an effective way to detect memory corruption vulnerabilities, intrusions, or live software updates. A traditional MVX system concurrently runs multiple copies of functionally identical, layout-different program variants. Therefore, a typical memory corruption attack that forges pointers can succeed on at most one variant, leading the other variant(s) to crash. The replicated execution adds software security and reliability but also brings multiple times of CPU and memory usage.

The end of Moore's Law has brought significant changes in the architecture of servers used in data centers, increasingly incorporating new ISAs beyond x86-64 as well as diverse accelerators. Further, single-board computers have become increasingly efficient and can run certain Linux applications at significantly lower equipment and energy costs compared to traditional servers. Past research has demonstrated that offloading applications at runtime from x86-based servers to ARM-based single-board computers can result in increases in throughput and energy efficiency. The RISC-V architecture has recently gained significant commercial interest, and OS-capable single-board computers with RISC-V cores are increasingly available at the commodity scale.

Even though heavily researched, a full formal model of the x86-64 instruction set is still not available. We present libLISA , a tool for automated discovery and analysis of the ISA of a CPU. This produces the most extensive formal x86-64 model to date, with over 118 000 different instruction groups. The process requires as little human specification as possible: specifically, we do not rely on a human-written (dis)assembler to dictate which instructions are executable on a given CPU, or what their in- and outputs are. The generated model is CPU-specific: behavior that is “undefined” is synthesized for the current machine. Producing models for five different x86-64 machines, we mutually compare them, discover undocumented instructions, and generate instruction sequences that are CPU-specific. Experimental evaluation shows that we enumerate virtually all instructions within scope, that the instructions’ semantics are correct w.r.t. existing work, and that we improve existing work by exposing bugs in their handwritten models.

Historically, memory management based on lock-free reference counting was very inefficient, especially for read-dominated workloads. Thus, approaches such as epoch-based reclamation (EBR), hazard pointers (HP), or a combination thereof have received significant attention. EBR exhibits excellent performance but is blocking due to potentially unbounded memory usage. In contrast, HP are non-blocking and achieve good memory efficiency but are much slower. Moreover, HP are only lock-free in the general case. Recently, several new memory reclamation approaches such as WFE and Hyaline have been proposed. WFE achieves wait-freedom, but is less memory efficient and performs suboptimally in oversubscribed scenarios; Hyaline achieves higher performance and memory efficiency, but lacks wait-freedom. We present a family of non-blocking memory reclamation schemes, called Crystalline, that simultaneously addresses the challenges of high performance, high memory efficiency, and wait-freedom. Crystalline can guarantee complete wait-freedom even when threads are dynamically recycled, asynchronously reclaims memory in the sense that any thread can reclaim memory retired by any other thread, and ensures (an almost) balanced reclamation workload across all threads. The latter two properties result in Crystalline’s high performance and memory efficiency. Simultaneously ensuring all three properties requires overcoming unique challenges. Crystalline supports ubiquitous x86-64 and ARM64 architectures, while achieving superior throughput than prior fast schemes such as EBR as the number of threads grows. We also accentuate that many recent approaches, unlike HP, lack strict non-blocking guarantees when used with multiple data structures. By providing full wait-freedom, Crystalline addresses this problem as well.

OS-capable embedded systems exhibiting a very low power consumption are available at an extremely low price point. It makes them highly compelling in a datacenter context. We show that sharing long-running, compute-intensive datacenter workloads between a server machine and one or a few connected embedded boards of negligible cost and power consumption can yield significant performance and energy benefits. Our approach, named Heterogeneous EXecution Offloading (HEXO), selectively offloads Virtual Machines (VMs) from server-class machines to embedded boards. Our design tackles several challenges. We address the Instruction Set Architecture (ISA) difference between typical servers (x86) and embedded systems (ARM) through hypervisor and guest OS-level support for heterogeneous-ISA runtime VM migration. We cope with the low amount of resources in embedded systems by using lightweight VMs – unikernels – and by using the server's free RAM as remote memory for embedded boards through a transparent lightweight memory disaggregation mechanism for heterogeneous server-embedded clusters, called Netswap. VMs are offloaded based on an estimation of the slowdown expected from running on a given board. We build a prototype of HEXO and demonstrate significant increases in throughput (up to 67%) and energy efficiency (up to 56%) using benchmarks representative of compute-intensive long-running workloads.

Hardware resource fragmentation is a common issue in data centers. Traditional solutions based on migration or overcommitment are unacceptably slow, and modern commercial or research solutions like Spot VM may reduce or evict VM's resources anytime. We propose an alternative solution that does not suffer from these drawbacks, the Aggregate VM. We introduce a new distributed hypervisor design, the resource-borrowing hypervisor, which creates Aggregate VMs: distributed VMs that temporarily aggregate fragmented resources belonging to different host machines, which require mobility of virtual CPUs, memory and IO devices. We implement a prototype, FragVisor, which runs guest software transparently. We also propose minimal modifications to the guest OS that can enable significant performance gains. We evaluate FragVisor over a set of microbenchmarks and IaaS-style real applications. Although Aggregate VMs are not a perfect fit for every type of applications, some workloads enjoy significant speedups compared to overcommitted scenarios (up to 3.9x with 4 distributed vCPUs). We further demonstrate that FragVisor is faster than a state-of-the-art competitor, GiantVM (up to 2.5x).

Software is becoming increasingly complex and feature-rich, yet only part of any given codebase is frequently used. Existing software customization and debloating approaches target static binaries, focusing on feature discovery, control-flow analysis, and binary rewriting. As a result, the customized program binary has a smaller attack surface as well as less available functionality. This means that once a software's use scenario changes, the customized binary may not be usable.

While address space layout randomization (ASLR) has been extensively studied for user-space programs, the corresponding OS kernel's KASLR support remains very limited, making the kernel vulnerable to just-in-time (JIT) return-oriented programming (ROP) attacks. Furthermore, commodity OSs such as Linux restrict their KASLR range to 32 bits due to architectural constraints (e.g., x86-64 only supports 32-bit immediate operands for most instructions), which makes them vulnerable to even unsophisticated brute-force ROP attacks due to low entropy. Most in-kernel pointers remain static, exacerbating the problem when pointers are leaked.

Converged multi-level secure (MLS) systems, such as Qubes OS or SecureView, heavily rely on virtualization and service virtual machines (VMs). Traditionally, driver domains - isolated VMs that run device drivers - and daemon VMs use full-blown general-purpose OSs. It seems that specialized lightweight OSs, known as unikernels, would be a better fit for those. Surprisingly, to this day, driver domains can only be built from Linux. We discuss how unikernels can be beneficial in this context - they improve security and isolation, reduce memory overheads, and simplify software configuration and deployment. We specifically propose to use unikernels that borrow device drivers from existing general-purpose OSs.

Lifting binaries to a higher-level representation is an essential step for decompilation, binary verification, patching and security analysis. In this paper, we present the first approach to provably overapproximative x86-64 binary lifting. A stripped binary is verified for certain sanity properties such as return address integrity and calling convention adherence. Establishing these properties allows the binary to be lifted to a representation that contains an overapproximation of all possible execution paths of the binary. The lifted representation contains disassembled instructions, reconstructed control flow, invariants and proof obligations that are sufficient to prove the sanity properties as well as correctness of the lifted representation. We apply this approach to Linux Foundation and Intel’s Xen Hypervisor covering about 400K instructions. This demonstrates our approach is the first approach to provably overapproximative binary lifting scalable to commercial off-the-shelf systems. The lifted representation is exportable to the Isabelle/HOL theorem prover, allowing formal verification of its correctness. If our technique succeeds and the proofs obligations are proven true, then – under the generated assumptions – the lifted representation is correct.

The concurrency literature presents a number of approaches for building non-blocking, FIFO, multiple-producer and multiple-consumer (MPMC) queues. However, existing wait-free queues are either not very scalable or suffer from potentially unbounded memory usage. We present a wait-free queue, wCQ, which uses its own variation of the fast-path-slow-path methodology to attain wait-freedom and bound memory usage. wCQ is memory efficient and its performance is often on par with the best known concurrent queue designs.

The concurrency literature presents a number of approaches for building non-blocking, FIFO, multiple-producer and multiple-consumer (MPMC) queues. However, only a fraction of them have high performance. In addition, many queue designs, such as LCRQ, trade memory usage for better performance. The recently proposed SCQ design achieves both memory efficiency as well as excellent performance. Unfortunately, both LCRQ and SCQ are only lock-free. On the other hand, existing wait-free queues are either not very performant or suffer from potentially unbounded memory usage. Strictly described, the latter queues, such as Yang & Mellor-Crummey's (YMC) queue, forfeit wait-freedom as they are blocking when memory is exhausted. We present a wait-free queue, called wCQ. wCQ is based on SCQ and uses its own variation of fast-path-slow-path methodology to attain wait-freedom and bound memory usage. Our experimental studies on x86 and PowerPC architectures validate wCQ's great performance and memory efficiency. They also show that wCQ's performance is often on par with the best known concurrent queue designs.

Byzantine consensus is a critical component in many permissioned Blockchains and distributed ledgers. We propose a new paradigm for designing BFT protocols called DQBFT that addresses three major performance and scalability challenges that plague past protocols: (i) high communication costs to reach geo-distributed agreement, (ii) uneven resource utilization hampering performance, and (iii) performance degradation under varying node and network conditions and high-contention workloads. Specifically, DQBFT divides consensus into two parts: 1) durable command replication without a global order, and 2) consistent global ordering of commands across all replicas. DQBFT achieves this by decentralizing the heavy task of replicating commands while centralizing the ordering process. Under the new paradigm, we develop a new protocol, Destiny that uses a combination of three techniques to achieve high performance and scalability: using a trusted subsystem to decrease consensus's quorum size, using threshold signatures to attain linear communication costs, reducing client communication. Our evaluations on 300-replica geo-distributed deployment reveal that DQBFT protocols achieve significant performance gains over prior art: ≈3x better throughput and ≈50% better latency.

Unikernels are minimal single-purpose virtual machines. They are highly popular in the research domain due to the benefits they provide. A barrier to their widespread adoption is the difficulty/impossibility to port existing applications to current unikernels. HermiTux is the first unikernel providing system call-level binary compatibility with Linux applications. It is composed of a hypervisor and a lightweight kernel layer emulating the load- and runtime Linux ABI. HermiTux relieves application developers from the burden of porting software, while providing unikernel benefits such as security through hardware-assisted virtualized isolation, swift boot time, and low disk/memory footprint. Fast system calls and kernel modularity are enabled through binary rewriting and analysis techniques, as well as shared library substitution. HermiTuxs design principles are architecture-independent and we present a prototype on both the x86-64 and ARM aarch64 ISAs, targeting various cloud as well as edge/embedded deployments. We demonstrate HermiTuxs compatibility over a range of native C/C++/Fortran/Python Linux applications. We also show that it offers a similar degree of lightweightness compared to other unikernels, and that it performs similarly to Linux in many cases: its performance overhead averages 3% in memory- and compute-bound scenarios, and its I/O performance is acceptable.

Datacenter servers are increasingly heterogeneous: from x86 host CPUs, to ARM or RISC-V CPUs in NICs/SSDs, to FPGAs. Previous works have demonstrated that migrating application execution at run-time across heterogeneous-ISA CPUs can yield significant performance and energy gains, with relatively little programmer effort. However, FPGAs have often been overlooked in that context: hardware acceleration using FPGAs involves statically implementing select application functions, which prohibits dynamic and transparent migration. We present Xar-Trek, a new compiler and run-time software framework that overcomes this limitation. Xar-Trek compiles an application for several CPU ISAs and select application functions for acceleration on an FPGA, allowing execution migration between heterogeneous-ISA CPUs and FPGAs at run-time. Xar-Trek's run-time monitors server workloads and migrates application functions to an FPGA or to heterogeneous-ISA CPUs based on a scheduling policy. We develop a heuristic policy that uses application workload profiles to make scheduling decisions. Our evaluations conducted on a system with x86-64 server CPUs, ARM64 server CPUs, and an Alveo accelerator card reveal 88%-l% performance gains over no-migration baselines.

We present a family of safe memory reclamation schemes, Hyaline, which are fast, scalable, and transparent to the underlying lock-free data structures. Hyaline is based on reference counting -- considered impractical for memory reclamation in the past due to high overheads. Hyaline uses reference counters only during reclamation, but not while accessing individual objects, which reduces overheads for object accesses. Since with reference counters, an arbitrary thread ends up freeing memory, Hyaline's reclamation workload is (almost) balanced across all threads, unlike most prior reclamation schemes such as epoch-based reclamation (EBR) or hazard pointers (HP). Hyaline often yields (excellent) EBR-grade performance with (good) HP-grade memory efficiency, which is a challenging trade-off with all existing schemes.

We present a new wait-free memory reclamation scheme, Crystalline, that simultaneously addresses the challenges of high performance, high memory efficiency, and wait-freedom. Crystalline guarantees complete wait-freedom even when threads are dynamically recycled, asynchronously reclaims memory in the sense that any thread can reclaim memory retired by any other thread, and ensures (an almost) balanced reclamation workload across all threads. The latter two properties result in Crystalline’s high performance and high memory efficiency, a difficult trade-off for most existing schemes. Our evaluations show that Crystalline exhibits outstanding scalability and memory efficiency, and achieves superior throughput than state-of-the-art reclamation schemes as the number of threads grows.

Contention plays a crucial role in the design of consensus protocols. State-of-the-art solutions optimize their performance for either very low or high contention situations. We proposeCaesar, a novel multi-leader Generalized Consensus protocol, most suitable for geographical replication, that is optimized for low-to-moderate contention. With an evaluation study, we show thatCaesaroutperforms other multi-leader (e.g., EPaxos) and single-leader (e.g., Multi-Paxos) competitors by up to 1.7x and 3.5x, respectively, in the presence of 30 percent conflicting requests, in a geo-replicated setting. Furthermore, we acknowledge that there is no one-size-fits- all consensus solution, especially for all levels of contentious workloads. Thus, we also proposeSpectrum, a consensus framework that is able to switch consensus protocols at runtime to enable a dynamic reaction to changes in the workload and deployment characteristics. We show empirically thatSpectrumcan guarantee high availability even during periods of transition between consensus protocols.

In this work, we present libHetMP , an OpenMP runtime for automatically and transparently distributing parallel computation across heterogeneous nodes. libHetMP targets platforms comprising CPUs with different instruction set architectures (ISA) coupled by a high-speed memory interconnect, where cross-ISA binary incompatibility and non-coherent caches require application data be marshaled to be shared across CPUs. Because of this, work distribution decisions must take into account both relative compute performance of asymmetric CPUs and communication overheads. libHetMP drives workload distribution decisions without programmer intervention by measuring performance characteristics during cross-node execution. A novel HetProbe loop iteration scheduler decides if cross-node execution is beneficial and either distributes work according to the relative performance of CPUs when it is or places all work on the set of homogeneous CPUs providing the best performance when it is not. We evaluate libHetMP using compute kernels from several OpenMP benchmark suites and show a geometric mean 41% speedup in execution time across asymmetric CPUs. Because some workloads may showcase irregular behavior among iterations, we extend libHetMP with a second scheduler called HetProbe-I. The evaluation of HetProbe-I shows it can further improve speedup for irregular computation, in some cases up to a 24%, by triggering periodic distribution decisions.

Edge computing is a recent computing paradigm that brings cloud services closer to the client. Among other features, edge computing offers extremely low client/server latencies. To consistently provide such low latencies, services should run on edge nodes that are physically as close as possible to their clients. Thus, when the physical location of a client changes, a service should migrate between edge nodes to maintain proximity. Differently from cloud nodes, edge nodes integrate CPUs of different Instruction Set Architectures (ISAs), hence a program natively compiled for a given ISA cannot migrate to a server equipped with a CPU of a different ISA. This hinders migration to the closest node. We introduce H-Container, a system that migrates natively compiled containerized applications across compute nodes featuring CPUs of different ISAs. H-Container advances over existing heterogeneous-ISA migration systems by being (a) highly compatible – no user’s source-code nor compiler toolchain modifications are needed; (b) easily deployable – fully implemented in user space, thus without any OS or hypervisor dependency, and (c) largely Linux-compliant – it can migrate most Linux software, including server applications and dynamically linked binaries. H-Container targets Linux and its already-compiled executables, adopts LLVM, extends CRIU, and integrates with Docker. Experiments demonstrate that H-Container adds no overheads during program execution, while 10–100 ms are added during migration. Furthermore, we show the benefits of H-Container in real-world scenarios, demonstrating, for example, up to 94% increase in Redis throughput when client/server proximity is maintained through heterogeneous container migration.

Increasing the computing performance within a single-machine form factor is becoming increasingly difficult due to the complexities in scaling processor interconnects and coherence protocols. On the other hand, converting existing applications to run on multiple nodes requires a significant effort to rewrite application logic in distributed programming models and adapt the code to the underlying network characteristics.This paper presents DeX, an operating system-level approach to extend the execution boundary of existing applications over multiple machines. DeX allows the threads in a process to be relocated and distributed dynamically through a simple function call. DeX makes it trivial for developers to convert any application to be distributed over multiple nodes and for applications to transparently utilize disaggregated resources in a rack-scale system with minimal effort. Evaluation results using a running prototype and eight real applications showed promising results - six out of the eight scaled beyond the single-machine performance on DeX.

In this work we present libHetMP, an OpenMP runtime for automatically and transparently distributing parallel computation across heterogeneous nodes. libHetMP targets platforms comprising CPUs with different instruction set architectures (ISA) coupled by a high-speed memory interconnect, where cross-ISA binary incompatibility and non-coherent caches require application data be marshaled to be shared across CPUs. Because of this, work distribution decisions must take into account both relative compute performance of asymmetric CPUs and communication overheads. libHetMP drives workload distribution decisions without programmer intervention by measuring performance characteristics during cross-node execution. A novel HetProbe loop iteration scheduler decides if cross-node execution is beneficial, and either distributes work according to the relative performance of CPUs when it is, or places all work on the set of homogeneous CPUs providing the best performance when it is not. We evaluate libHetMP using compute kernels from several OpenMP benchmark suites and show a geometric mean 41% speedup in execution time across asymmetric CPUs.

In this paper, we present a universal memory reclamation scheme, Wait-Free Eras (WFE), for deleted memory blocks in wait-free concurrent data structures. WFE's key innovation is that it is completely wait-free. Although some prior techniques provide similar guarantees for certain data structures, they lack support for arbitrary wait-free data structures. Consequently, developers are typically forced to marry their wait-free data structures with lock-free Hazard Pointers or (potentially blocking) epoch-based memory reclamation. Since both these schemes provide weaker progress guarantees, they essentially forfeit the strong progress guarantee of wait-free data structures. Though making the original Hazard Pointers scheme or epoch-based reclamation completely wait-free seems infeasible, we achieved this goal with a more recent, (lock-free) Hazard Eras scheme, which we extend to guarantee wait-freedom. As this extension is non-trivial, we discuss all challenges pertaining to the construction of universal wait-free memory reclamation.

Due to the slowdown of Moore's Law, systems designers have begun integrating non-cache-coherent heterogeneous computing elements in order to continue scaling performance. Programming such systems has traditionally been difficult - developers were forced to use programming models that exposed multiple memory regions, requiring developers to manually maintain memory consistency. Previous works proposed distributed shared memory (DSM) as a way to achieve high programmability in such systems. However, past DSM systems were plagued by low-bandwidth networking and utilized complex memory consistency protocols, which limited their adoption. Recently, new networking technologies have begun to change the assumptions about which components are bottlenecks in the system. Additionally, many popular shared-memory programming models utilize memory consistency semantics similar to those proposed for DSM, leading to widespread adoption in mainstream programming.

Abstract We present a methodology for generating a characterization of the memory used by an assembly program, as well as a formal proof that the assembly is bounded to the generated memory regions. A formal proof of memory usage is required for compositional reasoning over assembly programs. Moreover, it can be used to prove low-level security properties, such as integrity of the return address of a function. Our verification method is based on interactive theorem proving, but provides automation by generating pre- and postconditions, invariants, control-flow, and assumptions on memory layout. As a case study, three binaries of the Xen hypervisor are disassembled. These binaries are the result of a complex build-chain compiling production code, and contain various complex and nested loops, large and compound data structures, and functions with over 100 basic blocks. The methodology has been successfully applied to 251 functions, covering 12,252 assembly instructions.

We present LibrettOS, an OS design that fuses two paradigms to simultaneously address issues of isolation, performance, compatibility, failure recoverability, and run-time upgrades. LibrettOS acts as a microkernel OS that runs servers in an isolated manner. LibrettOS can also act as a library OS when, for better performance, selected applications are granted exclusive access to virtual hardware resources such as storage and networking. Furthermore, applications can switch between the two OS modes with no interruption at runtime. LibrettOS has a uniquely distinguishing advantage in that, the two paradigms seamlessly coexist in the same OS, enabling users to simultaneously exploit their respective strengths (i.e., greater isolation, high performance). Systems code, such as device drivers, network stacks, and file systems remain identical in the two modes, enabling dynamic mode switching and reducing development and maintenance costs.

Edge computing is a recent computing paradigm that brings cloud services closer to the client. Among other features, edge computing offers extremely low client/server latencies. To consistently provide such low latencies, services need to run on edge nodes that are physically as close as possible to their clients. Thus, when a client changes its physical location, a service should migrate between edge nodes to maintain proximity. Differently from cloud nodes, edge nodes are built with CPUs of different Instruction Set Architectures (ISAs), hence a server program natively compiled for one ISA cannot migrate to another. This hinders migration to the closest node.

Unikernels are minimal, single-purpose virtual machines. This new operating system model promises numerous benefits within many application domains in terms of lightweightness, performance, and security. Although the isolation between unikernels is generally recognized as strong, there is no isolation within a unikernel itself. This is due to the use of a single, unprotected address space, a basic principle of unikernels that provide their lightweightness and performance benefits. In this paper, we propose a new design that brings memory isolation inside a unikernel instance while keeping a single address space. We leverage Intel's Memory Protection Key to do so without impacting the lightweightness and performance benefits of unikernels. We implement our isolation scheme within an existing unikernel written in Rust and use it to provide isolation between trusted and untrusted components: we isolate (1) safe kernel code from unsafe kernel code and (2) kernel code from user code. Evaluation shows that our system provides such isolation with very low performance overhead. Notably, the unikernel with our isolation exhibits only 0.6% slowdown on a set of macro-benchmarks.

This paper presents a methodology for generating formally proven equivalence theorems between decompiled x86-64 machine code and big step semantics. These proofs are built on top of two additional contributions. First, a robust and tested formal x86-64 machine model containing small step semantics for 1625 instructions. Second, a decompilation-into-logic methodology supporting both x86-64 assembly and machine code at large scale. This work enables black-box binary verification, i.e., formal verification of a binary where source code is unavailable. As such, it can be applied to safety-critical systems that consist of legacy components, or components whose source code is unavailable due to proprietary reasons. The methodology minimizes the trusted code base by leveraging machine-learned semantics to build a formal machine model. We apply the methodology to several case studies, including binaries that heavily rely on the SSE2 floating-point instruction set, and binaries that are obtained by compiling code that is obtained by inlining assembly into C code.

Formally verifying functional and security properties of a large-scale production operating system is highly desirable. However, it is challenging as such OSes are often written in multiple source languages that have no formal semantics - a prerequisite for formal reasoning. To avoid expensive formalization of the semantics of multiple high-level source languages, we present a lightweight and rigorous verification toolchain that verifies OS code at the binary level, targeting ARM machines. To reason about ARM instructions, we first translate the ARM Specification Language that describes the semantics of the ARMv8 ISA into the PVS7 theorem prover and verify the translation. We leverage the radare2 reverse engineering tool to decode ARM binaries into PVS7 and verify the translation. Our translation verification methodology is a lightweight formal validation technique that generates large-scale instruction emulation test lemmas whose proof obligations are automatically discharged. To demonstrate our verification methodology, we apply the technique on two OSes: Google's Zircon and a subset of Linux. We extract a set of 370 functions from these OSes, translate them into PVS7, and verify the correctness of the translation by automatically discharging hundreds of thousands of proof obligations and tests. This took 27.5 person-months to develop.

OS-capable embedded systems exhibiting a very low power consumption are available at an extremely low price point. It makes them highly compelling in a datacenter context. In this paper we show that sharing long-running, compute-intensive datacenter HPC workloads between a server machine and one or a few connected embedded boards of negligible cost and power consumption can bring significant benefits in terms of consolidation. Our approach, named Heterogeneous EXecution Offloading (HEXO), selectively offloads Virtual Machines (VMs) from server class machines to embedded boards. Our design tackles several challenges. We address the Instruction Set Architecture (ISA) difference between typical servers (x86) and embedded systems (ARM) through hypervisor and guest OS-level support for heterogeneous-ISA runtime VM migration. We cope with the low amount of resources in embedded systems by using lightweight VMs: unikernels. VMs are offloaded based on an estimation of the slowdown expected from running on a given board. We build a prototype of HEXO and demonstrate significant increase in throughput (up to 67%) and energy efficiency (up to 56%) over a set of macro-benchmarks running datacenter compute-intensive jobs.

We present ezBFT, a novel leaderless, distributed consensus protocol capable of tolerating byzantine faults. ezBFT's main goal is to minimize the client-side latency in WAN deployments. It achieves this by (i) having no designated primary replica, and instead, enabling every replica to order the requests that it receives from clients; (ii) using only three communication steps to order requests in the common case; and (iii) involving clients actively in the consensus process. In addition, ezBFT minimizes the potentially negative effect of a byzantine replica on the overall system performance. We developed ezBFT's formal specification in TLA+, show that it provides the classic properties of BFT protocols including consistency, stability, and liveness, and developed an implementation. Our experimental evaluation reveals that ezBFT improves client-side latency by as much as 40% over state-of-the-art byzantine fault-tolerant protocols including PBFT, FaB, and Zyzzyva.

This paper presents a method for establishing a refinement relation between a binary and a high-level abstract model. The abstract model is based on standard notions of control flow, such as if-then-else statements, while loops and variable scoping. Moreover, it contains high-level data structures such as lists and records. This makes the abstract model amenable for off-the-shelf verification techniques such as model checking or interactive theorem proving. The refinement relation translates, e.g., sets of memory locations to high-level datatypes, or pointer arithmetic to standard HOL functions such as list operations or record accessors. We show applicability of our approach by verifying functions from a binary containing the Network Security Services framework from Mozilla Firefox, running on the x86-64 architecture. Our methodology is interactive. We show that we are able to verify approximately 1000 lines of x86-64 machine code (corresponding to about 400 lines of source code) in one person month.

A system's memory size is often dictated by worst-case workloads with highest memory requirements; this causes memory to be underutilized in the common case when the system is not running its worst-case workloads. Cognizant of this memory underutilization problem, many prior works have studied memory utilization and explored how to improve it in the context of cloud.

Despite extensive research on Byzantine Fault Tolerant (BFT) systems, overheads associated with such solutions preclude widespread adoption. Past efforts such as the Cross Fault Tolerance (XFT) model address this problem by making a weaker assumption that a majority of nodes are correct and communicate synchronously. Although XPaxos of Liu et al. (applying the XFT model) achieves similar performance as Paxos, it does not scale with the number of faults. Also, its reliance on a single leader introduces considerable downtime in case of failures. We present Elpis, the first multi-leader XFT consensus protocol. By adopting the Generalized Consensus specification, we were able to devise a multi-leader protocol that exploits the commutativity property inherent in the commands ordered by the system. Elpis maps accessed objects to non-faulty replicas during periods of synchrony. Subsequently, these replicas order all commands which access these objects. The experimental evaluation confirms the effectiveness of this approach: Elpis achieves up to 2x speedup over XPaxos and up to 3.5x speedup over state-of-the-art Byzantine Fault-Tolerant Consensus Protocols.

Attacks on the heap are an increasingly severe threat. State-of-the-art secure dynamic memory allocators can offer protection, however their memory footprint is high, making them suboptimal in many situations. We introduce Slim-Guard, a secure allocator whose design is driven by memory efficiency. Among other features, SlimGuard uses an efficient fine-grain size classes indexing mechanism and implements a novel dynamic canary scheme. It offers a low memory overhead due its size classes optimized for canary usage, its on-demand metadata allocation, and the combination of randomized allocations and over-provisioning into a single memory efficient security feature. SlimGuard protects against widespread heap-related attacks such as overflows, over-reads, double/invalid free, and use-after-free. Evaluation over a wide range of applications shows that it offers a significant reduction in memory consumption compared to the state-of-the-art secure allocator (up to 2x in macro-benchmarks), while offering similar or better security guarantees and good performance.

We present a new lock-free safe memory reclamation algorithm, Hyaline, which is fast, scalable, and transparent to the underlying data structures. Hyaline easily handles virtually unbounded number of threads that can be created and deleted dynamically, while retaining O(1) reclamation cost. We also extend Hyaline to avoid situations where stalled threads prevent others from reclaiming newly allocated objects, a common problem with epoch-based reclamation. Our evaluation reveals that Hyaline's throughput is high -- it steadily outperformed other reclamation schemes by >10% in one test and yielded even higher gains in oversubscribed scenarios.

In this paper, we investigate the effectiveness of multiprocessor architectures with ISA-different cores for executing HPC workloads. Our envisioned design point in the heterogeneous architecture space is one with multiple cache-coherency domains, with each domain hosting cores of a different ISA and no coherency between domains. We prototype such an architecture using an Intel Xeon x86-64 server and a Cavium ThunderX ARMv8 server, interconnected using a high-speed network fabric. We design, implement, and evaluate policies for scheduling HPC applications with the goal of maximizing workload makespan. Our results reveal that such an architecture is most effective for workloads that exhibit diverse execution times on ISA-different CPUs, with gains exceeding 60% over ISA-homogeneous architectures. Furthermore, cross-ISA execution migration can yield gains up to 38%.

Future computer platforms will likely be built with a multitude of on-chip and off-chip processing units being potentially of different ISAs, OS-capable, and sharing memory with a form of consistency. Multiple-kernel OSes, from multikernels to single-system image OSes, have been demonstrated to mange such platforms efficiently, but they assume no shared memory between kernels as a founding principle. This position paper proposes a new multiple-kernel OS design, which leverages consistent shared memory across homogeneous and heterogeneous processing units in a machine. Among other benefits, this design enables porting commodity SMP OSes to such future platforms, capitalizing on their shared memory programming model, and extend them to multiple-kernel OSes. Herein we present such design, based on two new software primitives tackling the problem of sharing and data format differences between eventually heterogeneous computing units: typed shared memory and type-morphable executable code. We also describe an initial implementation built around Popcorn Linux for x86 and ARM.

We investigate the effectiveness of executing SIMD workloads on multiprocessors with heterogeneous Instruction Set Architecture (ISA) cores. Heterogeneous ISAs offer an intriguing clock speed/parallelism tradeoff for workloads with frequent usage of SIMD instructions. We consider dynamic migration of SIMD and non-SIMD workloads across ISA-different cores to exploit this trade-off. We present the necessary modifications for a general compiler/run-time infrastructure to transform the dynamic program state of SIMD regions at run-time from one ISA format to another for cross-ISA migration and execution. Additionally, we present a SIMD-aware scheduling policy that makes cross-ISA migration decisions that improve system throughput. We prototype a heterogeneous-ISA system using an Intel Xeon x86-64 server and a Cavium ThunderX ARMv8 server and evaluate the effectiveness of our infrastructure and scheduling policy. Our results reveal that cross-ISA execution migration within SIMD regions can yield throughput gains up to 36% compared to traditional homogeneous ISA systems.

Unikernels are minimal single-purpose virtual machines. They are highly popular in the research domain due to the benefits they provide. A barrier to their widespread adoption is the difficulty/impossibility to port existing applications to current unikernels. HermiTux is the first unikernel providing binary-compatibility with Linux applications. It is composed of a hypervisor and lightweight kernel layer emulating OS interfaces at load- and runtime in accordance with the Linux ABI. HermiTux relieves application developers from the burden of porting software, while providing unikernel benefits such as security through hardware-assisted virtualized isolation, swift boot time, and low disk/memory footprint. Fast system calls and kernel modularity are enabled through binary rewriting and analysis techniques, as well as shared library substitution. Compared to other unikernels, HermiTux boots faster and has a lower memory/disk footprint. We demonstrate that over a range of native C/C++/Fortran/Python Linux applications, HermiTux performs similarly to Linux in most cases: its performance overhead averages 3% in memory- and compute-bound scenarios.

We present Lerna, an end-to-end tool that automatically and transparently detects and extracts parallelism from data-dependent sequential loops. Lerna uses speculation combined with a set of techniques including code profiling, dependency analysis, instrumentation, and adaptive execution. Speculation is needed to avoid conservative actions and detect actual conflicts. Lerna targets applications that are hard-to-parallelize due to data dependency. Our experimental study involves the parallelization of 13 applications with data dependencies. Results on a 24-core machine show an average of 2.7× speedup for micro-benchmarks and 2.5× for the macro-benchmarks.

We present Lerna, an end-to-end tool that automatically and transparently detects and extracts parallelism from data dependent sequential loops using speculation combined with a set of techniques including code profiling, dependency analysis, instrumentation, and adaptive execution. Speculation is needed to avoid conservative actions and detect actual conflicts. Lerna targets applications that are hard-to-parallelize due to data dependency. Our experimental study involves the parallelization of 13 applications with data dependencies. Results on a 24-core machine show an average of 2.7x speedup for micro-benchmarks and 2.5x for the macro-benchmarks.

Heterogeneous-ISA computing platforms have become ubiquitous, and will be used for diverse workloads which render static mappings of computation to processors inadequate. Dynamic mappings which adjust an application's usage in consideration of platform workload can reduce application latency and increase throughput for heterogeneous platforms. We introduce AIRA, a compiler and runtime for flexible execution of applications in CPU-GPU platforms. Using AIRA, we demonstrate up to a 3.78× speedup in benchmarks from Rodinia and Parboil, run with various workloads on a server-class platform. Additionally, AIRA is able to extract up to an 87 percent increase in platform throughput over a static mapping.

Energy efficiency is one of the most important design considerations in running modern datacenters. Datacenter operating systems rely on software techniques such as execution migration to achieve energy efficiency across pools of machines. Execution migration is possible in datacenters today because they consist mainly of homogeneous-ISA machines. However, recent market trends indicate that alternate ISAs such as ARM and PowerPC are pushing into the datacenter, meaning current execution migration techniques are no longer applicable. How can execution migration be applied in future heterogeneous-ISA datacenters?

This paper proposes CAESAR, a novel multi-leader Generalized Consensus protocol for geographically replicated sites. The main goal of CAESAR is to overcome one of the major limitations of existing approaches, which is the significant performance degradation when application workload produces conflicting requests. CAESAR does that by changing the way a fast decision is taken: its ordering protocol does not reject a fast decision for a client request if a quorum of nodes reply with different dependency sets for that request. The effectiveness of CAESAR is demonstrated through an evaluation study performed on Amazon's EC2 infrastructure using 5 geo-replicated sites. CAESAR outperforms other multi-leader (e.g., EPaxos) competitors by as much as 1.7x in the presence of 30% conflicting requests, and single-leader (e.g., Multi-Paxos) by up to 3.5x.

The datacenter is becoming fully heterogeneous, integrating multiple OS-capable CPUs of different Instruction Set Architectures in separate machines. These machines present diverse performance and power consumption profiles and we show that significant potential benefits for both metrics can be expected, should these machines be able to cooperate in the processing of datacenter, multi-programmed workloads. We advocate that this cooperation should be enabled at the level of the OS, relieving the programmer from any effort related to the heterogeneity of the managed machines. We propose a distributed OS architecture running on a fully heterogeneous computer cluster, enabling this cooperation through three main components: the abstraction of the entire cluster in a single system image, a distributed shared memory system, and a heterogeneous scheduler.

With the advances in network speeds a single processor cannot cope anymore with the growing number of data streams from a single network card. Multicore processors come at a rescue but traditional SMP OSes, which integrate the software network stack, scale only to a certain extent,limiting an application's ability to serve more connections while increasing the number of cores. On the other hand, kernel bypass solutions seem to scale better, but limit resource flexibility and control. We propose attacking these problems with a distributed OS design, using multiple network stacks (one per kernel) and relying on multi-queue hardware and hardware flow steering. This creates a single-socket abstraction among kernels while minimizing inter-core communication. We introduce our design, consisting of a distributed network stack, a distributed device driver, and a load-balancing algorithm. We compare our prototype, NetPopcorn, with Linux, Affinity Accept, FastSocket. NetPopcorn accepts between 5 to 8 times more connections and reduces the tail latency compared to these competitors. We also compare NetPopcorn with mTCP and observe that for high core counts, mTCP accepts only 18% more connections yet with higher tail latency than NetPopcorn.

As the number of processors and the size of the memory of computing systems keep increasing, the likelihood of CPU core failures, memory errors, and bus failures increases and can threaten system availability. Software components can be hardened against such failures by running several replicas of a component on hardware replicas that fail independently and that are coordinated by a State-Machine Replication protocol. One common solution is to replicate the physical machine to provide redundancy, and to rewrite the software to address coordination. However, a CPU core failure, a memory error, or a bus error is unlikely to always crash an entire machine. Thus, full machine replication may sometimes be an overkill, increasing resource costs. In this paper, we introduce full software stack replication within a single commodity machine. Our approach runs replicas on fault-independent hardware partitions (e.g., NUMA nodes), wherein each partition is software-isolated from the others and has its own CPU cores, memory, and full software stack. A hardware failure in one partition can be recovered by another partition taking over its functionality. We have realized this vision by implementing FT-Linux, a Linux-based operating system that transparently replicates race-free, multithreaded POSIX applications on different hardware partitions of a single machine. Our evaluations of FT-Linux on several popular Linux applications show a worst case slowdown (due to replication) by ≈20%.

The ability to quickly set up and tear down a virtual machine is critical for today's cloud elasticity, as well as in numerous other scenarios: guest migration/consolidation, event-driven invocation of micro-services, dynamically adaptive unikernel-based applications, micro-reboots for security or stability, etc.

The last two decades witnessed the success of many efficient designs of concurrent data structures. A large set of them has a common base principle: each operation is split into a read-only traversal phase, which scans the data structure without locking or monitoring, and a read-write commit phase, which atomically validates the output of the traversal phase and applies the needed modifications to the data structure. In this paper we introduce Optimistic Transactional Boosting (OTB), an optimistic methodology for extending those designs in order to support the composition of multiple operations into one atomic execution by building a single traversal phase and a single commitphase for the whole atomic execution. As a result, OTB-based data structures are optimisticand composable. The former because they defer any locking and/or monitoring to the commit phase of the entire atomic execution; the latter because they allow the execution of multiple operations atomically. Additionally, in this paper we provide a theoretical model for analyzing OTB-based data structures and proving their correctness. In particular, we extended a recent approach that models concurrent data structures by including the two notions of optimism and composition of operations.

The first release of hardware transactional memory (HTM) as commodity processor posed the question of how to efficiently handle its best-effort nature. In this paper we present Part-HTM, a hybrid transactional memory protocol that solves the problem of transactions aborted due to the resource limitations (space/time) of current best-effort HTM. The basic idea of Part-HTM is to partition those transactions into multiple sub-transactions, which can likely be committed in hardware. Due to the eager nature of HTM, we designed a low-overhead software framework to preserve transaction's correctness (with and without opacity) and isolation. Part-HTM is effective: our evaluation study confirms that its performance is the best in all tested cases, except for those where HTM cannot be outperformed. However, in such a workload, Part-HTM still performs better than all other software and hybrid competitors.

New multi-leader consensus protocols leverage the Generalized Consensus specification to enable low latency, even load balancing, and high parallelism. However, these protocols introduce inherent costs with significant performance impact: they need quorums bigger than the minimum required to solve consensus and need to track dependency relations among proposals. In this paper we present M2PAXOS, an implementation of Generalized Consensus that provides fast decisions (i.e., delivery of a command in two communication delays) by leveraging quorums composed of a majority of nodes and by exploiting workload locality. M2PAXOS does not establish command dependencies based on conflicts, instead mapping nodes to accessed objects and enforcing that commands accessing the same objects be ordered by the same node. Our experimental evaluation confirms the effectiveness of M2PAXOS, gaining up to 7X over state-of-the-art Consensus and Generalized Consensus algorithms under partitioned data accesses and up to 5.5× using the TPC-C workload.

Migrating legacy real-time software stacks to newer hardware platforms can be achieved with virtualization which allows several software stacks to run on a single machine. Existing solutions guarantee that deadlines of virtualized real-time systems are met but can only accommodate a reduced number of systems. Therefore, this paper introduces ExVM, a new scheduling framework to maximize the number of legacy uniprocessor real-time systems able to run on a single machine. Contrary to most existing solutions, ExVM uses a flattening approach where the host schedules the virtual machine which contains the task with the earliest deadline. The real-time characteristics of tasks are obtained through introspection during the execution. We implemented this framework using Linux's SCHED_DEADLINE real-time scheduling policy in the host. Simulations using an exact schedulability test show that ExVM is able to schedule 96% of randomly generated tasksets with a utilization of at least 0.8, while state-of-the-art solutions are only able to schedule 40% of the same tasksets. Experimental evaluations performed using synthetic benchmarks and production real-time applications show that ExVM always outperforms the existing solutions, always meeting more than 80% of deadlines while these solutions fall below 50% when the utilization increases.

Leaderless consensus algorithms in the vein of EPaxos have performance advantages, especially for geo-replication, but are also very intricate, making them hard to modify and adapt for specific use cases. In this paper we show that their core principle can be captured in a generic leaderless generalized-consensus algorithm that uses two new abstractions: a dependency-set algorithm, which suggests dependencies for commands, and a map-agreement algorithm, which ensures that, for each submitted command, processes agree on a dependency set. Our generic algorithm gives rise to a family of algorithms whose members are obtained by using concrete dependency-set and map-agreement algorithms. On top of enabling modular correctness proofs of leaderless consensus algorithms, we expect that the modular structure of our generic leaderless algorithm will allow a principled theoretical and empirical evaluation of the trade-offs that can be achieved by different implementations of our two abstractions.

NUMA architectures posed the challenge of rethinking parallel applications due to the non-homogeneity introduced by their design, and their real benefits are limited to the characteristics of the particular workload. We name as partitionable transactional workloads such workloads that may be able to exploit the distributed nature of NUMA, such as transactional workloads where data and accesses can be easily partitioned among the so called NUMA zones. However, in case those workloads require the synchronization on shared data, we have to face the issue of exploiting the NUMA architecture also in the concurrency control for their transactions. Therefore in this paper we present a NUMA-aware concurrency control for transactional memory that we designed for promoting scalability in scenarios where both the transactional workload is prone to scale, and the characteristics of the underlying memory model are inherently non-uniform, such as NUMA architectures.

In this poster paper, we briefly introduce an effective solution to address the problem of committing transactions enforcing a predefined order. To do that, we overview the design of two algorithms that deploy a cooperative transaction execution that circumvents the transaction isolation constraint in favor of propagating written values among conflicting transactions. A preliminary implementation shows that even in the presence of data conflicts, the proposed algorithms outperform other competitors, significantly.

Transactional Memory (TM) has recently emerged as an optimistic concurrency control technique that isolates concurrent executions at the level of memory reads and writes, therefore providing an easy programming interface. However, such transparency could be overly conservative from an application-level perspective. In this work, we propose an extension to the classical TM primitives (read and write) to capture program code semantics (e.g., conditional expressions) while maintaining the same level of programming abstraction. We deployed this extension on two state-of-the-art STM algorithms and integrated it into the GCC compiler and the RSTM software framework. Results showed speedups of up to 4x (average 1.6x) on different applications including micro benchmarks and STAMP.

We present SPCN, a framework that further extends the benefits of having distributed partially rollbackable (closed-nested) transactions by exploiting their parallel activation. SPCN provides support for executing each closed-nested transaction in parallel with others belonging to the same parent transaction. Their commit sequence is equivalent to the serial commit execution, but parallelism is leveraged to improve performance by reducing the amount of serial network communication. As we show in our evaluation study using 20 nodes on Amazon EC2 and three well-known benchmarks, SPCN provides performance improvement over the original closed nesting, gaining more than 2× in throughput.

Software Transactional Memory (STM) has recently emerged as a promising synchronization abstraction for multicore architectures. State-of-the-art STM algorithms, however, suffer from performance challenges due to contention and spinning on locks during the transaction commit phase. In this paper, we introduce Remote Transaction Commit (or RTC), a mechanism for executing commit phases of STM transactions. RTC dedicates server cores to execute transactional commit phases on behalf of application threads. This approach has two major benefits. First, it decreases the overheads of spinning on locks during commit, such as the number of cache misses, blocking of lock holders, and CAS operations. Second, it enables exploiting the benefits of coarse-grained locking algorithms (simple and fast lock acquisition, reduced false conflicts) and bloom filter-based algorithms (concurrent execution of independent transactions). Our experimental study on a 64-core machine with four sockets shows that RTC solves the problem of performance degradation due to spin locking on both micro-benchmarks (red-black trees), and macro-benchmarks (STAMP), especially when the commit phase is relatively long and when thread contention increases.

Distributed Transactional Memory (DTM) is a recent but promising model for programming distributed systems. It aims to present programmers with a simple to use distributed concurrency control abstraction (transactions), while maintaining performance and scalability similar to distributed fine-grained locks. Any complications usually associated with such locks (e.g., distributed deadlocks) are avoided. In this article, we analyze the use of open nesting in the DTM setting. We extend two DTM algorithms, Transactional Forwarding Algorithm (TFA) and SCORe with support for open nested transactions and we implement them into two frameworks for running distributed transactions, such as Hyflow and Infinispan. We discuss the mechanisms and performance implications of such nesting, and identify the cases where using open nesting is warranted and the relevant parameters for such a decision. To the best of our knowledge, our work also contributes the first ever implementations of DTM systems with support for open-nested transactions.

Modern transactional processing systems need to be fast and scalable, but this means many such systems settled for weak consistency models. It is however possible to achieve all of strong consistency, high scalability and high performance, by using fine-grained partitions and light-weight concurrency control that avoids superfluous synchronization and other overheads such as lock management. Independent transactions are one such mechanism, that rely on good partitions and appropriately defined transactions. On the downside, it is not usually straightforward to determine optimal partitioning schemes, especially when dealing with non-trivial amounts of data. Our work attempts to solve this problem by automating the partitioning process, choosing the correct transactional primitive, and routing transactions appropriately.

The recent possibility of integrating multiple-OS-capable, high-core-count, heterogeneous-ISA processors in the same platform poses a question: given the tight integration between system components, can a shared memory programming model be adopted, enhancing programmability? If this can be done, an enormous amount of existing code written for shared memory architectures would not have to be rewritten to use a new programming paradigm (e.g., code offloading) that is often very expensive and error prone. We propose a new software architecture that is composed of an operating system and a compiler framework to run ordinary shared memory applications, written for homogeneous machines, on OS-capable heterogeneous-ISA machines. Applications run transparently amongst different ISA processors while exploiting the most optimized instruction set for each code block. We have implemented and tested our system, called Popcorn, on a multi-core Intel Xeon machine with a PCIe Intel Xeon Phi to demonstrate the viability of our approach. Application execution on Popcorn demonstrates to be up to 52% faster than the most performant native execution on Linux, on either Xeon or Xeon Phi, while removing the burden of the programmer having to adopt a different programming model than shared memory on a heterogeneous system. When compared to an offloading programming model, Popcorn is shown to be up to 6.2 times faster.

Chip manufacturers continue to increase the number of cores per chip while balancing requirements for low power consumption. This drives a need for simpler cores and hardware caches. Because of these trends, the scalability of existing shared memory system software is in question. Traditional operating systems (OS) for multiprocessors are based on shared memory communication between cores and are symmetric (SMP). Contention in SMP OSes over shared data structures is increasingly significant in newer generations of many-core processors. We propose the use of the replicated-kernel OS design to improve scalability over the traditional SMP OS. Our replicated-kernel design is an extension of the concept of the multikernel. While a multikernel appears to application software as a distributed network of cooperating micro kernels, we provide the appearance of a monolithic, single-system image, task-based OS in which application software is unaware of the distributed nature of the underlying OS. In this paper we tackle the problem of thread migration between kernels in a replicated-kernel OS. We focus on distributed thread group creation, context migration, and address space consistency for threads that execute on different kernels, but belong to the same distributed thread group. This concept is embodied in our prototype OS, called Popcorn Linux, which runs on multicore x86 machines and presents a Linux-like interface to application software that is indistinguishable from the SMP Linux interface. By doing this, we are able to leverage the wealth of existing Linux software for use on our platform while demonstrating the characteristics of the underlying replicated-kernel OS. We show that a replicated-kernel OS scales as well as a multikernel OS by removing the contention on shared data structures. Popcorn, Barr elfish, and SMP Linux are compared on selected benchmarks. Popcorn is shown to be competitive to SMP Linux, and up to 40% faster.

Multicore architectures are increasingly becoming prone to transient faults. In this paper we briefly present Shield, a middleware to provide transactional applications with resiliency to those faults that can happen anytime during the execution of a processor but do not cause any hardware interruption. Shield is inspired by the state machine replication approach, where computational resources are partitioned, the shared state is fully replicated, and requests are executed by all partitions in the same order. Shield embeds a set of algorithmic and system innovations to limit the overhead with respect to non-fault-tolerant solutions. They include a fast total order layer that lets application threads and computational nodes co-operate in order to fast deliver.

Single leader-based Consensus protocols are known to stop scaling once the leader reaches its saturation point. On the other hand, establishing Consensus of commands by taking into account only their dependencies (as specified by Generalized Consensus) is appealing because of the potentially higher parallelism and lower latency. However, current solutions have well-known pitfalls due to the higher quorum size, which is required to exploit low-latency fast decisions, and the need for tracking dependency relations. In this paper we briefly introduce M2PAXOS, a new implementation of Generalized Consensus that provides a fast decision of commands by leveraging a classic quorum size, which matches just the majority of nodes deployed. M2PAXOS does not establish command dependencies based on conflicts, rather it associates accessed objects with nodes, so that the delivery decision of commands operating on the same objects is made by a common node. The evaluation study of M2PAXOS confirms its effectiveness by showing an improvement up to 7× over state-of-the-art (Generalized) Consensus protocols.

In this paper, we present a framework that automatically decomposes programmer-written flat transactions into closed-nested transactions. The framework relies on two key mechanisms for the decomposition. The first is a static tool that analyzes application source code and produces a compact representation of transactions' business logic. The second is a run-time monitor that captures the actual contention level of shared objects and, relying on the outcome of the static tool, triggers the optimal closed-nested configuration for the workload at hand. We implemented this framework atop QR-CN, an open source fault-tolerant DTM written in Java. Our experimental studies conducted using the TPC-C, Vacation and Bank benchmarks reveal that the framework yields better performance than flat nesting and manual closed nesting, especially when the workload changes.

Disjoint-Access Parallelism (DAP) is considered one of the most desirable properties to maximize the scalability of Transactional Memory (TM). This paper investigates the possibility and inherent cost of implementing a DAP TM that ensures two properties that are regarded as important to maximize efficiency in read-dominated workloads, namely having invisible and wait-free read-only transactions. We first prove that relaxing Real-Time Order (RTO) is necessary to implement such a TM. This result motivates us to introduce Witnessable Real-Time Order (WRTO), a weaker variant of RTO that demands enforcing RTO only between directly conflicting transactions. Then we show that adopting WRTO makes it possible to design a strictly DAP TM with invisible and wait-free read-only transactions, while preserving strong progressiveness for write transactions and an isolation level known in literature as Extended Update Serializability. Finally, we shed light on the inherent inefficiency of DAP TM implementations that have invisible and wait-free read-only transactions, by establishing lower bounds on the time and space complexity of such TMs.

The first release of hardware transactional memory (HTM) as commodity processor posed the question of how to efficiently handle its best-effort nature. In this paper we present Part-HTM, the first hybrid transactional memory protocol that solves the problem of transactions aborted due to the resource limitations (space/time) of current best-effort HTM. The basic idea of Part-HTM is to partition those transactions into multiple sub-transactions, which can likely be committed in hardware. Due to the eager nature of HTM, we designed a low-overhead software framework to preserve transaction's correctness (with and without opacity).

This paper shows the issues to face while designing contention management policies that involve best-effort hardware transactions. Also, in this paper we present Octonauts, a solution for scheduling HTM transactions without relying on on-the-fly information. Octonauts learns the objects accessed by a hardware transaction while running and it uses them in case of conflict. It also proposes an innovative scheme for optimizing the communication between transactions running in hardware and software.

Consolidation and isolation are key technologies that promoted the undisputed popularity of virtualization in most of the computer industry. This popularity has recently led to a growing interest in real-time virtualization, making this technology enter the real-time system market. However, it has several issues due to the strict timing guarantees contracted. Moreover supporting legacy software stacks adds another level of complexity when the software is a black box. We present KairosVM, a latency-bounded, real-time extension to Linux's KVM module. It aims to bridge the lack of communication of the real-time requirements between the guest scheduler and the host scheduler, exploiting virtual machine introspection. The hypervisor captures the real-time requirements of the guest by catching previously added undefined instructions, without the need to do any modification to the guests. Our evaluations show that KairosVM's overhead is negligible when compared to existing introspection solutions thus can be used in real-time.

Software Transactional Memory (STM) systems are increasingly emerging as a promising alternative to traditional locking algorithms for implementing generic concurrent applications. To achieve generality, STM systems incur overheads to the normal sequential execution path, including those due to spin locking, validation (or invalidation), and commit/abort routines. We propose a new STM algorithm called Remote Invalidation (or RInval) that reduces these overheads and improves STM performance. RInval's main idea is to execute commit and invalidation routines on remote server threads that run on dedicated cores, and use cache-aligned communication between application's transactional threads and the server routines. By remote execution of commit and invalidation routines and cache-aligned communication, RInval reduces the overhead of spin locking and cache misses on shared locks. By running commit and invalidation on separate cores, they become independent of each other, increasing commit concurrency. We implemented RInval in the Rochester STM framework. Our experimental studies on micro-benchmarks and the STAMP benchmark reveal that RInval outperforms InvalSTM, the corresponding non-remote invalidation algorithm, by as much as an order of magnitude. Additionally, RInval obtains competitive performance to validation-based STM algorithms such as NOrec, yielding up to 2x performance improvement.

We present Archie, a high performance fault-tolerant transactional system. Archie complies with the State Machine Approach, where the transactional state is fully replicated and total ordered transactions are executed on the replicas. Archie avoids the serial execution after transactions get ordered, which is the typical bottleneck of those protocols, by anticipating the work and using speculation to process transactions in parallel, enforcing a predefined order. The key feature of Archie is to avoid any non-trivial operation to perform post total order's notification, in case the sequencer node remains stable (only a single timestamp increment is needed for committing a transaction). This approach significantly shortens the transaction's critical path. The contention of speculative execution is always kept limited by activating a fixed number of transactions at a time. A comprehensive evaluation, using three competitors and three well known benchmarks, shows that Archie outperforms competitors in all medium/high contention scenarios.

Multicore architectures are becoming increasingly prone to transient faults and data corruption. Relying on a multicore architecture is the common solution for increasing performance and scalability of core applications including transactional applications. In this paper we present SoftX, a low-invasive protocol for supporting execution of transactional applications relying on speculative processing and dedicated committer threads. Upon starting a transaction, SoftX forks a number of threads running the same transaction independently. The commit phase is handled by dedicated threads for optimizing synchronization's overhead. We conduct an evaluation study showing the performance obtained with the implementation of SoftX on a 48 cores AMD machine, running List, Bank and TPC-C benchmarks. Results reveal better performance than classical replication-based fault-tolerant systems and limited overhead with respect to non fault-tolerant protocols. We ported SoftX to a message-passing architecture, Tilera TILE-Gx. Hardware message-passing is an important emerging trend in multicore architectures. Our experiments on Tilera show that SoftX is still more efficient than replication.

Herlihy and Koskinen's transactional boosting methodology addressed the challenge of converting concurrent data structures into transactional ones. We present an optimistic methodology for boosting concurrent collections. Optimistic boosting allows greater data structure-specific optimizations, easier integration with STM frameworks, and lower restrictions on the boosted operations than the original boosting methodology.

Modern transactional processing systems need to be fast and scalable, but this means many such systems settled for weak consistency models. It is however possible to achieve all of strong consistency, high scalability and high performance, by using fine-grained partitions and light-weight concurrency control that avoids superfluous synchronization and other overheads such as lock management. Independent transactions are one such mechanism, that rely on good partitions and appropriately defined transactions. On the downside, it is not usually straightforward to determine optimal partitioning schemes, especially when dealing with non-trivial amounts of data. Our work attempts to solve this problem by automating the partitioning process, choosing the correct transactional primitive, and routing transactions appropriately.

We consider software transactional memory (STM) concurrency control for embedded multicore real-time software, and present a novel contention manager for resolving transactional conflicts, called PNF. We upper bound transactional retries and task response times. Our implementation in RSTM/real-time Linux reveals that PNF yields shorter or comparable retry costs than competitors.

Distributed software transactional memory (DTM) is an emerging, alternative concurrency control model for distributed systems that promises to alleviate the difficulties of lock-based distributed synchronization. Object replication can improve concurrency and achieve fault-tolerance in DTM, but may incur high communication overhead (in metric-space networks) to ensure one-copy serializability. We consider metric-space networks and develop a cluster-based object replication model for DTM. In this model, object replicas are distributed to clusters of nodes, where clusters are determined based on distance between nodes, to maximize locality and fault-tolerance and to minimize communication overhead. We develop a transactional scheduler for this model, called CTS. CTS enqueues live transactions and identifies some of the transactions that must be aborted in advance to enhance concurrency of the other transactions over clusters, reducing a significant number of future conflicts. Our implementation and experimental evaluation reveals that CTS improves transactional throughput over state-of-the-art replicated DTM solutions by as much as (average) 1.55x and 1.73x under low and high contention, respectively.

We consider distributed transactional memory (DTM) for concurrency control in distributed real-time programs, and present an algorithm called RT-TFA. RT-TFA transparently handles object relocation and versioning using an asynchronous clock-based validation technique, and resolves transactional contention using task time constraints. We implement the RT-TFA on top of JChronOS, a layer extending the scheduling capabilities of ChronOS for Java programs. We conduct an extensive evaluation study comparing RT-TFA with well known competitors for real-time distributed applications. Our results reveal that RT-TFA outperforms competitors in mostly scenarios up to 43% with added advantage of better programmability and composability.

We consider software transactional memory (STM) concurrency control for embedded multicore real-time software, and present a novel contention manager for resolving transactional conflicts, called FBLT. We upper bound transactional retries and task response times under FBLT, and identify when FBLT has better real-time schedulability than the previous best contention manager, PNF. Our implementation in the Rochester STM framework reveals that FBLT yields shorter or comparable retry costs than competitor methods.

We consider the closed nesting and checkpointing model for transactions in fault-tolerant distributed transactional memory (DTM). The closed nested model allows inner-nested transactions to be aborted (in the event of a transactional conflict) without aborting the parent transaction, while checkpointing allows transactions to rollback to a previous execution state, potentially improving concurrency over flat nesting. We consider a quorum-based replicated model for fault-tolerant DTM, and present algorithms to support closed nesting and checkpointing. The algorithms use incremental validation to avoid communication overhead on commit, and ensure 1-copy equivalence. Our experimental studies using a Java DTM implementation of the algorithms on micro and macro benchmarks reveal the conditions when they improve transactional throughput over flat nesting, and also their relative advantages and disadvantages.

We present the first ever distributed transactional memory (DTM) framework for distributed concurrency control in C++, called HyflowCPP. HyflowCPP provides distributed atomic sections, and plug gable support for policies for concurrency control, directory lookup, contention management, and networking. While there exists other DTM frameworks, they mostly target VM-based languages (e.g., Java, Scala). Additionally, HyflowCPP provides uniquely distinguishing TM features including strong atomicity, closed and open nesting, and check pointing. Our experimental studies revealed that HyflowCPP achieves up to 6x performance improvement over state-of-the-art DTM frameworks.

We investigate the feasibility of systematic speculative processing in the context of Optimistic Atomic Broadcast (OAB) based replication of database systems. Specifically, we present the design and prototypal implementation of a fully speculative version of the Postgre SQL open source relational database, together with experimental results showing performance advantages over non-speculative replication.

Current Virtual Machine (VM) live migration mechanisms only focus on providing a high availability service by offering minimal downtime to users. In this paper, we present a novel live migration technique called HSG-LM, which also aims to provide short waiting time to whoever is responsible for triggering the VM migration (e.g., the data center administrator). HSG-LM is implemented in the guest OS kernel in order to not rely on the hypervisor throughout the entire migration process. HSG-LM exploits a hybrid strategy that reaps the benefits of both pre-copy and post-copy mechanisms. Furthermore, HSG-LM integrates a speculation mechanism that improves the efficiency of handling post-copy page faults. From our evaluation on different real-world workloads (Sysbench, Apache, etc.), the results show that HSG-LM incurs minimal downtime as well as short total migration time. Moreover, compared with competitors, HSG-LM reduces the downtime by up to 55%, and reduces the total migration time by up to 27%.

We consider the problem of least-latency end-to-end routing over adaptively duty-cycled wireless sensor networks. Such networks exhibit a time-dependent feature, where the link cost and transmission latency from one node to other nodes vary constantly in different discrete time moments. We model the problem as the time-dependent Bellman-Ford problem. We show that such networks satisfy the first-in-first-out (FIFO) property, which makes the time-dependent Bellman-Ford problem solvable in polynomial-time. Using the β-synchronizer, we propose a fast distributed algorithm to construct all-to-one shortest paths with polynomial message complexity and time complexity. The algorithm determines the shortest paths for all discrete times in a single execution, in contrast with multiple executions needed by previous solutions. We further propose an efficient distributed algorithm for time-dependent shortest path (TDSP) maintenance. The proposed algorithm is loop-free with low message complexity and low space complexity of O(maxdeg), where maxdeg is the maximum degree for all nodes. We discuss a suboptimal implementation of our proposed algorithms that reduces their memory requirement. The performance of our algorithms are experimentally evaluated under diverse network configurations. The results reveal that our algorithms are more efficient than previous solutions in terms of message cost and space cost.

A surveillance system, which tracks mobile targets, is one of the most important applications of wireless sensor networks. When nodes operate in a duty cycling mode, tracking performance can be improved if the target motion can be predicted and nodes along the trajectory can be proactively awakened. However, this will negatively influence the energy efficiency and constrain the benefits of duty cycling. In this paper, we present a Probability-based Prediction and Sleep Scheduling protocol (PPSS) to improve energy efficiency of proactive wake up. We start with designing a target prediction method based on both kinematics and probability. Based on the prediction results, PPSS then precisely selects the nodes to awaken and reduces their active time, so as to enhance energy efficiency with limited tracking performance loss. We evaluated the efficiency of PPSS with both simulation-based and implementation-based experiments. The experimental results show that compared to MCTA algorithm, PPSS improves energy efficiency by 25-45 percent (simulation based) and 16.9 percent (implementation based), only at the expense of an increase of 5-15 percent on the detection delay (simulation based) and 4.1 percent on the escape distance percentage (implementation based), respectively.

We consider software transactional memory (STM) concurrency control for multicore real-time software, and present a novel contention manager (CM) for resolving transactional conflicts, called length-based CM (or LCM). We upper bound transactional retries and response times under LCM, when used with G-EDF and G-RMA schedulers. We identify the conditions under which LCM outperforms previous real-time STM CMs and lock-free synchronization. Our implementation and experimental studies reveal that G-EDF/LCM and G-RMA/LCM have shorter or comparable retry costs and response times than other synchronization techniques.

Distributed software transactional memory (D-STM) is an emerging, alternative concurrency control model for distributed systems that promises to alleviate the difficulties of lock-based distributed synchronization -- e.g., distributed deadlocks, live locks, and lock convoying. We consider Herlihy and Sun's dataflow D-STM model, where objects are migrated to invoking transactions, and the \emph{closed nesting} model of managing inner (distributed) transactions. We present a transactional scheduler called, reactive transactional scheduler (or RTS) to boost the throughput of closed-nested transactions. RTS determines whether a conflicting parent transaction must be aborted or enqueued according to the level of contention. If a transaction is enqueued, its nested inner transactions do not have to retrieve objects again, resulting in reduced communication delays. Our implementation of RTS in the HyFlow D-STM framework and experimental evaluations reveal that RTS improves throughput over D-STM without RTS, by as much as 88%.

A virtual cluster (VC) consists of multiple virtual machines (VMs) running on different physical hosts, inter-connected by a virtual network. A fault-tolerant protocol and mechanism are essential to the VC's availability and usability. We present Virtual Predict Check pointing (or VPC), a lightweight, globally consistent check pointing mechanism, which checkpoints the VC for immediate restoration after VM failures. By predicting the checkpoint-caused page faults during each check pointing interval, VPC further reduces the solo VM downtime than traditional incremental check pointing approaches. Besides, VPC uses a globally consistent check-pointing algorithm, which preserves the global consistency of the VMs' execution and communication states, and only saves the updated memory pages during each check pointing interval to reduce the entire VC downtime. Our implementation reveals that, compared with past VC check pointing/migration solutions including VNsnap, VPC reduces the solo VM downtime by as much as 45%, under the NPB benchmark, and reduces the entire VC downtime by as much as 50%, under the NPB distributed program. Additionally, VPC incurs a memory overhead of no more than 9%. In all cases, VPC's performance overhead is less than 16%.

Distributed software transactional memory (or DTM) is an emerging promising model for distributed concurrency control, as it avoids the problems with locks (e.g., distributed deadlocks), while retaining the programming simplicity of coarse-grained locking. We consider DTM in Herlihy and Sun's data flow distributed execution model, where transactions are immobile and objects dynamically migrate to invoking transactions. To support DTM in this model and ensure transactional properties including atomicity, consistency, and isolation, we develop an algorithm called Transactional Forwarding Algorithm (or TFA). TFA guarantees a consistent view of shared objects between distributed transactions, provides atomicity for object operations, and transparently handles object relocation and versioning using an asynchronous version clock-based validation algorithm. We show that TFA is opaque (its correctness property) and permits strong progressiveness (its progress property). We implement TFA in a Java DTM framework and conduct experimental studies on a 120-node system, executing over 4 million transactions, with more than 1000 active concurrent transactions. Our implementation reveals that TFA outperforms competing distributed concurrency control models including Java RMI with spin locks, distributed shared memory, and directory-based DTM, by as much as 13x (for read-dominant transactions), and competitor DTM implementations by as much as 4x.

We implement and experimentally evaluate the timeliness and energy consumption behaviors of fourteen Real-Time Dynamic Voltage and Frequency Scaling (RT-DVFS) schedulers on two hardware platforms. The schedulers include CC-EDF, LA-EDF, REUA, DRA, and AGR1, among others, and the hardware platforms include the Intel i5 processor and the AMD Zacate processor. Our studies reveal that measuring the CPU power consumption as the cube of CPU frequency -- as often done in the simulation-based RT-DVFS literature -- ignores the idle state CPU power consumption, which is significantly smaller than the active power consumption. Consequently, power savings obtained by optimizing active power (i.e., RT-DVFS) is offset by completing tasks sooner by running at high frequency and quickly transitioning to the idle state (i.e., no DVFS). Thus, the active power consumption savings of the RT-DVFS techniques' revealed by our measurements are significantly smaller than their simulation-based savings reported in the literature.

Distributed Transactional Memory (DTM) is a recent but promising model for programming distributed systems. It aims to present programmers with a simple to use distributed concurrency control abstraction (transactions), while maintaining performance and scalability similar to distributed fine-grained locks. Any complications usually associated with such locks (e.g., distributed deadlocks) are avoided. Building upon the previously proposed Transactional Forwarding Algorithm (TFA), we add support for open-nested transactions. We discuss the mechanisms and performance implications of such nesting, and identify the cases where using open nesting is warranted and the relevant parameters for such a decision. To the best of our knowledge, our work contributes the first ever implementation of a DTM system with support for open-nested transactions.

We present ChronOS Linux, a best-effort real-time Linux kernel for chip multiprocessors (CMPs). ChronOS addresses the intersection of three problem spaces: a) OS-support for obtaining best-effort timing assurances, b) real-time Linux kernel augmented with the PREEMPT_RT patch, and c) OS support for CMP-aware real-time scheduling. While each of these spaces have been studied in the past, their intersection, which has strong problem motivations, was previously empty. Best-effort timeliness targets real-time applications with run-time uncertainties and resource overloads, and optimizes collective application timeliness --- as specified by the application. ChronOS directly supports the implementation of best-effort real-time schedulers on CMPs, in addition to others, in the global and partitioned scheduling disciplines. ChronOS extends the PREEMPT_RT Linux patch, and thus provides full kernel preemptibility and retains stock Linux features. We validate our claims by reporting on the implementation of a suite of best-effort and non-best-effort CMP schedulers on a quad-core AMD Phenom platform.

We present HyFlow --- a distributed software transactional memory (D-STM) framework for distributed concurrency control. HyFlow is a Java framework for D-STM, with pluggable support for directory lookup protocols, transactional synchronization and recovery mechanisms, contention management policies, cache coherence protocols, and network communication protocols. HyFlow exports a simple distributed programming model that excludes locks: using (Java 5) annotations, atomic sections are defined as transactions, in which reads and writes to shared, local and remote objects appear to take effect instantaneously. No changes are needed to the underlying virtual machine or compiler. We describe HyFlow's architecture and implementation, and report on experimental studies comparing HyFlow against competing models including Java remote method invocation (RMI) with mutual exclusion and read/write locks, distributed shared memory (DSM), and directory-based D-STM. Our studies show that HyFlow outperforms competitors by as much as 40-190% on a broad range of transactional workloads on a 72-node system, with more than 500 concurrent transactions.

Particle filters (or PFs) are widely used for the tracking problem in dynamic systems. Despite their remarkable tracking performance and flexibility, PFs require intensive computation and communication, which are strictly constrained in wireless sensor networks (or WSNs). Thus, distributed particle filters (or DPFs) have been studied to distribute the computational workload onto multiple nodes while minimizing the communication among them. However, weight normalization and resampling in generic PFs cause significant challenges in the distributed implementation. Few existing efforts on DPF could be implemented in a completely distributed manner. In this paper, we design a completely distributed particle filter (or CDPF) for target tracking in sensor networks, and further improve it with neighborhood estimation toward minimizing the communication cost. First, we describe the particle maintenance and propagation mechanism, by which particles are maintained on different sensor nodes and propagated along the target trajectory. Then, we design the CDPF algorithm by adjusting the order of PFs' four steps and leveraging the data aggregation during particle propagation. Finally, we develop a neighborhood estimation method to replace the measurement broadcasting and the calculation of likelihood functions. With this approximate estimation, the communication cost of DPFs can be minimized. Our experimental evaluations show that although CDPF incurs about 50% more estimation error than semi-distributed particle filter (or SDPF), its communication cost is lower than that of SDPF by as much as 90%.

Publish/Subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in large-scale distributed systems. The weak coupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as ad hoc networks. However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in ad hoc networks. In this article, we present, evaluate benefits of, and compare with past work an architecture design that can effectively support timely and reliable delivery of events and causally related events in ad hoc environments, and especially in mobile ad hoc networks (MANETs). With observations from both realistic application model and simulation experiments, we reveal causal dependencies among events and their significance in a typical use notional system. We also examine and propose engineering methodologies to further tailor an event-based system to facilitate its self-reorganizing capability and self-reconfiguration. Our design features a two-layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance. The trace-based experimental simulation studies illustrate our design's effectiveness in both cases with and without causal dependencies.

We revisit the shortest path problem in asynchronous duty-cycled wireless sensor networks, which exhibit time-dependent features. We model the time-varying link cost and distance from each node to the sink as periodic functions. We show that the time-cost function satisfies the FIFO property, which makes the time-dependent shortest path problem solvable in polynomial-time. Using the ß-synchronizer, we propose a fast distributed algorithm to build all-to-one shortest paths with polynomial message complexity and time complexity. The algorithm determines the shortest paths for all discrete times with a single execution, in contrast with multiple executions needed by previous solutions. We further propose an efficient distributed algorithm for time-dependent shortest path maintenance. The proposed algorithm is loop-free with low message complexity and low space complexity of O(maxdeg), where maxdeg is the maximum degree for all nodes. The performance of our solution is evaluated under diverse network configurations. The results suggest that our algorithm is more efficient than previous solutions in terms of message complexity and space complexity.

Transactional memory is an alternative programming model for managing contention in accessing shared in-memory data objects. Distributed transactional memory (TM) promises to alleviate difficulties with lock-based (distributed) synchronization and object performance bottlenecks in distributed systems. In distributed TM systems, both the management and consistency of a distributed transactional object are ensured by a cache-coherence protocol. The Relay protocol is a cache-coherence protocol that operates on a fixed spanning tree. The protocol efficiently reduces the total number of abortions for a given set of transactions. We analyze the Relay protocol for a set of transactions which are dynamically generated in a given time period, and compare the protocol's time complexity against that of an optimal offline clairvoyant algorithm. We show that Relay is O(log D)-competitive, where D is the diameter of the spanning tree, for a set of transactions that request the same object, given the condition that the maximum local execution time of transactions is sufficiently small.

Peer-to-peer (P2P) multimedia streaming provides a scalable solution for IPTV. However, delays from channel switch and streaming recovery are typically in the scale of 10-60 seconds, which have hindered the extensive commercial deployment of P2P systems. We call these two types of delays, churn-induced delays. Obtaining assurances on churn-induced delays in dynamic and heterogeneous network environments is a challenge. In this paper, we devise a simple, yet efficient agent-based P2P streaming scheme, called NAP, which reduces churn-induced delays. We first formulate the problems of minimizing channel-switching delay and streaming recovery delay. We then present the detailed methodology of NAP. In addition, we develop a queuing model for the P2P streaming scenario and analyze the properties of NAP based on this model. Our numerical study reveals the effectiveness of NAP, and shows that NAP significantly reduces churn-induced delays, especially channel-switching delays.

Distributed transactional memory (TM) models based on globally-consistent contention management policies may abort many transactions that could potentially commit without violating correctness. To reduce unnecessary aborts and increase concurrency, we propose the distributed dependency-aware (or DDA) model for distributed TM, which manages dependencies between conflicting and uncommitted transactions so that they can commit safely. We present a distributed algorithm to decide whether to abort a transaction based on local precedence graphs that model the established dependency relationships. We analyze the performance of our algorithm and illustrate the inherent tradeoff of the DDA model between communication cost and concurrency.

In distributed transactional memory (TM) systems, both the management and consistency of a distributed transactional object are ensured by a cache-coherence protocol. We formalize two classes of cache-coherence protocols: distributed queuing cache-coherence (DQC) protocols and distributed priority queuing cache-coherence (DPQC) protocols, both of which can be implemented based on a given distributed queuing protocol. We analyze the two classes of protocols for a set of dynamically generated transactions and compare their time complexities against that of an optimal offline clairvoyant algorithm. We show that a DQC protocol is O(Nlog Dδ)-competitive and a DPQC protocol is O(log Dδ)-competitive for a set of N transactions, where Dδ is the normalized maximum communication latency provided by the underlying distributed queuing protocol.

We present heterogenous quorum-based asynchronous wake-up scheduling schemes for wireless sensor networks. The schemes can ensure that two nodes that adopt different quorum systems as their wake-up schedules can hear each other at least once in bounded time intervals. We propose two such schemes: cyclic quorum system pair (cqs-pair) and grid quorum system pair (gqs-pair). The cqs-pair which contains two cyclic quorum systems provides an optimal solution, in terms of energy saving ratio, for asynchronous wake-up scheduling. To quickly assemble a cqs-pair, we present a fast construction scheme which is based on the multiplier theorem and the (N,k,M, l)-difference pair defined by us. Regarding the gqs-pair, we prove that any two grid quorum systems will automatically form a gqs-pair. We further analyze the performance of both designs, in terms of average discovery delay, quorum ratio, and energy saving ratio. We show that our designs achieve better trade-off between the average discovery delay and quorum ratio (and thus energy consumption) for different cycle lengths. We implemented the proposed designs in a wireless sensor network platform of Telosb motes. Our implementation-based measurements further validate the analytically-established performance trade-off of our designs.

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger “adversary” than most traditional arrival models. We derive an upper bound on lock-free retries under the UAM with utility accrual scheduling—the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities' accrued timeliness utility is greater under lock-free than lock-based, and the consequent lower and upper bound on the total accrued utility that is possible with lock-free and lock-based sharing. We confirm our analytical results with a POSIX RTOS implementation.

We consider the problem of recovering from the failures of distributable threads (“threads”) in distributed real-time systems that operate under runtime uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. When a thread experiences a node failure, the result is a broken thread having an orphan. Under a termination model, the orphans must be detected and aborted, and exceptions must be delivered to the farthest, contiguous surviving thread segment for resuming thread execution. Our application/scheduling model includes the proposed distributable thread programming model for the emerging Distributed Real-Time Specification for Java (DRTSJ), together with an exception-handler model. Threads are subject to time/utility function (TUF) time constraints and an utility accrual (UA) optimality criterion. A key underpinning of the TUF/UA scheduling paradigm is the notion of “best-effort” where higher importance threads are always favored over lower importance ones, irrespective of thread urgency as specified by their time constraints. We present a thread scheduling algorithm called HUA and a thread integrity protocol called TPR. We show that HUA and TPR bound the orphan cleanup and recovery time with bounded loss of the best-effort property. Our implementation experience for HUA/TPR in the Reference Implementation of the proposed programming model for the DRTSJ demonstrates the algorithm/protocol's effectiveness.

We consider multiprocessor distributed real-time systems where concurrency control is managed using software transactional memory (or STM). For such a system, we propose an algorithm to compute an upper bound on the response time.The proposed algorithm can be used to study the behavior of systems where node crash failures are possible. We compare the result of the proposed algorithm to a simulation of the system being studied in order to determine its efficacy. The results of our study indicate that it is possible to provide timeliness guarantees for multiprocessor distributed systems programmed using STM.

Network capacity is a critical feature of wireless ad hoc and sensor networks. It is particularly challenging to determine network capacity when combined with other performance objectives such as timeliness. This paper investigates real-time capacity for event-driven data-gathering sensor networks w

Peer-to-peer (P2P) technology provides a scalable solution in multimedia streaming. Many streaming applications, such as IPTV and video conferencing, have rigorous constraints on end-to-end delays. Obtaining assurances on meeting those delay constraints in dynamic and heterogenous network environments is a challenge. In this paper, we devise a streaming scheme which minimizes the maximum end-to-end streaming delay for a mesh-based overlay network paradigm. We first formulate the minimum-delay P2P streaming problem, called the MDPS problem, and prove its NP-completeness. We then present a polynomial-time approximation algorithm to this problem, and show that the performance of our algorithm is bounded by a ratio of O. Our simulation study reveals the effectiveness of our algorithm, and shows a reasonable message overhead.

A transactional memory API utilizes contention managers to guarantee that whenever two transactions have a conflict on a resource, one of them is aborted. While they have been well studied in the context of multiprocessors, their properties for distributed transactional memory systems are still unknown. Compared with multiprocessor transactional memory systems, the design of distributed transactional memory systems is more challenging because of the need for distributed cache-coherence protocols and the underlying (higher) network latencies involved. The choice of the combination of the contention manager and the cache-coherence protocol is critical for the performance of distributed transactional memory systems. How does a designer go about deciding what contention manager and what cache-coherence protocol to use in a distributed transactional memory system? In this paper, we answer this question. We consider metric-space networks, where the communication delay between nodes forms a metric. We show that the performance of a distributed transactional memory system on metric-space networks is O(Ni2) for Nitransactions requesting for a single object under the Greedy contention manager and an arbitrary cache-coherence protocol. To improve the performance, we propose a class of location-aware distributed cache-coherence protocols, called LAC protocols. We show that the combination of the greedy contention manager and an efficient LAC protocol yields an O(N log N middot s) competitive ratio, where N is the maximum number of nodes that request the same object, and s is the number of objects. This is the first such performance bound established for distributed transactional memory contention managers. Our results yield the following design strategy: select a distributed contention manager and determine its performance without considering distributed cache-coherence protocols; then find an appropriate cache-coherence protocol to improve performance.

We consider garbage collection (GC) in dynamic, multiprocessor real-time systems. We consider the time-based, concurrent GC approach and focus on real-time scheduling to obtain mutator timing assurances, despite memory allocation and garbage collection. We present a scheduling algorithm called GCMUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, stochastic execution-time and memory demands, and overloads. We establish that GCMUA probabilistically lower bounds each mutator activity's accrued utility, lower bounds the system-wide total accrued utility, and upper bounds the timing assurances' sensitivity to variations in mutator execution-time and memory demand estimates. Our simulation experiments validate our analytical results and confirm GCMUA's effectiveness.

We consider scheduling real-time tasks in the presence of message loss and Byzantine node failures in unreliable networks. We present scheduling algorithms called RTQG and RTQG-B. The algorithms use quorum-based gossip communication strategies for dynamically and dependably discovering eligible nodes. Compared with its predecessors,our protocol exhibits better performance. RTQG utilizes quorum systems to limit the range of each gossip round. Using the intersection property of quorum systems, RTQG has advantages in message propagation and robustness to Byzantine node failures. Our simulation studies verify our analytical results.

In this paper, we present RT-P2P, a real-time peer-to-peer (P2P) system that allows application-level end-to-end timing requirements to be satisfied in P2P systems. Key aspects of our RT-P2P infrastructure include a real-time P2P protocol, real-time communication algorithm, and analytical performance models. We analytically establish the timing properties of RT-P2P. Our simulation studies validate the analytical results and demonstrate RT-P2P outperforms the traditional client-server model in large-scale and dynamic system.

In unreliable and untrustworthy systems, information dissemination may suffer network failures and attacks from Byzantine nodes which are controlled by traitors or adversaries, and can perform destructive behaviors. Typically, Byzantine nodes together or individually "swallow" messages, or fake disseminated information. In this paper, we present an authentication-free, gossip-based real-time information dissemination mechanism called RT-LASIRC, in which "healthy" nodes utilize Byzantine features to defend against Byzantine attacks. We show that RT-LASIRC is robust against blackhole and message-faking attacks. Our experimental studies verify RT-LASIRC's effectiveness.

We consider distributed real-time systems that operate under run-time uncertainties including those on execution times and communication delays, and subject to arbitrary node failures and message losses. We present an integrated real-time scheduling and communication algorithm called real-time scheduling with reliable data delivery (RTSRD) that provides probabilistic end-to-end assurances on distributed task timeliness behaviors in such systems. RTSRD considers distributed tasks with end-to-end timing requirements that are expressed using time/utility functions and the optimality criterion of maximizing the total accrued utility. The algorithm decomposes end-to-end time constraints into local time constraints, and uses local slack time for node-local real-time scheduling and node-to-node real-time communication. We analytically establish RTSRD's properties including probabilistic satisfaction of task time constraints. We also compare RTSRD with a prior algorithm called RTG- L for the same problem. Our comparisons show that RTSRD outperforms RTG-L in terms of timeliness assurances (stronger) and algorithm overhead (lower).

This paper presents a target direction-based sleep scheduling algorithm (TDSS) for target tracking surveillance sensor networks. TDSS reduces the number of the proactively awakened sensor nodes and schedules their sleep pattern to enhance energy efficiency but suffer little performance loss. Both approaches are based on two probabilistic distribution models of target moving directions, normal distribution and linear distribution. We compare TDSS with the two models against the legacy circle-based proactively waking up scheme (Circle) and a working node reducing algorithm - MCTA. The evaluation result shows that TDSS achieves better energy efficiency but with less performance loss in terms of detection probability and detection delay.

Some emerging networked embedded real-time applications have relatively long reaction time magnitudes-e.g., milliseconds to minutes. These longer execution time magnitudes allow opportunities for more computationally expensive scheduling algorithms than what is traditionally considered for device-level real-time control sub-systems. In this paper, we review recent research conducted on collaborative scheduling algorithms in such systems that are subject to dynamic behavior such as transient and sustained resource overloads, arbitrary activity arrivals, and arbitrary node failures and message loss. We show that collaborative scheduling algorithms have an advantage over non-collaborative scheduling algorithms.

We consider efficient real-time communication mechanisms for applications in unreliable and partitionable networks. Utilizing quorum systems, we present a quorum based protocol called SOQ to let nodes update and query service information to a selected set of servers (a quorum). Due to the intersection property of quorums, nodes can obtain latest updated information by simply accessing a quorum. To make the protocol adaptive to network partitions, we propose update/query triggering mechanisms to determine when nodes trigger updates/queries. A quorum access strategy for nodes to judiciously select a quorum to access is designed so that the probability that a query returns the latest service information is maximized. We give in-depth analysis of the protocol, including the communication overhead, load and availability relationship of quorum systems and timeliness analysis of distributed applications. Our experimental studies show that SOQ is resilient to network partitions without incurring large overheads.

In this paper, we present a reliable real-time data delivery (communication) mechanism for ad-hoc networks, called RTRD. The mechanism makes use of a proactive wireless routing protocol (DSDV) for path finding and maintenance, and timely delivers data through a priori bandwidth reservation. In addition, to be robust to network failures, or to deliver large data chunks, it simultaneously delivers data in multiple paths. The simulation results conducted by NS-2 validate RTRD's effectiveness.

We consider the rate allocation problem for data aggregation in wireless sensor networks with two objectives: 1) maximizing the lifetime of a local aggregation cluster and 2) achieving fairness among all data sources. The two objectives are generally correlated with each other and usually they cannot be maximized simultaneously. We adopt a lexicographic method to solve this multi-objective programming problem. First, we recursively induce the maximum lifetime for the local aggregation cluster. Under the given maximum lifetime, we then formulate the problem of maximizing fairness as a convex optimization problem, and derive the optimal rate allocation strategy. We also present low-complexity algorithms that a local aggregation cluster can use to determine the optimal rate allocation. Our simulation results validate our analytical results and illustrate the effectiveness of the approach.

We consider scheduling real-time distributable threads in the presence of node/link failures, message losses, and dynamic node joins and departures. We present a distributed scheduling algorithm called RTMG. The algorithm uses gossip-based communication for discovering eligible nodes. Traditionally, gossip protocols incur high message overhead. We explain that this problem is not that serious. We present a hybrid message propagation protocol with lower message overhead, and improve it by evenly distributing the overhead into all gossip rounds. In scheduling local thread sections, RTMG exploits slacks to optimize gossip time utilization. Thereby, it satisfies end-to-end time constraints with probabilistic assurance. Our simulation studies verify our analytical results.

We consider the problem of recovering from failures of distributable threads in distributed real-time systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. When a thread encounters a node failure, it causes orphans. Under a termination model, the orphans must be detected and aborted, and exceptions must be delivered to farthest, contiguous surviving thread segment for resuming thread execution. Our application/scheduling model includes distributable threads and their exception handlers that are subject to time/utility function (TUF) time constraints and a utility accrual (UA) optimality criterion. A key underpinning of the TUF/UA scheduling paradigm is the notion of "best-effort" where high importance threads are always favored over low importance ones, irrespective of thread urgency. We present a scheduling algorithm called HUA and a thread integrity protocol called TPR. We show that HUA and TPR bound the orphan cleanup and recovery time with bounded loss of the best-effort property. Our implementation experience of HUA/TPR within Sun's distributed real-time specification for Java demonstrates the algorithm/protocol's effectiveness

We consider scheduling real-time distributable threads in the presence of node/link failures and message losses in large-scale network systems. We present a distributed scheduling algorithm called RTG-L. The algorithm uses gossip-based communication for dynamically and dependably discovering eligible nodes. Traditionally, gossip protocols incur high message overhead. We explain that this problem is not that serious. We present a gossip-based message propagation protocol with lower message overhead. In scheduling local thread sections, RTG-L exploits slacks to optimize gossip time utilization. Thereby, it satisfies end-to-end time constraints with probabilistic assurance. Our simulation studies verify our analytical results.

We consider scheduling distributable real-time threads that are subject to dependencies (e.g., due to mutual exclusion constraints) in ad hoc networks, in the presence of node and link failures, message losses, and dynamic node joins and departures. We present a gossip-based distributed scheduling algorithm, called RTG-D. We prove that thread blocking times under RTG-D are probabilistically bounded, thereby probabilistically bounding thread time constraint satisfactions'. Our simulation results validate RTG-D's effectiveness.

We present a utility accrual real-time scheduling algorithm called CIC-VCUA for tasks whose execution times are functions of their starting times (and, potentially, other factors). We model such variable execution times using variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints, execution times described using VCFs, and mutual exclusion constraints on concurrent sharing of non-CPU resources. We consider the twofold scheduling objective of 1) assuring that the maximum interval between any two consecutive, successful completions of job instances in an activity must not exceed the activity period (an application-specific objective) and 2) maximizing the system's total accrued utility while satisfying mutual exclusion resource constraints. Since the scheduling problem is intractable, CIC-VCUA is a polynomial-time heuristic algorithm. The algorithm statically computes worst-case task sojourn times, dynamically selects tasks for execution based on their potential utility density, and completes tasks at specific times. We establish that CIC-VCUA achieves optimal timeliness during underloads, and tightly upper bounds inter and intratask completion times. Our simulation experiments confirm the algorithm's effectiveness and superiority

We consider wait-free synchronization for the single-writer/multiple-reader problem in small-memory embedded real-time systems. We present an analytical solution to the problem of determining the minimum, optimal space cost required for this problem, considering a priori knowledge of interferences $the first such result. We also show that the space costs required by previous algorithms can be obtained by our analytical solution, which subsumes them as special cases. We also present a wait-free protocol that utilizes the minimum space cost determined by our analytical solution. Our evaluation studies and implementation measurements using the SHaRK RTOS kernel validate our analytical results

In this paper, we consider timeliness and energy optimization in battery-powered dynamic embedded real-time systems, which must remain functional during an operation/mission with a bounded energy budget. We consider application activities that are subject to time/utility function time constraints, statistical assurance requirements on timeliness behavior, and an energy budget which cannot be exceeded at runtime. To account for the inevitable variability in activity arrivals in dynamic systems, we describe arrival behaviors using the unimodal arbitrary arrival model (UAM) [15]. For such a model, we present a dynamic voltage scaling (DVS)-based CPU scheduling algorithm called the energy-bounded utility accrual algorithm (EBUA). Since the scheduling problem is intractable, EBUA allocates CPU cycles, scales clock frequency, and heuristically computes schedules using statistical estimates of cycle demands in polynomial time. We analytically establish EBUA's properties, including satisfaction of energy bounds, statistical assurances on individual activity timeliness behavior, optimal timeliness during underloads, and bounded time for mutually exclusively accessing shared non-CPU resources. Our simulation experiments validate our analytical results and illustrate the algorithm's effectiveness and superiority over past algorithms.

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger“adversary” than most traditional arrival models. We derive the upper bound on lock-free retries under the UAM with utility accrual scheduling—the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities’accrued timeliness utility is greater under lock-free than lock-based, and the consequent upper bound on the increase in accrued utility that is possible with lock-free. We confirm our analytical results with a POSIX RTOS implementation.

We consider garbage collection (GC) in dynamic realtime systems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain assurances on mutator timing behavior, while ensuring that memory is never exhausted. We present a scheduling algorithm called GCUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, variable execution time demands, the unimodal arbitrary arrival model that allows a strong adversary, and resource overloads. We establish several properties of GCUA including probabilistically-satisfied utility lower bounds for each mutator activity, a lower bound on the system-wide total accrued utility, bounded sensitivity for the assurances to variations in mutator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and confirm the algorithm's effectiveness and superiority.

We present a garbage collector scheduling algorithm for dynamic multiprocessor real-time systems called GCMUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, stochastic execution-time and memory demands, and overloads. We prove that GCMUA probabilistically lower bounds each mutator's accrued utility, lower bounds the total accrued utility, and upper bounds the assurances' sensitivity to variations in execution-time and memory demand estimates. Our simulation results confirm our analytical results

We present an optimal real-time scheduling algorithm for multiprocessors $one that satisfies all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. The algorithm called LLREF, is designed based on a novel abstraction for reasoning about task execution behavior on multiprocessors: the time and local execution time domain plane (or T-L plane). LLREF is based on the fluid scheduling model and the fairness notion, and uses the T-L plane to describe fluid schedules without using time quanta, unlike the optimal Pfair algorithm (which uses time quanta). We show that scheduling for multiprocessors can be viewed as repeatedly occurring T-L planes, and feasibly scheduling on a single T-L plane results in the optimal schedule. We analytically establish the optimality of LLREF. Further, we establish that the algorithm has bounded overhead, and this bound is independent of time quanta (unlike Pfair). Our simulation results validate our analysis on the algorithm overhead

We consider the problem of recovering from failures of distributable threads with assured timeliness. When a node hosting a portion of a distributable thread fails, it causes orphans - i.e., thread segments that are disconnected from the thread's root. We consider a termination model for recovering from such failures, where the orphans must be detected and aborted, and failure-exception notification must be delivered to the farthest, contiguous surviving thread segment for resuming thread execution. We present a realtime scheduling algorithm called AUA, and a distributable thread integrity protocol called TP-TR. We show that AUA and TP-TR bound the orphan cleanup and recovery time, thereby bounding thread starvation durations, and maximize the total thread accrued timeliness utility. We implement AUA and TP-TR in a real-time middleware that supports distributable threads. Our experimental studies with the implementation validate the algorithm/protocol's time-bounded recovery property and confirm their effectiveness

We consider real-time CORBA 1.2 (dynamic scheduling) distributable threads operating in multihop networks. When distributable threads are subject to time/utility function-time constraints, and timeliness optimality criteria such as maximizing accrued system-wide utility is desired, utility accrual real-time channels must be established. Such channels transport messages that are generated as distributable threads transcend nodes, in a way that maximizes system-wide, message-level utility. We present 1) a localized utility accrual channel establishment algorithm called localized decision for utility accrual channel establishment (or LocDUCE) and 2) a distributed utility accrual channel establishment algorithm called global decision for utility accrual channel establishment (or GloDUCE). Since the channel establishment problem is NP-complete. LocDUCE and GloDUCE heuristically compute channels, with LocDUCE making decisions based on local information pertaining to the node and GloDUCE making global decisions. We simulate the performance of the algorithms and compare them with the open shortest path first (OSPF) routing algorithm and the optimal algorithm. We also implement these algorithms in a prototype testbed and experimentally compare their performance with OSPF. Our simulation and experimental measurements reveal that GloDUCE and LocDUCE accrue significantly higher utility than OSPF and also perform close to the optimal for some cases. Furthermore, GloDUCE outperforms LocDUCE under high downstream traffic.

This paper presents a uni-processor real-time scheduling algorithm called the generic utility scheduling algorithm (which we refer to simply as GUS). GUS solves a previously open real-time scheduling problem-scheduling application activities that have time constraints specified using arbitrarily shaped time/utility functions and have mutual exclusion resource constraints. A time/ utility function are a time constraint specification that describes an activity's utility to the system as a function of that activity's completion time. Given such time and resource constraints, we consider the scheduling objective of maximizing the total utility that is accrued by the completion of all activities. Since this problem is NP-hard, GUS heuristically computes schedules with a polynomial-time cost of O(n/sup 3/) at each scheduling event, where n is the number of activities in the ready queue. We evaluate the performance of GUS through simulation and by an actual implementation on a real-time POSIX operating system. Our simulation studies and implementation measurements reveal that GUS performs close to, if not better than, the existing algorithms for the cases that they apply. Furthermore, we analytically establish several properties of GUS.

We present an energy-efficient, utility accrual, real-time scheduling algorithm called ReUA. ReUA considers an application model where activities are subject to time/utility function time constraints, mutual exclusion constraints on shared non-CPU resources, and statistical performance requirements on individual activity timeliness behavior. The algorithm targets mobile embedded systems where system-level energy consumption is also a major concern. For such a model, we consider the scheduling objectives of (1) satisfying the statistical performance requirements and (2) maximizing the system-level energy efficiency, while respecting resource constraints. Since the problem is NP-hard, ReUA allocates CPU cycles using statistical properties of application cycle demands, and heuristically computes schedules with a polynomial time cost. We analytically establish several timeliness and nontimeliness properties of the algorithm. Further, our simulation experiments illustrate ReUA's effectiveness and superiority.

We present an energy-efficient real-time scheduling algorithm called EUA*, for the unimodal arbitrary arrival model (or UAM). UAM embodies a "stronger" adversary than most arrival models. The algorithm considers application activities that are subject to time/utility function time constraints, UAM, and the multi-criteria scheduling objective of probabilistically satisfying utility lower bounds, and maximizing system-level energy efficiency. Since the scheduling problem is intractable, EUA* allocates CPU cycles, scales clock frequency, and heuristically computes schedules using statistical estimates of cycle demands, in polynomial-time. We establish that EUA* achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate EUA*'s superiority.

We present a wait-free protocol for the single-writer/multiple-reader problem in small-memory embedded real-time systems. We analytically establish that our protocol requires lesser (or equal) number of buffers than previously best wait-free protocols for this problem. Further, we prove that our protocol is space-optimal - the first space optimality established for wait-free protocols that consider a-priori knowledge of preemptions. Our evaluation studies and implementation measurements using the SHaRK RTOS kernel confirm the protocol's superiority and effectiveness.

Heuristic algorithms have enjoyed increasing interests and success in the context of utility accrual (UA) scheduling. However, few analytical results, such as bounds on task-level and system-level accrued utilities are known. In this paper, we propose the S-UA algorithm that can provide probabilistic bounds on task-level accrued utilities. Lower bound on system-level accrued utility ratio (AUR) is also derived and maximized by S-UA.

We argue that the key underpinning of the current state-of-the real-time practice - the priority artifact - and that of the current state-of-the real-time art - deadline-based timeliness optimality - are entirely inadequate for specifying timeliness objectives, for reasoning about timeliness behavior, and for performing resource management that can dependably satisfy timeliness objectives in many dynamic real-time systems. We argue that time/utility functions and the utility accrual scheduling paradigm provide a more generalized, adaptive, and flexible approach. Recent research in the utility accrual paradigm has significantly advanced the state-of-the-art of that paradigm. We survey these advances.

We present a real-time scheduling algorithm called VCUA, for tasks whose execution times are functions of their starting times. We model such variable execution times with variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints, VCFs, and the scheduling objective of assuring that the maximum interval between any two consecutive successful completions of jobs of a task must not exceed a specified bound, and maximizing the system's total utility. We establish that VCUA achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate VCUA's effectiveness and superiority.

We consider Real-Time CORBA 1.2's distributable threads (DTs), whose time constraints are specified using time/utility functions (TUFs), operating in legacy environments. In legacy environments, system node resources - both physical and logical - are shared among time-critical DTs and local applications that may also be time-critical. Hence, DTs that are scheduled using their propagated TUFs, as mandated by Real-Time CORBA 1.2's Case 2 approach, may suffer performance degradation, if a node utility accrual (UA) scheduler achieves higher locally accrued utility by giving higher eligibility to local threads than to DTs. To alleviate this, we consider decomposing TUFs of DTs into "sub-TUFs" for scheduling segments of DTs. We present five decomposition techniques, called UT, SCEQF, SCALL, OPTCON, and TUFS, which are specific to different classes of UA scheduling algorithms, such as those that use utility density and those that use deadline as their key decision metric. Our experimental studies identify the decomposition technique that performs best for each class of UA scheduling algorithms. In particular, our studies show that OPTCON and TUFS perform best for utility density-based UA algorithms, while SCEQF and SCALL perform best for deadline-based UA algorithms.

We present an energy-efficient real-time scheduling algorithm called the Resource-constrained Energy-Efficient Utility Accrual Algorithm (or ReUA). ReUA considers an application model where activities are subject to time/utility function-time constraints, resource dependencies including mutual exclusion constraints, and statistical performance requirements including probabilistically satisfied, activity (timeliness) utility bounds. Further, ReUA targets mobile embedded systems where system-level energy consumption is a major concern. For such a model, we consider the scheduling objectives of (1) satisfying statistical performance requirements, and (2) maximizing system-level energy efficiency, while respecting resource dependencies. Since the problem is NP-hard, ReUA allocates resources using statistical properties of application cycle demands and heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm. Further, our simulation experiments illustrate ReUA's effectiveness.

Summary form only given. We extend Jensen's time/utility functions and utility accrual model with the concept of joint utility functions (or JUFs) that allow an activity's utility to be described as a function of the completion times of other activities and their progress. We also specify the concept of progressive utility that generalizes the previously studied imprecise computational model, by describing an activity's utility as a function of its progress. Given such an extended utility accrual model, we consider the scheduling criterion of maximizing the weighted sum of completion time, progressive, and joint utilities. We present an algorithm called the combined utility accrual algorithm (or CUA) for this criterion. Experimental measurements with an implementation of CUA on a POSIX RTOS illustrate the effectiveness of JUFs in a class of applications of interest to us.

We consider real-time CORBA 2.0 (dynamic scheduling) distributable threads operating in multihop networks. When distributable threads are subject to time/utility function-time constraints and utility accrual optimality criteria, utility accrual real-time channels must be established. Such channels transport inter-node messages of distributable threads in a way that maximizes system-wide, message-level accrued utility. We present a utility accrual channel establishment algorithm called local decision for utility accrual channel establishment (or Loc-DUCE) that heuristically computes channels. Our experimental measurements using a prototype implementation reveal that LocDUCE accrues significantly higher utility than the open shortest path first routing algorithm

We extend time/utility functions and utility accrual model with the concept of joint utility functions (or JUFs) that allow an activity's utility to be described as a function of the completion times of other activities and their progress. We also specify the concept of progressive utility that generalizes the previously studied imprecise computational model, by describing an activity's utility as a function of its progress. Given such an extended utility accrual model, we consider the scheduling criterion of maximizing the weighted sum of completion time, progressive, and joint utilities. We present an algorithm called the combined utility accrual algorithm (or CUA)for this criterion. Experimental measurements with an implementation of CUA on a POSIX RTOS illustrate the effectiveness of JUFs in a class of applications of interest to us.

This paper presents two fast, best-effort real-time scheduling algorithms called MDASA and MLBESA. MDASA and MLBESA are novel in the way that they heuristically, yet accurately, mimic the behavior of the DASA and LBESA scheduling algorithms, but are faster with O(n) and O(n lg(n)) worst-case complexities, respectively. Experimental results show that the performance of MDASA and MLBESA, in general, is close to that of DASA and LBESA, respectively, for a broad range of realistic workloads. However, for a highly bursty workload, MLBESA is found to perform worse than LBESA. Furthermore, the task response times under MDASA and MLBESA are very close to the values under their counterpart scheduling algorithms. Thus, MDASA and MLBESA can substitute for DASA and LBESA algorithms, respectively, in adaptive resource allocation techniques for asynchronous real-time distributed systems where DASA and LBESA have previously been serious bottlenecks on computational costs.

We present two proactive resource allocation algorithms, called DPR and LPR, for satisfying the timeliness requirements of real-time tasks in asynchronous real-time distributed systems. The algorithms are proactive in the sense that they allow application-specified and user-triggered resource allocation by allowing anticipated task workloads to be specified for future time intervals. When proactively triggered, the algorithms allocate resources to maximize the aggregate deadline-satisfied ratio for the future time interval under the anticipated workload. While DPR uses the earliest deadline first scheduling algorithm as the underlying algorithm for process scheduling and packet scheduling, LPR uses a modified least laxity first scheduling algorithm. We show that LPR is computationally more expensive than DPR. Further, our experimental studies reveal that LPR yields a higher deadline-satisfied ratio than DPR.

We present a MAC-layer, soft real-time packet scheduling algorithm called UPA. UPA considers a message model where message packets have end-to-end timeliness requirements that are specified using Jensen's time-utility functions (TUFs). The algorithm seeks to maximize system-wide, aggregate packet utility. Since this scheduling problem is NP-hard, UPA heuristically computes schedules with a quadratic worst-case cost, faster than the previously best CMA algorithm. Our simulation studies show that UPA performs the same as or significantly better than CMA for a broad set of TUFs. Furthermore, we implement UPA and prototype a TUF-driven switched Ethernet system. The performance measurements of UPA from the implementation reveal its strong effectiveness. Finally, we derive timeliness feasibility conditions of TUF-driven switched Ethernet systems that use the UPA algorithm.

We present a framework, called meta scheduler, for implementing real-time scheduling algorithms. The meta scheduler is a portable middleware layer component designed for implementations over POSIX-compliant operating systems. It accommodates pluggable real-time scheduling algorithms while offering the flexibility of platform independence - the singular underlying OS requirement is the now nearly ubiquitous POSIX compliance. The versatility of pluggable schedulers positions the meta scheduler for deployment in an interoperable heterogeneous real-time environment. We present the design of the meta scheduler and outline its implementation. Furthermore, we present a mechanized correctness verification using the UPPAAL model checker. Prototype implementation of the meta scheduler over QNX Neutrino real-time operating system demonstrates high performance and a small footprint.

Asynchronous real-time distributed systems are inherently non-deterministic. To deal with such non-determinism's, we have developed a family of proactive resource management algorithms that support benefit-function based, end-to-end QoS management. This paper describes a middleware implementation of these algorithms, called Choir. The Choir middleware allows the user express the task end-to-end timeliness requirements using Jensen's benefit functions. Furthermore, the middleware system can transparently replicate, and possibly migrate the computational subtasks to conquer uncertainties such as workload fluctuations, changes of system resources, so that the system aggregate benefit is maximized. Initial experimental results suggest the effectiveness the Choir middleware.

In this paper, we present a systems engineering methodology for constructing certifiable realtime distributed systems. In the proposed approach, an architectural and algorithmic solution to an application problem is designed by considering the "weakest" models including the weakest asynchronous computational model and multimodal arrival model. Furthermore, timeliness properties are described using Jensen's benefit accrual predicates. Once a system solution is designed, timeliness properties are established by constructing necessary feasibility conditions that are expressed as non-valued predicates. The predicates are quantified and verified to produce the specification of a certified solution. We illustrate the approach by considering a packet transmission problem that desire soft timeliness. We present a certifiable solution to this problem that consists of switched Ethernet, a soft real-time packet scheduling algorithm (that was previously developed), and feasibility conditions.

In this paper, we present a best-effort communication protocol, called ABA, that seeks to maximize aggregate application benefit and deadline-satisfied ratio of asynchronous real-time distributed systems that use CSMA/DDCR broadcast networks. ABA considers an application model where end-to-end timeliness requirements of trans-node application tasks are expressed using Jensen's benefit functions. Furthermore, the protocol assumes that the application is designed using CSMA/DDCR feasibility conditions that is driven by a "best" possible estimate of upper bounds on message arrival densities that is possible at design-time. When such design-time postulations get violated at run-time, ABA directs message traffic so that messages that will increase applications' aggregate benefit are only transmitted, buffering others, until such time when the workloads respect their design-time postulated values. To study the performance of ABA, we consider a previously studied algorithm called RBA* as a baseline algorithm. Our experimental results indicate that ABA yields higher aggregate benefit and higher deadline-satisfied ratio than RBA* when message arrival densities increase at faster rates or at the same rates as that of process execution latencies due to the dynamics of the workload.

In this paper, we present a MAC-layer packet scheduling algorithm, called BPA, for real-time switched Ethernet networks. BPA considers a message model where trans-node application-level messages have end-to-end timeliness requirements that are specified using Jensen's benefit functions. The objective of BPA is to maximize the aggregate message-level benefit. The algorithm reasons that this objective can be achieved by maximizing aggregate packet-level benefit, where packets of messages are allowed to inherit benefit functions of their parent messages. BPA thus solves a non-preemptive packet scheduling problem. Since this problem is NP-hard, BPA heuristically computes packet schedules to maximize aggregate benefit, incurring a worst-case computational complexity of O(n/sup 2/). This is better than the O(n/sup 3/) complexity of the previously known best algorithm (called CMA) for the same problem. Further, our experimental studies show that BPA performs as good as CMA for a broad set of benefit functions, and significantly outperforms CMA for some benefit functions. Furthermore, we observe that BPA yields lower missed-deadline ratio than CMA when message arrival density increases.

This paper presents two proactive resource allocation algorithms, called RBA* and OBA, for asynchronous real-time distributed systems. The algorithms consider an application model where timeliness requirements are expressed using Jensen's benefit functions and propose adaptation functions to describe anticipated application workload during future time intervals. Furthermore, the algorithms consider an adaptation model, where application processes are dynamically replicated for sharing workload increases and a switched real-time Ethernet network as the underlying system model. Given such models, the objective of the algorithms is to maximize the aggregate application benefit and minimize the aggregate missed deadline ratio. Since determining the optimal allocation is computationally intractable, the algorithms heuristically compute near-optimal resource allocations in polynomial-time. While RBA* analyzes the process response times to determine resource allocation decisions, which is computationally expensive, OBA analyzes processor overloads to compute its decisions in a much faster way. RBA* incurs a quadratic amortized complexity in terms of process arrivals for its most computationally intensive component when DASA is used as the underlying scheduling algorithm, whereas OBA incurs a logarithmic amortized complexity for the corresponding component. Our benchmark-driven experimental studies reveal that RBA* produces a higher aggregate benefit and lower missed deadline ratio than OBA.

ASYNCHRONOUS real-time distributed systems are emerging in many domains, including defense, space, financial markets, autonomy and artificial intelligence, telecommunication, and industrial automation for real-time control above the device-level. Such systems are fundamentally distinguished by the significant runtime uncertainties that are inherent in their application environment and system resource states. Another source of nondeterminism is that some events and state changes are apparently spontaneous to the computer system per se because their causal reasons are from outside the system. Consequently, it is difficult to postulate upper bounds on application workloads or distributions for failure occurrences for such systems that will always be respected at runtime. Thus, they violate the deterministic foundations of hard real-time theory that ensures that all timing constraints are always satisfied under deterministic postulations of application workloads, execution environment characteristics, and failure distributions. Asynchronous real-time distributed systems thus raise the fundamental, apparently contradicting, issue: “How to build timely systems that operate in the presence of uncertain timeliness?” This special section presents papers that answer this question by focusing on different, but fundamental problems in asynchronous real-time distributed computing systems. The section presents four papers that address fundamental problems, including uniform agreement, group communication, and group priority inversion. Furthermore, the section presents a paper that describes a generic architectural construct for asynchronous real-time distributed systems. From the papers, we find that two divergent schools of thought are emerging. The two schools of thought are divergent in that each school of thought contradicts the other. The first school of thought is the “measure-compareadapt” approach. Mishra and Fetzer and Wang, Anceaume, Brasileiro, Greve, and Hurfin show how group communication services can be constructed and the group priority inversion problem can be solved, respectively, in asynchronous real-time distributed systems using the Timed Asynchronous (TA) model. Furthermore, Verissimo and Casimiro show how asynchronous real-time distributed systems can be built using the Timely Computing Base (TCB) architectural construct. The TA model and the TCB construct are based on the principle that uncertainty in asynchronous real-time distributed systems can be countered by postulating upper bounds on delays for timing variables such as clock drift rates and end-to-end interprocess communications. Based on such postulates, and thus assuming a partially synchronous model, one can construct higher level services such as group communication services or network of TCB modules that can detect when timing failures occur at runtime. Fundamental to this belief is that such postulates on upper bounds on timing variables are respected most of the time in asynchronous realtime distributed systems, but clearly, not always. Upon detection of timing failures, one may employ some sort of an adaptation scheme to counter the failure. While Mishra and Fetzer is silent on how adaptation can be achieved as their focus is on how the group communication service itself can be constructed, Verissimo and Casimiro propose the notion of coverage stability, which provides a framework for runtime adaptation. Wang, Anceaume, Brasileiro, Greve, and Hurfin present a protocol for solving the group priority inversion problem that occurs in real-time distributed systems that perform actively replicated processing based on static priorities. Group priority inversion is an extension of the priority inversion problem that was originally studied in the context of single processor systems. Their protocol assumes the TA model that is equipped with failure detectors. The second school of thought is the “no runtime adaptation, but guaranteed safety” paradigm. Hermant and Le Lann subscribe to this divergent philosophy. They believe that the “measure-compare-adapt” school of thought cannot help in improving timeliness guarantees. This is due to 1) runtime uncertainties that will cause postulated upper bounds on timing variables to be violated and, thus, the fail-aware property (which is used to detect timing failures) itself is lost and 2) the difficulty in conducting accurate schedulability analysis, which is exacerbated by the need to account for the overhead of the measure-compare-adapt techniques for performing runtime adaptation. IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002 881

The paper presents an architectural framework and algorithms for engineering dynamic real-time distributed systems using commercial off-the-shelf technologies. In the proposed architecture, a real-time system application is developed in a general-purpose programming language. Further, the architectural-level description of the system such as composition and interconnections of application software and hardware, and the operational requirements of the system such as timeliness and survivability are specified in a system description language. The specification of the system is automatically translated into an intermediate representation (IR) that models the system in a platform-independent manner. The IR is augmented with dynamic measurements of the system by a language runtime system to produce a dynamic system model. The dynamic model is used by resource management middleware strategies to perform resource management that achieves timeliness and survivability requirements. We present two classes of algorithms: predictive and availability-based, for performing resource allocation. To validate the viability of the approach, we use a real-time benchmark application that functionally approximates dynamic real-time command and control systems. The benchmark results illustrate that the middleware is able to achieve the desired timeliness requirements during a number of load situations. Furthermore, availability-based allocation algorithms perform resource allocation less frequently, whereas predictive algorithms give a better steady state performance for the application.

We present a "predictive" resource management algorithm for periodic tasks in real-time distributed applications that are characterized by significant execution-time uncertainties. The algorithm is predictive in the sense that it forecasts the timeliness behavior of the tasks during the resource allocation process and select allocations that yield the optimal forecasted timeliness. The algorithm uses statistical regression theory for predicting task timeliness. The performance of the predictive algorithm is studied by comparing with a nonpredictive resource management algorithm that uses heuristic rules for allocating resources. The experimental results indicate that the predictive algorithm outperforms the non-predictive algorithm when the workload shows fluctuating behavior.

Presents feedback control techniques for performing adaptive resource management in asynchronous real-time distributed systems. Such systems are characterized by significant execution time uncertainties in the application environment and system resource state. Thus, such systems require adaptive resource management that dynamically monitor the system for adherence to the desired real-time requirements and perform run-time adaptation of the application to changing workloads when unacceptable timeliness behavior is observed. We propose adaptive resource management techniques that are based on feedback control theory. The controllers solve resource allocation problems that arise during run-time adaptation using the classical proportional-integral-derivative (PID) control functions. We study the performance of the controllers through simulation. The simulation results indicate that the controllers produce low missed deadline ratios and resource utilizations during situations of high workloads.

This paper describes an implementation and the performance evaluation of the DASAATD best-effort scheduling algorithm [4] in the pC1id/pCsinunm micro-controller system Experimental results under synthetic wrkload show that in some cases, the DASALND scheduler outperfom both the EDF (Earliest Deadline First) and the RMS (Rate Monotonic Scheduling) schedulers [7]. Meanwhile, the system performance gracefully degrades as the aggregate CPU Load increases. However, the scheduling overhead in general, is not negligible, which may lead to poorer performance than non best-effort scheduling algorithms. It is found that the schealuling overhead strongly depends on the task set properties. Using the Regression Analysis technique, we developed a statistical model accounting for the scheduling overhead We show that this model, combined with a simulation tool can well predict the system performance.

Presents intelligent feedback control techniques for adaptive resource management in asynchronous, decentralized real-time systems. We propose adaptive resource management techniques that are based on feedback control theory and are designed using the intelligent control design paradigm. The controllers solve resource allocation problems that arise during run-time adaptation using the classic proportional-integral-derivative (PID) control functions and fuzzy logic. We study the performance of the controllers through simulation. The simulation results indicate that the controllers produce low missed deadline ratios and resource utilizations during high-workload situations.

Time constrained systems which operate in dynamic environments may have unknown worst case scenarios, may have large variances in the sizes of the data and event sets that they process (and thus, have large variances in execution latencies and resource requirements), and may not be statically characterizable, even by time invariant statistical distributions. The paper presents a specification language for describing environment dependent features. Also presented is an abstract model that is constructed (statically) from the specifications, and is augmented (dynamically,) with the state of environment dependent features. The model is used to define techniques for QoS (quality of service) monitoring, QoS diagnosis, and resource allocation analysis. Experimental results show the effectiveness of the approach for specification of real time QoS, detection and diagnosis of QoS failures, and restoration of acceptable QoS via reallocation of distributed computer and network resources.

This paper defines a new paradigm for high performance embedded systems. We present a model of distributed embedded control system software to capture the real-time computing requirements of complex computer-based systems. The hierarchical software architecture defines the notion of a software path the construct identified by studying embedded real-time applications. We present a technique for dynamic scheduling of sporadic paths. The novel feature of the approach is to enhance schedulability through high performance concurrent computing.

This article presents a process for the reengineering of computer-based control systems, and describes tools that automate portions of the process. The intermediate representation (IR) for capturing features of computer-based systems during reverse engineering is presented. A novel feature of the IR is that it incorporates the control system software architecture, a view that enables information to be captured at five levels of granularity: the program level, the task level, the package level, the subprogram level, and the statement level. A reverse engineering toolset that constructs the IR from Ada programs, displays the IR, and computes concurrency, communication and object-orientedness metrics is presented. Also described is the design of hypermedia techniques that enhance the usability of the reverse engineering tools.