Modern cloud services such as AI inference, video analytics, and scientific computing exhibit highly variable and bursty GPU demand patterns that static provisioning and coarse-grained sharing mechanism struggle to accommodate efficiently. Existing GPU multiplexing approaches, including NVIDIA MPS and MIG, provide limited flexibility in multi-tenant environments, often leading to resource fragmentation, under-utilization, or unpredictable latency. We present Flyt, a transparent, latency-0aware GPU orchestration framework for virtualized cloud services. Flyt enables fine-grain runtime scaling of Streaming Multiprocessors (SMs) and breaks the traditional VM–GPUs binding by allowing applications inside a VM to execute on different GPUs over time. This design supports elastic scaling and live inter–node GPU migration without application or guest OS modifications, by virtualizing GPU memory through address translation and enforcing elastic SM execution caps.

With the growth of multi-cloud computing across a heterogeneous substrate of public cloud, edge, and on-premise sites, observability has been gaining importance in compre-hending the state of availability and performance of large-scale geo-distributed systems. Collecting, processing and analyzing observability data from multiple geo-distributed clouds can be naturally modelled as dataflows comprising chained functions. These observability flows pose a unique set of challenges in-cluding ($a$) keeping cost budgets, resource overheads, network bandwidth consumed and latency low, (b) scaling to a large number of clusters, (c) adapting the volume of observability data to satisfy resource constraints and service level objectives (d) supporting diverse engines per dataflow depending on each processing function of the flow and (e) automating and optimizing placement of observability processing functions including closed-loop orchestration. Towards this end, we propose Octopus, a multi-cloud multi-engine observability processing framework. In Octopus, declarative observability dataflows (DODs) serve as an intent-driven abstraction for site reliability engineers (SREs) to specify self-driven observability dataflows. A dataflow engine in Octopus, then orchestrates these DODs to automatically deploy and self-manage observability dataflows over large fabrics spanning multiple clouds and clusters. Octopus supports a mix of streaming and batch functions and supports pluggable run-time engines, thereby enabling flexible composition of multi-engine observability flows. Our early deployment experience with Octopus is promising. We have successfully deployed production-grade metrics analysis and log processing data flows in an objective-optimized fashion across 1 cloud and 10 edge clusters spanning continents. Our results indicate data volume and WAN bandwidth savings of$2.3\mathrm{x}$and 56 %, respectively, the ability to support auto-scaling of DODs as input load varies, and the ability to flexibly relocate functions across clusters without hurting latency targets.

Though Chaos Engineering is a popular method to test reliability and performance assurance, available tools can only inject random or manually curated faults into a target system. Given the vast array of faults that can be injected, it is crucial to a.) intelligently pick the faults that can have tangible effects, b.) increase the test coverage, and c.) reduce the overall time needed to assess the reliability of a system under adverse conditions. To the effect, we are proposing to learn from past major outages and use genetic algorithm-based meta-heuristics to evolve complex fault injections.

Decentralized exchange markets leveraging blockchain have been proposed recently to provide open and equal access to traders, improve transparency and avoid single-point-of-compromise of centralized exchanges. However, they compromise on the privacy of traders with respect to their asset ownership, account balance, order details and their identity. In this paper, we present Rialto, a fully decentralized privacy-preserving exchange marketplace with support for matching trade orders, on-chain settlement and market price discovery. Rialto provides order rate and account balance confidentiality and unlinkability between traders and their trade orders, while retaining the desirable properties of a traditional marketplace like front-running resilience and market fairness. We define formal security notions of the marketplace. We perform a detailed evaluation of our solution, demonstrate that it scales well and is suitable for a large class of goods and financial instruments traded in modern exchange markets.

