This disclosure describes a virtual desktop brokering system that brokers a virtual desktop session. During operation, a broker receives a request to establish the session. Next, the broker broadcasts, to a set of agent concentrators, a request to find an available machine for the session, wherein each agent concentrator maintains state information of a respective group of available machines. The broker receives, from at least one agent concentrator, a list of available machines. Subsequently, the broker chooses an available machine from the list for the session, and the broker sends a request to the agent concentrator associated with the chosen machine to initiate the session.