The current document is directed to efficient, distributed-search methods and subsystems within distributed computer systems, including computer systems distributed over multiple sets of geographically distributed data centers, each comprising multiple discrete computer systems, such as multi-processor servers. In one implementation, the distributed-search methods and subsystems are implemented locally within participating entities as well as within one or more distributed-search engines. Each search is directed, by a participant, to identify attribute-associated entities within, provided by, connected to, or otherwise accessible to a distributed computing system having attribute values specified or indicated by the search query. Certain attribute values are continuously collected and centrally stored by the one or more centralized distributed-search engines while other attribute values are obtained through information requests distributed among participating entities.