Skip to content

1. Parallel Computation

Jan 11, 2021

Sequential vs. parallel worlds

According to Leslie Vallant, success of sequential computation is based on 3 factors:

  1. Universal notation - high level languages - studied in algorithms/programming
  2. Simple and reliable model - studied in comp org./architecture
    • if possible to do on a Turing machine, it may be realizable on a real computer
  3. Efficient and effective mapping - compilers
    • compilers run in linear time

In parallel computation:

  • no universal language/notation
  • no simple model
  • no efficient mapping

Performance always depends on architecture and algorithms cannot be separated from architecture.

2 generals problem

Goal: agree on a time to meet by exchanging messages

Setting: messages may or may not get through communication channel. Assume a finite solution exists. The very last message is to confirm receipt.

Let \(k\) be the optimal (minimum) number of messages needed to reach goal. This leads to a contradiction: if \(k\) is minimum, message to agree on time would have had to occur at time \(k-1\), \(k-2\), \(k-3\) ... etc. Cannot reliably solve in presence of dynamic failures.

Triple modular redundancy (TMR)

Have 3 machines solve the same problem and choose majority answer.

This doesn't work with 3 processors if there is a malicious/failing processor, proof by Leslie Lamport (see Paxos).