Here's how quantum computing really works:

It splits reality into millions of possible universes, trying a different answer in each one. Then it uses quantum interference to destroy every universe where the answer comes out wrong. When it's done, you know the answer you have is right.

Vinge's books are great, but they have little relevance to the question at hand; he assumes messages can travel faster than light under certain circumstances. The real world isn't like this, no matter how much you want it to be.

The real question becomes: "How do we extend internet protocols to handle ping latencies ranging anywhere from seconds to centuries?" The new protocols should have redundant transmissions and *very* large buffer caches. Timeouts shouldn't occur until some multiple of the latency has passed.

Programs using these protocols should try to anticipate demand and pre-send as much data as possible. For huge distances, it might just be better to send a complete backup regularly until told it isn't necessary anymore.

Another thing worth noting is that these protocols will be relatively immune to the "embrace, extend, extinguish" attacks we all know and love because of the amount of time it will take to update the entire network.