## 4 Impossibility Results
### Generalized Theorem  
A distributed algorithm is an algorithm in which each process is initialized with its local variable values and incident edge parameters; no process has access to any other variables and parameters of the system. The process can communicate only with its neighboring processes (depending on the overlay, if any) along incident edges.  
For any problem \(X\) which requires a distributed algorithm to solve it, there are two characteristic events. \(e_{h}^{x_{h}}\) is an internal event at which process \(p_{h}\) completes its calculation of local variable values required to solve the problem after communicating with other processes in a distributed manner. \(e_{i}^{\vartheta}\) is an event at which process \(p_{i}\) determines that a global solution to the problem has been attained. When \(h\
eq i\), in order that \(p_{i}\) at \(e_{i}^{\vartheta}\) can detect that problem \(X\) has been solved, there needs to be an actual causal path from \(e_{h}^{x_{h}}\) to \(e_{i}^{y_{h}}\) (\(\forall h\) and where \(y_{h}\leq\hat{y}\)) that is also detectable by \(p_{i}\), i.e., \(\bigwedge_{h}e_{h}^{x_{h}}\to e_{i}^{y_{h}}|_{E}=e_{h}^{x_{h}}\to e_{i}^{y_{h}} |_{F}=1\).  
* **Safety specification of \(X\)** states the correctness conditions of a solution to \(X\), as captured by a global formula \(\Phi_{X}\).
* **Liveness (or termination) specification of \(X\)** states that some process should eventually be able to detect that a global formula \(\Phi_{X}\) has become true.  
**Theorem 12**.: _In a system with even one Byzantine process, when a process \(p_{i}\) has to detect that a problem \(X\) has been locally solved at events \(e_{h}^{x_{h}}\), the distributed \(X\) problem is subject to the same limitations (exposure to false positives and false negatives) as the CD problem, resulting in safety and liveness violations._  
**Proof.** Solving \(X\) requires satisfying  
\[\Phi_{X}(\varepsilon_{i}^{\vartheta})\stackrel{{ def}}{{=}}\bigwedge_ {h}(\varepsilon_{h}^{x_{h}}\to e_{i}^{y_{h}}|_{E}=\varepsilon_{h}^{x_{h}}\to e_ {i}^{y_{h}}|_{F}=1)\wedge\phi(e_{i}^{\vartheta}),\]  
where \(e_{h}^{x_{h}}\) is an event where the local variables at the process take values that specify that the local computation has completed at \(p_{h}\), \((\forall h)\,y_{h}\leq\vartheta\), \(\phi\) is a predicate capturing the other requirements of the \(X\) problem besides the first predicate, \(e_{i}^{\vartheta}\) is an event where the global formula \(\Phi_{X}\) is detected as true, and \(\to\) is defined on algorithm messages for solving \(X\).  
As \(e_{h}^{x_{h}}\) is an internal event, from Theorem 1 for the CD problem, detecting \(e_{h}^{x_{h}}\to e_{i}^{y_{h}}\) is susceptible to false positives and false negatives. Thus, it cannot be guaranteed that the predicate \(e_{h}^{x_{h}}\to e_{i}^{y_{h}}|_{E}=e_{h}^{x_{h}}\to e_{i}^{y_{h}}|_{F}\) in the formula \(\Phi_{X}\) can be satisfied. Hence, \(X\) cannot be solved.  
A false positive of the CD problem is a safety violation--there is no real satisfaction of the global formula \(\Phi_{X}\)--in the \(X\) problem. A false negative of the CD problem is a liveness violation--the global formula \(\Phi_{X}\) that becomes true is never detected (because the process did not disclose its local value that could satisfy \(\Phi_{X}\))--in the \(X\) problem.