1. 36

  2. 14

    CAP Theorum doesn’t really need to be limited to the scope of packet-switched computer networks and relational database management systems. Internet people may care very deeply about serializing messages across TCP/IP connections, but there’s more to life than that sort of thing. (I know, I know, hard to imagine…)

    Within the context of computer science, though, you might consider system buses to be a form of partition intolerant network. A system bus could tolerate temporary inconsistencies, and recover from multiple nodes conflicting with each other, after they cease to conflict, while struggling to remain generally available to other network members.

    If you choose define your degree of partition intolerance as something that does not require a continuous laminar-flow, up-to-the-nanosecond, speed-of-light communication channel, partition-intolerant systems do, in fact, exist, and could be considered quite abundant, both within and beyond the realm of computer science.

    If your network is considered contiguous, as long as at least one full-duplex exchange of a complete, integral information message is passed in each direction, per every 24 hours, then you get to exclude partition tolerance from your network requirements.

    Example: Say you have a “network” of traveling sales people, and you need them to communicate a single number, denoting the total value of their gross sales, each day, before midnight UTC. Some of the sales people are regional managers, but the subordinates can relay their number to any manager, who, in turn will validate and forward their tallies to an accountant that publishes master ledger with a final grand total for replication to all members, then, at the broad scope of 24 hour intervals, the network of sales people is capable of operating in a consistent manner, without partitions.

    1. 8

      The point is you can’t choose not to have partitions. Sure, maybe you tell your salespeople to check in every day. You still have to choose between consistency and availability in deciding what you do if one day one of them doesn’t.

      1. 3

        Not true. A partition intolerant system which refuses to accept partitioned scenarios can self-destruct if a partitioned state is unacceptable.

        Consider circulatory systems in living organisms. If you try to partition an animal, it’s probably going to die. Granted, such a scenario in living organisms is not entirely binary at time scales of maybe minutes or hours, but if you try to partition a dog or a cat for more than a day, it’s probably going to be a bad day, and after that you’ll have a hard time reverting to the unpartitioned state.

        1. [Comment removed by author]

          1. 3

            Hey, if you wanna partition Schrödinger’s Cat, that’s fine by me.

    2. 6

      This is a nice summary. The Gilbert & Lynch proof is precise in its definitions of the three terms. You can find useful systems by varying each of the definitions.

      For example, if you step away from linearizability as a requirement then you can admit CRDT systems.

      Or, changing the definition of availability to split reads & writes leads you to CQRS.

      The underlying network might be circuit based instead of packet based. In which case, failure detection is automatic and simply.

      You might have an external reliable clock source with no risk of skew. (E.g., GPS synchronized atomic clocks.) Then consistency can be reconstructed after a partition.

      And so on…

      Nancy Lynch isn’t just co-author of the theorem, by the way. She wrote the excellent textbook “Distributed Algorithms” which covers much more than CAP.

      1. 2

        Nancy Lynch isn’t just co-author of the theorem, by the way. She wrote the excellent textbook “Distributed Algorithms” which covers much more than CAP.

        Phew, 80 Euros at certain places named like a south-american river. Is the book still worth the investment even if it is 20 years old?

        1. 2

          The underlying theorems still work. We have found new algorithms that aren’t in her book, of course. I found that the book was invaluable to understand those algorithms and their proofs.

          Whether it’s worth 80 Euros is more of a personal question. I did find my (used) copy for considerably less than that, so it might be worth putting on a watch list.

          1. 1

            Thanks, I’m fine with that. I’m fine with new stuff not being in, as long as the general line of thinking still fits. Sometimes, old and time-tested books are great because they don’t bother you with the finer details of new things while giving you a general frame of thinking.

            I’m fine with 80 Euros for a rarely-bought book. I got Purely Functional Data Structures for ~60 and I’m very happy with having bought it.

            I’ll put it on my list.

      2. 4

        I saw Martin present that at Strange Loop a couple years ago and I liked the paper so much, I ran a conversation about it at my local Papers We Love group. In the interest of sharing information, here are my slides from the PWL discussion: https://docs.google.com/a/trevreport.org/presentation/d/1w12FF0OHovLtrwB_h1E6e9RTqpBT-gbBQdYVZXzr2OQ/edit?usp=sharing