A method, system, and computer program product for implementing indexes in a dispersed storage network (dsNet) are provided. The method accesses an unordered work queue containing a set of key-value pairs. A subset of expired key-value pairs are determined from the set of key-value pairs. The method transmits a work request to a plurality of data source units. The work request indicates a key-value pair being selected at random from the subset of expired key-value pairs. A threshold number of work responses is received from the plurality of data source units. The work responses include a set of available key-value pairs. The method selects an available key-value pair from the set of available key-value pairs and generates a work lease on the available key-value pair.