Blockchain networks are trustless, enabling different organizations to come together and collaborate towards a business goal. Enterprise blockchain networks are permissioned, where participation in the network is by invitation and each participant has an identity to transact on the network. Typically the incentive for joining such a permissioned network, is the value gained in terms of ease of doing business with untrusted entities, a reduction in disputes, or greater visibility into the business process and associated data, to name a few. This also means that participation in the network is asymmetric, i.e., different participants bring different levels of value to the network and gain different value from the network. The purpose of this paper is to present a mechanism to track the value brought and gained by participants, by using fine grained provenance tracking in a decentralized manner leveraging blockchain. In addition, the fine-grained provenance tracking permits us to share the value back with the contributing organizations in a fair and decentralized manner, paving the way for new modes of value sharing, incentivization and monetization mechanisms for organizations participating in the blockchain ecosystem.

In this paper, we design and implement the first-ever decentralized replicated relational database with blockchain properties that we term blockchain relational database . We highlight several similarities between features provided by blockchain platforms and a replicated relational database, although they are conceptually different, primarily in their trust model. Motivated by this, we leverage the rich features, decades of research and optimization, and available tooling in relational databases to build a blockchain relational database. We consider a permissioned blockchain model of known, but mutually distrustful organizations each operating their own database instance that are replicas of one another. The replicas execute transactions independently and engage in decentralized consensus to determine the commit order for transactions. We design two approaches, the first where the commit order for transactions is agreed upon prior to executing them, and the second where transactions are executed without prior knowledge of the commit order while the ordering happens in parallel. We leverage serializable snapshot isolation (SSI) to guarantee that the replicas across nodes remain consistent and respect the ordering determined by consensus, and devise a new variant of SSI based on block height for the latter approach. We implement our system on PostgreSQL and present detailed performance experiments analyzing both approaches.

We discuss the problem of constructing efficient temporal indexes on Hyperledger Fabric, a popular Blockchain platform. The temporal nature of the data inserted by Fabric transactions can be leveraged to support various use-cases. This requires that temporal queries be processed efficiently on this data. Currently this presents significant challenges as this data is organized on file-system, is exposed via limited API and does not support temporal indexes. In a prior work [1], we presented two models for creating temporal indexes on Fabric which overcome these limitations and improve the performance of temporal queries on Fabric. The first model creates a copy of each event inserted and stores temporally close events together on Fabric. The second model keeps the event count intact but tags metadata to each event s.t. temporally close events share the same metadata. In this paper, we present variants on these two models which are better able to handle the skew present in Fabric data. We discuss the details and show that these variants significantly outperform the approaches presented in [1] when Fabric data contains skew. We also discuss the performance tradeoffs among these variants across various dimensions - data storage, query performance, event insertion time etc.

Blockchains are designed for trustworthy and transparent execution of transactions involving multiple parties. An important class of applications requires data to be shared selectively among mutually anonymous transacting peers while retaining the tamper-resistant evidentiary and validation features of a blockchain. KYC validations of corporate customers by banks is one example, where both banks and customers benefit from sharing process and data on a blockchain network. However, sharing of confidential KYC data must be authorized by customers, and a bank-customer relationship must be kept secret from other banks in the network. In this paper, we describe the design and implementation of a smart contract for consent-driven and double-blind data sharing on the Hyperledger Fabric blockchain platform. We show how a KYC application was built around this model to address the needs of the banks while meeting regulatory requirements.

In this paper, we discuss the problem of efficiently handling temporal queries on Hyperledger Fabric, a popular implementation of Blockchain technology. The temporal nature of the data inserted by the Hyperledger Fabric transactions can be leveraged to support various use-cases. This requires that the temporal queries be processed efficiently on this data. Currently this presents significant challenges as this data is organized on file-system, is exposed to users via a limited API and does not support any temporal indexes. We present two models for overcoming these limitations and improving the performance of temporal queries on Fabric. The first model creates a copy of each event inserted by a Fabric transaction and stores temporally close events together on Fabric. The second model keeps the event count intact but tags some metadata to each event being inserted on Fabric s.t. temporally close events share the same metadata. We discuss these two models in detail and show that these two models significantly outperform the naive ways of handling temporal queries on Fabric. We also discuss the performance trade-offs for these two models across various dimensions - data storage, query performance, data ingestion time etc.

