Anyone with a reasonably large collection of records (or books, or indeed anything) will be familiar with the problem of finding the item that you want in as short a time as possible. Do you file them in purely alphabetical order (in which case you end up with Bob Marley next to Bohuslav Martinu), do you store them by category (in which case is Philip Glass' Low Symphony "classical" or "rock"?) or do you keep all the ones with the same label together? It's a real dilemma, but at least the items in question are self-cataloging.
It gets considerably more complex if you indulge in home taping. I used to do an awful lot of this (even to the extent of having an amateur recording license in the days when you could get one). The problem was that you couldn't guarantee that the two things that you had recorded on either side of the cassette would be sufficiently similar to each other to enable you to treat the cassette as a single entity from the point of view of classification. (We're entering the seriously sad zone here, but let's stick with it — it's a useful analogy.) In the end, the only viable way to store them was to number them in the order in which you recorded them, and keep a separate card index, cross-referencing artists and records with the appropriate cassettes.
Libraries, of course, have a similar problem, only far, far worse. Let's imagine that I go to my local library in search of a copy of, say, Bill Gates' The Road Ahead; as I'm feeling in need of a little self-improvement. If I can't find the book on the shelves, I might search the library's CD-ROM to find out its Dewey decimal classification, so I can check to see if I was looking in the right place. If the book definitely isn't there, I'll go and ask the librarian.
The first thing that they will do is search their own database to establish whether or not they have a copy at all, and, if so, whether or not it is currently out on loan. Suppose they don't have a copy — the next step is to search the other libraries in the county. Fortunately, they find out that the central library in the next town has two, although both are currently out on loan. Reluctantly, I pay my fee to request the book, and wait to achieve enlightenment.
Here we have a reasonably typical example of a distributed directory search. You don't even really need computers for it. In the old days, your friendly librarian would have simply got on the phone and called up the other libraries to ask them. The problem, however, is basically the same: How do you find something that you need as quickly as possible, even if it's stored in a totally different geographical location?
Incidentally, once you have located the object in question, getting hold of it is a different matter — but that's outside the jurisdiction of the directory service.