Thread: Leader election on tree.

Hello,

I have to make a leader election emulator on a tree. The whole project is based on this pseudocode:

Code:

var ws: boolean init false;
    wr: integer init 0;
    rec[q]: Boolean for each q ∈ Neigh init false;
    v: P init p;
    state: (sleep, leader, lost) init sleep;
begin if p is initiator then
    begin ws:=true;
        forall q ∈ Neigh do send <wakeup> to q
    end;
    while wr < #Neigh do
        begin receive <wakeup>;
            wr:=wr+1;
            if not ws then
                begin ws:=true;
                    forall q ∈ Neigh do send <wakeup> to q
                end
    end;

    /* Now start the tree algorithm */
    while #{q: &#172;rec[q]} >1 do
        begin receive <tok,r> from q;
            rec[q]:=true;
            v:=min(v,r)
        end;
    send <tok, v> to q0 with &#172;rec[q0];
    receive <tok,r> from q0;
    v:=min(v,r);
    if v=p then state:=leader else state:=lost;
    forall q ∈ Neigh, q≠q0 do send <tok,v> to q
end

Have anyone did something similar or can publish a similar C source code for leader election on trees?
I am totally lost... Don't know how to start except define variables....

Thanks a lot.

How mathematically minded of you, crash21.

Originally Posted by Salem

So where did you get the pseudo-code from - your tutor?

Did they explain all the ¬ and ∈ notation to you? Did you understand it?

yes my tutor. and yeah have understand the symbols and the whole process of the pseudocode but i can't find it easy to do it in c.

I have made some code but some things missing and probably is not 100% right. That's why i asked if there is a sample or example in C.

Here is the code so far but i know that is incorrect.... I can't find how to make it in C this pseudocode and binary tree confuses me more....

This pseudocode send messages to neighbours but I can't do it in the binary tree.....
How on binary tree find last branch and check how many leaves this branch have and after send a virtual message to parent?

This pseudocode will run in a machine and will be only an emulator and maybe this confuses me more in order to make it work....

Code:

#include <stdio.h>

#include<stdlib.h>
#include <stdbool.h>

 

typedef struct bnode{

	int id;
	char* id2;

	struct bnode* left;

	struct bnode* right;

}BNODE;
 

void printKeysReverse(BNODE* current);

void inorder(BNODE* current);

void insert(BNODE **root,int id,char* id2); 

int main(void){

	BNODE* root = NULL;

	int i,wr,nodes;
	bool ws,p;
	int state[2]; //1=sleep,2=leader,3=lost
	p = true;

	
	insert(&root,27,"fghfhfgh");
	insert(&root,63,"225");
	insert(&root,3,"225");
	printf("%d\n",size(root));
	if(p){
		ws = true;
		wr = 0;
		for(i=1;i<=size(root);i++){ //forall q ∈ Neigh do send <wakeup> to q;

			//send wakeup neighbours
	     }
		while (wr<size(root)){
			//receive wakeup
			wr++;
			if (!ws){ 
				ws=true;
				for(i=1;i<=size(root);i++){
					//send wakeup

							   }
				  }
			}



		 /* Now start the tree algorithm */
   		/* while #{q: ¬rec[q]} >1 do
                 begin receive <tok,r> from q;
                    rec[q]:=true;
                    v:=min(v,r)
                 end;
    		send <tok, v> to q0 with ¬rec[q0];
	        receive <tok,r> from q0;
                v:=min(v,r);
                if v=p then state:=leader else state:=lost;
                   forall q ∈ Neigh, q≠q0 do send <tok,v> to q
 		end*/

		//printf("---------\n");

		//printf("---------\n");

		//inorder(root);
		






	}
}



//--------------------------FUNCTIONS------------------------------//



void insert(BNODE **root, int val, char* val2){

	BNODE *newnode;

 

	newnode=(BNODE*)malloc(sizeof(BNODE));        

	newnode->right=NULL;

	newnode->left=NULL;

 

	if ((*root)==NULL){

		*root=newnode;

		(*root)->id=val; 
		(*root)->id2=val2;             

		return;

	}

	if (val<(*root)->id) insert(&(*root)->left,val,val2);

	else insert(&(*root)->right,val,val2);     

}//end 

 

void inorder(BNODE *root){

 

	if (root==NULL) return ;

	inorder(root->left);

	printf("%d,%s \n",root->id,root->id2);

	inorder(root->right);

}//end inorder



int size(BNODE *root)
{
    if (root == NULL)
        return 0;
    else
        return 1 + size(root->left) + size(root->right);
}