The OpenKnowledge project aims at knowledge sharing through open and flexible peer interactions. Within this project, we are developing a system that supports search- ing, developing and sharing of interactions/workflows con- sisting of roles implemented by software that can be shared and executed by peers. Its main requirements are open- ness, scalability, decentralization and robustness. Part of this system is a discovery service, which will be the focus of this paper. This service aspires to fulfill the above re- quirements featuring a Peer-to-Peer architecture and Dis- tributed Hash Tables (DHTs) to achieve robustness through redundancy and scalability through decentralization. Re- sources are discovered using a set of attribute-value pairs. A straightforward DHT-based approach that creates a dis- tributed inverted index suffers from a linear increase of mes- sages and replicas with the number of attributes. We try to reduce this number by proposing an efficient multi-attribute routing algorithm. We emulate and test our implementation on the DAS-2 distributed supercomputer.