Deploying a team of autonomous robots, operating collaboratively towards a common objective within dynamic environments, has the potential to improve the system efficiency across several fields. This paper proposes a distributed comprehensive framework enabling a networked multi-robot system to serve time-varying requests arising from different locations within the environment in a distributed and safe manner, i.e., by guaranteeing no collisions with possible obstacles and preserving connectivity among the robots. To this aim, a two-layer architecture is proposed where the top layer is in charge of distributively assigning new service requests to the robots by resorting to an auction-based algorithm, while the bottom layer is in charge of safely navigating the environment to serve the assigned requests by relying on Control Barrier Functions. However, the presence of connectivity constraints might affect the number of service requests that the multi-robot system can handle simultaneously and might lead to deadlock situations where robots cannot reach the designated locations due to loss of network connectivity. Hence, a distributed strategy based on consensus algorithms to detect and solve deadlocks in a distributed fashion is proposed. The completeness of the approach is proved. Simulation results in an agricultural setting and real-world laboratory experiments are provided to validate the effectiveness of the proposed approach.