In this work, we address problem determination in virtualized clouds. We show that high dynamism, resource sharing, frequent reconfiguration, high propensity to faults and automated management introduce significant new challenges towards fault diagnosis in clouds. Towards this, we propose CloudPD, a fault management framework for clouds. CloudPD leverages (i) a canonical representation of the operating environment to quantify the impact of sharing; (ii) an online learning process to tackle dynamism; (iii) a correlation-based performance models for higher detection accuracy; and (iv) an integrated end-to-end feedback loop to synergize with a cloud management ecosystem. Using a prototype implementation with cloud representative batch and transactional workloads like Hadoop, Olio and RUBiS, it is shown that CloudPD detects and diagnoses faults with low false positives (<; 16%) and high accuracy of 88%, 83% and 83%, respectively. In an enterprise trace-based case study, CloudPD diagnosed anomalies within 30 seconds and with an accuracy of 77%, demonstrating its effectiveness in real-life operations.

Virtualization has significantly reduced the cost of creating a new virtual machine and cheap storage allows VMs to be turned down when unused. This has led to a rapid proliferation of virtual machine images, both active and dormant, in the data center. System management technologies have not been able to keep pace with this growth and the management cost of keeping all virtual machines images, active as well as dormant, updated is significant. In this work, we present ImageElves, a system to rapidly, reliably and automatically propagate updates (e.g., patches, software installs, compliance checks) in a data center. ImageElves analyses all target images and creates reliable image patches using a very small number of online updates. Traditionally, updates are applied by taking the application offline, applying updates, and then restoring the application, a process that is unreliable and has an unpredictable downtime. With ImageElves, we propose a two phase process. In the first phase, images are analyzed to create an update signature and update manifest. In the second phase, downtime is taken and the manifest is applied offline on virtual images in a parallel, reliable and automated manner. This has two main advantages, (i) spontaneously apply updates to already dormant VMs, and (ii) all updates following this process are guaranteed to work reliably leading to reduced and predictable downtimes. ImageElves uses three key ideas: (i) a novel per-update profiling mechanism to divide VMs into equivalence classes, (ii) a background logging mechanism to convert updates on live instances into patches for dormant images, and (iii) a cross-difference mechanism to filter system-specific or random information (e.g., host name, IP address), while creating equivalence classes. We evaluated the ability of ImageElves to speed up mix of popular system management activities and observed upto 80% smaller update times for active instances and upto 90% reduction in update time for dormant instances.

This paper develops a software service for dynamic performance optimization and control in performance-sensitive systems. The next generation of performance-sensitive systems is expected to be more distributed and dynamic. They will have multiple "knobs” that affect performance and resource allocation. However, relying on the conglomeration of independent knob controls can become increasingly suboptimal. The problem lies in performance composability or lack thereof; a challenge that arises because individual optimizations in performance-sensitive systems generally do not compose well when combined. Performance adaptation in such systems needs to be carefully designed and implemented by holistically considering performance composability in order to achieve desired system performance. A flexible supporting software layer is therefore needed to easily apply different holistic performance management techniques. In this paper, we develop a software service, called OptiTuner, that monitors the current performance and the resource availability in performance-sensitive systems and allows easy implementation of different performance management schemes based on theoretical concepts of constrained optimization and feedback control. In order to show the efficacy of OptiTuner, we apply it to implement three holistic energy minimization techniques in a real-time web server farm comprising 18 machines. Using an industry standard e-Business benchmark, TPC-W, we demonstrate that the three approaches save up to 40 percent of total energy cost compared to the baseline approaches that do not holistically optimize the cost.

