This is a key question: "What is the family of problems that can be consistently computed in a distributed fashion without coordination, and what problems lie outside that family?" Here's the proposed answer: "Consistency as Logical Monotonicity (CALM). A program has a consistent, coordination-free distributed implementation if and only if it is monotonic." By monotonic, we mean this: "once we learn something to be true, no further information can come down the line later on to refute that fact." How do we get monotonicity? Confluent operations, that is, "If it produces the same sets of outputs for any non-deterministic ordering and batching of a set of inputs." Give it the same data, however ordered, and it produces the same results. It gives you something to think about. Accounting is confluent; the order of transactions doesn't matter, the balance is the same in the end. Voting is confluent; you vote in morning or evening, but the final tally is the same. But causation and agency are not confluent. When you're trying to make something happen, order matters.
Today: 5 Total: 1102 [Direct link] [Share]
