[nyan_sandwich]

MCMC isn't strictly serial; you can run multiple chains in parallel and get decent results (provided your break in period isn't too big), and this is commonly done for multicore.

The "all the data" problem is interesting. It seems solvable if each node summarizes the likelihood function for part of the data. I'll have to read the paper and see if that's what they did.

[tristanz]

All of it's definitely solvable, it's just harder than lots of Monte Carlo problems that are embarrassingly parallel.