1. 为什么在MapReduce计算模型之外还需要图并行计算模型？图并行计算框架与MapReduce批处理模型的主要差别在哪里？
参考答案：现实世界中有很多应用数据更适合以网络或图的形式展现。比如Facebook，Twitter，新浪微博，人人等大型社交网络中存在的Web社团，这种社交网络数据最适合用网络图来表示。这类以图（graph）形式表征的数据在大数据系统需要处理的数据量中占了相当一个比例（Google公司提到其搜索引擎处理的数据量中有20%是由图处理引擎完成），因此需要一个针对这类网络图计算问题的计算模型。
许多图计算问题算法都带有全局循环迭代（iteration）步骤（如求解单源最短路径问题的Dijkstra算法、最大流/最小割问题（Max-Flow Min-Cut）、数据聚类K-means算法等）,而 MapReduce计算模型是一种典型的批处理（batch processing）模式，即数据计算是按照流水线方式执行，完成第一步，才会执行第二步；每一步内可能有大量的并行处理线程，但没有跨越很多步的迭代循环计算。因此图计算问题对于批处理计算模型是一个难题。
与MapReduce批处理模型比较，图计算模型具有如下特点：1）图计算问题具有全局性，计算过程中有大量节点间通信；2）图算法需要完成全局循环迭代步骤；3）图分割问题（即将一个大图的数据集划分为小图的子数据集）很复杂。
2. 图并行计算系统目前有三种技术方案：基于BSP模型的Pregel和Hama，基于节点计算（vertex-program）的GraphLab，以及图数据库Neo4j和InfiniteGraph，试论述三种技术方案的差异。
参考答案：基于BSP模型的图并行计算模式（Pregel, Hama）采用Master/Slave计算架构，与Hadoop平台架构能较好地匹配。它采用全局同步（Superstep和Synchronization Barrier）方式来实现计算同步与节点间通信，具有简便易行、编程界面友好的特点。
GraphLab采用了基于节点计算（vertex-program）的GAS（gather-apply-scatter）模型来处理图并行计算，其并行机制与Pregel/HAMA不一样，它把计算任务分解到各个独立计算节点（Map），但各计算节点与其相邻节点之间存在data-dependency和computation-dependency，即某个节点计算的下一步还需取决于相邻节点的计算状态。由于GraphLab没有一个全局时钟来实现同步控制，因此每个节点的程序需要提供同步功能。
图数据库（Neo4j, InfiniteGraph）则是将社交关系图（graph）描述为点（vertex）、边（edge）及它的属性（property），这里“点”代表实体，比如人、企业、账户或其他任何数据项，类似于关系数据库中的数据记录或文档数据库中的文件；“边”则代表点与点之间的关系；“属性”则是“边”所包含的用户关注的特性。图数据库更多是以图的数据存储方式的角度去提供图数据查询解决方案。
三者的主要差别在于前两者侧重于支持各种图算法（计算模型有差异），而第三者侧重于支持图数据存储与查询。
3. 为什么Pregel的节点间通信必须被局限在超步之间的障碍期（barrier）进行？不这样做会导致什么后果？
参考答案：Pregel设计了各顶点的计算都在节点本地进行，各顶点计算是独立的，没有对其他顶点计算结果或计算逻辑上的依赖性，这就决定了没有顶点之外的资源竞争，因此避免了分布式异步计算系统中容易发生的deadlock。顶点间的通信被局限在超步之间的barrier期间完成（每个顶点可以在超步内送出给其它顶点的消息，但这些消息不会马上处理。当这个超步结束时下一个超步开始前（即barrier期间），所有的顶点统一处理它们各自收到的消息）可使得：1）实现一种统一的顶点间全局通信机制（barrier期间全部顶点都进行通信）；2）各顶点上的迭代循环计算不受到其他顶点的牵扯。
如果不采用这种统一的障碍期（barrier）全局通信机制，而容许顶点之间可以随时发送消息，接收到消息的顶点随时处理，势必造成顶点相互间的计算依赖关系，大大影响计算速度或导致顶点处的迭代循环无法进行。
4． 在BSP模型中，消息发送和接收的Combiner机制可在发送节点实现，也可以在接收节点实现。什么时候我们选择在发送节点实现Combiner？什么时候选择在接收节点实现Combiner？各自的目的是什么？
参考答案：在BSP模型中，多个顶点（vertex）可能同时向另一个顶点发送消息，如图所示，节点Worker 1上的顶点V0，V1, V2都向Worker 3上的顶点V6发送消息。但在某些算法设计中，接受顶点关注的并不是每一个发送顶点的单独值，而可能是其中的最大值或是求和值。这种情况下，Pregel提供了Combiner机制来合并发出消息，使得多个顶点发给同一目标点的多个消息可以先合并成一条消息，然后再发出。
如果目的是减少消息传递开销、降低网络流量负担，这种Combiner功能可以在发送端实现，将多条消息合并为一条再发出；如果为了在接收端加快处理进度，可以将Combiner在接受端实现（图中的Worker 3的Combiner）。需要注意，接收端Combiner并没有降低网络流量。
5． 节点通信中Combiner的使用是为了降低节点间网络通信开销，更有效地使用网络资源。但是不是所有节点计算都适用Combiner？使用Combiner时需遵循的一条准则是什么？
参考答案：使用Combiner时需遵循的准则是：不管是在发送端还是接收端，对消息的combine处理（实际是一种预处理）都不能影响最终的计算结果的正确性。也即是，不管是否进行combine处理，其最终计算结果都是一样的（使用Combiner只是降低了网络流量或是加快了处理速度）。这就要求combine操作应该符合交换律和结合律。
6． 参照图12-18的最大值算例，若将问题改为需要将最小值传播到每个项点，列出传播过程的各个超步步骤。
参考答案：如果图12-18的算例改为最小值问题，则问题变为：给定一个有向连通图，图中每个顶点都包含一个值，它需要将最小值传播到每个顶点。在每个步骤中，顶点会从接收到的消息中选出一个最小值，并将这个值传送给其所有的相邻顶点。当某个步骤已经没有顶点更新其包含值，那么计算就告结束。
按照Pregel的设计，所有的顶点值的更新都在超步内；每个顶点只在超步结束时向其所有邻接点发送消息（传送顶点值）。当一个顶点收到的消息中含有值比它目前值小，则用最小的一个值替换它目前值，状态设置为“活跃”，否则就将状态改为“非活跃”；当所有顶点状态为“非活跃”时，计算结束。
计算过程如下（参加上图）：
超步 0：A，B, C, D四个顶点状态均设为“活跃”，各自包含一个初始值；
超步 1：A向B传送值3；B接受A的消息值3，用3替代目前值6，B保持为
“活跃”；B向A和D传送值6，B接受C的消息值2，B用2代替3，B状态为“活跃”；A的值不变（因为3<6），状态改变为“非活跃”；C向B和D传送值2，C接受D的消息值1，C值改变为1，状态为“活跃”；D向C传送值1，D接受A的消息值6，D的值保持为1，D状态改变为“非活跃”；
超步1结束时，A，B, C, D四个顶点的即时值分别为3, 2，1，1，状态分别为“非活跃”，“活跃”，“活跃”，“非活跃”；
超步 2：我们只对状态是“活跃”的顶点执行操作，B向A传送值2，A的值替换为2，因此A状态变为“活跃”；B向D传送值2，D收到后保持原来值1不变，D的状态仍然为“非活跃”；C向B发送值1，B收到后更换为1，B状态仍然为“活跃”；C向D发送值1，D收到保持原来值1不变，C状态变为“非活跃”。
超步2结束时，A，B, C, D四个顶点的即时值分别为2, 1，1，1，状态分别为“活跃”，“活跃”，“非活跃”，“非活跃”；
超步 3：此时有顶点A和B状态是“活跃”，只需对顶点A和B执行操作。A向B传送值2，B收到不需更新，因此B状态又变为“非活跃”；B向A发送消息值1，A替换为1，A状态更新为“活跃”；B向D发送消息值1，D不做更新，D状态保存为“非活跃”。
超步3结束时，A，B, C, D四个顶点的即时值分别为1, 1，1，1，状态分别为“活跃”，“非活跃”，“非活跃”，“非活跃”；
超步 4：此时只有顶点A状态是“活跃”，只需对顶点A执行操作。A向B传送值1，B收到不作更新，因此A状态又变为“非活跃”。
超步4结束时，A，B, C, D四个顶点状态全部为“非活跃”，且下一步无消息产生（只有“活跃”状态的顶点才能发消息），至此计算全部结束。
