Why "non-determinism" and not "uncalm"

[shadaj]

As rightfully brought up earlier today, there's an important decision if we focus on non-determinism of "unsafe" APIs or try to align with past Berkeley naming on "monotonicity". Here I make the argument that determinism makes more sense to expose to developers.

1. Monotonicity focuses on underlying implementation. Determinism focuses on user-observable properties. With Flo semantics, a "live collection" in Hydro abstracts over underlying details of how updates are propagated, how the underlying data is stored and updated, and how operators are scheduled. A live collection semantically captures its contents at the end of time, rather than lower level details such as a single batch. Monotonicity is a property of the implementation of a live collection, restricting how its outputs must be propagated (no retractions). Therefore, a monotonic operator is naturally deterministic in Hydro semantics. But for users, this is a low-level detail, and they care more about whether the system will output the wrong thing because of asynchrony. Determinism captures this more opaquely, guaranteeing that the output is unaffected by asynchrony without discussing the underlying reason.
2. There are non-deterministic functions that are monotonic. Consider an operator that emits a snapshot of a Hydro Singleton at a periodic time interval. By a native developer's definition of monotonicity, this operator is monotonic: it emits new elements over time and never retracts them. But sampling a Singleton is an easy way to introduce bugs into your program, because it is non-deterministic which "version" of the value will be captured. It would be strange to mark this as safe simply because it is monotone, and even more confusing to developers if we claim that this is non-monotone.
3. Determinism is well-understood to developers, monotonicity is not. Monotonicity has been conflated a bit too much with commutativity and idempotence throughout our group's past research, to the point where its meaning has deviated far from its mathematical definition. It is even more confusing for developers who have never heard of the word. When we support a set with retractions (Z-Set), we will have APIs like .set_difference. This feels non-monotone even though the underlying implementation is monotone, and can be quite confusing. I've heard many questions from external developers already about "how do you remove from a set in Hydro if it has to be monotone". Focusing on "monotone programming is good and you should do more of it" is IMO detrimental to our adoption story and scares away developers who a) don't know what monotonicity is or b) make incorrect assumptions about what is monotone. It took me 4 years to fully understand why monotonicity is good. On the other hand, "even with network delays your program does the same thing" is a) straightforward for developers to understand and b) obviously a good thing.
4. Neither monotonicity nor determinism have anything to do with consistency. The C in CALM has long been incredibly confusing. In distributed systems literature, C refers to invariants of data across several replicas. Neither determinism nor monotonicity are sufficient to guarantee such properties. The best we can do is show that the value on each replica resolves to some deterministic result, but this does not give any guarantees across them. While there are ways we can help developers reason about cross-replica properties, these are independent of determinism / monotonicity. The underlying issue is that the definition of "consistency" in CALM actually should be "determinism" (assuming liveness, a prefix otherwise); but DALM has less of a ring to it...

Regarding point (1), I'd like to point out that focusing on determinism does not mean throwing away monotonicity. In fact monotonicity is what enables us to guarantee determinism through the various live collections (Z-Sets, LVars, etc). But I think it will be beneficial long term to focus on monotonicity when working on Hydro internals, but determinism as the guaranteed property at the high-level.

[davidchuyaya]

I think Hydro has a more coherent and relevant pitch as "a way to make writing distributed systems easier" by showing where your code is unsafe and (on my part) doing the trickier optimizations for you.

I think monotonicity is a property that the optimizer can leverage (as one of many preconditions for applying a rewrite) but much like we don't expect developers to read the SIGMOD paper, we don't expect them to understand how to use it correctly.