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 }^{2}N/\lg \lg N})$
  • in oracle model same analysis $\mathrm{\forall }W=O(N^{{\lg }^{2}N/\lg \lg N})$
  • lower bound is the same $\mathrm{\exists }LB=\mathrm{\Omega }(N^{{\lg }^{2}N/\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 }^{2}N}{\lg \lg N})$
• message complexity is bad: $M=\mathrm{\Omega }(N^2)$

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

• all would have locally consistent knowledge
• $M$ becomes $\mathrm{\Omega }(N)$

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