4 ms·

I like how the article steps through and examines the key points of Paxos with a relatable scenario. Still a complicated subject for sure. Makes me want to go h

by altendo 10y ago

I like how the article steps through and examines the key points of Paxos with a relatable scenario. Still a complicated subject for sure. Makes me want to go home and implement a working version for myself.

defenestration 10y ago
Here you can find an example in JavaScript that visualizes the Paxos algorithm: http://harry.me/blog/2014/12/27/neat-algorithms-paxos/ http://harry.me/blog/2014/12/27/neat-algorithms-paxos/
sillysaurus3 10y ago
It's surprisingly easy to fool oneself into thinking they've successfully implemented Paxos. You may want to try 6.824: Distributed Systems https://pdos.csail.mit.edu/6.824/ https://pdos.csail.mit.edu/6.824/ I learned a lot from working through the online coursework. Alternatively, download the labs and see the wide variety of unit tests. There are a few devilishly difficult ones.
peterwwillis 10y ago
If you want a system that's going to "just work" and not be complicated or potentially error-prone (what happens when too many nodes don't respond?), use synchronous distributed design. Paxos has its uses, but I would argue they're few and far between.
- justinsaccount 10y ago
  What is "synchronous distributed design"? Where all nodes have to respond and the entire system blocks until they do?
  - m00dy 10y ago
    2PC is a nice algorithm for it.
    - justinsaccount 10y ago
      Right... 2PC is where all nodes have to respond and the entire system blocks until they do.
  - duaneb 10y ago
    Depending on your needs, that may be sufficient. It's certainly much simpler if you can tolerate a higher rate of downtime.
  - pablo_honey 10y ago
    To answer your question, Fundamentally a Synchronous distributed design has nodes in the system set an upper limit on how long it takes for things to happen, like max RTT and computation time. Algorithms based on synchronous systems are much simpler but theyre also unrealistic both in theory and usually in practice as well (without clever hacks handling edge cases). For example its difficult to set time limit on how long a node on the internet will take to respond. One may reasonably say 10 seconds max, but what happens on the day it takes 10.1 seconds? The system collapses. Asynchronous systems do not consider time at all so they don't suffer from those classes of problems but algorithms based on them are more complex.
- DblPlusUngood 10y ago
  If you don't care about tolerating a single failure, then yes, pretending the network is synchronous can simplify your system.
  - peterwwillis 10y ago
    Uh. Synchronous distributed systems tolerate failure just fine. It's a distributed system. You expect failure. Hell, failure happens in all kinds of systems and components. If your applications (and system) can't cope with that you won't last long.
    - DblPlusUngood 10y ago
      What exactly do you mean by "synchronous"? Do you have a particular system in mind? If you mean "block waiting for all replicas to respond", then the failure mode is quite different from Paxos. I don't know of one such system that can tolerate two simultaneous failures or network partitions, unlike Paxos.
      - peterwwillis 10y ago
        Well first of all, for Paxos to survive 2 failures it would need 5 nodes; Paxos won't work very well for smaller networks, and a bad network design [or lack of good maintenance] could take out a majority or all of your nodes, making the whole system worthless. Second, most systems don't need atomic write operations to succeed across network partitions, when network partition is even a concern (for general operations), which it isn't usually. If your network is partitioned, you can't really "decide" anything until it un-partitions, at which point you don't need to come to consensus if you have simpler methods of solving discrepancy - like using a higher level decision process than block-level or database-level. Even after the discrepancy is solved, network-wide changes may have invalidated the initial partitioned operations. Paxos tries to over-simplify a complex operation. When it is a concern, application design often trumps system design in terms of reliable operation. It completely depends on your network, system, platform and application design. In general, you won't need Paxos to reap the benefits of distributed systems, and synchronous systems will give you more benefits and less headaches.
- acjohnson55 10y ago
  Interesting. I'm working on an auction platform, and I created something called Atomic Store [1] to enforce consistency in an Akka-based append-only log deployed on a cluster. But it relies on the logs being singletons. I suppose another way to do it would be to have the logs not be singletons, but have them use two-phase commit, or something similar, to keep the whole thing synchronized. [1] https://github.com/artsy/atomic-store https://github.com/artsy/atomic-store

