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.

[jhellerstein]

Counterpoint:

Why nondet may not be the right choice

• non-determinism has a well-recognized meaning to any programmer, but we're not using it precisely in our checks. Protecting against all forms of non-determinism would require either very conservative or very sophisticated program analysis (of libraries etc). This will mislead/confuse users in its own right, as we only mean to say "exposes network non-determinism"
• Unless we want true non-determinism detection, we need to choose a more vague term that makes people ask "what do you mean"? C.f. unsafe.
• nondet doesn't roll off the tongue

Alternative names for the property we test

• Ideally sounds like natural English (like unsafe)
• Ideally feels on-brand for Hydro, reinforces a developer's sense of being "in the family, in the know" when they understand it
• some alternatives to nondet and uncalm:
  • a water term: turbulent
  • racy
  • divergent
  • uncoordinated
  • disorderly (Peter Alvaro's term)

I don't want to get stubborn about uncalm, but I don't think we should discard calm-related words without further discussion:

The case against uncalm, summarized

• programmers unlikely to recognize the words in the macro-expansion of CALM
• monotonicity is a property to test, not the outcome to be managed
• monotonicity doesn't feel like a fit to all cases we want to analyze (even though it may be, under the hood... quibbling would need to follow on this point)
• we're not checking consistency right now, only non-determinism across runs (How is that different? This blog post has an example, but it's subtle)
• quibbles about the guarantees of the CALM theorem wrt Hydro (the discussion above is not on target: "Neither monotonicity nor determinism have anything to do with consistency" is saying the CALM theorem is wrong, which it's not.)

The case for uncalm

• it's on-brand for Hydro's roots
• the initial inscrutability could be an advantage in branding
  • for aficionados, once they've heard of the CALM theorem, it feels on point at a high level: uncalm code needs coordination.
  • for newbies, it raises the question "what does this mean"?
    • the initial answer need not be "let me explain: the M means monotonicity. let me explain further..."
    • the answer can simply be "you can't calmly leave this uncoordinated. attention must be paid. this is in the spirit of something called the CALM theorem"
    • teachable moment for those who care to dig in (we can offer a gentle intro in the docs)
• open research question: when is non-determinism in the sense we test in Hydro meaningfully different from "consistency" in the sense of confluence meant in the CALM theorem? what, if any, are the good reasons to differentiate these?