Paper introduces several forms of parallel computation, randomizing algorithms, matching algorithms, does mathematical models of some of this, and describes the actual algorithms as step-by-step English and pseudocode (no math required). Tagged it CompSci, not formal methods, for that reason.
Pretty cool. This contradicts a recent assertion made by ESR http://esr.ibiblio.org/?p=8223
That assertion inspired my search. When people say it’s impossible, I start DuckDuckGoing for terms that might lead to the counter-example. I just typed each thing he said was sequential into search with “parallel” next to it. Found a few things. Here’s another found from that search.
As side effect, you can tell he wasn’t fact checking those statements before publishing them. ;)