Re: Parallelism (Re: Introduction)

From: J. Andrew Rogers (
Date: Thu Sep 08 2005 - 23:48:24 MDT

On 9/8/05 4:55 PM, "Phil Goetz" <> wrote:
> Parallelizing serial algorithms is not that hard.

To the extent it is practical, that is. Sometimes, just decoupling
artificial dependencies does not buy much.

> Distributing serial algorithms so that there is no central
> memory, clock, or administrator is hard.

The real trick for humans when designing these types of things is realizing
that determinism is an illusion and that absolutes do not reasonably exist.
It is not so obvious when talking nano- or femto-second latencies, but when
the communication latencies creep into the high nanosecond or microsecond
range the lie becomes hard to disguise convincingly on current hardware. I
can't remember how many times I've had to explain that you cannot have
geographically distributed ACID transactions that are highly reliable *and*
scalable. But then, I've also had to explain more than once why it is not
possible to guarantee 10ms RTT latency in a transcontinental fiber network
to people who should know better. It is good to see that the education
system is doing its usual fine job. :-)

Letting go of the idea of global state, embracing the idea that time is
local and relative in the transaction graph, and accepting that one can only
speak of correctness in terms of probability is difficult for computer
scientists used to thinking in terms of absolutes and strict determinism.

While it is not too difficult to design a geographically distributed system
that is genuinely decentralized with a high probability of being in a
correct (though not synchronous) state at any point in the system, the
difficult part is defending the system from intentional attacks against the
inherent weak points of such designs without the system becoming too heavy.
This latter issue often tilts real implementations toward locality and
centralization even if the decentralization model is perfectly acceptable in
a theoretical transaction theory kind of sense.

> Conceiving of algorithms that are parallel, asynchronous,
> and error-tolerant from the beginning, and have no
> conceptually equivalent serial algorithm, is very hard.

Heh -- "very hard". Understatement of the year...

J. Andrew Rogers

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:52 MDT