Prom: An Asynchronous Distributed Framework for Graph Algorithms

---

1. Introduction

Prom is a distributed framework targeted at the class of graph algorithms that need to propagate messages between vertices while the structure of the graph is fixed. Many graph algorithms fall into this class, such as Belief Propagation and Personalized Pagerank. Prom supports vector messages, flexible update functions, and prioritized block scheduling. These features are important to accommodate a broad class of algorithms and to accelerate algorithms. The design of Prom is introduced in the paper Scalable Distributed Belief Propagation with Prioritized Block Updates, (Jiangtao Yin and Lixin Gao) in CIKM 2014. The paper uses Belief Propagation as a running example.

Prom is a MPI based framework, which can run on hundreds of machines or in the cloud. It is implemented by modifying Maiter.

2. Usage

Download the package, Prom-0.1.tar.gz, 

Before using Prom, you will need to modify conf/mpi-cluster to point out the machines that Prom will be running on. Also, make sure every machine has one copy of Prom.

To run the built-in algorithm (Belief Propagation) on your own data, you must preprocess the data. The input  data needs to be split into a number of partitions. The number of partitions should be the same with the number of workers you configured.

Then type the following command on any worker machine to run the algorithm (e.g., the SumProduct verion of Belief Propagation).

"./prom --runner=SumProduct --workers=? --graph_dir=? --result_dir=? --num_nodes=? --snapshot_interval=? --portion=? --termcheck_threshold=?". Replace the question mark with your settings. 

If you would like to implement other graph algorithms on Prom. Several things need to be done.

2.1 Preparing a compiling environment 

Prom is C++ framework and uses OpenMPI as well as Protocol Buffers (from Google) for communication. Hence, the following packages are necessary:
    CMake
    OpenMPI
    Python
    gcc/g++
    Protocol Buffers

2.2 Programming on Prom

In order to be able to program on Prom, you should have read the CIKM paper mentioned in the introduction section. To start, create your .cc file in the src/example directory. The code already in that directory would be a good example. Then, complete the .cc file. Also, add the name of your .cc file into the CMakeLists.txt file in the same directory.

2.3 Building and Running

To build, simply run the build.sh shell script in the top level directory of Prom.

Running the implemented algorithm is similar with running the built-in algorithm. In the command, set runner as the implemented algorithm and fill other parameters according to your settings.


Please contact Jiangtao if you run into any issues (jyin AT ecs DOT umass DOT edu).