Vision: Distribution of Uncertainty

Adam Rifkin, http://www.ifindkarma.com/attic/phd/

(work in progress)

The Observation: Reality is Probabilistic

Distributed system theory talks of absolute correctness. But, decision making in asynchronous distributed networks is fundamentally unsolvable [see for example, Nancy Lynch's work].

Furthermore, what we typically have in networks is partial knowledge [see for example, Eve Schooler's work].

What the world needs are tools for reasoning about probable distribution behavior -- probabilistic convergence, probabilistic consensus, probabilistic mutual exclusion, probabilistic diffusion of uncertainty...

The Vision: Uncertainty Can Be Distributed

The forward vision: We need distributed system algorithms based on partial knowledge and probabilistic confidence, because that is all we can rely on in the global Internet. These can help us reason more realistically about problems such as group membership, netnews broadcast, and eventual delivery of bits.

The reverse vision: We need to apply probabilistic consistency arguments in reasoning about such distributed algorithms because that's all we guarantee in real life. These can help us reason more realistically about problems such as groupware, coda, cuban cooperation, and consensus requirements.

As an example, consider the overbooking of flights. In this and many other real-world examples, mutual exclusions to the same resources aren't actually 100%. But the real-world is not brittle; we can compensate for mutex violations such as overbooking.

The contribution for the forward vision is probability analysis for standard applications. The contribution for the reverse vision is API exposure. For example, when making reservations there might be a lockSeat method. Presently, the API is absolute (yes or no). What we would like is probabilistic consensus that may have failure modes (for example, for maximum timeout).

The abstraction is to expose the risk *above* the API. To break the illusion [for example, see Bayou and Coda]. Perhaps a mathematical abstraction using entropy, half-life, or disappearing ink. This could be in line with the whole paradigm of risk management, with informational entropy as something fluid.

Last modified: Tue Mar 10 15:51:08 PST 1998