by altendo 10y ago

defenestration 10y ago

Here you can find an example in JavaScript that visualizes the Paxos algorithm: http://harry.me/blog/2014/12/27/neat-algorithms-paxos/ http://harry.me/blog/2014/12/27/neat-algorithms-paxos/

sillysaurus3 10y ago

It's surprisingly easy to fool oneself into thinking they've successfully implemented Paxos. You may want to try 6.824: Distributed Systems https://pdos.csail.mit.edu/6.824/ https://pdos.csail.mit.edu/6.824/ I learned a lot from working through the online coursework. Alternatively, download the labs and see the wide variety of unit tests. There are a few devilishly difficult ones.

peterwwillis 10y ago

If you want a system that's going to "just work" and not be complicated or potentially error-prone (what happens when too many nodes don't respond?), use synchronous distributed design. Paxos has its uses, but I would argue they're few and far between.

justinsaccount 10y ago
What is "synchronous distributed design"? Where all nodes have to respond and the entire system blocks until they do?
- m00dy 10y ago
  2PC is a nice algorithm for it.
  - justinsaccount 10y ago
    Right... 2PC is where all nodes have to respond and the entire system blocks until they do.
- duaneb 10y ago
  Depending on your needs, that may be sufficient. It's certainly much simpler if you can tolerate a higher rate of downtime.
- pablo_honey 10y ago
  To answer your question, Fundamentally a Synchronous distributed design has nodes in the system set an upper limit on how long it takes for things to happen, like max RTT and computation time. Algorithms based on synchronous systems are much simpler but theyre also unrealistic both in theory and usually in practice as well (without clever hacks handling edge cases). For example its difficult to set time limit on how long a node on the internet will take to respond. One may reasonably say 10 seconds max, but what happens on the day it takes 10.1 seconds? The system collapses. Asynchronous systems do not consider time at all so they don't suffer from those classes of problems but algorithms based on them are more complex.
DblPlusUngood 10y ago
If you don't care about tolerating a single failure, then yes, pretending the network is synchronous can simplify your system.
- peterwwillis 10y ago
  Uh. Synchronous distributed systems tolerate failure just fine. It's a distributed system. You expect failure. Hell, failure happens in all kinds of systems and components. If your applications (and system) can't cope with that you won't last long.
  - DblPlusUngood 10y ago
    What exactly do you mean by "synchronous"? Do you have a particular system in mind? If you mean "block waiting for all replicas to respond", then the failure mode is quite different from Paxos. I don't know of one such system that can tolerate two simultaneous failures or network partitions, unlike Paxos.
    - peterwwillis 10y ago
      Well first of all, for Paxos to survive 2 failures it would need 5 nodes; Paxos won't work very well for smaller networks, and a bad network design [or lack of good maintenance] could take out a majority or all of your nodes, making the whole system worthless. Second, most systems don't need atomic write operations to succeed across network partitions, when network partition is even a concern (for general operations), which it isn't usually. If your network is partitioned, you can't really "decide" anything until it un-partitions, at which point you don't need to come to consensus if you have simpler methods of solving discrepancy - like using a higher level decision process than block-level or database-level. Even after the discrepancy is solved, network-wide changes may have invalidated the initial partitioned operations. Paxos tries to over-simplify a complex operation. When it is a concern, application design often trumps system design in terms of reliable operation. It completely depends on your network, system, platform and application design. In general, you won't need Paxos to reap the benefits of distributed systems, and synchronous systems will give you more benefits and less headaches.
acjohnson55 10y ago
Interesting. I'm working on an auction platform, and I created something called Atomic Store [1] to enforce consistency in an Akka-based append-only log deployed on a cluster. But it relies on the logs being singletons. I suppose another way to do it would be to have the logs not be singletons, but have them use two-phase commit, or something similar, to keep the whole thing synchronized. [1] https://github.com/artsy/atomic-store https://github.com/artsy/atomic-store