CODEWITHSUNDEEP
c#algorithmvisual-studiosimulationdistributed-computing
Sach
Sach

Reputation: 10393

Visual Simulator for Distributed Leader Election Algorithm

This is going to be a little long, so bear with me.

I have written a Visual Studio C# Console program to simulate distributed leader election algorithms in unidirectional ring networks.

Let me briefly describe the leader election problem first: imagine you have a ring network comprising of nodes who have unique (or non unique, but let us consider the case of unique) IDs assigned to each of them. Each of them have the same program (algorithm). Messages can be passed between only the neighbors, in one pre-determined direction (CW or CCW). Once the algorithm is completed, one node has to be elected as the 'leader', and all the other nodes should know that a leader has been elected AND the leader's ID.

The simplest of them all, the LCR algorithm (which I've used), is as follows. At step 1, each node sends their own ID in a message to their (say) CW neighbor. This implies everyone receives one too. Once you receive a message:

This way, after n-steps (n = size of the network), only the node with the largest ID remains active and is elected as leader. Then it sends a message around the ring informing everyone that it is the leader, and when it gets that message back, we complete the execution.

I have written a Console program as follows. I have my main program, and I have my algorithm in a separate DLL. The DLL has a TimeTick() function inside which are all the steps of the algorithm. From my main program, I repeatedly call the TimeTick() function at a user specified time interval, say, 10ms. So one execution of TimeTick() in my program is analogous to one message passing 'step' in the algorithm. I have access to all the important variables in the DLL, so from my main program I can know each node's state, whether it is active or not, whether it knows a leader is being elected and so on.

Here's a sample screenshot of the execution of the following ring: 1-3-2 in clockwise order.

enter image description here

Don't worry about all the clutter, pay attention to the 'Active' and 'Elected' columns. Those represent the state of two variables in each node. If true, it means active and it knows the elected leader respectively.

Now, I want to convert this into a visual program. That is, I want to display a ring of nodes at each TimeTick(), and display them in one color if Active == TRUE and put a cross over each if Active == FALSE. Furthermore, I want to display next to each node the state of various variables in the node. For example, the above execution, if displayed visually the way I want it would look like the following. Each ring is what is displayed at each time step.

Click to enlarge

How would I go about this? Before I dive into it I'd like to get a few opinions from you people, hence the post.

My first question, I don't know the ring size until the run-time, so how would I display my 'nodes' at run-time? I assume I'd have to use a picture-control or something similar. I know I can't show a large number of nodes so I have the freedom to limit the size of the ring. Basically, I want to space out the number of nodes I have in a circle-orientation, at equal distances.

I would also like to have, as shown in the example image, status of various variables displayed next to each other. So should I perhaps create a new class which contains all the stuff I want to display, then attach it somehow to the picture-control?

Any tips leading me in a good direction would be handy!

Upvotes: 3

Views: 843

Answers (2)

Olivier Jacot-Descombes
Olivier Jacot-Descombes

Reputation: 112324

You have a lot of options. A relatively simple one it to draw a graphic on a custom WinForms control using the namespace System.Drawing (GDI+). You will not need more performing but also much more complicated game engines for this simple graphic. GDI+ is pretty fast. Drawing your own graphic gives you the flexibility of producing any type of shape in any color in variable configurations and to draw text as well.

Simply create a custom control by deriving a class from System.Windows.Forms.Control. After compiling, this control will automatically appear in the Toolbox of the Form designer and you can drag and drop it on a form surface.

public class ElectionDisplayControl : Control
{
    public ElectionDisplayControl()
    {
        this.DoubleBuffered = true;
    }

    protected override void OnPaint(PaintEventArgs e)
    {
        Graphics g = e.Graphics;
        g.SetHighQuality();

        // TODO: put your drawing logic here!
    }

    protected override void OnResize(EventArgs e)
    {
        Invalidate();
        base.OnResize(e);
    }
}

It is important to understand that you should not draw by calling the OnPaint method directly. Instead call the Invalidate method of your control at each TimeTick. Windows decides when the control has to be redrawn and calls OnPaint when necessary. (For instance when your control was hidden behind another form and now becomes visible.)

// At each tick:
electionDisplayControl1.Invalidate();

DoubleBuffered eliminates flicker. It is good to redraw the control when it is resized. You could anchor the control to the edges of your form in order to allow the user to resize it by resizing the form. It is a good idea to determine the size of the shapes relative to the size of the control. This creates an automatic zoom effect. You can easily adapt the coordinate system with g.ScaleTransform(sx, sy); and g.TranslateTransform(dx, dy);.

You can find a tutorial here: GDI+ & Graphics GDI+ Tutorial for Beginners (and many others here).

How to evenly distribute shapes on a circle? Well you need some math. Calculate point on a circle at angle phi (assuming the center of the circle at { x = 0, y = 0 }):

x = radius * cos(phi)
y = -radius * sin(phi)

The minus sign for y is because the y-axis is pointing downwards in GDI+. The static System.Math class expects the angles in radians, i.e., a full circle = 2 * pi.

I forgot: SetHighQuality is one of my extension methods. Here it is with some other useful ones:

public static class GraphicsExtensions
    public static void SetHighQuality(this Graphics g)
    {
        g.CompositingMode = CompositingMode.SourceOver;
        g.CompositingQuality = CompositingQuality.HighQuality;
        g.InterpolationMode = InterpolationMode.HighQualityBicubic;
        g.SmoothingMode = SmoothingMode.HighQuality;
        g.PixelOffsetMode = PixelOffsetMode.HighQuality;
    }

    public static void DrawCircle(this Graphics g, Pen pen, float centerX, float centerY, float radius)
    {
        g.DrawEllipse(pen, centerX - radius, centerY - radius, radius + radius, radius + radius);
    }

    public static void FillCircle(this Graphics g, Brush brush, float centerX, float centerY, float radius)
    {
        g.FillEllipse(brush, centerX - radius, centerY - radius, radius + radius, radius + radius);
    }
}

Upvotes: 3

R593B
R593B

Reputation: 59

Hey my first answer on here so if I can improve anything let me know.

You could make a very simple visual representation of it with a forms application.

I am not sure if it is the correct use of a timer but you could indeed use a timer to check if the variables you've got in the script have changed, and if they did you could simply change the text of a label to Activated or Deactivated depending on the situation.

For the cross/circle stuff I would use a Picturebox and simply change the image from within the code whenever the value changes.

            RSS_Button.Image = Properties.Resources.RSS;

Is what I used to make custom buttons with the picturebox (my picturebox was named rss_button).

I hope it helps!

Upvotes: 0

Related Questions