Introduction to Distributed Computing
Notes
- This is not in the book, I am pulling from many sources.
- Distributed is a subset of parallel computation
- I will use the terms incorrectly and differentiate between the two.
- Multiprocessor is probably a better term than parallel, but ...
- We will look at a semi "hardware" definition here.
- Distributed vs Parallel
- A parallel computer typically will have multiple CPUs/cores
- PRAM - parallel random access machine
- A shared clock
- A shared memory
- Generally we have atomic operations
- We can do a check/save on a memory location uniquely in one process on one cpu/core
- Stable communications
- Generally we assume nothing breaks.
- Generally the system is well known
- A distributed computation will typically have many computers
- No shared clock/memory
- Communications may or may not be reliable
- Computers may be removed from the computation.
- Unreliable communications/nodes in the computation
- It is possible that the system is not well known
- Distributed computations are subject to some of the same problems as parallel computations.
- Race conditions
- Exact order of execution of instructions is deterministic in a sequential computation
- It is no longer predictable in multi-threaded computations.
- Sometimes this causes problems.
- Deadlock
- Computations frequently need to share a resource
- For multiple resources, a problem occurs if two or more processes need two or more resources.
- Each process holds one resource and is waiting for the other
- This is deadlock
- An easy example in all cases is the dining philosophers
- A though experiment by Edsger Dijkstra
- There are n>2 philosophers sitting at a round table.
- Each has a plate of spaghetti in front of them.
- Each has 1 fork.
- But they need two forks to eat.
- So there is a fork between each of the philosophers
- A philosopher either thinks or eats.
- When a philosopher decides to eat they pick up the forks and eat
- Do you see the deadlock potential here?
- Assume that we have very regimented philosophers.
- Each thinks for a set amount of time.
- Each picks up the fork on their right at the same time
- Each waits (forever) for the fork on their left.
- Deadlock!
- Deadlock is easily overcome in parallel computation by atomic instructions
- This is an OS topic, but it involves a hardware instruction that does a compare and assignment without interruption.
- But no such thing is available in distributed.