Skip to content

25. Parallel W

Apr 21, 2021

Parallel Algo W

  • DO-ALL in message passing systems → can do in any setting with help from oracle
  • \(P=N\) algorithm W work = \(O(N^{\lg^2N/{\lg\lg N}})\)
    • in oracle model same analysis \(\forall W = O(N^{\lg^2N/{\lg\lg N}})\)
    • lower bound is the same \(\exists LB = \Omega(N^{\lg^2N/{\lg\lg N}})\)

Can we make this into a parallel algorithm? Oracle tells what to do → in parallel algorithm processors would need to be able to share knowledge to know what work remains.

One strategy:

  • broadcast your knowledge to everyone
  • assume synchronous environment then everyone has a consistent view of the remining work
  • it may not be fully consistent if there is a broadcast and crash before message reaches every node
  • each crash causes inconsistent knowledge, but can happen at most once
  • work when broadcasting \(W = O(\frac{\lg^2N}{\lg\lg N})\)
  • message complexity is bad: \(M = \Omega(N^2)\)

Would be nice to have an infallible leader who would broadcast to all

  • all would have locally consistent knowledge
  • \(M\) becomes \(\Omega(N)\)

...but we do not know who this leader is.