Distributed Systems and Parallel Computing
No matter how powerful individual computers become, there are still reasons to harness the power of multiple computational units, often spread across large geographic areas. Sometimes this is motivated by the need to collect data from widely dispersed locations (e.g., web pages from servers, or sensors for weather or traffic). Other times it is motivated by the need to perform enormous computations that simply cannot be done by a single CPU.
From our company’s beginning, Google has had to deal with both issues in our pursuit of organizing the world’s information and making it universally accessible and useful. We continue to face many exciting distributed systems and parallel computing challenges in areas such as concurrency control, fault tolerance, algorithmic efficiency, and communication. Some of our research involves answering fundamental theoretical questions, while other researchers and engineers are engaged in the construction of systems to operate at the largest possible scale, thanks to our hybrid research model.
Recent Publications
Brief Announcement: Efficient Recoverable Writable-CAS
Prasad Jayanti
Sucharita Jayanti
Submitting to Principles of Distributed Computing (PODC) (2023)
Preview abstract
We present DuraCAS, a durable, i.e., recoverably linearizable and detectable implementation of the CAS (compare-and-swap) primitive. DuraCAS is writable, meaning it supports a Write() operation along with CAS() and Read(); has constant time complexity per operation; allows for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join the protocol and access our implementation; and has adaptive space complexity, meaning the space use scales in the number of processes n that actually use the objects, as opposed to previous protocols whose space complexity depends on N, the maximum number of processes that the protocol is designed for. Furthermore, DuraCAS, requires only O(m + n) space to support m objects that get accessed by n processes, improving on the state-of-the-art O(m + N2). To our knowledge, DuraCAS is the first durable CAS algorithm that allows for dynamic joining, and is the first to exhibit adaptive space complexity.
View details
Preview abstract
This document reserves a Top-Level Domain (TLD) label "alt" to be used in non-DNS contexts. It also provides advice and guidance to developers creating alternative namespaces.
View details
A Model-based, Quality Attribute-guided Architecture Re-Design Process at Google
Qin Jia
Yuanfang Cai
2023 IEEE/ACM 45th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP)
Preview abstract
Communicating and justifying design decisions are difficult, especially when the architecture design has to evolve.
In this paper, we report our experiences of using formal but lightweight design models to communicate, justify, and analyze the quality trade-offs of an architecture revision plan for Monarch, a large-scale legacy system from Google.
We started from a few critical user scenarios and their associated quality attribute scenarios, which makes these models lightweight and concise, expressing high-level abstractions only. We also separated static views from dynamic views so that each diagram can be precise and suitable for analyzing different types of quality attributes respectively. The combination of scenarios, quality attributes, and lightweight modeling was well accepted by the team as an effective way to analyze and communicate the trade-offs. A few days after we presented and shared this process, two new projects within the Monarch team adopted component and sequence diagrams in their design documents, and two other product areas within Google started to learn and to adopt the process as well. Our experience indicates that these architecture modeling and analysis techniques can be integrated into software development process to communicate and assess features, quality attributes, or design decisions continuously and iteratively.
View details
Constant RMR System-wide Failure Resilient Durable Locks with Dynamic Joining
Anup Joshi
Prasad Jayanti
ACM Symposium on Parallelism in Algorithms and Architectures (2023)
Preview abstract
We design a Recoverable Mutual Exclusion (RME) algorithm for the system-wide failure model. Our algorithm requires only O(1) space per process, and achieves O(1) worst-case RMR complexity in both the CC and DSM models. Furthermore, in contrast to existing RME algorithms which can only support a pre-declared set of n threads with names from 1 to n, our algorithm can be accessed by arbitrarily many dynamically allocated threads of arbitrary names.
View details
SAC123 - SSAC Report on the Evolution of Internet Name Resolution
Internet Corporation for Assigned Names and Numbers (ICANN) , vol. ICANN Security and Stability Advisory Committee (SSAC) Reports and Advisories (2023), pp. 36
Preview abstract
New technologies are changing how name resolution happens on the Internet. The DNS remains the prominent, or default, naming system for the Internet, but alternative naming systems are in use as well. This is nothing particularly new, as there have always been naming systems besides the DNS in use throughout the Internet’s history. These alternative naming systems use the same syntax as the DNS, dot-separated labels. There are many motivations for copying this syntax, but the primary reason is because designers of these alternative naming systems wish to benefit from the existence of software applications built to receive DNS names as input.
This has the potential to create situations where the same name exists in DNS and in an
alternative system, potentially causing name collisions. However, there is only one domain
namespace and its referential integrity is important for Internet users and for the stability and
security of Internet names. Thus, as alternative naming systems increase in popularity their use
threatens to increase ambiguity in the shared single domain namespace. This increased ambiguity in Internet naming threatens to undermine the trust that users have in Internet identifiers and the services that rely on them.
Additionally, names are becoming less visible to Internet end users, yet they remain vital to the
security and stability of Internet infrastructure. Technologies such as QR codes and URL
shorteners offer great utility to Internet users while also obscuring the underlying domain names used and creating new opportunities for malicious behavior. Meanwhile, QR codes and URL shorteners use domain names to access the Internet resource, even if the human user does not see it.
These are the two main trends that the SSAC identifies in this report. The same name can resolve in different ways (ambiguous name resolution), and names of service endpoints are less visible (names are less conspicuous to end users). It is the combination of these two trends that fundamentally threatens to undermine confidence in services on the Internet.
View details
Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining
Prasad Jayanti
Sucharita Jayanti
International Symposium on Distributed Computing (2023)
Preview abstract
We present durable implementations for two well known universal primitives---CAS (compare-and-swap), and its ABA-free counter-part LLSC (load-linked, store-conditional). Our implementations satisfy method-based recoverable linearizability (MRL) and method-based detectability (M-detectability)---novel correctness conditions that require only a simple usage pattern to guarantee resilience to individual process crashes (and system-wide crashes), including in implementations with nesting. Additionally, our implementations are: writable, meaning they support a Write() operation; have constant time complexity per operation; allow for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join a protocol and access our implementations; and have adaptive space complexity, meaning the space use scales in the number of processes $n$ that actually use the objects, as opposed to previous protocols whose space complexity depends on $N$, the maximum number of processes that the protocol is designed for. Our durable Writable-CAS implementation, DuraCAS, requires $O(m + n)$ space to support $m$ objects that get accessed by $n$ processes, improving on the state-of-the-art $O(m + N^2)$. By definition, LLSC objects must store ``contexts'' in addition to object values. Our Writable-LLSC implementation, DuraLL, requires $O(m + n + C)$ space, where $C$ is the number of ``contexts'' stored across all the objects. While LLSC has an advantage over CAS due to being ABA-free, the object definition seems to require additional space usage. To address this trade-off, we define an External Context (EC) variant of LLSC. Our EC Writable-LLSC implementation is ABA-free and has a space complexity of just $O(m + n)$.
To our knowledge, our algorithms are the first durable CAS algorithms that allow for dynamic joining, and are the first to exhibit adaptive space complexity. To our knowledge, we are the first to implement any type of durable LLSC objects.
View details
Some of our teams
