Implementing reliable pairwise average in distributed systems

Question

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:

1. Each node sends its value to the other node.
2. 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.

Answer 1

Full reliability is simply not possible in (distributed) systems; at some point of fractional system failure you reach a level where system state and/or data is no longer recoverable. You should consider that this is dependent not only on node failure, but also on data distortion (bits might flip as they travel across the network, etc.). As a result, you can reach very high levels of certainty about correctness but it's very difficult if not impossible to guarantee it.

One of the most well known examples of this is the Byzantine Generals/Byzantine Fault problem, which deals with consensus in networks (https://en.wikipedia.org/wiki/Byzantine_fault).