Special Relativity: Time dilation paradox Two spaceships, A and B, travelling rapidly through space, pass each other on a parallel course. According to special relativity:
A observes B speeding past, and perceives that time on B's ship is running more slowly than his own. 
B observes A speeding past, and perceives that  time on A's ship runs more slowly than his own. 
How is this possible?
 A: *

*Your description is wrong: the time of spaceships with parallel movement does not run differently. I suppose that you are meaning two spaceships whose movement is differing by the respective relative velocity v. In the following I will consider this case.

*One main feature of special relativity is the fact that time is no longer universal, instead each particle is following its own intrinsic time. 

*Now you are spaceship A with the board clock A. You are measuring your own heartbeat and the heartbeat of B, C and D in other spaceships, and you record the respective worldlines in your Minkowski diagram.
You will find that your own worldline will never leave the time axis of your own Minkowski diagram. Your heart is beating in the rhythm of your own proper time (coordinate time = proper time). Then you draw the worldlines of the spaceships B, C and D in your Minkowski diagrams. Depending on their respective relative velocity to A, their worldlines are not straight upwards as the worldline of A but diagonal. By consequence, their coordinate time will not be their proper time. According to the proper time equation
$$\tau = \frac{1}{\gamma}t = \sqrt{(1-\frac{v^2}{c^2})}\ t$$
the coordinate time t is always bigger than or (in case of parallel movement) equal to proper time $\tau$. This is why from the point of view of the reference frame of A, the heartbeat of B, C and D is always measured to be slower than the own heartbeat. In contrast, the coordinate time of the own heartbeat is identic with the proper time which is the fastest coordinate time possible.


*The mirrored situation is found from the point of view of spaceship B: The own heartbeat is measured as the proper time and as such it is the fastest heartbeat, faster than the heartbeat of the other spaceships.

*In summary: The paradox is using the fact that the proper time is the fastest time of all possible coordinate times in a Minkowski diagram. The time of other spaceships is observed to advance slower because the time of the own spaceship is the proper time.
A: What you ask reflects perfectly how counter intuitive relativity may appear to us, but it is nevertheless understandable. The key point is that the present is relative (simultaneity is relative).
The normal misconception comes when thinking of it as if A and B measured time with respect to some universal clock. Then, say when A measures 1 sec B measures 0.5 sec, so it is natural to think that B's clock goes more slowly with respect to this universal clock than A's clock. If two events happen at the same time, they happen at the same time for A, and at the same time for B (although the actual time measured by A or B will be different). But now, how would it be possible that this worked the other way around? It seems inconsistent.
The solution comes throwing away the idea of a universal clock. Now, A's present is not the same as B's. 
Suppose A could freeze his time. Then, freezing it at 1 sec of his clock he looks where B is and what B's clock is telling. What A sees is that B is some distance away and that B's clock shows 0.5 sec. This is the picture of A's present when its clock tells 1 sec. 
Now, imagine B could also freeze his time. B's present when B's clock shows 0.5 sec is completely different from A's present when A's clock shows 1 sec !!! What B sees when his clock shows 0.5 sec is that A is some distance away and that A's clock shows 0.25 sec. So when B freezes his time at 1 sec he sees A's time to be 0.5 sec. This is the actual resolution, for which you have to break with the idea that the present is absolute.
The principle of Relativity is actually the statement that everything A and B measure must be symmetric (and not only mechanical stuff but every physical experiment). This question is very related to the twin experiment, although in that experiment there is an asymmetry because one of the twins is not an inertial observer all the time, and that is what makes that twin to be old when they meet again.
