Algorithm Puzzle - Sync'ing Big Lists And Nodes

Here’s a mathematical algorithmic puzzle for all you bright challange-seeking minds:

I’ve my own big business contact list and so does my friends. One day we decide to call up with each other on phone (only 2 people on one line), talk to each other and have our lists sync’ed up with each other. That is to say, we add any contacts we didn’t had already, update any outdated ones and delete anyone who has gone out of business. However, you will be pleased to know that content of any two contact lists are pretty much same with only few differences. Infect many of my friends have identical contact lists and so they don’t need sync’ing at all (though they don’t know if they do have identical lists). We’ll let you arrange pairs of people calling each other any way and at any time you’d like. Eventually, we hope to end up with exactly identical one mega list. But we want you to be fair, i.e., schemes like appointing one “central person” and having everyone talk to him in turns and let him do all the sync work is not cool. That’s not fair for him and that would take lot of time too because talking in turns uses only one phone line at a time. For us “fair” means each person only needs to talk with same number of people as every other person needs to. And yes, before I forget to mention, our contact lists are really big and so does the count of my friends - both currently running over a million - and of course, us busy tired souls want you to finish this exercise in as little time and effort as possible.

So how would you do that?

[UPDATE: I’d posted the answer in the off topic group. Excerpt is in comments. Enjoy!]