How can we define $\epsilon$-differential privacy for non-deterministic algorithms? We know that  non-trival deterministic algorithm does not guarantee privacy and randomization is essential for privacy (pp.16 in [Dwork and Roth 2014] ).  The well-known $\epsilon$-diferential privacy is defined for randomized (probabilistic) algorithm (see the link https://en.wikipedia.org/wiki/Differential_privacy).
From a broader perspective of uncertainty, I wonder whether we can define a similar diferential privacy notion for non-determinstic (multi-valued or set-valued) algorithms? And how?
I find that question very interesting. They are arguing that there is not a notion of diferential privacy for all non-deterministic algorithms. Some non-deterministic algorithms could be $(\varepsilon,\delta)$-differential private. But not every non-deterministic algorithm is $(\varepsilon,\delta)$-differential private, they give the example of the algorithm.
Algoritm:
Input: Database $D$
Output: $f(D)$ dropping a row/register from D (non-deterministically), where $f$ is the query function (median,sum,etc).
Note this algorithm is non-deterministic but it is possible to know all the information from the databases if you use this algorithm repetitively. Consider the worst case, the attacker knows all the database except one row (That's why is a condition that $|D-D'|\leq 1$). Therefore you can't guarantee privacy for all or some the rows/registers.