  The area of computing with uncertainty considers problems where some
information about the input elements is uncertain, but can be obtained using
queries. For example, instead of the weight of an element, we may be given an
interval that is guaranteed to contain the weight, and a query can be performed
to reveal the weight. While previous work has considered models where queries
are asked either sequentially (adaptive model) or all at once (non-adaptive
model), and the goal is to minimize the number of queries that are needed to
solve the given problem, we propose and study a new model where $k$ queries can
be made in parallel in each round, and the goal is to minimize the number of
query rounds. We use competitive analysis and present upper and lower bounds on
the number of query rounds required by any algorithm in comparison with the
optimal number of query rounds. Given a set of uncertain elements and a family
of $m$ subsets of that set, we present an algorithm for determining the value
of the minimum of each of the subsets that requires at most $(2+\varepsilon)
\cdot \mathrm{opt}_k+\mathrm{O}\left(\frac{1}{\varepsilon} \cdot \lg m\right)$
rounds for every $0<\varepsilon<1$, where $\mathrm{opt}_k$ is the optimal
number of rounds, as well as nearly matching lower bounds. For the problem of
determining the $i$-th smallest value and identifying all elements with that
value in a set of uncertain elements, we give a $2$-round-competitive
algorithm. We also show that the problem of sorting a family of sets of
uncertain elements admits a $2$-round-competitive algorithm and this is the
best possible.
