Resource discovery technologies for Grids and Peer-to-Peer (P2P) systems share some characteristics. However, some P2P systems such as Skip Graph cannot simply be applied to Grid resource discovery because complex grid resources need to be searched by using multi-attribute queries. This paper proposes a new multi-attribute P2P resource discovery approach (SkipMard) that extends Skip Graph structure to support multi-attribute queries. SkipMard provides a prefix matching resource routing algorithm to resolve multi-attribute queries, and introduces the concepts of "layer" and "crossing layer nearest neighbor" into the data structure. To decrease message passing numbers, an approximate closest-point method is addressed that can help routing a searching key to a node with a key value that has the minimum distance between two keys. Each node has O(m *l) neighbors for total m layers and l levels in SkipMard. The expected time for a multi-attribute query is O(log N) and the message passing number is O(log N)+O(k).