The Verification of a Distributed System
A practitioner's guide to increasing confidence in system correctness
Leslie Lamport, known for his seminal work in distributed systems, famously said, "A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable." Given this bleak outlook and the large set of possible failures, how do you even begin to verify and validate that the distributed systems you build are doing the right thing?
Accountability in Algorithmic Decision-making
A view from computational journalism
Every fiscal quarter automated writing algorithms churn out thousands of corporate earnings articles for the AP (Associated Press) based on little more than structured data. Companies such as Automated Insights, which produces the articles for AP, and Narrative Science can now write straight news articles in almost any domain that has clean and well-structured data: finance, sure, but also sports, weather, and education, among others. The articles aren't cardboard either; they have variability, tone, and style, and in some cases readers even have difficulty distinguishing the machine-produced articles from human-written ones.
Privacy and Rights, HCI, AI
Immutability Changes Everything
We need it, we can afford it, and the time is now.
There is an inexorable trend toward storing and sending immutable data. We need immutability to coordinate at a distance, and we can afford immutability as storage gets cheaper. This article is an amuse-bouche sampling the repeated patterns of computing that leverage immutability. Climbing up and down the compute stack really does yield a sense of déjà vu all over again.
Time is an Illusion
Lunchtime doubly so.
- Ford Prefect to Arthur Dent in "The Hitchhiker's Guide to the Galaxy", by Douglas Adams
One of the more surprising things about digital systems is how poorly they keep time. When most programs ran on a single system this was not a significant issue for the majority of software developers, but once software moved into the distributed-systems realm this inaccuracy became a significant challenge. Few programmers have read the most important paper in this area, Leslie Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" (1978), and only a few more have come to appreciate the problems they face once they move into the world of distributed systems.
Implications of the Datacenter's Shifting Center
For the entire careers of most practicing computer scientists, a fundamental observation has consistently held true: CPUs are significantly more performant and more expensive than I/O devices. The fact that CPUs can process data at extremely high rates, while simultaneously servicing multiple I/O devices, has had a sweeping impact on the design of both hardware and software for systems of all sizes, for pretty much as long as we've been building them. This assumption, however, is in the process of being completely invalidated.
Data and Databases
Schema.org: Evolution of Structured Data on the Web
R.V. Guha, Google
Dan Brickley, Google
Steve Macbeth, Microsoft
Big data makes common schemas even more necessary.
Separation between content and presentation has always been one of the important design aspects of the Web. Historically, however, even though most Web sites were driven off structured databases, they published their content purely in HTML. Services such as Web search, price comparison, reservation engines, etc. that operated on this content had access only to HTML. Applications requiring access to the structured data underlying these Web pages had to build custom extractors to convert plain HTML into structured data. These efforts were often laborious and the scrapers were fragile and error prone, breaking every time a site changed its layout.
Data and Databases
A Purpose-built Global Network:
Google's Move to SDN
A discussion with Amin Vahdat, David Clark, and Jennifer Rexford
Everything about Google is at scale, of course—a market cap of legendary proportions, an unrivaled talent pool, enough intellectual property to keep armies of attorneys in Guccis for life, and, oh yeah, a private WAN (wide area network) bigger than you can possibly imagine that also happens to be growing substantially faster than the Internet as a whole.
Kode Vicious: Pickled Patches
On repositories of patches and tension between security professionals and in-house developers
Dear KV, I recently came upon a software repository that was not a repo of code, but a repo of patches. The project seemed to build itself out of several other components and then had complicated scripts that applied the patches in a particular order. I had to look at this repo because I wanted to fix a bug in the system, but trying to figure out what the code actually looked like at any particular point in time was baffling. Are there tools that would help in working like this? I've never come across this type of system before, where there were over a hundred patches, some of which contained thousands of lines of code.
Kode Vicious, Security
It Probably Works
Tyler McMullen, Fastly
Probabilistic algorithms are all around us. Not only are they acceptable, but some programmers actually seek out chances to use them.
Probabilistic algorithms exist to solve problems that are either impossible or unrealistic (too expensive, too time-consuming, etc.) to solve precisely. In an ideal world, you would never actually need to use probabilistic algorithms. To programmers who are not familiar with them, the idea can be positively nerve-wracking: "How do I know that it will actually work? What if it's inexplicably wrong? How can I debug it? Maybe we should just punt on this problem, or buy a whole lot more servers..."
Challenges of Memory Management on Modern NUMA System
Fabien Gaud, Simon Fraser University
Baptiste Lepers, CNRS
Justin Funston, Simon Fraser University
Mohammad Dashti, Simon Fraser University
Alexandra Fedorova, University of British Columbia
Vivien Quéma, Grenoble INP
Renaud Lachaize, UJF
Mark Roth, Simon Fraser University
Optimizing NUMA systems applications with Carrefour
Modern server-class systems are typically built as several multicore chips put together in a single system. Each chip has a local DRAM (dynamic random-access memory) module; together they are referred to as a node. Nodes are connected via a high-speed interconnect, and the system is fully coherent. This means that, transparently to the programmer, a core can issue requests to its node's local memory as well as to the memories of other nodes. The key distinction is that remote requests will take longer, because they are subject to longer wire delays and may have to jump several hops as they traverse the interconnect. The latency of memory-access times is hence non-uniform, because it depends on where the request originates and where it is destined to go. Such systems are referred to as NUMA (non-uniform memory access).
Componentizing the Web
We may be on the cusp of a new revolution in web development.
There is no task in software engineering today quite as herculean as web development. A typical specification for a web application might read: The app must work across a wide variety of browsers. It must run animations at 60 fps. It must be immediately responsive to touch. It must conform to a specific set of design principles and specs. It must work on just about every screen size imaginable, from TVs and 30-inch monitors to mobile phones and watch faces. It must be well-engineered and maintainable in the long term.
Automation Should Be Like Iron Man, Not Ultron
Thomas A. Limoncelli
The "Leftover Principle" Requires Increasingly More Highly-skilled Humans.
A few years ago we automated a major process in our system administration team. Now the system is impossible to debug. Nobody remembers the old manual process and the automation is beyond what any of us can understand. We feel like we've painted ourselves into a corner. Is all operations automation doomed to be this way?
The Soft Side of Software:
Lean Software Development - Building and Shipping Two Versions
Catering to developers' strengths while still meeting team objectives
Once I was managing a software team and we were working on several initiatives. Projects were assigned based on who was available, their skillsets, and their development goals. This resulted in two developers, Mary and Melissa, being assigned to the same project.
The Soft Side of Software
Fail at Scale
Reliability in the face of rapid change
Failure is part of engineering any large-scale system. One of Facebook's cultural values is embracing failure. This can be seen in the posters hung around the walls of our Menlo Park headquarters: "What Would You Do If You Weren't Afraid?" and "Fortune Favors the Bold."
Web Services, Failure and Recovery
How to De-identify Your Data
Olivia Angiuli, Joe Blitzstein, and Jim Waldo - Harvard University
Balancing statistical accuracy and subject privacy in large social-science data sets
Big data is all the rage; using large data sets promises to give us new insights into questions that have been difficult or impossible to answer in the past. This is especially true in fields such as medicine and the social sciences, where large amounts of data can be gathered and mined to find insightful relationships among variables. Data in such fields involves humans, however, and thus raises issues of privacy that are not faced by fields such as physics or astronomy.
Privacy and Rights, Data and Databases
Still Finding the Right Questions
George Neville-Neil and Steve Bourne
Branching out and changing with the times at acmqueue
Welcome to the newest incarnation of acmqueue. When we started putting together the first edition of ACM Queue in early 2003, it was a completely new experiment in publishing for ACM. Targeting a practitioner audience meant that much of what we did would differ from academic publishing.
Thanumalayan Sankaranarayana Pillai,
Andrea C. Arpaci-Dusseau,
Remzi H. Arpaci-Dusseau
Rethinking the Fundamental Abstractions of the File System
The reading and writing of data, one of the most fundamental aspects of any Von Neumann computer, is surprisingly subtle and full of nuance. For example, consider access to a shared memory in a system with multiple processors. While a simple and intuitive approach known as strong consistency is easiest for programmers to understand, many weaker models are in widespread use (e.g., x86 total store ordering); such approaches improve system performance, but at the cost of making reasoning about system behavior more complex and error-prone. Fortunately, a great deal of time and effort has gone into thinking about such memory models, and, as a result, most multiprocessor applications are not caught unaware.
File Systems and Storage
Testing a Distributed System
Testing a distributed system can be trying even under the best of circumstances.
Distributed systems can be especially difficult to program, for a variety of reasons. They can be difficult to design, difficult to manage, and, above all, difficult to test. Testing a normal system can be trying even under the best of circumstances, and no matter how diligent the tester is, bugs can still get through. Now take all of the standard issues and multiply them by multiple processes written in multiple languages running on multiple boxes that could potentially all be on different operating systems, and there is potential for a real disaster.
Natural Language Translation at the Intersection of AI and HCI
Spence Green, Jeffrey Heer, and Christopher D. Manning
Old questions being answered with both AI and HCI
The fields of artificial intelligence (AI) and human-computer interaction (HCI) are influencing each other like never before. Widely used systems such as Google Translate, Facebook Graph Search, and RelateIQ hide the complexity of large-scale AI systems behind intuitive interfaces. But relations were not always so auspicious. The two fields emerged at different points in the history of computer science, with different influences, ambitions, and attendant biases. AI aimed to construct a rival, and perhaps a successor, to the human intellect. Early AI researchers such as McCarthy, Minsky, and Shannon were mathematicians by training, so theorem-proving and formal models were attractive research directions. In contrast, HCI focused more on empirical approaches to usability and human factors, both of which generally aim to make machines more useful to humans. Many of the attendees at the first CHI conference in 1983 were psychologists and engineers. Papers were presented with titles such as "Design principles for human-computer interfaces" and "Psychological issues in the use of icons in command menus," hardly appealing fare for most mainstream AI researchers.
Beyond Page Objects: Testing Web Applications with State Objects
Arie van Deursen
Use states to drive your tests
End-to-end testing of Web applications typically involves tricky interactions with Web pages by means of a framework such as Selenium WebDriver. The recommended method for hiding such Web-page intricacies is to use page objects, but there are questions to answer first: Which page objects should you create when testing Web applications? What actions should you include in a page object? Which test scenarios should you specify, given your page objects?
While working with page objects during the past few months to test an AngularJS Web application, I answered these questions by moving page objects to the state level. Viewing the Web application as a state chart made it much easier to design test scenarios and corresponding page objects. This article describes the approach that gradually emerged: essentially a state-based generalization of page objects, referred to here as state objects.
Kode Vicious: Hickory Dickory Doc
On null encryption and automated documentation
While reviewing some encryption code in our product, I came across an option that allowed for null encryption. This means the encryption could be turned on, but the data would never be encrypted or decrypted. It would always be stored "in the clear." I removed the option from our latest source tree because I figured we didn't want an unsuspecting user to turn on encryption but still have data stored in the clear. One of the other programmers on my team reviewed the potential change and blocked me from committing it, saying that the null code could be used for testing. I disagreed with her, since I think that the risk of accidentally using the code is more important than a simple test. Which of us is right?