3 ms·

I feel like the correct approach is accepting that determinacy is nonsensical in a world where time is relative and instead doubling down on nondeterministic (b

by User23 5y ago

I feel like the correct approach is accepting that determinacy is nonsensical in a world where time is relative and instead doubling down on nondeterministic (but predictable!) algorithms. This means leveraging concepts like commutativity and associativity to ensure predictability.

choeger 5y ago
> nondeterministic (but predictable!) Huh? How could a nondeterministic algorithm be predictable? Do you mean algorithms with a nondeterministic but overall irrelevant component ("pick a random element from this set")?
- deleted 5y ago
  [deleted]
- User23 5y ago
  A simple example is algorithms that compute the value of applying associative and commutative functions. For example we can sum a set of integers by nondeterministically picking and removing an element and iterating until the set is empty. Despite the large number of possible processes, the result at termination will always be the same.
- lupire 5y ago
  Local nondeterminism, where random variations can be introduced but disappears later: Example: size of a set = 1 + (remove an element from the set and then compute size of reduced set, or 0 if set is empty)
_vvhw 5y ago
Surprisingly, some of the most powerful distributed systems algorithms or tools are actually deterministic. They're powerful because they can "load the dice" and so make the distributed system more intuitive for humans to reason about, more resilient to real world faults, and do all this with more performance. For example, Barbara Liskov and James Cowling's deterministic view change from VSR [1][2], which isn't plagued by the latency issues of RAFT's randomized dueling leader problem. VSR's deterministic view change can react to a failed primary much quicker than RAFT since heartbeat timeouts don't require the randomized "padding" that they do in RAFT, commence the leader election, and also ensure that the leader election succeeds without a split vote. Determinism makes all this possible. Deterministic testing [3][4] is also your best friend when it comes to testing distributed systems. [1] An introductory talk on VSR and it's deterministic view change — https://www.youtube.com/watch?v=Wii1LX_ltIs https://www.youtube.com/watch?v=Wii1LX_ltIs [2] James Cowling on determinism, working with Barbara Liskov — https://www.youtube.com/watch?v=ps106zjmjhw https://www.youtube.com/watch?v=ps106zjmjhw [3] FoundationDB are pioneers of deterministic testing — https://www.youtube.com/watch?v=OJb8A6h9jQQ https://www.youtube.com/watch?v=OJb8A6h9jQQ [4] TigerBeetle's deterministic simulation tests — https://github.com/coilhq/tigerbeetle#simulation-tests https://github.com/coilhq/tigerbeetle#simulation-tests

by User23 5y ago

choeger 5y ago

> nondeterministic (but predictable!) Huh? How could a nondeterministic algorithm be predictable? Do you mean algorithms with a nondeterministic but overall irrelevant component ("pick a random element from this set")?

deleted 5y ago
[deleted]
User23 5y ago
A simple example is algorithms that compute the value of applying associative and commutative functions. For example we can sum a set of integers by nondeterministically picking and removing an element and iterating until the set is empty. Despite the large number of possible processes, the result at termination will always be the same.
lupire 5y ago
Local nondeterminism, where random variations can be introduced but disappears later: Example: size of a set = 1 + (remove an element from the set and then compute size of reduced set, or 0 if set is empty)

_vvhw 5y ago

Surprisingly, some of the most powerful distributed systems algorithms or tools are actually deterministic. They're powerful because they can "load the dice" and so make the distributed system more intuitive for humans to reason about, more resilient to real world faults, and do all this with more performance. For example, Barbara Liskov and James Cowling's deterministic view change from VSR [1][2], which isn't plagued by the latency issues of RAFT's randomized dueling leader problem. VSR's deterministic view change can react to a failed primary much quicker than RAFT since heartbeat timeouts don't require the randomized "padding" that they do in RAFT, commence the leader election, and also ensure that the leader election succeeds without a split vote. Determinism makes all this possible. Deterministic testing [3][4] is also your best friend when it comes to testing distributed systems. [1] An introductory talk on VSR and it's deterministic view change — https://www.youtube.com/watch?v=Wii1LX_ltIs https://www.youtube.com/watch?v=Wii1LX_ltIs [2] James Cowling on determinism, working with Barbara Liskov — https://www.youtube.com/watch?v=ps106zjmjhw https://www.youtube.com/watch?v=ps106zjmjhw [3] FoundationDB are pioneers of deterministic testing — https://www.youtube.com/watch?v=OJb8A6h9jQQ https://www.youtube.com/watch?v=OJb8A6h9jQQ [4] TigerBeetle's deterministic simulation tests — https://github.com/coilhq/tigerbeetle#simulation-tests https://github.com/coilhq/tigerbeetle#simulation-tests