Consider an asynchronous and unreliable distributed system. Each node has a value. Suppose that p and q are two neighbor nodes of the system (p_val and q_val are the values of p and q respectively). p and q want to compute the average of their values and change their values to the average. If one node changes its value to the average, the other node should change as well. This problem is called distributed reliable pairwise average.
Question: Is it possible to implement distributed reliable pairwise average? or it is impossible?
I think that it is impossible. Please consider the following simple protocol:
- Each node sends its value to the other node.
- Each node after receiving the value of the other node changes its value to the average.
Suppose that p receives q_val but q doesn't receive p_val due to occurring a link-failure, so if p changes its value to the average, it is not correct. It seems that they need to send acknowledgments. If they start to send acknowledgments, they enter an endless loop.