Decomposing an Algorithm into Local Transformations/Perturbations
there are several ways to measure this "local vs global" decomposition dichotomy of problems which does show up in a wide variety of CS contexts.


how many local minima there are versus a global minimum for optimization problems. if there are many local minima it is harder to find the global minimum. roughly this is also a measure of how effective greedy algorithms are on that problem.
algorithmic speedup due to parallelism. this metric is sensitive to both the problem and the algorithm chosen. for example the problem may not be very "decomposable", or a problem may be decomposable but it is not solved with a most efficient algorithm. for more decomposable problems, algorithmic speedup is nearly linear in increasing processors. for less decomposable problems, it is more an asymptotic sub-linear relationship.
communication overhead of parallel processing. the decomposability is known as "granularity". for problems that are not as granular, there is more communication required between separate parallel threads or processors. problems with very "fine" granularity ie not requiring much or any communication between processors are called embarrassingly parallel.
NC is the class of efficiently parallelizable algorithms. NC=?P is an open question. ie in short are all P-time algorithm efficiently parallelizable, or not?


one paper that does attempt to study these concepts more formally/systematically within the context of parallel computing is Landscape of parallel computing, the view from Berkeley. see eg "7+ dwarves" for the basic algorithmic patterns that seem to appear in practice and commentary on their decomposability wrt parallelism.

another influential researcher recently looking into the inherent limits/ceilings/gains of parallelism in CPU design (ie multicore) which relates to the general decomposability of everyday running code is Esmaeilzadeh.