Communications and Coordination
Notes
- Most distributed systems involve some form of message passing
- In PRAM machines, you can copy data between memory locations
- In distributed you need to send the data over an interconnection network.
- Distributed systems are connected with a network.
- This can be commodity (ethernet of some form, wireless, ...)
- Or it can be specialized like InfiniBand, which is apparently on the way out.
- It can be reliable or unreliable.
- But it is memory speed at best, so 10-1000 times slower than the cpu
- This means that moving data around between machines is slow.
- Distributed mergesort is probably a bad idea.
- It can be in-order or not
- When there are multiple routes through the network, messages, from the same sender, can possibly arrive out of order.
- It can be synchronus or asynchronus
- Ie we can just send a message (asynch)
- Or we can send a message and wait for it to be received. (synch)
- For asynch we can have multiple messages in flight at the same time.
- The "Two Generals Problem"
- Just so Connor can completely drive me nutty in the next ten minutes :)
- In a strange 2D world, two generals are sitting on either side of a city they want to attack
-
2 0 \|/ \|/ | | 1 / \ / \ \|/ /======== =======\ | / \ / \ / \==========/ - 0 wants to send a message to attack to 2
- But when 0 sends the message 1 might intercept it
- So 0 needs to be sure the message got back
- They need an ack from 2
- 2 recieves the message, but wants an ack from 0 that said they got the ack.
- ...
- There is no solution
- This is an example of a consensus problem.
- But acceptable solutions have been found.
- Consensus requires
- All participating nonfaulty processes agree on the same value
- The agreed-upon value must be valid
- The process will terminate.
- Byzantine Generals Problem
- Leslie Lamport
- "We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action."
- One possible scenario
- Three players, a commander and two Lt Generals
- Command is either attack or retreat
- Sending reliable messages
- Lt General is a trator (sends opposite of what they recieve) , they will do opposite things as they got opposite messages
- Commander is a trator (sends two different messages)
- They can not reach consensis.
- Repeat this with four generals.
- Consuses is possible.
- Leslie Lamport