Global Sequence Protocol: A Robust Abstraction for Replicated Shared State - Burckhardt et al. 2015 This is the ECOOP '15 paper that we've been building up to so far this week. The problem domain is the familiar desire to support replicated shared data across nodes (mobile devices here) with eventual consistency. In the mobile context, … Continue reading Global Sequence Protocol
Tag: Distributed Systems
Cloud Types for Eventual Consistency
Cloud Types for Eventual Consistency - Burckhardt et al. 2012 Providing good programming abstractions for cloud storage, synchronization, and disconnected operation appears crucial to accelerate the production of useful and novel applications on today’s and tomorrow’s mobile devices. This paper proposes a model based on cloud types (which may be integrated with a programming language). … Continue reading Cloud Types for Eventual Consistency
Eventually Consistent Transactions
Eventually Consistent Transactions - Burckhardt et al. 2012 There's another ECOOP'15 paper I'd like to cover this week - Burckhardt et al.'s "Global Sequence Protocol." But that paper builds on the notion of Cloud Types (similar in spirit to CRDTs, and not something I've personally come across before), which in turn builds on work on … Continue reading Eventually Consistent Transactions
Heracles: Improving Resource Efficiency at Scale
Heracles: Improving Resource Efficiency at Scale - Lo et al. 2015 Until recently, scaling from Moore’s law provided higher compute per dollar with every server generation, allowing datacenters to scale without raising the cost. However, with several imminent challenges in technology scaling, alternate approaches are needed. Those approaches involve increasing server utilization, which is still … Continue reading Heracles: Improving Resource Efficiency at Scale
The Drinking Philosophers Problem
The Drinking Philosophers Problem - Chandy & Misra 1984 How could I resist a paper with a title like that! The Drinking Philosophers is referenced in the PowerGraph paper as a solution to the problem of serializable execution in graph-parallel computation. Vertices are philosophers, and edges are forks (drinks). Let's take a look at how … Continue reading The Drinking Philosophers Problem
A higher order estimate of the optimum checkpoint interval for restart dumps
A higher order estimate of the optimum checkpoint interval for restart dumps - Daly 2004 TL;DR: if you know how long it takes your system to create a checkpoint/snapshot (δ), and you know the expected mean-time between failures (M), then set the checkpoint interval to be √(2δM) - δ. OK, I grant that today's paper … Continue reading A higher order estimate of the optimum checkpoint interval for restart dumps
Detecting Termination of Distributed Computations Using Markers
Detecting Termination of Distributed Computations Using Markers - Misra 1983 There's an intriguing line in the Distributed GraphLab paper that caught my eye: "Termination is evaluated using distributed consensus algorithm described in [Ref]." Today's choice is the paper by Misra in 1983 that describes this distributed termination detection algorithm. The solution is similar in spirit … Continue reading Detecting Termination of Distributed Computations Using Markers
A Bridging Model for Parallel Computation
A Bridging Model for Parallel Computation - Valiant 1990 We've seen a lot of references to the 'Bulk Synchronous Parallel' model over the last two weeks. When it was conceived by Valiant in 1990 though, it was intended as a much more general model than simply an abstraction to support graph processing. As the von … Continue reading A Bridging Model for Parallel Computation
Scalability! But at what COST?
Scalability! But at what COST? - McSherry et al. 2015 With thanks to Felix Cuadrado, @felixcuadrado, for pointing this paper out to me via twitter. Scalability is highly prized, yet it can be a misleading metric when studied in isolation. McSherry et al. study the COST of distributed systems: the Configuration that Outperforms a Single … Continue reading Scalability! But at what COST?
FAWN: A Fast Array of Wimpy Nodes
FAWN: A Fast Array of Wimpy Nodes - Andersen et al. 2009 A few days ago we looked at FaRM (Fast Remote Memory), which used RDMA to match network speed with the speed of CPUs and got some very impressive results in terms of queries & transactions per second. But maybe there's another way of … Continue reading FAWN: A Fast Array of Wimpy Nodes
the morning paper 