Computing strongly-connected components of graphs and their periods using a Pregel model

Our research focuses on attempting to implement algorithms related to the strongly-connected components of a graph and their periods in a parallel environment. We chose to explore the viability of achieving this goal through two different tools: the MASC programming model, and Google’s Pregel C++ library. Initial investigations suggest that either model is well-suited to our purposes; MASC provides a theoretical architecture that allows us to perform many different parallel operations in linear time; and Google’s Pregel library was specifically designed to implement graph algorithms in parallel, distributed environments. However, comparing both tools suggests Pregel might be of greater interest to us since it builds on a concrete and well-established system, the C++ programming language, as opposed to the MASC model, which remains largely theoretical at this time. That said, Pregel is not openly available at the time of this research. Therefore, we decided to explore how to produce an implementation of algorithms to compute strongly-connected components and their periods using Pregel-like functionality. The MASC model is very promising, but until physical MASC computers become widely available, concrete tools such as C++ libraries that follow the Pregel model will be more useful to our purposes.