## 1 Introduction
This problem requires enforcing that only a single process is in control (in execution) of a specific piece of code called the _critical section_ at any point in time. 2. Global snapshot recording (GSR). This problem requires recording the states of distributed processes and communication channels in a consistent manner so that no process records an effect whose cause has not been recorded at other processes. More specifically, no message is recorded as received by a receiving process in its recorded state if the corresponding message sender process has not recorded that message as sent in its recorded state. 3. Termination detection (TD). This problem requires determining the occurrence of a consistent global state such that all processes have gone from an _active_ to _passive_ (locally terminated) state and there are no messages in transit whose receipt would cause the recipient to transition from a _passive_ to _active_ state. 4. Distributed deadlock detection (DD). When a process requests resources, it blocks on other processes. A process can block in the single-request model, OR request model, AND request model, or the AND-OR request model. Distributed deadlock detection requires determining a consistent global state in which the processes are blocked on each other in a cycle or more generally a knot topology, for the above request models. 5. Distributed predicate detection (PD). This problem requires detecting a consistent global state in which the variables local to different processes satisfy a predicate \(\phi\). The predicate may be an arbitrary relational predicate such as \(x_{i}+y_{j}>10\) or a restricted conjunctive predicate such as \(x_{i}=3\wedge y_{j}=8\), where \(x_{i}\) and \(y_{j}\) are variables local to processes \(p_{i}\) and \(p_{j}\), respectively. (f) Causal ordering of messages (CO). This problem requires enforcing that if \(s_{1}\to s_{2}\) for send events \(s_{1}\) and \(s_{2}\), then for all common destinations of the corresponding messages \(m_{1}\) and \(m_{2}\), \(m_{2}\) is not delivered before \(m_{1}\). 2. Distributed graph problems. 1. Spanning tree construction (ST). A spanning tree of a graph \(G=(V,L)\) where \(V\) is the set of nodes and \(L\) is the set of edges is an acyclic sub-graph \(ST=(V,L^{\prime})\) where \(|L^{\prime}|=|V|-1\). The ST construction problem requires identifying edges of a graph as belonging to \(L^{\prime}\). 2. Distributed minimum spanning tree construction (MST). In a weighted graph, a MST is a spanning tree having a minimum sum of edge weights among all spanning trees of the graph. The MST construction problem requires identifying edges of a graph as belonging to the MST. 3. All-all shortest paths construction (AASP). Given a weighted graph, this problem requires identifying the shortest length paths from each node to each other node. 4. Maximal independent set construction (MIS). An MIS of a graph \(G=(V,L)\) is a subset \(V^{\prime}\subseteq V\) such that for all \(u,v\in V^{\prime}\), \((u,v)\
ot\in L\) and \(\
ot\exists w\in V\setminus V^{\prime}\) such that \(V^{\prime}\cup\{w\}\) is an MIS. The MIS construction problem requires identifying the nodes in an MIS. Solving these problems using distributed algorithms requires the determination of the existence of a causal path between two events \(e\) and \(e^{\prime}\) where \(e\) is an event where a process finishes setting its local variables as a result of the distributed algorithm and \(e^{\prime}\) is an event where an(other) process detects the global completion of the distributed algorithm in order to use/further process the result of the distributed algorithm. The determination of the existence of such a causal path in the execution in a Byzantine system is not solvable as shown in [4] and hence, these problems are also not solvable. Finally, we generalize our results and show that any problem which uses a distributed algorithm is subject to at least the same limitations as the CD problem in a Byzantine failure-prone system.