The Nov/Dec issue of acmqueue is out!

acmqueue is free for ACM professional members

Download the app from iTunes or Google Play,
or view within your browser.

More information here




November/December 2015


The Verification of a Distributed System

  Caitie McCaffrey

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?

Distributed Development, Distributed Computing



Accountability in Algorithmic Decision-making

  Nicholas Diakopoulos

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

  Pat Helland

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.

Data



Time is an Illusion

  George Neville-Neil

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.

Distributed Computing



Non-volatile Storage

  Mihir Nanavati,
  Malte Schwarzkopf,
  Jake Wires,
  Andrew Warfield

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



September/October 2015


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.

Case Studies, Networks



Kode Vicious: Pickled Patches

  George Neville-Neil

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..."

Development



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).

Concurrency



Componentizing the Web

  Taylor Savage

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.

Web Development



Everything Sysadmin:
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?

Everything Sysadmin



The Soft Side of Software:
Lean Software Development - Building and Shipping Two Versions


  Kate Matsudaira

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

  Ben Maurer

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.



July 2015


Crash Consistency

  Thanumalayan Sankaranarayana Pillai,
  Vijay Chidambaram,
  Ramnatthan Alagappan,
  Samer Al-Kiswany,
  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

  Philip Maddox

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.

Distributed Development, Distributed Computing



June 2015


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.

AI, HCI



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.

Web Development



Kode Vicious: Hickory Dickory Doc

  George Neville-Neil

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?

Kode Vicious



Older Issues