On Knowledge and Communication Complexity in Distributed Systems

This paper contributes to exploring the connection between epistemic knowledge and communication complexity in distributed systems. We focus on Action Models, a well-known variant of dynamic epistemic logic, which allows to cleanly separate the state of knowledge of the processes and its update due to communication actions: Exactly like the set of possible global states, the possible actions are described by means of a Kripke model that specifies which communication actions are indistinguishable for which process. We first show that the number of connected components in the action model results in a lower bound for communication complexity. We then apply this result, in the restricted setting of a two processor system, for determining communication complexity lower bounds for solving a distributed computing problem \(\mathcal {P}\): We first determine some properties of the action model corresponding to any given protocol that solves \(\mathcal {P}\), and then use our action model communication complexity lower bounds. Finally, we demonstrate our approach by applying it to synchronous distributed function computation and to a simple instance of consensus in directed dynamic networks.