Logic-based languages, such as Datalog and Answer Set Programming, have been recently put forward as a data-centric model to efectively specify and implement network services and protocols, seeing them as dynamic systems of distributed computational nodes. In such systems, which we call Communicating Datalog Programs (CDPs), each node evolves an internal database, exchanges data with other nodes of the network via channels, and may incorporate fresh data from the external world. A rigorous, comprehensive characterization of the decidability and complexity of verification of temporal properties in CDPs is still missing. In this talk we analyze the diferent assumptions characterizing the problem space, and then discuss several diferent variants of the problem. In particular, for the significant case where the number of nodes in the network is fixed, we delineate the decidability frontier of verification and provide tight complexity bounds. The presented results are based on joint work with C. Aiswarya, Francesco Di Cosmo, Jorge Lobo, and Marco Montali.