We need a decentralized search just like DNS is a central service, but not centrally managed (OK, mostly not centrally managed).

How about each web site indexing their own contents and then there being a mechanism for your client to crawl the indexes, just like a DNS resolver will query servers until it finds the answer it wants. My iPhone is leaps and bounds more powerful than desktops of a decade ago - there is zero reason to pool power in data centers. Indeed it would be impractical for Google to replicate the power of all the clients worldwide in a data center.