My concern was that I saw the blog did the run on real life big(actually big) data and outperform everything on the market. This got me thinking, are we still not there on the problem size/computing power curve so as to justify use of distributed computing?
Of course distributed makes sense in a lot of places specially web and where problem is embarrassingly parallel but running graph algos is a bug chunk of the market and it seems for most firms a laptop will do.
Again, thanks for sharing.
I'd also wager that those Spark, GraphLab, or Naiad programs would be far from optimal, by at least an order of magnitude. My ideal would be to see someone attack the distributed graph processing problem with the same eye for systems performance issues that the TritonSort folks brought to the distributed sort problem [3] and MapReduce [4].
[1] http://law.di.unimi.it/webdata/twitter-2010/
[2] http://law.di.unimi.it/webdata/uk-2007-05/
I fantasize about this work inspiring a competition like the sort benchmark [2], but for single-threaded graph algorithms. Not only would this encourage people to develop usable single-threaded implementations, but it have the side effect of increasing the COST for all distributed implementations....
As for providing scalability break points, I think this work goes some of the way, but doesn't take into account the fact that the input data for a particular real-world computation might not reside in a conveniently-compressed format on a local SSD. Extracting the Common Crawl from an HDFS cluster just to replicate the blog post's experiments could take much longer than the computation itself; extracting the social graph from Facebook's Tao [3] to do offline processing might be similarly non-trivial. Academic experiments don't typically take this cost into account, but recent work like Musketeer [4] has started to consider it, and even offer ways to automate the system choice problem.
[1] https://www.usenix.org/conference/osdi12/technical-sessions/...
[2] http://www.sortbenchmark.org/
[3] https://www.usenix.org/conference/atc13/technical-sessions/p...
[4] http://www.cl.cam.ac.uk/research/srg/netos/camsas/musketeer/
What these posts rail against is a tendency (post-MapReduce/Hadoop) to motivate and evaluate distributed systems solely in terms of their batch performance. This is a particularly common problem in graph processing research, where 2008-era general-purpose systems (i.e. Hadoop) have terrible performance, and so provide a straw-man baseline that a reasonably competent grad student should have had no difficulty in outperforming.
"Does my new system outperform a single thread?" seems like a proper hypothesis to test for a distributed system that claims only a performance motivation. Instead our grad student finds that there is a long list of peer-reviewed systems to compare against, and doing that should be enough, right? It would be fine if those systems had been tested against the first hypothesis, but in most cases they have not, so the new system can be much worse than a single thread (for a small set of benchmarks) and this will go undetected. The COST work is a remedy for this issue.
To return to your original question, I do think that distributed systems are good for some things. First, the OP concerns running graph algorithms on genuinely big data: 128 billion edges, and 3.5 billion vertices. A distributed system should be able to outperform Frank's laptop on that graph, and hopefully this post will encourage developers of new systems to aim higher and evaluate their systems on this scale of data.
The second is that distributed systems offer far more than pure batch performance. For example, geo-distribution is critical to providing a good user experience in web properties; and serving interactive queries with low latency and high availability is a particular interest of mine. We touched on the first part in the Naiad paper [1], and I expect this will become especially important for inference in online learning systems [2]. Hopefully the COST work will force the authors of these systems to try harder in their implementation, and we will all benefit as a result.
[1] http://dl.acm.org/citation.cfm?id=2522738
[2] http://www.cidrdb.org/cidr2015/Papers/CIDR15_Paper19u.pdf