Monarch is a globally-distributed in-memory time series database system in Google. Monarch runs as a multi-tenant service and is used mostly to monitor the availability, correctness, performance, load, and other aspects of billion-user-scale applications and systems at Google. Every second, the system ingests terabytes of time series data into memory and serves millions of queries. Monarch has a regionalized architecture for reliability and scalability, and global query and configuration planes that integrate the regions into a unified system. On top of its distributed architecture, Monarch has flexible configuration, an expressive relational data model, and powerful queries. This paper describes the structure of the system and the novel mechanisms that achieve a reliable and flexible unified system on a regionalized distributed architecture. We also share important lessons learned from a decade's experience of developing and running Monarch as a service in Google.

In this paper, we present an overview of our approach to C macro handling in the Proteus C/C++ code transformation system. This approach gives us the capability to fully capture the semantics of complex macros without sacrificing high fidelity. As part of the Proteus system, they have been successfully applied to millions of lines of C/C++ code

Most documented efforts in fault-tolerant computing address the problem of recovering from failures that occur during normal system operation. To bring a system to a point where it can begin performing its duties first requires that the system successfully complete initialization. Large-scale distributed systems may take hours to initialize. For such systems, a key challenge is tolerating failures that occur during initialization, while still completing initialization in a timely manner. In this paper, we present a dependable initialization model that captures the architecture of the system to be initialized, as well as interdependencies among system components. We show that overall system initialization may sometimes complete more quickly if recovery actions are deferred as opposed to commencing recovery actions as soon as a failure is detected. This observation leads us to introduce a recovery decision function that dynamically assesses when to take recovery actions. We then describe a dependable initialization algorithm that combines the dependable initialization model and the recovery decision function for achieving fast initialization. Experimental results show that our algorithm incurs lower initialization overhead than that of a conventional initialization algorithm. This work is the first effort we are aware of that formally studies the challenges of initializing a distributed system in the presence of failures.

This paper presents Aurora, a software toolkit that dramatically reduces the effort required to develop configurable, reliable, and scalable wireless applications. The toolkit consists of software libraries, code generation tools, and executable software components that provide initialization and fault tolerance support typically needed by these applications. Aurora has been used in several experimental wireless systems at Lucent Technologies. Empirical results show that it provides 35% to 75% of the software used in these systems, excluding operating system and third party class library software. These results indicate huge savings in reduced development effort, lowering development costs and shortening time to market, over systems that do not use Aurora.

In this paper, we present the design and implementation of a software system that performs the control functions of current mobile switching centers (MSCs) and visitor location registers (VLRs), and provides support for third generation services. The novelty of the system design is in its software architecture. To allow flexible deployment of the system as the migration from second generation to third generation systems occurs, the software is modular. To provide scalability in terms of capacity, distributed processing is used. We show that a deployment of this system using three Sun Ultra workstations achieves a call throughput of 300,000 calls/hour with a latency of below 300 milliseconds. This meets the latency requirements of third generation systems.

We present a comparison of the control signaling load of two vastly different architectures for providing personal communication services (PCSs). One architecture is based on current cellular networks. The other architecture, called the wireless distributed call processing architecture (WDCPA), distributes processing from the mobile switching centers and cell sites and executes new procedures for tracking mobile users and locating mobile users to deliver calls. We determine the signaling load generated within each system to support mobility management and call control based on standard assumptions about the operating parameters of a cellular network. Our results show that, when compared to current cellular systems, for simple single-connection services, WDCPA has marginally reduced cross-network signaling loads. For multiconnection calls, WDCPA incurs 35% less total signaling load for mobility management, has reduced cross-network signaling load for mobility management by up to 65%, and depending on the user model (e.g., data or telecommunication), has reduced total cross-network signaling load, including procedures for call/connection and mobility management, by up to 55% when compared to current cellular systems, while more flexibly supporting services.

As dependence on wide-area and other point-to-point networks increases, the need for diagnosis of the distributed resources becomes critical. Continuous online distributed diagnosis at the system-level provides a desirable solution. The Adapt algorithm, which performs online adaptive distributed diagnosis in arbitrary networks in the presence of node failures, is examined. Simulation results depicting operation for various network topologies are given, including test and message counts and diagnosis latency. The results indicate that Adapt performs significantly better than derived worst-case bounds. The best- and worst-case performance bounds are analyzed.>

The practical application and implementation of online distributed system-level diagnosis theory is documented. Proven distributed diagnosis algorithms are shown to be impractical in real systems due to high resource requirements. A distributed system-level diagnosis algorithm called Adaptive DSD is shown to minimize network resources and has resulted in a practical implementation. Adaptive DSD assumes a distributed network, in which network nodes can test other nodes and determine them to be faulty or fault-free. Tests are issued from each node adaptively and depend on the fault situation of the network. Test result reports are generated from test results and forwarded between nodes in the network. Adaptive DSD is proven correct in that each fault-free node reaches an accurate independent diagnosis of the fault conditions of the remaining nodes. No restriction is placed on the number of faulty nodes; any fault situation with any number of faulty nodes is diagnosed correctly. An implementation of the Adaptive DSD algorithm is described.>