Maps are a good representation of the information state of a network-centric multi-vehicle system that tracks targets. The map service uses information pushed to it by sensors to compute a probabilistic map, i.e., the conditional density of the location of targets given all the past observations. We have designed the map service to be distributed, i.e. the entities participating in the map service divide the probabilistic mapping task amongst themselves, so that it scales well to large operating environments. We present an architecture and algorithms for implementing such a distributed map service. We also put forward a definition of correctness that relates the distributed conditional density computation to a centralized computation. We then show in the context of a random walk model for the target motion that correctness can be preserved provided the time scales of communication are faster than the time scales of actor motion. Finally, we describe our prototype implementation based on the above ideas.