IMSuite: IIT Madras Benchmark Suite for Simulating
Distributed Algorithms

IMSuite Kernel Categorization

IMSuite implements twelve classical distributed algorithms as benchmark kernels. Considering the different popular parallel programming styles, IMSuite consists multiple variations for each kernel in two task parallel languages (X10 and HJ). These variations can be categorized under following two heads:

• Varying Synchronization Primitives - with and without fine grain synchronization primitives.
• Varying Forms of Parallelization - data parallel and recursive task parallel.

IMSuite Packaging

The IMSuite tar file consists of kernels subdivided under two heads - timing and characterization. The main intuition for this approach is summarized through following points:

Timing

• These kernels are specifically designed to measure the time taken by a benchmark kernel to execute.
• Each kernel part of this category provides a measure of the time taken in nanoseconds.
• The timing phase does not include time taken to initialize the data structures, print and validate the output.

Characterization

• These kernels measure the properties relevant to the distributed and parallel systems.
• We provide counters for measuring the total amount of dynamic communication and atomic/isolated operations.
• We also provide counters to calculate the communication per round.
• For the recursive kernels we provide counters for calculating dynamic async, finish and synchronization operations in addition to the other counters.

The kernels are further subdivided under following four language subsets:

• X10-FA - utilizes X10 constructs finish, async and atomic for task creation, join and mutual exclusion respectively. Here synchronization is achieved by joining/terminating the tasks and recreating them later.
• X10-FAC - utilizes the abstraction of clocks in addition to the constructs of X10-FA.
• HJ-FA - utilizes HJ constructs finish, async and atomic for task creation, join and mutual exclusion respectively.
• HJ-FAP - utilizes the abstraction of phasers in addition to the constructs of HJ-FA.

Benchmark Details

IMSuite consists of twelve classical algorithms covering important and complex problems in the domain of distributed systems such as breadth first search, consensus, routing table creation, dominating set, maximal independent set, committee creation, leader election, spanning tree and vertex coloring. A brief discussion on these classical algorithms follows:

1. Breadth First Search: We use two different breadth first search algorithms.
   • Bellman Ford: This algorithm assigns the breadth first search information in a general network for a given root node. It outputs the distance of every node from the root. The time complexity for the algorithm is O(D), where D is the diameter of the graph. The algorithm starts by marking the root node and setting its distance value to 0. The root node then increments the distance value by one and sends it to its neighbors. If a node receives a distance value smaller than its own value, updation takes place.
   • Dijkstra: This algorithm aims to create a breadth first spanning tree in a general network. It outputs the BFS tree that marks the parent and child (if any) node for each node in the network. The time complexity of this algorithm is O(D²), where D refers to the diameter of the graph. But compared to Bellmand Ford algorithm, it has a reduced message complexity of O(m + n × D). The algorithm starts by marking the root as the current tree. In each phase p, nodes at a distance p from the root are added to the current tree. Every newly added node echoes its arrival by sending an acknowledgement to its parent. Each node receiving an acknowledgement, echoes the acknowledgment back to its parent.
   
   
2. Byzantine Agreement: This algorithm aims at generating a consensus vote among the nodes of a network. The algorithm admits both " good " and " faulty " nodes. In each iteration, the good nodes share their vote with their neighbors, while the faulty ones may send arbitrary votes. Each node sets its own vote for the next iteration based on the votes it received in the current iteration. The time complexity of the algorithm is constant on expectation for complete graphs, and O(D) otherwise.
3. Dijkstra Routing: This algorithm aims to compute a routing table for each node in the network. Each node works independently and computes the routing table in parallel. The routing table contains information such as total cost of the path, next node on the path to the destination, total hop counts, and so on.
4. Dominating Set: This algorithm aims to find a dominating set by selecting nodes using a probabilistic method that depends on the neighbors at first and second level of a node. The algorithm creates a dominating set by coloring the nodes in a specific way:
   • Initially color of each node is assumed to be White, i.e. not part of a dominating set.
   • As a node becomes part of the dominating set then its color changes to Black.
   • Color of all the neighbors of a Black node is set to Grey.
5. k-Committee: This algorithm partitions the nodes of a network into committees of size at most k, where k is a given integer. In the current version of IMSuite we work with static networks. Initially each node in the network has a key value. The execution of the algorithm takes place in a set of k phases. In the initial phase, some of the nodes are designated as leaders -- the nodes whose key value is the minimum compared to all their neighbors at a distance ≤ k. In each subsequent phase, every node that is not associated with any committee and whose key value is minimum among all its non-leader neighbors at a distance ≤ k associates itself with a committee.
6. Maximal Independent Set: MIS utilizes a randomized algorithm to generate a maximal independent set of a set of nodes. In each iteration each eligible node generates a random number and one or more nodes get added to the MIS, if their random value is the smallest among all of their neighbors. The time complexity of the algorithm is O(log₂n) on expectation.
7. Leader Election: We implement three popular leader election algorithms. In each of these algorithms, every node in the network has a unique identifier and at the end of the algorithm the node with the highest identifier is selected as the leader.
   • LCR: This algorithm finds the leader for a set of nodes organized in a ring network, where the data flow is unidirectional. The distinguishing feature of this algorithm is its simplicity and negligible computation.
   • HS: This algorithm finds the leader from a set of nodes organized in a ring network, where the data flow is bidirectional. The algorithm works on the principle, that in each ongoing phase only the leader of the previous phase will be initiator of messages.
   • DP: This algorithm finds the leader for a set of nodes organized in any general network. We have implemented a synchronous version of the proposed algorithm. The algorithm computes the leader and the diameter of the network.
8. Minimum Spanning Tree: This algorithm generates a minimum spanning tree of a weighted graph. The algorithm starts by keeping every node as an independent fragment. The algorithm proceeds by joining fragments along the minimum weighted edge till all nodes are in the same fragment.
9. Vertex Coloring: This algorithm colors the nodes of a tree with three colors. The algorithm starts by initially coloring the nodes of the tree with six colors which takes O(log^*n) time. Next the algorithm uses a shift down operation (constant time) to color the tree using three colors.