No, I am referring to the set of problems related to graph partitioning.

This is essentially the same underlying problem that is the source of why distributed NoSQL databases do not support join operations. In the case of NoSQL databases, they simply do not support joins because it is not a core operations. (Technically you can still do a join, it just has terrible scaling characteristics.)

The fundamental operation of graph databases are relational joins by another name, which means that graph databases have the same limitation on distribution that distributed NoSQL databases have on joins. However, unlike NoSQL databases it is their primary operation so they can't just not support it. Consequently, the only way to have a "graph database" that is massively distributable is to solve the same problem that prevents distributed databases from supporting joins.

There are several distributed triple stores (triple stores are a specialised graph store).

http://4store.org http://virtuoso.openlinksw.com/ http://www.systap.com/bigdata.htm

There's a paper on 4store here: http://4store.org/publications/harris-ssws09.pdf

I've been working on the graph partitioning issues for distirbuted graphdbs for a while (my own pet project that my brain won't let me give up on) but it's been from the perspective of someone who's not been keeping up to date with the Comp Sci literature. Have you got any suggestions for canonical papers from the last decade or so, for the state of the art?

There has not been much that is both new and interesting in the graph partitioning literature in a long time. What you already know is probably not too far off from what is in the current literature. The literature on this topic has been stagnant for years.

Solutions to the graph partitioning problem exist and among people doing high-end graph analytics this has been rumored for years now. It just is not published and people that know how it is done are slathered in NDAs. I know of two different (related) algorithms for parallelizing graph analysis. IBM Research currently has the most advanced algorithms for graph analysis and they disclose very little about how they work.

Worth a re-read: http://codahale.com/you-cant-sacrifice-partition-tolerance/

Thank you, this is really great to show AP or CP but never CA and call it distributed.

See https://speakerdeck.com/u/okram/p/titan-the-rise-of-big-grap...

Thank you, this shows that for the one you want, the choice is in the backend.