In a distributed system, a method and system for negotiating a multi-category Quality-of-Service (QoS) agreement between a client and a server includes a client agent enabled to calculate an expected utility to a client of multiple multi-category QoS specifications. The client agent obtains the QoS specifications by transmitting a QoS specification request to a server agent or a broker. The expected utility calculation, based on a probabilistic estimate of QoS levels included in the QoS specifications, enables the client agent to distinguish the QoS specifications of greater value from those of lesser value. The client agent selects at least one of the QoS specifications to be included into an offer for a QoS agreement based on the expected utility calculation. In a preferred embodiment, the client agent selects the QoS specifications determined to be most valuable to the client. The offer is transmitted to the server agent to request a service provided by a server at QoS levels represented by the selected QoS specifications. After transmitting the offer, the client monitors a connection to the server agent for either an acceptance, a rejection, or a counteroffer to the offer. Communication between the client agent and the server agent conforms to a negotiation protocol which provides a set of rules for transmission of negotiation messages.