We study the end-to-end delay bounds that can be achieved in wireless networks using packet deadlines. We assume a set of flows in the network, for which flow i has burst parameter ¿i, injection rate ¿i, and path length Ki. It was already known that, in wireline networks, the Coordinated-Earliest-Deadline-First (CEDF) protocol can achieve and end-to-end delay of approximately (¿i/¿i)+Ki, whereas other schedulers such as Weighted Fair Queuing, have end-to-end delay bounds of the form (¿i+ Ki)/¿i. For the case of wireless networks of arbitrary topology, the focus has typically been more on throughput optimality than minimizing delay. In this paper, we study the delay bounds that can be achieved by combining wireless link scheduling algorithms with a CEDF packet scheduler. We first present a centralized scheduler that has an end-to-end delay of approximately O(¿/(¿i) + ¿¿¿piN/(r¿)), where r¿is the total rate of flows through link ¿, N is the number of links in the network, and piis the path followed by packets of flow i. We then show how to convert this into a distributed scheduler. We also study the extent to which results on the schedulability of packet deadlines can be carried over from the wireline to the wireless context. Lastly, we examine ways in which the theoretical schedulers considered in this paper can be transferred to a more practical random-access based setting. This work was supported by NSF contract CCF-0728980 and was performed while the first author was visiting Bell Labs in Summer, 2009.

As real-time systems are becoming increasingly distributed, it becomes important to understand their structural robustness with respect to timing uncertainty. Structural robustness, a concept that arises by virtue of multi-stage execution, refers to the robustness of end-to-end timing behavior of an execution graph towards unexpected timing violations in individual execution stages. A robust topology is one where such violations minimally affect end-to-end execution delay. The paper shows that the manner in which resources are allocated to execution stages can make a difference in robustness. Algorithms are presented and evaluated for resource allocation that improve the robustness of execution graphs. Evaluation shows that such algorithms are able to significantly reduce deadline misses due to unpredictable timing violations. Hence, the approach is important for soft real-time systems, systems where timing uncertainty exists, or where worst-case timing is not entirely verified.

A significant problem with no simple solutions in current real-time literature is analyzing the end-to-end schedulability of tasks in distributed systems with cycles in the task graph. Prior approaches including network calculus and holistic schedulability analysis work best for acyclic task flows. They involve iterative solutions or offer no solutions at all when flows are non-acyclic. This paper demonstrates the construction of the first generalized closed-form expression for schedulability analysis in distributed task systems with non-acyclic flows. The approach is a significant extension to our previous work on schedulability in directed acyclic graphs. Our main result is a bound on end-to-end delay for a task in a distributed system with non-acyclic task flows. The delay bound allows one of several schedulability tests to be performed. Evaluation shows that the schedulability tests thus constructed are less pessimistic than prior approaches for large distributed systems.

This paper is the first to consider new uniprocessor task models motivated by the needs of reduction-based schedulability analysis techniques for distributed systems. Reduction-based analysis is a recent category of distributed system schedulability analysis techniques that reduces distributed real-time workloads to equivalent virtual uniprocessor ones for purposes of analysis using classical uniprocessor techniques. The approach motivates research on uniprocessor task models that better match the peculiarities of task loads reduced from distributed systems. We show that previous reduction-based schedulability analysis techniques suffer from pessimism that results from mismatches between uniprocessor analysis assumptions and characteristics of workloads reduced from distributed systems. To address the problem, we introduce flow-based mode changes, a uniprocessor load model tuned to the novel constraints of workloads reduced from distributed system tasks. Reducing distributed workload to this model, our simulation studies suggest that the resulting schedulability analysis is able to admit over 25% more utilization than other existing techniques, while still guaranteeing that all end-to-end deadlines of tasks are met.

Many scientific disciplines provide composition primitives whereby overall properties of systems are composed from those of their components. Examples include rules for block diagram reduction in control theory and laws for computing equivalent circuit impedance in circuit theory. No general composition rules exist for real-time systems whereby a distributed system is transformed to an equivalent single stage analyzable using traditional uniprocessor schedulability analysis techniques. Towards such a theory, in this paper, we extend our previous result on pipeline delay composition for preemptive and non-preemptive scheduling to the general case of distributed acyclic systems. Acyclic systems are defined as those where the superposition of all task flows gives rise to a Directed Acyclic Graph (DAG). The new extended analysis provides a worst-case bound on the end-to-end delay of a job under both preemptive as well as non-preemptive scheduling, in the distributed system. A simple transformation is then shown of the distributed task system into an equivalent uniprocessor task-set analyzable using traditional uniprocessor schedulability analysis. Hence, using the transformation described in this paper, the wealth of theory available for uniprocessor schedulability analysis can be easily applied to a larger class of distributed systems.

