For massively distributed and parallel algorithms, a core part of the computer science is based around space decomposition data structures. If your algorithm is not based on a space decomposition structure, it won't linearly parallelize across a vast number of cores. When I say some algorithm won't distribute or parallelize, this is what I am usually (but not always) looking at.

Space decomposition structures take a metric space and decompose it using an invariant space partitioning function. The partition points are fixed regardless of data distribution, the only decision process is when to apply the partitioning function.

The two well-known examples in literature are quad-trees and distributed hash tables. These are both very simple, narrow examples of space decomposition structures in a universe of possible metric spaces and possible partitioning functions. Many parallel data problems can't be made to fit into the simple space decomposition structures computer scientists are familiar with.

When massively parallel machinery is the foundational assumption, every computational structure must be represented in terms of space decomposition primitives. Right now, most computer scientists treat space decomposition structures as dumb data buckets and are largely oblivious to their expressiveness. Most published parallel algorithm computer science is based on computational structures that will only sort of parallelize on sufficiently small systems.

> "Right now, most computer scientists treat space decomposition structures as dumb data buckets and are largely oblivious to their expressiveness."

This is very interesting. Is there an example of the expressiveness of spatial decomposition you could share?

Are you referring to space-filling curves?

Not really, though there is a natural relationship between partitioning functions and space-filling curves.