Coordinated Attack Problem Different Requirements

Question

There is a famous Coordinated Attack Problem. Let define a simple message-passing system $S$ with requirements

• Uniform Agreement: No two processes decide dierently.
• Validity:

(a) If all processes start with 0, then no process decides 1.

(b) If all processes start with 1, and there are no failures, then no process decides 0.

• Termination: All nonfaulty processes eventually decide.

System $S$ consisting of two processes $p$ and $q$ connected by a bidirectional communication link such that (a) processes proceed in synchronous rounds, (b) processes do not fail, and (c) any number of messages can be lost.

It's well known that system $S$ cannot satisfy all above requirements, therefore let consider different requirements.

• Weak Termination: If there are no failures, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

All processes eventually decide when there is no failures, so when inputs are $0$ and $0$ and no failures, both generals decide $0$. By dropping one of the message I cannot ensure the termination, therefore the standard reasoning doesn't work here.

• Unanimous Termination: If any process decides, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

It's also very tricky requirement. Assume the both inputs are $0$ and $0$ and no failures than both decide $0$, let drop the message from $P_1$ to $P_0$, regarding to $P_1$ it is the undistinguishable execution, therefore $P_1$ still decide $0$ and according to unanimous termination, someday $P_0$ will decide the same $0$ according to agreement, noq according to the standard schema, change the input of $P_0$ to $1$ and this undistinguishable execution to $P_0$, so the same agreement and so forth we reach a contradiction, no solution.

I am sure if it's correct. In addition the case with weak termination I don't know how to solve, even if it's solvable.

Answer 1

This looks like the Byzantine generals problem. There's a lot written on that subject; I suggest you start by reading the available literature and material on that subject.

I'm not entirely clear on you mean by "solvable in system S" (system S says processes don't fail, but the weak termination condition refers to failures, so what's going on there?), so I can't confidently answer that part of your question.

There's an obvious algorithm for the case of two parties:

• Each party continually broadcasts a message saying "my input is X" (fill in X with whatever its input bit is).

• Whenever you receive one of those messages, you respond with an acknowledgement describing your input, what you received from the other party, and what you will output; then you immediately produce the appropriate output and halt.

• If you receive an acknowledgement message and have not halted yet, then produce the appropriate output and halt.

It looks like this satisfies all three of your requirements, including weak termination, assuming that messages can be dropped/lost but are not modified in transit and no forged/fake messages are inserted by the network.