Recursive Programming

January 30, 2015 ~ Adrian Colyer ~ 1 Comment

Recursive Programming - Dijkstra 1960 * Updated link to one that is not behind a paywall - thanks to Graham Markall for the catch * This paper deals with something we take so much for granted that it's hard to imagine a time when it had yet to be introduced to the world. That time ... Continue Reading

On Distributed Communications Networks

January 29, 2015 ~ Adrian Colyer ~ Leave a comment

On Distributed Communications Networks - Baran 1962 Way before it became fashionable to build large-scale distributed systems out of relatively unreliable commodity hardware, Baran was investigating the properties a network built in such a way might have. This paper is very much of its time, and all the more enjoyable for it: want to know ... Continue Reading

Eraser: A dynamic data race detector for multi-threaded programs

January 28, 2015 ~ Adrian Colyer ~ Leave a comment

Eraser: A dynamic data race detector for multi-threaded programs - Savage et al. 1997 Debugging a multithreaded program can be difficult. Simple errors in synchronization can produce timing-dependent data races that can take weeks or months to track down. Eraser dynamically detects data races in multi-threaded programs. There are two basic approaches to doing this, ... Continue Reading

ZooKeeper: wait-free coordination for internet scale systems

January 27, 2015 ~ Adrian Colyer ~ 4 Comments

ZooKeeper: wait-free coordination for internet scale systems - Hunt et al. (Yahoo!) 2010 Distributed systems would be much simpler if the distributed parts didn't have to coordinate in some fashion. But it's this notion of 'working together' to achieve some aim that differentiates a distributed system from an unrelated bag of parts. Examples of the ... Continue Reading

Dremel: interactive analysis of web-scale datasets

January 26, 2015 ~ Adrian Colyer ~ 2 Comments

Dremel: interactive analysis of web-scale datasets - Melnik et al. (Google), 2010. Dremel is Google's interactive ad-hoc query system that can run aggregate queries over trillions of rows in seconds. It scales to thousands of CPUs, and petabytes of data. It was also the inspiration for Apache Drill. Dremel borrows the idea of serving trees ... Continue Reading

The MADlib Analytics Library

January 23, 2015 ~ Adrian Colyer ~ 1 Comment

The MADlib Analytics Library - MAD Skills, the SQL - Hellerstein et al. 2012 The way that we use large databases has evolved from being primarily in support of accounting and financial record-keeping, to primarily in support of predictive analytics over a wide range of potentially noisy data. Analytics at scale requires the marriage of ... Continue Reading

The Design Philosophy of the DARPA Internet Protocols

January 22, 2015 ~ Adrian Colyer ~ 6 Comments

The Design Philosophy of the DARPA Internet Protocols - Clark 1988 While there have been papers and specifications that describe how the (internet) protocols work, it is sometimes difficult to deduce from these why the protocol is as it is. For example, the Internet protocol is based on a connectionless or datagram mode of service. ... Continue Reading

A new presumed commit optimisation for two-phase commit

January 21, 2015 ~ Adrian Colyer ~ 2 Comments

A new presumed commit optimisation for two phase commit - Lampson and Lomet 1993. Two phase commit (2PC) is the protocol used to coordinate distributed transactions. In this paper Lampson and Lomet first recap the basic 2PC protocol in its 'presumed nothing' form, then go on to describe the traditional 'presumed abort' and 'presumed commit' ... Continue Reading

Architecture of a Database System

January 20, 2015 ~ Adrian Colyer ~ 9 Comments

Architecture of a Database System - Hellerstein, Stonebraker & Hamilton, 2007. This is a longer read (and hence a slightly longer write-up too) coming in at 119 pages, but it's written in a very easy style so the pages fly by. It oozes wisdom and experience from every paragraph as Joe Hellerstein and Michael Stonebroker ... Continue Reading

Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing

January 19, 2015 ~ Adrian Colyer ~ 5 Comments

Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing - Google 2014 Mesa is another in the tapestry of systems that support Google's advertising business. Previously editions of The Morning Paper have covered Photon, Spanner, F1, and F1's online schema update mechanism. Mesa is a highly scalable analytic data warehousing system that stores critical measurement data related ... Continue Reading

the morning paper

a random walk through Computer Science research, by Adrian Colyer
Made delightfully fast by strattic

Month: January 2015