  We extend the multi-pass streaming model to sliding window problems, and
address the problem of computing order statistics on fixed-size sliding
windows, in the multi-pass streaming model as well as the closely related
communication complexity model. In the $2$-pass streaming model, we show that
on input of length $N$ with values in range $[0,R]$ and a window of length $K$,
sliding window minimums can be computed in $\widetilde{O}(\sqrt{N})$. We show
that this is nearly optimal (for any constant number of passes) when $R \geq
K$, but can be improved when $R = o(K)$ to $\widetilde{O}(\sqrt{NR/K})$.
Furthermore, we show that there is an $(l+1)$-pass streaming algorithm which
computes $l^\text{th}$-smallest elements in $\widetilde{O}(l^{3/2} \sqrt{N})$
space. In the communication complexity model, we describe a simple
$\widetilde{O}(pN^{1/p})$ algorithm to compute minimums in $p$ rounds of
communication for odd $p$, and a more involved algorithm which computes the
$l^\text{th}$-smallest elements in $\widetilde{O}(pl^2 N^{1/(p-2l-1)})$ space.
Finally, we prove that the majority statistic on boolean streams cannot be
computed in sublinear space, implying that $l^\text{th}$-smallest elements
cannot be computed in space both sublinear in $N$ and independent of $l$.
