What are good algorithms for distributed purchasing?

Question

I'm looking for some algorithms/patterns to solve a distributed systems problem.

Lets say I have created a trading platform buying stock (I haven't), and I have a distributed system of 50 nodes that are making these purchases for me. I also know that I have a budget of 50ドルk, and it needs to be spent by the end of the day. I have some set of rules that determines whether or not to make the purchase, and if thats the case I purchase the stock.

How do I ensure that I don't exceed my budget when these purchases occur quickly across every node? So node 49 doesn't get the memo that we are out of money, and spends 20ドルK that I don't have.

Assume in this case, that a small amount overpurchase is acceptable, lets say 2% over time. We are also only concerned with the first discrete purchase beyond 50K, not a single purchase taking us from 49,999 to 50,100.

Are there good patterns that fit this sort of problem? Its seems similar to what Amazon or others might do for inventory management.

Thank you!

• Effie: here are some general pointers that might be useful: (0) there is a problem, called (distributed) consensus (1) the CAP theorem is a tradeoff between ensuring that data is synchronized and how fast the system responsds. (2) The C in CAP theorem can be achieved with algorithms, such as paxos and raft. there are a number of implementations available. I think there are a couple of other algorythms (3) the A part, also called eventual consistency. The classical example is Amazon Dynamo (there is a paper with this name). If this is what you need, you could probably look into gossip protocols too.
• Effie: i don't know which one of those is good for trading.

Answer 1

Your nodes will need to coordinate, otherwise the risk is unavoidable that they overspend. If you want there to be zero chance of overspending, then you might need a consensus algorithm, such as Paxos etc. If you are OK with a small amount of overspending (as it appears you are), you might be able to give each node a budget it can spend without coordination (e.g., up to \100ドル without coordinating), and have each node eagerly/optimistically spend up to that amount but waiting for the coordination algorithm to complete before spending more than that.

Some topics to learn about: https://en.wikipedia.org/wiki/State_machine_replication, https://en.wikipedia.org/wiki/Paxos_(computer_science), https://en.wikipedia.org/wiki/Raft_(algorithm).

Answer 2

DW answer is awesome - you could get a linearizable fault tolerant system to get you going.

But you could get the desired outcome in a much simpler way: have a one single database which will track all spendings one by one. Single database is by definition linearizable - single copy of data. When a node will want to execute a trade, the node will have to run a transaction first:

update Account set balance = balance - MoneyToSpend where balance >= MoneyToSpend and

Assuming your database executes these updates atomically (many dbs do, and if they don't you could use explicit SELECT FOR UPDATE), that will make sure you won't over spend.

Having a db is much simpler comparing to building or even understanding a consensus based strongly consistent system. But there is a trade off - singe db system is not 100% available, it can go down - the big question is if that's a real concern. Most system don't have 100% uptime SLA anyway