A distributed peer to peer system for computing fractals, with load balancing (generating fractal images).
The peer to peer network is a complete graph where communication between nodes is asynchronous and non-FIFO.
The system can concurrently compute one or more fractals.
Fractals are computed using the Chaos game algorithm.
When nodes join/leave the network or new fractal jobs are initiated, the system reorganizes (rebalances) the workload.
A bootstrap node/server is used to connect/disconnect nodes to/from the network.
The user can request for an image to be generated (the entire fractal, or a specified part of it) using the computed data up until that moment.
The user can also ask for status information of all nodes in the system, which lists all active nodes with their work progress up until that moment.
The system supports scripted launching, for running multiple nodes simultaneously and providing input commands to nodes using text files as input.
To run the system, a MultipleServentStarter class is provided.
This class reads the configuration file and starts separate Node programs using the ProcessBuilder.
For each node program the System.out, System.err and System.in are redirected to files /output/serventID_out.txt, /error/serventID_err.txt and /input/serventID_in.txt, to allow the user to supply all nodes with input commands simultaneously.
The user can also interact with nodes using the CLI (command line interface).
The sending of each message is delayed by a small random amount to simulate a realistic distributed system (because the system is tested locally on one machine).
The bootstrap node keeps track of all nodes in the network, and has a known static address.
New nodes in order to join the network must contact the boot node which provides them with a random node from the network.
The new node exchanges information with the provided node, after whch a series of update messages are sent in multiple rounds to notify all the existing nodes about the new node.
Finally the new node contacts the boot node to finish the joining process.
The process of leaving the network is similar to the joining process.
Each node is assigned a fractal region which it computes. This region depends on the number of active nodes in the network and the number of vertices of the polygon from which the fractal is calculated.
A fractal region is the entire polygon or a sub-polygon. For an example:
If there are 3 nodes in the network and a triangle fractal is being computed, each node gets a different sub-triangle as a region to compute.
If a 4th node joins the network, no re-balancing occurs (two new nodes are required to subdivide an existing triangle (sub-triangle)). The new node is idle.
After the 5th node joins the network, a sub-triangle is divided into 3 smaller sub-triangles. Subdivision in to a new depth level occurs only if all regions are on the same depth level.
If multiple fractals are computed concurrently, nodes are equally split among them, and the workload for each fractal is then organized using the above explained method.
Seven nodes are active in the system and working on a triangle fractal.
The status command has returned the fractal region ID and number of iterations for each node.
In this example thanks to the region IDs we can see that Servent[1] is working on a sub-triangle of the original triangle, and the rest six servents are working on the six remaining sub-sub-triangles.
After starting a square fractal concurrently, the job is rebalanced and now 3 nodes are working on 3 sub-triangles of the original triangle, and 4 nodes are working on the 4 sub-squares of the original square.
Arguments in [] are optional
- status [X [id]] - Shows the work progress of each active node in the system (the fractal job and the fractal region that the node is working on, and the number of iterations it has done). The optional argument X specifies the fractal, and optional argument id the region of the specified fractal X.
- start X - Starts the job X from the configuration file.
- result X [id] - Generates a PNG image of the specified fractal, or a specified region of the specified fractal if the id is provided.
- stop - Disconnects a node from the system and shuts down the node program. If provided to the MultipleServentStarter class, the entire system shuts down.
Parameters are read and set during application launch and cannot be changed during operation.
File structure:
bootstrap=192.168.0.17,2000 - address and port of the bootstrap node
weaklimit=1000 - not used
stronglimit=2000 - not used
servent_count=7 - number of nodes to start
servent0=1100 - list of nodes with their port number
servent1=1200
servent2=1300
servent3=1400
servent4=1600
servent5=1700
servent6=1800
servent7=1900
job_count=4 - list of jobs which the user can start using the CLI
job0_name=trougao
job0_N=3 - number of verticies
job0_P=0.5 - chaos game algorithm parameter
job0_WH=1920x1080 - image resolution
job0_points=300,100;960,900;1620,100 - verticy coordinates
job1_name=kvadrat
job1_N=4
job1_P=0.5
job1_WH=1920x1080
job1_points=300,100;300,900;1620,900;1620,100
job2_name=petougao
job2_N=5
job2_P=0.3
job2_WH=1920x1080
job2_points=670,990;1250,990;1250,390;670,390;90,690
This project was an assignment as a part of the course - Concurrent and Distributed Systems during the 8th semester at the Faculty of Computer Science in Belgrade. All system functionalities were defined in the assignment specifications.
- Stefan Ginic - stefangwars@gmail.com