MST in Message-passing Model
The message-passing model is one of the most commonly used models in distributed computing. In this model, each process is modeled as a node of a graph. The communication channel between two processes is an edge of the graph.
Two commonly used algorithms for the classical minimum spanning tree problem are Prim’s algorithm and Kruskal’s algorithm. However, it is difficult to apply these two algorithms in the distributed message-passing model. The main challenges are:
- Both Prim’s algorithm and Kruskal’s algorithm require processing one node or vertex at a time, making it difficult to make them run in parallel. (For example, Kruskal's algorithm processes edges in turn, deciding whether to include the edge in the MST based on whether it would form a cycle with all previously chosen edges.)
- Both Prim’s algorithm and Kruskal’s algorithm require processes to know the state of the whole graph, which is very difficult to discover in the message-passing model.
However, Nobari et al. in proposed a novel parallel algorithm, PMA, that is parallelizing Prim’s algorithm.
Due to these difficulties, new techniques were needed for distributed MST algorithms in the message-passing model. Some bear similarities to Borůvka's algorithm for the classical MST problem.
Read more about this topic: Distributed Minimum Spanning Tree
Famous quotes containing the word model:
“The best way to teach a child restraint and generosity is to be a model of those qualities yourself. If your child sees that you want a particular item but refrain from buying it, either because it isn’t practical or because you can’t afford it, he will begin to understand restraint. Likewise, if you donate books or clothing to charity, take him with you to distribute the items to teach him about generosity.”
—Lawrence Balter (20th century)