SE$454$ Term Project

Deadline for demos and reports: $04\mathrm{.}01\mathrm{.}2024$ class time

Object: Realization of a Distributed Vertex Coloring Algorithm Using Python and

mpi$4$py$.$ The aim of this project is to design and implement a distributed vertex coloring

algorithm using SSI model of communication. This model requires to have a spanning

tree built prior to the working of the algorithm to implement synchronous rounds. You

may assume such a tree is built and you can assign parents and children to the nodes as

you like.

At each round any unassigned node that has the highest rank among its neighbors selects

an unused color and colors itself and notifies its neighbors of its choice.

You can work in groups of two. If you do$,$ each member is responsible for the whole of

the project.

Procedure:

High Level Design:

Provide high level design of the distributed algorithm using a finite state ma$-$

chine $($FSM$)$ diagram with descriptions.

Convert FSM to FSM table.

Provide pseudocode of the algorithm or pesudocode of the actions with brief

comments.

Detailed Design: $($Using actions is optional$)$ Convert actions to Python code and

implement the algorithm using mpi$4$py$.$ You can implement without using actions.

Demo: Show the operation of the algorithm for the sample network represented

by the graph in Fig. $1$

Figure $1$: A sample graph for Demo

Report: Your report should contain description of high level design with FSM diagrams

and FSM table. Either give the pseudocode of actions or the pesudocode of the whole

algorithm. Send your Python code as assignment in blackboard.

Grading

Demo $40\%$

Report $60\%$ including design