In this paper, we consider distributed utility maximizing rate allocation in cyber-physical multihop wireless networks carrying prioritized elastic flows with different end-to-end delay requirements. This scenario arises in military wireless networks (dominated by audio and video flows) that must satisfy end-to-end deadlines. Due to the inherent difficulty in providing hard guarantees in such wireless environments, the problem is cast as one of utility maximization, where utility depends on meeting deadlines. Based on a recent result in real-time scheduling, we relate end-to-end delay of prioritized flows to flow rates and priorities, then impose end-to-end delay constraints that can be expressed in a decentralized manner in terms of flow information available locally at each node. The problem of utility maximization in the presence of these constraints is formulated, where utility depends on the ability to meet deadlines. The solution to the network utility maximization (NUM) problem yields a distributed rate control algorithm that nodes can independently execute to collectively maximize global network utility, taking into account delay constraints. Results from simulations demonstrate that a low deadline miss ratio is achieved for real-time packets, without significantly impacting throughput, resulting in a higher total utility compared to a previous state-of-the-art approach.

This paper presents the delay composition algebra: a set of simple operators for systematic transformation of distributed real-time task systems into single-resource task systems such that schedulability properties of the original system are preserved. The transformation allows performing schedulability analysis on distributed systems using uniprocessor theory and analysis tools. Reduction-based analyses techniques have been used in other contexts such as control theory and circuit theory, by defining rules to compose together components of the system and reducing them into equivalent single components that can be easily analyzed. This paper is the first to develop such reduction rules for distributed real-time systems. By successively applying operators such as PIPE and SPLIT on operands that represent workload on composed subsystems, we show how a distributed task system can be reduced to an equivalent single resource task set from which the end-to-end delay and schedulability of tasks can be inferred. We show through simulations that the proposed analysis framework is less pessimistic with increasing system scale compared to traditional approaches.

Uniprocessor schedulability theory made great strides, in part, due to the simplicity of composing the delay of a job from the execution times of higher-priority jobs that preempt it. In this paper, we bound the end-to-end delay of a job in a multistage pipeline as a function of higher-priority job execution times on different stages. We show that the end-to-end delay is bounded by that of a single virtual "bottleneck" stage plus a small additive component. This contribution effectively transforms the pipeline into a single stage system. The wealth of schedulability analysis techniques derived for uniprocessors can then be applied to decide the schedulability of the pipeline. The transformation does not require imposing artitifical per-stage deadlines, but rather models the pipeline as a whole and uses the end-to-end deadlines directly in the single-stage analysis. It also does not make assumptions on job arrival patterns or periodicity and thus can be applied to periodic and aperiodic tasks alike. We show through simulations that this approach outperforms previous pipeline schedulability tests except for very short pipelines or when deadlines are sufficiently large. The reason lies in the way we account for execution overlap among stages. We discuss how previous approaches account for overlap and point out interesting differences that lead to different performance advantages in different cases. We hope that the pipeline delay composition rule, derived in this paper, may be a step towards a general schedulability analysis foundation for large distributed systems.

Sensor networks introduce a new application domain and set of challenges in distributed computing including new network-level programming languages, global system abstractions, and general-purpose communication protocols. These challenges are brought about by the tight integration of computation, communication, and distributed real-time interaction with the physical world. With the growing interest in interconnecting different sensor networks across a wide-area communication infrastructure, an overarching challenge becomes one of arriving at an agreed-upon global sensor network architecture that ensures interoperability. Unlike the Internet, where a layered communication stack (namely, the TCP/IP stack) defines the network architecture, a sensor network architecture must unify not only communication interfaces but also programming interfaces, since network communication and computation functions are tightly intertwined. In that sense, the sensor network architecture refers to a layered stack of distributed computing abstractions. This paper presents an architecture and key considerations in designing and interconnecting local and global sensor networks. Candidate protocols and middleware instantiations are described from the authors' ongoing work that meet the discussed considerations

