Re: Reliable Web Services

Cutler, Roger (RogerCutler) wrote,
> However, there are clear problems that I think people are calling the
> "two army" problem (why two armies I have been unable to determine).

It's from Lamport et al.'s 1982 ACM TOPLAS paper "Byzantine Generals 
Problem",

  http://makeashorterlink.com/?Z46461EB2

Details of the impossibility proof for asynchronous systems can be found 
in Fischer et al., "Impossibility of Distributed Consensus with one 
Faulty Process",

  http://makeashorterlink.com/?Q4B422EB2

(unfortunately you'll need an ACM Digital Library subscrption to get the 
full text of these)

> Would the situation be changed materially if the spec were changed so
> that A, at the time of "giving up", sent a "last message" to B
> saying, stated informally, "I've been trying to send you a message
> with ID xxx and I have not gotten an ack.  I'm giving up now.  If in
> fact you got the message, be warned that I don't know it.  Here is
> some contact information in case you want to try to explore this
> situation further"? I believe that this extension would address some
> of the failure scenarios but not others.

How does this help? This message could be lost too.

Or, to put it another way, if you're able to make strong delivery 
guarantees for the "I'm giving up" message, there's no obvious reason 
why you couldn't have made the same strong delivery guarantees for the 
earlier non-failure messages, in which case the "I'm giving up" message 
would be irrelevant.

Cheers,


Miles

Received on Thursday, 12 December 2002 03:16:55 UTC