  We introduce the concurrent shuffle model of differential privacy. In this
model we have multiple concurrent shufflers permuting messages from different,
possibly overlapping, batches of users. Similarly to the standard (single)
shuffle model, the privacy requirement is that the concatenation of all
shuffled messages should be differentially private.
  We study the private continual summation problem (a.k.a. the counter problem)
and show that the concurrent shuffle model allows for significantly improved
error compared to a standard (single) shuffle model. Specifically, we give a
summation algorithm with error $\tilde{O}(n^{1/(2k+1)})$ with $k$ concurrent
shufflers on a sequence of length $n$. Furthermore, we prove that this bound is
tight for any $k$, even if the algorithm can choose the sizes of the batches
adaptively. For $k=\log n$ shufflers, the resulting error is polylogarithmic,
much better than $\tilde{\Theta}(n^{1/3})$ which we show is the smallest
possible with a single shuffler.
  We use our online summation algorithm to get algorithms with improved regret
bounds for the contextual linear bandit problem. In particular we get optimal
$\tilde{O}(\sqrt{n})$ regret with $k= \tilde{\Omega}(\log n)$ concurrent
shufflers.