We have developed an analysis-based design tool, ANDES, for modeling a wireless sensor network system and analyzing its performance before deployment ANDES enables designers to systematically develop a model for the system, refine it iteratively by tuning the system parameters based on existing analysis techniques, and resolve key design decisions according to the required system performance. We also present a real-time communication schedulability analysis for sensor networks based on exact characterization which utilizes information regarding network topology and workload characteristics to analyze the schedulability of a set of periodic streams with real-time constraints. We further demonstrate the use of ANDES for the designers through detailed case studies where we design wireless sensor network applications (for target detection and environmental monitoring) using ANDES and validate the results through simulations. Currently, ANDES supports communication schedulability analysis, target tracking analysis and real-time capacity analysis which work on system models with differing levels of detail. ANDES has been developed by extending the AADL/OSATE framework which has been used extensively for real-time and embedded systems. Based on key insights gained from the development of this analysis tool, we address issues in AADL for its use in the field of wireless sensor networks. We have developed a plug-in for ANDES, called ModelGeneration, which bridges the gap between the semantics needed for sensor networks and the syntax supported by AADL. This makes it easy for sensor network designers to build system models that are intuitive to them. Furthermore, ANDES is extensible and new analysis techniques can be easily incorporated into the toolset.

Personal instrumentation and monitoring services that collect and archive the physical activities of a user have recently been introduced for various medical, personal, safety, and entertainment purposes. A general software architecture is needed to support different categories of such monitoring services. This paper presents a software architecture, implementation, and preliminary evaluation of SATIRE, a wearable personal monitoring service transparently embedded in user garments. SATIRE records the owner's activity and location for subsequent automated uploading and archiving. The personal archive can later be searched for particular events to answer questions regarding past and present user activity, location, and behavior patterns. A short feasibility and usage study of a prototype based on MicaZ motes provides a proof of concept for the SATIRE architecture.

Datalink layer framing in wireless sensor networks usually faces a trade-off between large frame sizes for high channel bandwidth utilization and small frame sizes for effective error recovery. Given the high error rates of intermote communications, TinyOS opts in favor of small frame sizes at the cost of extremely low channel bandwidth utilization. In this paper, we describe Seda: a streaming datalink layer that resolves the above dilemma by decoupling framing from error recovery. Seda treats the packets from the upper layer as a continuous stream of bytes. It breaks the data stream into blocks, and retransmits erroneous blocks only (as opposed to the entire erroneous frame). Consequently, the frame-error-rate (FER), the main factor that bounds the frame size in the current design, becomes irrelevant to error recovery. A frame can therefore be sufficiently large in great favor of high utilization of the wireless channel bandwidth, without compromising the effectiveness of error recovery. Meanwhile, the size of each block is configured according to the error characteristics of the wireless channel to optimize the performance of error recovery. Seda has been implemented as a new datalink layer in the TinyOS, and evaluated through both simulations and experiments in a testbed of 48 MicaZ motes. Our results show that, by increasing the TinyOS frame size from the default 29 bytes to 100 bytes (limited by the buffer space at MicaZ firmware), Seda improves the throughput around 25% under typical wireless channel conditions. Seda also reduces the retransmission traffic volume by more than 50%, compared to a framebased retransmission scheme. Our analysis also exposes that future sensor motes should be equipped with radios with more packet buffer space on the radio firmware to achieve optimal utilization of the channel capacity.

Integrated services schemes have not been used to support QoS in OBS networks, largely because of the high control overhead involved in monitoring bursts continuously at intermediate nodes. In this paper, we propose for the first time, an integrated services scheme to support elastic QoS in OBS networks. Our scheme relieves intermediate nodes of the burden of monitoring individual bursts continuously, thus largely decreasing the control overhead. We show how absolute bandwidth guarantees can be provided, and how bandwidth used by each connection can be made elastic. We demonstrate the effectiveness of our scheme using simulation studies.