© 2003-2006 David Moles
Chrononautic Log |
|
Main |
|
Causality violation as a technical term in distributed systems programming4 o'clock, May 11, 2005Who knew? A causality violation occurs when a message ordering problem results in one host taking an action based on information that another host has not yet received. In this case P2 is trying to invoke a method on P1, because P2 thinks that P1 has Obj. In designing systems, we assume that any action a host takes may be affected by any message it has previously received. As a result, we would consider the situation above to be a potential causality violation, even if the message from P2 to P1 turned out to be completely independent of the messages that it received. Colloquially, we don't distinguish between potential causality violations and causality violations that have real consequences. Instead we call them both causality violations — even if the messages turn out to be independent. (Gregory Kesden, lecture notes for CS 15-612, Distributed Systems, Carnegie-Mellon, Lecture 3.) It gets funnier: Student Question: Couldn’t we just make it the responsibility of the invoking process to check with the target process first, before trying to invoke the method on the remote object? Answer: I’m glad you asked. This is an outstanding opportunity to mention the time-honored distrbuted systems principle, “It is easier to move a problem in a distributed system than it is to actually fix it.” . . . This is also a good opportunity to mention another famous principle in the design of distributed systems, the ostrich principle. The ostrich is famous for burying its head in the sand. This technique is also frequently used in distributed systems. Sometimes particularly unlikely or obscure problems are allowed to remain in a design. This is particularly true if the cost of the resulting failure is low enough. The bottom line is that implementing a perfect distributed system may involve additional overhead that, in the aggregate, will result in a greater loss in productivity than the rare occurance of an unlikely error state. There has got to be a way to use those ideas to deal with spacetime causality violation in my gonzo space opera. [Side note: “Planet of the Amazon Women” (excerpt here), my first published story set in the gonzo space opera’s universe, will be going live on Strange Horizons next week. I like to think of it as: Ammonite and “Biographical Notes to ‘A Discourse on the Nature of Causality, with Air-Planes’ by Benjamin Rosenbaum” go out on double-date with Roadside Picnic and “Hinterlands.”] |
Comments |
|
But the distributed system situation isn't even vaguely a causality violation. Such a causality violation would arise if a host is taking an action based on information that it hasn't received yet. I seem to recall reading in a paper by Deutsch an analysis of quantum computation with information flows into the past. Unfortunately, my folders full of interesting papers are packed away at the moment. I couldn't find the Deutsch paper online, but I did find http://dabacon.org/pontiff/?p=529 which looks interesting. |
|
Obviously the CS folks are being a little looser with the terms. :) Maybe causality violation request would be closer to the truth? The Bacon paper looks interesting — I’ll have to check it out. |
|
A fairly well-known discussion of time travel and computation is Hans Moravec's, here. |
I read:
'This is particularly true if the cost of the resulting failure is low enough.'
as:
'This is particularly true if the perceived cost of the resulting failure is low enough.'
or:
'This is particularly true if one can get away with convincing others that the cost of the resulting failure is low enough.'
I'm reminded of a rant by Shriram Krishnamurthi in the 'Worse is Better' panel, starting from 24:45.
(Is there no way to address a subsection of an audio file via URL?)