The Maay protocol contains two messages devoted to search documents:

• a request message contains a query id, the set of queried words and some parameters to control the propagation of the request.
• a response message contains a query id, some meta-data of the documents matching the query, the scores of words describing the document profile and the document providers.

All request messages and responses messages issued from the same search have the same query id. A node initiating a request is called an initiator. From the point of view of a node receiving a request, the request emitter is a requester. This requester is either the initiator itself, or a node which forwarded an incoming request.

The propagation control parameters aim to avoid the well-known broadcast storm effect. The ttl parameter counts the number of remaining hops of the message. It is decremented after each hop and the message is not forwarded when equal to 0. The fnc parameter sets the number of neighbors to forward the request. It is a not-null integer halved after each hop.

Request Message

Upon reception of a request message, the node

1. scans the set of documents it has published, downloaded or just observed in previous search responses,
2. extracts the list of documents which are the most relevant for the requester and the queried words. The selection of these documents is detailled here,
3. stores this list in a buffer B
4. sends it back to the requester in a response message.

Each document in B contains the meta-data of the matching documents, scores describing the document profiles and the providers of the documents. If the ttl is not null, the node should forward the request. The node stores information related to the search for further use: query id, requester, B.

Then it selects a list of fnc neighbors to forward the request. Most of them are chosen among the top ranked neighbors as detailled here. Te remaining part is chosen randomly to give the opportunity for new nodes to get known. The fnc factor is halved at each step, so that most queried nodes are in the close neighborhood - and so have close profile - of the requester.

Response Message

Upon reception of a response message , a node

1. retrieves the information previously stored for this query id : requester, B
2. merges B with the responses contained in the response

As the node may have forwarded the request message to several neighbors, it may receive several response messages. It should obviously not forward all these messages, but only "complete" the response it previously sent by forwarding to the requester only new relevant documents.

Responses appear for the initiator as a sorted list of document descriptions with the scores describing the documents and some links toward document providers.