Leader election on tree.

This is a discussion on Leader election on tree. within the C Programming forums, part of the General Programming Boards category; Hello, I have to make a leader election emulator on a tree. The whole project is based on this pseudocode: ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    3

    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.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,832
    So where did you get the pseudo-code from - your tutor?

    Did they explain all the &#172; and ∈ notation to you? Did you understand it?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    How mathematically minded of you, crash21.

  4. #4
    Registered User
    Join Date
    Nov 2008
    Posts
    3
    Quote Originally Posted by Salem View Post
    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.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,832
    So post some code then.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User
    Join Date
    Nov 2008
    Posts
    3
    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);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 02:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21