Review of "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs"

I thought this paper was pretty interesting - intuitively the power law distribution of natural graphs makes sense, but I would not have originally thought about it when working with something like GraphLab. I'm not sure exactly how general the power law distribution is, but it's definitely true for social networks, which are extremely important for graph processing in today's world, so this is definitely a worthwhile problem to solve.

There are two main ideas: first, separate the program explicitly into Gather / Apply / Scatter phases, allowing PowerGraph to optimize your program by having a better understanding of what needs to occur where. Second, partition the graph based on edges, not vertices, since this is more representative of the work that needs to be done.

The first trade-off I see is simply usability / programmability; it seems that it is a bit easier to reason about the programs which are written in GraphLab and Pregel than in PowerGraph due to the developer having to be more aware of the different phases in PowerGraph. However, this increase in complexity is relatively minor, and certainly seems worth the performance benefits in applicable situations.

I can definitely see this being impactful in 10 years - graph processing is a very hot subject right now, and this paper seems to introduce some ideas that seem very promising.

Review of "Materialization Optimizations for Feature Selection Workloads"

In the current state of machine learning, using a machine learning algorithm on your data often essentially comes down to deciding on what features to use, which can sometimes be extremely nonintuitive, and requires a great deal of testing. With machine learning becoming more ubiquitous all the time, being able to do this quickly is important.

The main ideas of this paper to speed up this process are: intelligent subsampling (since this is just to determine good features and not to actually make business decisions, exact results aren't necessary), materializing partial results to be able to reuse them on similar computations, and maintaining a cache of computed values (since much of the computation will be the same on each iteration of trying new features, with only a few things changed).

Subsampling comes with a fundamental trade-off in terms of speed vs accuracy, but this is easily tunable, and due to the intelligent nature of their subsampling they show that in some cases they can achieve an 89x speedup with only a 1% error, which is pretty impressive.

I am pretty surprise that no one has already done work on this, since besides the transformation materialization, these optimizations seem to be pretty intuitive, and I am somewhat skeptical that they are the first to apply this... I think that these techniques will be influential in 10 years, but whether or not this paper specifically will be, I am not sure.

Review of "Towards a Unified Architecture for in-RDBMS Analytics"

While I am not sure that running your data analytics in your RDBMS (which generally isn't designed for such a thing) is the best way to go about the problem, people are certainly doing it, so making this faster is definitely a valuable problem to tackle.

The main idea of this paper is to note that many of these analytics algorithms can be solved using IGD (incremental gradient descent). By leveraging this common solution mechanism, they can implement a framework which requires only small extensions to be able to run a wide variety of algorithms, making the development of new algorithms and applying them to new RDBMSes much easier. They also make clever use of data layout and parallelism.

Intuitively, it would seem that there should be a trade-off between performance and generality, with more specific implementations being more performant. This doesn't end up to be the case in their analysis, with their more general solution outperforming specific implementations. This may be more of a result of their other techniques; perhaps if they leveraged the techniques used to implement the general framework to fine-tune the individual algorithms, they could achieve even better performance at a loss of generality and ease of development.

Review of "Scaling Distributed Machine Learning with the Parameter Server"

Machine learning is becoming increasingly ubiquitous and complex, running over increasingly large datasets. Being able to run these algorithms (some of which don't lend themselves well to large-scale parallelism) in a distributed fashion quickly is increasingly important, so this is definitely a real problem.

The main idea is to use a centralized set of parameter servers which maintain the shared state of the system, coupled with a large number of worker nodes which actually perform computation. Worker nodes push state updates and pull down state. The system highly leverages the fact that machine learning algorithms are generally convergent and are not significantly disrupted by having stale state, so they don't require synchronous state updates.

One trade-off they discuss is convergence rate vs per-iteration performance. As state becomes more stale, things converge less slowly, but having more stale state allows you to do more computation asynchronously.

Review of "Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary"

This paper aims to present a solution to the issue of maintaining consistency across multiple datacenters. As services become increasingly global, this becomes important to decrease latency to users across the globe, which also ensuring consistency.

The main idea is to separate operations into two categories: Blue (commutative, eventual consistency) and Red (strong consistency). They provide guidelines for how to determine what operations fall into each category, plus a system for forcing more operations to fit into the blue category: decomposing operations into generator and shadow operations, which can turn some non-commuting operators into commuting ones.

This work comes about most likely because the scale of geo-replication that exists now is significantly larger than in the past, and being able to maintain low latency (small consistency overheads) is very important - higher latency has a significant correlation to decreased per-user profits.

There are a number of trade-offs here. Using blue operations only guarantees eventual consistency, which still may come with issues ("eventual consistency is no consistency"), though it provides much higher speed. Breaking down operations into generator/shadow operations may grant much lower latency, but also makes things more difficult to reason about.

I can see this being influential in the future - services are becoming increasingly more global and people expect increasingly lower latencies, but application programmers also want consistency. This seems to provide a good framework for maintaining both of these things simultaneously.

Review of "CRDTs: Consistency without Concurrency Control"

Attempting to balance strong consistency models with low concurrency control overhead is a very important line of research because as systems grow larger our current concurrency control schemes have overheads which are often prohibitively high, but some reduced-consistency schemes make things difficult to reason about for application programmers and result in complex handling logic. Any work to bridge this gap is certainly solving a meaningful problem.

The main idea is to use CRDTs, commutative replicated data types, on which all operations commute, to allow for the construction of data structures without communication: if all operations can be applied in any order, just apply it locally and them disseminate the operation, since eventually it will reach all replicas and we don't mind if it was applied out-of-order. Note that this is still eventual consistency and makes no guarantees about how soon things will be consistent, just that they will eventually reach such a state.

I think this work was different from previous work partly because of the size of systems in today's world; concurrency control schemes which previously worked fine are reaching the limits of their scalability and it is important that we investigate new ways to achieve the same consistency guarantees in more scalable ways.

One trade-off is generality vs. speed; not everything can easily be represented as a CRDT. There is also the trade-off of ease of use; CRDTs are only eventually consistent, and this must be planned for as an application programmer.

I can definitely see this paper being influential moving forward--though I don't see CRDTs in this form being widely used, the ideas are important.

Review of "Coordination Avoidance in Database Systems"

Scalability is hugely important in today's world, and communication/coordination is the bane of scaling. This paper works towards reducing the amount of coordination necessary for maintaining correctness, a very important problem.

The main idea is to analyze transaction sets against application invariants to determine when exactly coordination is necessary, in contrast to traditional database systems which serialize all transactions. By only coordinating when absolutely necessary, many transactions can run independently in parallel.

A trade-off here is complexity vs. speed. It is much easier to reason about transactions as completely serializable, and you don't need to write down all of your invariants, but this will often be worth it in a high performance setting.

This work seems very interesting - I feel that most literature I have seen uses the same concurrency scheme for all transactions, and the idea of predetermining which transactions actually need coordination seems like it will have a lot of practical benefits as systems scale larger and larger. I can definitely see this being influential in 10 years.