## 1 Introduction  
This paper considers the solvability of several fundamental state observation, synchronization, and graph computation problems in asynchronous message-passing distributed systems in the presence of Byzantine processes using distributed algorithms. In a _distributed algorithm_, each process has access only to its local variables and incident edge parameters (such as edge weight, edge cost, edge delay); its local variables are not accessible to any other process/node. We show the impossibility of solving these fundamental problems by proving that they require a solution to the causality determination problem [1, 2, 3], which has been shown to be unsolvable in asynchronous message-passing distributed systems [4]. In a seminal paper, [PERSON] formulated the \"happened before\" or the causality relation, denoted \(\rightarrow\), between events in an asynchronous distributed system [5]. Given two events \(e\) and \(e^{\prime}\), the _causality determination_ (CD) problem asks to determine whether \(e\to e^{\prime}\). Examples of events from real-world applications include users making bids in an online auction, physical parameters like temperature and pH value reaching certain thresholds in a chemical manufacturing plant, and program variable values in a parallel program satisfying an application-specific predicate. In computing systems, applications of causality determination include determining consistent recovery points in distributed databases, deadlock detection, termination detection, distributed predicate detection, distributed debugging and monitoring, and the detection of race conditions and other synchronization errors [6]. It was shown in [4] that it is impossible to determine the causality or the happens before relation \(\rightarrow\) between two events \(e1\) and \(e2\) when there is even a single Byzantine process in an asynchronous message-passing distributed system. False negativesand/or false positives are possible. A false negative means that \(e\to e^{\prime}\) whereas \(e\
ot\to e^{\prime}\) is perceived/detected. A false positive means that \(e\
ot\to e^{\prime}\) whereas \(e\to e^{\prime}\) is detected. Specifically, the following results were shown. 1. It is impossible to determine causality \(e\to e^{\prime}\) between events in the presence of even a single Byzantine process when \(e\) is a communication (send or receive) event and processes communicate by unicasting. This is because both false positives and false negatives can occur. 2. A similar impossibility result when processes communicate by broadcasting was shown. In this case, false positives cannot occur but false negatives can occur. 3. A similar impossibility result to the unicasting case was shown where processes communicate by multicasting. Both false positives and false negatives can occur. We show that many problems in distributed computing in the presence of Byzantine processes, which might be locally solved at event(s) at individual processes but require another process to detect the occurrence of such event(s), are not solvable in asynchronous message-passing systems by showing that solving them requires solving the CD problem. This also establishes the CD problem as a fundamental first-class problem as all the other problems for which we show impossibility results inherently require causality determination between a pair of events. The occurrence of false negatives (false positives) in the CD problem manifests as the occurrence of liveness and safety violations in these problems. A direct implication of our results is that none of the many algorithms proposed to solve these problems over the past five decades for failure-free systems/crash failures can be adapted for Byzantine failures. We consider the following problems; the reader is referred to any standard textbook such as [6; 7; 8; 9; 10] for a centralized source of algorithms to solve these problems in asynchronous message-passing failure-free systems/graphs. 1. Synchronization and state observation problems. 1. Distributed mutual exclusion (ME).