4 ms·

No complexity is hidden here. Streamlet is (essentially) in the same setting as paxos. Just like in paxos, messages can take arbitrarily long to deliver. The o

No complexity is hidden here. Streamlet is (essentially) in the same setting as paxos. Just like in paxos, messages can take arbitrarily long to deliver. The only assumption is that clocks are synchronized, which is much, much weaker. (We can actually remove even this assumption. But it's easier to think about this way.) i.e. I think it's monday at the same time you think it's monday, or I think it's epoch 1 at the same time you think it's epoch 1. or my quartz crystal oscillates at the same rate as your quartz crystal. Importantly, a message sent during epoch 1 might arrive in epoch 3, or never at all. Paxos is also in the partially synchronous setting - it requires some network synchrony in order to terminate, just like streamlet (For truly asynchronous protocols, there's a whole, complicated literature).

the-smug-one 6y ago
>Paxos is also in the partially synchronous setting - it requires some network synchrony in order to terminate, just like streamlet As far as I've understood it Paxos is fully asynchronous, but you can either guarantee correctness or termination and never both for those systems. Paxos decided on correctness. Am I wrong in this?
- Vervious 6y ago
  Right, when run in a fully asynchronous setting, where the network adversary can always deliver messages in the order of their choice, the FLP impossibility result says that Paxos cannot terminate. Thus, for Paxos to make progress, the network needs to eventually "heal" and deliver messages in a timely manner -- that's what we mean by partial synchrony. Streamlet, likewise, tolerates arbitrary network delays (in the sense that no two players will agree on different things even if Comcast maliciously scheduled every message), but also requires partial synchrony to make progress (i.e. once in a while Comcast will deliver messages in timely fashion and in order, like you expect). (Partial synchrony is arguably the most practical of the theoretical synchrony models for consensus. There are other models, i.e. "periods of synchrony", but they all end up capturing the same idea). FLP, however, is a fairly weak statement. It only rules out termination for deterministic protocols. We can in fact design randomized asynchronous protocols that make progress (with good probability), regardless of the ordering in which messages are delivered. I.e. as long as Comcast eventually delivers every message -- and letting it choose delays arbitrarily -- a randomized protocol could make progress. These are the "true" asynchronous protocols. (Paxos is not one of them) I guess the original asynchronous consensus protocol is Ben-Or's protocol (which takes 2^n time in expectation IIRC, where n is the number of players). We can reduce the running time using some (fairly sophisticated) cryptography -- the most famous is the Canetti-Rabin protocol, and Cachin and many others have worked on it since. Most of the complexity (for polynomial time protocols) is in building a "global common coin" -- i.e. a global coin that everyone agrees on the result of; once you have that we can use Mostefaoui's protocol for instance. Building this coin is incredibly complicated (much more so than Paxos) unless we assume some strong cryptographic trusted setup (i.e. a nice threshold signature scheme). How practical any of these schemes are is an open question.
  - Vervious 6y ago
    (For more, Ittai Abraham has a series of nice posts: https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/ https://decentralizedthoughts.github.io/2019-06-01-2019-5-31...)

the-smug-one 6y ago

>Paxos is also in the partially synchronous setting - it requires some network synchrony in order to terminate, just like streamlet As far as I've understood it Paxos is fully asynchronous, but you can either guarantee correctness or termination and never both for those systems. Paxos decided on correctness. Am I wrong in this?

Vervious 6y ago
Right, when run in a fully asynchronous setting, where the network adversary can always deliver messages in the order of their choice, the FLP impossibility result says that Paxos cannot terminate. Thus, for Paxos to make progress, the network needs to eventually "heal" and deliver messages in a timely manner -- that's what we mean by partial synchrony. Streamlet, likewise, tolerates arbitrary network delays (in the sense that no two players will agree on different things even if Comcast maliciously scheduled every message), but also requires partial synchrony to make progress (i.e. once in a while Comcast will deliver messages in timely fashion and in order, like you expect). (Partial synchrony is arguably the most practical of the theoretical synchrony models for consensus. There are other models, i.e. "periods of synchrony", but they all end up capturing the same idea). FLP, however, is a fairly weak statement. It only rules out termination for deterministic protocols. We can in fact design randomized asynchronous protocols that make progress (with good probability), regardless of the ordering in which messages are delivered. I.e. as long as Comcast eventually delivers every message -- and letting it choose delays arbitrarily -- a randomized protocol could make progress. These are the "true" asynchronous protocols. (Paxos is not one of them) I guess the original asynchronous consensus protocol is Ben-Or's protocol (which takes 2^n time in expectation IIRC, where n is the number of players). We can reduce the running time using some (fairly sophisticated) cryptography -- the most famous is the Canetti-Rabin protocol, and Cachin and many others have worked on it since. Most of the complexity (for polynomial time protocols) is in building a "global common coin" -- i.e. a global coin that everyone agrees on the result of; once you have that we can use Mostefaoui's protocol for instance. Building this coin is incredibly complicated (much more so than Paxos) unless we assume some strong cryptographic trusted setup (i.e. a nice threshold signature scheme). How practical any of these schemes are is an open question.
- Vervious 6y ago
  (For more, Ittai Abraham has a series of nice posts: https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/ https://decentralizedthoughts.github.io/2019-06-01-2019-5-31...)