Lambda the Ultimate

The network computer is a stochastic computer in the sense that there's a probability of things failing - there was a lambda calculus mentioned on LtU a while back that deals with such things for reasoning about handling hardware failure. Which moves onto the second point: all hardware computers have that issue (just like none of them actually have unbounded memory), but the probability is higher with the network computer.

The difference that I see is that in the event of RAM failure on a single computer, it is acceptable for the whole system to fail. Whereas it is generally not okay for a network computer to fail if one piece of RAM on one computer fails. So it is really this failure handling that strikes me as different. The rate of partial failure for distributed applications is very high relative to the rate of failure of my laptop, say, so there is a real difference in style.

The difference that I see is that in the event of RAM failure on a single computer, it is acceptable for the whole system to fail.

Not necessarily! ;-)

The rate of partial failure for distributed applications is very high relative to the rate of failure of my laptop, say, so there is a real difference in style.

Except in harsher environments, like space, where pervasive radiation can flip many bits randomly. The above faulty lambda calculus is a step to addressing that at the software level.

The difference that I see is that in the event of RAM failure on a single computer, it is acceptable for the whole system to fail.

Not necessarily! ;-)

Thanks for posting this link -- it's certainly a step in the right direction. However, you are unfairly pushing aside my point. In some of the cases mentioned by the paper -- for example eBay -- it would have been okay to fail the computation entirely had the failure been detected. So for them, total failure of a single system is still an acceptable way to handle RAM or processor failure.

More generally, we allow ourselves the convenient fiction that partial failure of a single computer amounts to total failure of a computation depending on the failing subsystem -- and in the case of RAM or processor failure, it is acceptable to shove the entire OS off the brink. Outside of the space program, programmers don't write code that recovers from RAM failure (RAM striping?) or processor failure -- or even detects these things.

Why is three so special? Because you have a simple majority in every failure scenario?

Thank you for the link.

...you seem to be suggesting a computability perspective which is rather different than the way these issues are usually studied in the field.

The counter-example you give, of many computers with only one performing computation, is a good sign that I am painting with too broad a brush. Distributed systems generally expose failure events to the programmer in a way that non-distributed programs don't, generally because distributed systems aim for high-availability. In an "eventually consistent" storage system, for example, you can't reliably read back what you wrote from storage -- so the storage in your "computer" is stochastic. The metaphorical "tape walking machine" would have probabilistic behaviour in the presence of an eventually consistent paper tape.

It is more usual to take failure into account with distributed systems than with single computers.

You may find my articles on Wikipedia enlightening; Paxos Algorithm and State Machine Approach.

To answer some of your questions:
- A network of computers can compute anything a single computer can compute.
- A network of computers is not more likely to fail.
- You must have more than two computers.

A distributed system must place nodes carefully to avoid correlated failures. If it does so, it can withstand any number and type of failure that is planned for, which is far better than single (even HA) computers. But the price for this resilience is the difficult task of writing software for it.

Algorithms like Paxos and system architectures like the State Machine Approach reduce this complexity to a minimal core component. That component encapsulates all distributed failure cases, freeing application programmers from managing this burden.

Can you explain why I must have more than two computers? Are odd numbers better?

I already read the Paxos article and I'm reading the "State Machine Approach" article right now.

...as even numbers have the chance for a tie when there's a disagreement. But I don't know that democracy is a better algorithm (Minority Report).

This discussion is in danger of becoming off-topic. The subject is huge and many of results are rather counterintuitive (it's a fascinating subject). If anyone can suggest good places for discussion of distributed algorithms, go ahead. Otherwise, unless a PL connection is being explored, I'd recommend taking the discussion offline.