Facility level caching and request deduplication would become important, you don't want everyone requesting the same news article from earth when the second shift wakes up. But if there is a local copy of it then it's functionally free.

And with caching comes cache invalidation.

DNS has kind of solved this problem. A TTL on data/pages. This breaking news story gets a four hour refresh interval, this article from a week ago probably isn't going to change so TTL of a month is fine.

But back to search. Your local search service would initially respond with "here are the results I know about. I last ran a similar query N hours/days/months ago."

Then give you the option to send the query to other known search services, the search would be saved and you'd receive a notification when a new result came back.

"We received four results from mars for your search. We are still waiting for responses from earth, the moon, and Neptune"

Identifying stuff and where it is was an easy thing, just use the existing domain system but with a new top layer with the planet or system for routing, however the explosion of top level domains (including .earth) kind of made that harder.

Maybe instead DNS gets extended with a routing field that allows the sender to know where to send messages. (Assuming wanting to avoid broadcasting messages to places that don't need them)

That would also allow people to move easily between locations and keep their email address/identifier, for the "cost" of a DNS update which isn't too bad.

Of course all of this needs some nice UX that explains what the fuck is going on all the time.

"It's April so this message to mars is going to take 20 minutes to get there, plus processing time, so don't expect a response for at least 40 minutes"