title: Internal working of Spark - Communication/Synchronization
body: <p>I am quite new to Spark but already have programming experience in BSP model. In BSP model (e.g. Apache Hama), we have to handle all the communication and synchronization of nodes on our own. Which is good on one side because we have a finer control on what we want to achieve but on the other hand it adds more complexity. </p>
  
  <p>Spark on the other hand, takes all the control and handles everything on its own (which is great) but I don't understand how it works internally especially in cases where we have alot of data and message passing between nodes. Let me put an example</p>
  
  <pre><code>zb = sc.broadcast(z)
  r_i = x_i.map(x =&gt; Math.pow(norm(x - zb.value), 2))
  r_i.checkpoint()
  u_i = u_i.zip(x_i).map(ux =&gt; ux._1 + ux._2 - zb.value)
  u_i.checkpoint()
  x_i = f.prox(u_i.map(ui =&gt; {zb.value - ui}), rho)
  x_i.checkpoint()
  x = x_i.reduce(_+_) / f.numSplits.toDouble
  u = u_i.reduce(_+_) / f.numSplits.toDouble
  z = g.prox(x+u, f.numSplits*rho)
  r = Math.sqrt(r_i.reduce(_+_))
  </code></pre>
  
  <p>This is a method taken from <a href="https://github.com/dieterichlawson/admm/blob/master/code/src/main/scala/admm/solver/ConsensusADMMSolver.scala" rel="nofollow noreferrer">here</a>, which runs in a loop (let's say 200 times). x_i contains our data (let's say 100,000 entries). </p>
  
  <p>In a BSP style program if we have to process this map operation, we will partition this data and distribute on multiple nodes. Each node will process sub part of data (<strong>map</strong> operation) and will return the result to master (after barrier synchronization). Since master node wants to process each individual result returned (centralized master- see figure below), we send the result of each entry to master (<strong>reduce</strong> operator in spark). So, (<strong><em>only</em></strong>) master receives 100,000 messages after each iterations. It processes this data and sends the new values to slaves again which again start processing for next iteration. </p>
  
  <p>Now, since Spark takes control from user and does internally everything, I am unable to understand how Spark collects all the data after map operations (asynchronous message passing? i heard it has p2p message passing ? what about synchronization between map tasks? If it does synchronization, then is it right to say that Spark is actually a BSP model ?). Then in order to apply the reduce function, does it collects all the data on a central machine (If yes, does it receives 100,000 messages on a single machine?) or it reduces in a distributed fashion (If yes, then how can this be performed ?)</p>
  
  <p>Following figure shows my reduce function on master. x_i^k-1 represents the <em>i</em>-th value calculated (in previous iteration) against x_i data entry of my input. x_i^k represents the value of x_i calculated in current iteration. Clearly, this equation, needs the results to be collected.</p>
  
  <p><a href="https://i.stack.imgur.com/5ewgA.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/5ewgA.png" alt="enter image description here"></a></p>
  
  <p>I actually want to compare both styles of distributed programming to understand when to use Spark and when to move to BSP. Further, I looked alot on the internet, all I find is how map/reduce works but nothing useful was available on actual communication/synchronization. Any helful material will be useful aswell.</p>