The bulk of the traffic going over the North Atlantic flies on an organised track system. The eastbound and westbound tracks are not fixed but move north or south daily depending on the most favourable wind conditions. The westbound day tracks are promulgated by Scottish, the eastbound night tracks by Gander in Canada. The operators notify their preferred routes and around those the tracks are defined.
The tracks are separated laterally by a minimum one degree of latitude, i.e. 60nm. Within a track levels are separated vertically by 1,000ft.
On a track, from memory, the longitudinal separation is 10 minutes. A slower aircraft following a faster one, if they both stayed at the same level all the way across, would have to arrive at the landfall fix with that 10mins time separation so would have to enter the track with a greater time interval than 10mins to allow for the overtake. There was a 5min trial, not sure what the result of that was.
There is also random track and opposite direction traffic to be knitted through the traffic on the organised tracks.
Concorde (sigh) had it's own fixed tracks high above the slow moving masses and used to get its westbound Oceanic clearance from LHR ATC before departure.
The part of the North Atlantic controlled by NATS from the UK is the
Shanwick Oceanic Control Area where the ATC is done from Scottish Centre at Prestwick and the communications from Ballygirreen in Ireland.
The SAATS system used by the Ocean controllers at Scottish is a pretty sophisticated bit of kit providing conflict probing and resolution capabilities before issuing clearances and monitoring traffic en-route. These days there's also a 'virtual' radar display of traffic on the Ocean using the aircraft's ADS capabilities, but as of the moment this is not used for separation purposes.
My ATC career started at Scottish Centre longer ago than I care to remember. Back then the Oceanic controllers used a very large flight progress strip and did all the arithmetical separation calculations in their head. Respect!