There is no clear answer to the question whether DBSCAN is deterministic or not.
Fact is, that if you shuffle the data set, it can return slightly different results on some data sets and parameters ("rare situations").
This will also happen if SetOfPoints
is actually implemented as a set, with no well-defined iteration order (usually, this will only depend on the data order; but in some implementations this may yield a different order every time!)
However, the actual pseudocode of DBSCAN does not contain non-determinism itself. So it is perfectly reasonable to call DBSCAN deterministic, given the data, minPts, eps, distance function, and iteration order.
From a mathematical point of view, DBSCAN is deterministic (but some points are border points to more than one cluster; and the DBSCAN algorithm proposed only approximates the definition).
From an experimental point of view, DBSCAN is deterministic: unless I change my data, the result usually does not change; and I do not need to experiment with shuffled data, because the results will often not change at all, or only so little that it does not make a difference. In contrast to k-means, where I must consider different random seeds, I do not need to do shuffling for DBSCAN.
From an implementors point of view, DBSCAN is not deterministic: Different implementations can both be correct, yet yield slightly different results. So if I compare my results to the results of someone else, I cannot blindly require the labels to be identical, because different data structures and processing order can yield different results. This also applies, e.g., to parallel and distributed versions of DBSCAN. These can be correct, yet yield a different result on multiple-border-objects.