## 3 The Causality Determination Problem Formulation  
The problem formulation in this section is based on [4]. An algorithm to solve the causality determination problem collects the execution history of each process in the system and derives causal relations from it. Let \(E_{i}\) denote the _actual_ execution history at \(p_{i}\) and let \(E=\bigcup_{i}\{E_{i}\}\). For any causality determination algorithm, let \(F_{i}\) be the execution history at \(p_{i}\) as perceived and collected by the algorithm and let \(F=\bigcup_{i}\{F_{i}\}\). \(F\) thus denotes the execution history as collected by the algorithm. Let \(T(E)\) and \(T(F)\) denote the sets of all events in \(E\) and \(F\), respectively. Analogous to Definition 1, we can define the _happened before_ relation on \(T(F)\) instead of on \(T(E)\). Let \(e1\to e2|_{E}\) and \(e1\to e2|_{F}\) be the evaluation (1 (_true_) or 0 (_false_)) of \(e1\to e2\) using \(E\) and \(F\), respectively. Byzantine processes may corrupt the collection of \(F\) to make it different from \(E\). We assume that a correct process \(p_{i}\) needs to determine whether \(e_{h}^{x}\to e_{i}^{*}\) holds and \(e_{i}^{*}\) is an event in \(T(E)\). If \(e_{h}^{x}\
ot\in T(E)\), then \(e_{h}^{x}\to e_{i}^{*}|_{E}\) evaluates to _false_. If \(e_{h}^{x}\
ot\in T(F)\) (or \(e_{i}^{*}\
ot\in T(F)\)), then \(e_{h}^{x}\to e_{i}^{*}|_{F}\) evaluates to _false_. We assume an oracle that is used for determining the correctness of the causality determination algorithm; this oracle has access to \(E\), which can be any execution history such that \(T(E)\supseteq CP(e_{i}^{*})\). Byzantine processes may collude as follows. 1. To delete \(e_{h}^{x}\) from \(F_{h}\) or in general, record \(F\) as any alteration of \(E\) such that \(e_{h}^{x}\to e_{i}^{*}|_{F}=0\), while \(e_{h}^{x}\to e_{i}^{*}|_{E}=1\); or
2. To add a fake event \(e_{h}^{x}\) in \(F_{h}\) or in general, record \(F\) as any alteration of \(E\) such that \(e_{h}^{x}\to e_{i}^{*}|_{F}=1\), while \(e_{h}^{x}\to e_{i}^{*}|_{E}=0\). Without loss of generality, we have that \(e_{h}^{x}\in T(E)\cup T(F)\). Note that \(e_{h}^{x}\) belongs to \(T(F)\setminus T(E)\) when it is a fake event in \(F\). Definition 3: The causality determination problem \(CD(E,F,e_{i}^{*})\) for any event \(e_{i}^{*}\in T(E)\) at a correct process \(p_{i}\) is to devise an algorithm to collect the execution history \(E\) as \(F\) at \(p_{i}\) such that \(valid(F)=1\), where  
\[valid(F)=\left\{ \begin{array}{ll}1&\text{if }\forall e_{h}^{x},e_{h}^{x} \to e_{i}^{*}|_{E}=e_{h}^{x}\to e_{i}^{*}|_{F}\\ 0&\text{otherwise}\end{array} \right.\]  
When one is returned, the algorithm output matches the actual truth and solves \(CD\) correctly. Thus, returning one indicates that the problem has been solved correctly by the algorithm using \(F\). A value of 0 is returned if either  
* \(\exists e_{h}^{x}\) such that \(e_{h}^{x}\to e_{i}^{*}|_{E}=1\wedge e_{h}^{x}\to e_{i}^{*}|_{F}=0\) (denoting a false negative, abbreviated \(FN\)); or
* \(\exists e_{h}^{x}\) such that \(e_{h}^{x}\to e_{i}^{*}|_{E}=0\wedge e_{h}^{x}\to e_{i}^{*}|_{F}=1\) (denoting a false positive, abbreviated \(FP\)). To determine whether \(CD\) is solved correctly, we have to evaluate \(\forall e_{h}^{x},e_{h}^{x}\to e_{i}^{*}|_{E}=e_{h}^{x}\to e_{i}^{*}|_{F}\) even if \(e_{h}^{x}\in T(F)\setminus T(E)\) because such an \(e_{h}^{x}\) is recorded by the algorithm as part of \(F\). The key observation we make is that in \(CD\), a single Byzantine process \(p_{b}\) can cause \(F\) (as recorded by the algorithm) to be different from \(E\). * An FN arises because a send-receive event pair \((e_{f}^{u},e_{g}^{v})\) of \(E\) in a causal chain from \(e_{h}^{x}\) to \(e_{i}^{v}\) is missing as per \(F\). In addition, an FN may arise if \(e_{h}^{x}\) is a receive event or an internal event, \(e_{h}^{x}\in E\setminus F\). * An FP arises because a non-existent send-receive message pair \((e_{f}^{u},e_{g}^{v})\) in \(E\) appears in a causal chain from \(e_{h}^{x}\) to \(e_{i}^{*}\) as per \(F\).