  We study the randomized version of a computation model (introduced by Grohe,
Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that
restricts random access to external memory and internal memory space.
Essentially, this model can be viewed as a powerful version of a data stream
model that puts no cost on sequential scans of external memory (as other models
for data streams) and, in addition, (like other external memory models, but
unlike streaming models), admits several large external memory devices that can
be read and written to in parallel.
  We obtain tight lower bounds for the decision problems set equality, multiset
equality, and checksort. More precisely, we show that any randomized
one-sided-error bounded Monte Carlo algorithm for these problems must perform
Omega(log N) random accesses to external memory devices, provided that the
internal memory size is at most O(N^(1/4)/log N), where N denotes the size of
the input data.
  From the lower bound on the set equality problem we can infer lower bounds on
the worst case data complexity of query evaluation for the languages XQuery,
XPath, and relational algebra on streaming data. More precisely, we show that
there exist queries in XQuery, XPath, and relational algebra, such that any
(randomized) Las Vegas algorithm that evaluates these queries must perform
Omega(log N) random accesses to external memory devices, provided that the
internal memory size is at most O(N^(1/4)/log N).
