How can the gravitational n-body problem be solved numerically in parallel?
Is precision-complexity tradeoff possible?
How does precision influence the quality of the model?
Both methods make use of a tree data structure where nodes essentially only interact with their nearest neighbors at each level of the tree; you can think of splitting the tree between the set of processes at a sufficient depth, and then having them cooperate only at the highest levels.
You can find a recent paper discussing FMM on petascale machines here.
Look at the fast multipole method. It is highly scalable and $O(n)$. It allows trading off between precision and cost. Here's an example where it is run at 42 Tflops on a GPU cluster.
As an alternative source, you could also look at mesh-based Ewald-like methods. The genesis of the "particle mesh" methods (such as PPPM and smoothed particle mesh Ewald) lies in simulations of galaxies for astrophysics; the connection to charges was an unintentional side effect (that just happened to eventually overtake the original usage).
More recently, there has also been some literature on multilevel summation methods which are akin in spirit to fast multipole methods and the Barnes-Hut, but may offer advantages in different circumstances (more general and flexible geometries, some efficiency gains, etc.).
For the classical gravitational n-body problem, I think the following two papers do a good job at discussing the guts of the parallel implementation for the force evaluation step. Although the papers discuss a GPU implementation, they do a good job at discussing the parallelism and provide details of the algorithms:
This paper by Nyland, Harris, and Prins presents the direct n-body algorithm in CUDA for GPUs.
This other paper by Yokota and Barba has a good discussion on of the treecode and fast multipole algorithm also in the context of GPU-computing
Your questions about the accuracy of n-body numerical simulations are a bit more involved and there are so many important details that an answer can spawn several books. I think the best think to do is to give you a couple of book references. I suggest:
Gravitational N-body Simulations by Sverre J. Aarseth
Computer simulations using particles by Hockney and Eastwood. (Sorry no pdf version)
If you need a simple implementation approach which is not optimal in the asymptotic sense, you may want to consider using all-gather communication operations. Since each of the N-bodies needs to know the gravitational effect of the other bodies, it is important for every processor to know the entire dataset. This is what all-gather operations do. There is a good book: Parallel Programming in C with MPI and OPENMP by Michael J. Quinn (2004) which discusses exactly this topic on page 82. It might be worth looking at to give you a start.
See Google Scholar and look for references to HACC and GADGET, among other codes.