Byzantine General Problem

Byzantine General Problem

PROBLEM STATEMENT:

Write a program to implement Byzantine general problem. The program consists of ‘n’, where n > 4, number loyal generals and ’m’, where m <= n, number of disloyal generals. The program produces random values for representing armies of each of the general. The army strength of each general is send to each other general. The list of army strength of every general, except of the current general, is send to every other general for confirmation. Finally, this procedure identifies the disloyal traitor general(s) and displays them.  (In the program a general is represented by a node or terminal.).

DESCRIPTION:

Byzantine Algorithm follows following steps;

Step1:
Every general sends a (reliable) message to every other general announcing his troops. Here loyal generals tell the truth,ehile the traitors may tell every other general a different lie.

Step2:
The results of the announcements of step1 are collected together in the form of the vectors.

Step3:
Every general passing his vector from to every other general.

Step4:
Each general examines the ith element of each of the newly received vectors. If any value has the majority, that value is put into result vector. If no value has a majority, the result vector is marked unknown.


SOURCE CODE:

ByzGenOne.java

import java.io.*;
import java.net.*;
import java.util.*;

public class ByzGenOne
{
     public static void main(String args[])throws Exception
    {
        int icounter;
        InetAddress lclhost;
        GenOne gentwo,genthree,genfour;
       
        for(icounter=0;icounter<2;icounter++)
        {
            lclhost = InetAddress.getLocalHost();
            gentwo = new GenOne(lclhost);
            gentwo.setSendPort(9001);
            gentwo.setRecPort(8002);
            gentwo.sendData();
            gentwo.recData();
           
           
            lclhost = InetAddress.getLocalHost();
            genthree = new GenOne(lclhost);
            genthree.setSendPort(9003);
            genthree.setRecPort(8004);
            genthree.sendData();
            genthree.recData();
       
           
            lclhost = InetAddress.getLocalHost();
            genfour = new GenOne(lclhost);
            genfour.setSendPort(9005);
            genfour.setRecPort(8006);
            genfour.sendData();
            genfour.recData();
           
            GenOne.vecdata = true;
        }
    }

}

class GenOne
{
    InetAddress lclhost;
    int sendport,recport;
    private static String vecstr="",datastr="";
    static boolean vecdata = false; //Used to send received armies' strength
    private static int recctr = 0;  //No of received msgs
    private static int ctr=0;
    private static int fnctr = 0;
    private static int recdata=0;
    static int dataarr[] = new int[12];
    static int finalarr[] = new int[3];
    GenOne(InetAddress lclhost)
        {
            this.lclhost = lclhost;
        }
       
   
    void setSendPort(int sendport)
        {
            this.sendport = sendport;
        }
       
    void setRecPort(int recport)
        {
            this.recport = recport;
        }

    void  sendData()throws Exception
        {   
             DatagramSocket ds;
             DatagramPacket dp;
            BufferedReader br;
           
            System.out.println("Enter the Data");
           
            if(vecdata == false)
            {
br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
            }
            else
            {
            br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
                datastr = vecstr;
            }
            ds = new DatagramSocket(sendport);
            dp = new DatagramPacket(datastr.getBytes(),datastr.length(),lclhost,sendport-1000);
            ds.send(dp);
            ds.close();
        }

        void recData()throws Exception
        {
            DatagramSocket ds;
            DatagramPacket dp;
            byte[]  buf = new byte[256];
             String msgstr;

            ds = new DatagramSocket(recport);
            dp = new DatagramPacket(buf,buf.length);
            ds.receive(dp);
            ds.close();

            msgstr = new String(dp.getData(),0,dp.getLength());
            System.out.println(msgstr);
            int l=msgstr.length();
            System.out.println("Hello");
            System.out.println("Length =  "+l);
            if(msgstr.length() == 9)
            {
                recctr++;   
                recdata = Integer.parseInt(msgstr);
                dataarr[ctr++] = recdata/1000000;       
               
                recdata  = recdata % 1000000;
                dataarr[ctr++] = recdata / 1000;

                recdata = recdata %1000;
                dataarr[ctr++] = recdata;
               
                if(recctr == 3)
                    maxval();
            }
           
            if(vecdata == false)
            {
                vecstr = vecstr.concat(msgstr);
               
                System.out.println("Vector Data "+vecstr);
            }
        }           
           

        void  maxval()
        {
              int ctr1,ctr2,i,j;
            boolean gentwo=false,genthree=false,genfour=false;
           
            for(ctr1=0;ctr1<9;ctr1++)
                {
                    i=0;
                    j = dataarr[ctr1];
                   
                    if(dataarr[ctr1]!=0)
                    {
                        //System.out.println("found");
                        for(ctr2=0;ctr2<9;ctr2++)
                        {
                            if(j==dataarr[ctr2])
                            {
                                i++;
                                dataarr[ctr2] =0;
                            }
                           
                        }
                    if(i==2)
                   
                        finalarr[fnctr++] = j;
                }   
            }
Arrays.sort(finalarr);
                System.out.println("Final Vector");
                   
                for(ctr1 = 0 ;ctr1<3 ; ctr1++)
                    System.out.println(finalarr[ctr1] + " ");
               
                for(ctr1 =0 ; ctr1<3 ; ctr1++)
                {
                if(finalarr[ctr1] >=200 && finalarr[ctr1] <300)
                {
                System.out.println("General Number two is
                Loyal");

                gentwo = true;
                }
               
            else if(finalarr[ctr1] >=300 && finalarr[ctr1] <400)
                {
                 System.out.println("General Number three is
                 Loyal");
                 genthree = true;
                }

            else if(finalarr[ctr1] >=400 && finalarr[ctr1] <500)
                {
                System.out.println("General Number four is
                Loyal");
genfour = true;
                }

           
                   
                    }
            if(gentwo ==false)
            System.out.println("General Number Two is Not Loyal");
           
            if(genthree ==false)
            System.out.println("General Number Three is Not
            Loyal");
           
            if(genfour ==false)                                        System.out.println("General Number Four is Not
            Loyal");

            }

        }

ByzGenTwo.java

import java.io.*;
import java.net.*;
import java.util.*;

public class ByzGenTwo
{
    public static void main(String args[])throws Exception
    {
        int icounter;
        InetAddress lclhost;
        GenTwo gentwo,genthree,genfour;
       
        for(icounter=0;icounter<2;icounter++)
        {
            lclhost = InetAddress.getLocalHost();
            gentwo = new GenTwo(lclhost);
            gentwo.setSendPort(9002);
            gentwo.setRecPort(8001);
           
            gentwo.recData();
            gentwo.sendData();
           
            lclhost = InetAddress.getLocalHost();
            genthree = new GenTwo(lclhost);
            genthree.setSendPort(9007);
            genthree.setRecPort(8008);
            genthree.sendData();
            genthree.recData();
       
           
            lclhost = InetAddress.getLocalHost();
            genfour = new GenTwo(lclhost);
            genfour.setSendPort(9009);
            genfour.setRecPort(8010);
            genfour.sendData();
            genfour.recData();
           
            GenTwo.vecdata = true;
        }
    }

}

class GenTwo
{
    InetAddress lclhost;
    int sendport,recport;
    private static String vecstr = "",datastr="";
    static boolean vecdata = false; //Used to send received armies' strength
    private static int recctr = 0;  //No of received msgs
    private static int ctr=0;
    private static int fnctr = 0;
    private static int recdata=0;
    static int dataarr[] = new int[12];
    static int finalarr[] = new int[3];
    GenTwo(InetAddress lclhost)
        {
            this.lclhost = lclhost;
        }
       
   
    void setSendPort(int sendport)
        {
            this.sendport = sendport;
        }
       
    void setRecPort(int recport)
        {
            this.recport = recport;
        }

    void  sendData()throws Exception
        {   
             DatagramSocket ds;
             DatagramPacket dp;
            BufferedReader br;
   
            ds = new DatagramSocket(sendport);
           
            System.out.println("Enter the Data");
           
            if(vecdata == false)
            {
                br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
            }
            else
            {
                br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
                datastr = vecstr;
            }

            dp = new DatagramPacket(datastr.getBytes(),datastr.length(),lclhost,sendport-1000);
            ds.send(dp);
            ds.close();
        }

        void recData()throws Exception
        {
            DatagramSocket ds;
            DatagramPacket dp;
            byte[]  buf = new byte[256];
             String msgstr;

            ds = new DatagramSocket(recport);
            dp = new DatagramPacket(buf,buf.length);
            ds.receive(dp);
            ds.close();

            msgstr = new String(dp.getData(),0,dp.getLength());
            System.out.println(msgstr);

            if(msgstr.length() == 9)
            {
                recctr++;   
                recdata = Integer.parseInt(msgstr);
                dataarr[ctr++] = recdata/1000000;       
               
                recdata  = recdata % 1000000;
                dataarr[ctr++] = recdata/1000;

                recdata = recdata %1000;
                dataarr[ctr++] = recdata;
               
                if(recctr == 3)
                    maxval();
            }
           
            if(vecdata ==false)
            {
                vecstr = vecstr.concat(msgstr);
                System.out.println("Vector Data "+vecstr);
            }
        }           
           

        void  maxval()
        {
             int ctr1,ctr2,i,j;
            boolean gentwo=false,genthree=false,genfour=false;
           
            for(ctr1=0;ctr1<9;ctr1++)
                {
                    i=0;
                    j = dataarr[ctr1];
                    if(dataarr[ctr1]!=0)
                    {
                        for(ctr2=0;ctr2<9;ctr2++)
                        {
                            if(j==dataarr[ctr2])
                            {
                                i++;
                                dataarr[ctr2] =0;
                            }
                        }
                   
                    if(i==2)
                   
                        finalarr[fnctr++] = j;
                    }
                }   
           
                Arrays.sort(finalarr);
                System.out.println("Final Vector");
                   
                for(ctr1 = 0 ;ctr1<3 ; ctr1++)
                    System.out.println(finalarr[ctr1] + " ");
               
                for(ctr1 =0 ; ctr1<3 ; ctr1++)
                    {
                if(finalarr[ctr1] >=100 && finalarr[ctr1] <200)
                {
            System.out.println("General Number One is
            Loyal");

                gentwo = true;
                }
               
            else if(finalarr[ctr1] >=300 && finalarr[ctr1] <400)
            {
            System.out.println("General Number three is Loyal");
            genthree = true;
            }

            else if(finalarr[ctr1] >=400 && finalarr[ctr1] <500)
                        {
            System.out.println("General Number four is Loyal");
            genfour = true;
            }
}
            if(gentwo ==false)
            System.out.println("General Number One is Not Loyal");
           
            if(genthree ==false)
            System.out.println("General Number Three is Not
            Loyal");

            if(genfour ==false)                                          System.out.println("General Number Four is Not                     Loyal");

}

        }

ByzGenThree.java

import java.io.*;
import java.net.*;
import java.util.*;

public class ByzGenThree
{
    public static void main(String args[])throws Exception
    {
        int icounter;
        InetAddress lclhost;
        GenThree gentwo,genthree,genfour;
       
        for(icounter=0;icounter<2;icounter++)
        {
            lclhost = InetAddress.getLocalHost();
            gentwo = new GenThree(lclhost);
            gentwo.setSendPort(9004);
            gentwo.setRecPort(8003);
            gentwo.recData();
            gentwo.sendData();
           
            lclhost = InetAddress.getLocalHost();
            genthree = new GenThree(lclhost);
            genthree.setSendPort(9008);
            genthree.setRecPort(8007);
            genthree.recData();
            genthree.sendData();
           
            lclhost = InetAddress.getLocalHost();
            genfour = new GenThree(lclhost);
            genfour.setSendPort(9011);
            genfour.setRecPort(8012);
            genfour.sendData();
            genfour.recData();
           
            GenThree.vecdata = true;
        }
    }

}

class GenThree
{
    InetAddress lclhost;
    int sendport,recport;
    private static String vecstr = "",datastr="";
    static boolean vecdata = false; //Used to send received armies' strength
    private static int recctr = 0;  //No of received msgs
    private static int ctr=0;
    private static int fnctr = 0;
    private static int recdata=0;
    private static int dataarr[] = new int[12];
    private static int finalarr[] = new int[3];
    GenThree(InetAddress lclhost)
        {
            this.lclhost = lclhost;
        }
       
   
    void setSendPort(int sendport)
        {
            this.sendport = sendport;
        }
       
    void setRecPort(int recport)
        {
            this.recport = recport;
        }

    void  sendData()throws Exception
        {   
             DatagramSocket ds;
             DatagramPacket dp;
            BufferedReader br;
   
            ds = new DatagramSocket(sendport);
           
            System.out.println("Enter the Data");
           
            if(vecdata == false)
            {
                br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
            }
            else
            {
                br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
                datastr = vecstr;
            }

            dp = new DatagramPacket(datastr.getBytes(),datastr.length(),lclhost,sendport-1000);
            ds.send(dp);
            ds.close();
        }

        void recData()throws Exception
        {
            DatagramSocket ds;
            DatagramPacket dp;
            byte[]  buf = new byte[256];
             String msgstr;

            ds = new DatagramSocket(recport);
            dp = new DatagramPacket(buf,buf.length);
            ds.receive(dp);
            ds.close();

            msgstr = new String(dp.getData(),0,dp.getLength());
            System.out.println(msgstr);

            if(msgstr.length() == 9)
            {
                recctr++;   
                recdata = Integer.parseInt(msgstr);
                dataarr[ctr++] = recdata/1000000;       
               
                recdata  = recdata % 1000000;
                dataarr[ctr++] = recdata / 1000;

                recdata = recdata %1000;
                dataarr[ctr++] = recdata;
               
                if(recctr == 3)
                    maxval();
            }
           
            if(vecdata ==false)
            {
                vecstr = vecstr.concat(msgstr);
                System.out.println("Vector Data "+vecstr);
            }
        }           
           

        void  maxval()
        {
             int ctr1,ctr2,i,j;
            boolean gentwo=false,genthree=false,genfour=false;
           
            for(ctr1=0;ctr1<9;ctr1++)
                {
                    i=0;
                    j = dataarr[ctr1];
                    if(dataarr[ctr1]!=0)
                    {
                        for(ctr2=0;ctr2<9;ctr2++)
                        {
                            if(j==dataarr[ctr2])
                            {
                                i++;
                                dataarr[ctr2] =0;
                            }
                        }
                   
                    if(i==2)
                   
                        finalarr[fnctr++] = j;
                    }
                }   
           
                Arrays.sort(finalarr);
                System.out.println("Final Vector");
                   
                for(ctr1 = 0 ;ctr1<3 ; ctr1++)
                    System.out.println(finalarr[ctr1] + " ");
               
                for(ctr1 =0 ; ctr1<3 ; ctr1++)
                {
                if(finalarr[ctr1] >=100 && finalarr[ctr1] <200)
                {
                System.out.println("General Number one is
                Loyal");
                gentwo = true;
                }
               
            else if(finalarr[ctr1] >=200 && finalarr[ctr1] <300)
                {
                System.out.println("General Number two is
                Loyal");
                genthree = true;
                }

            else if(finalarr[ctr1] >=400 && finalarr[ctr1] <500)
            {
                System.out.println("General Number four is
                Loyal");
                genfour = true;
            }

        }
            if(gentwo ==false)
            System.out.println("General Number One is Not Loyal");
           
            if(genthree ==false)
            System.out.println("General Number Two is Not Loyal");
           
             if(genfour ==false)                                        System.out.println("General Number Four is Not
            Loyal");
}
        }

ByzGenFour.java

import java.io.*;
import java.net.*;
import java.util.*;

public class ByzGenFour
{
    public static void main(String args[])throws Exception
    {
        int icounter;
        InetAddress lclhost;
        GenFour gentwo,genthree,genfour;
       
        for(icounter=0;icounter<2;icounter++)
        {
            lclhost = InetAddress.getLocalHost();
            gentwo = new GenFour(lclhost);
            gentwo.setSendPort(9006);
            gentwo.setRecPort(8005);
           
            gentwo.recData();
            gentwo.sendData();
           
            lclhost = InetAddress.getLocalHost();
            genthree = new GenFour(lclhost);
            genthree.setSendPort(9010);
            genthree.setRecPort(8009);
           
            genthree.recData();
            genthree.sendData();
           
            lclhost = InetAddress.getLocalHost();
            genfour = new GenFour(lclhost);
            genfour.setSendPort(9012);
            genfour.setRecPort(8011);
           
            genfour.recData();
            genfour.sendData();
            GenFour.vecdata = true;
        }
    }

}

class GenFour
{
    InetAddress lclhost;
    int sendport,recport;
    private static String vecstr = "",datastr="";
    static boolean vecdata = false; //Used to send received armies' strength
    private static int recctr = 0;  //No of received msgs
    private static int ctr=0;
    private static int fnctr = 0;
    private static int recdata=0;
    static int dataarr[] = new int[12];
    static int finalarr[] = new int[3];
    GenFour(InetAddress lclhost)
        {
            this.lclhost = lclhost;
        }
       
   
    void setSendPort(int sendport)
        {
            this.sendport = sendport;
        }
       
    void setRecPort(int recport)
        {
            this.recport = recport;
        }

    void  sendData()throws Exception
        {   
             DatagramSocket ds;
             DatagramPacket dp;
            BufferedReader br;
   
            ds = new DatagramSocket(sendport);
           
            System.out.println("Enter the Data");
           
            if(vecdata == false)
            {
                br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
            }
            else
            {
                br = new BufferedReader(new InputStreamReader(
System.in));
                datastr = br.readLine();
                datastr = vecstr;
            }

            dp = new DatagramPacket(datastr.getBytes(),datastr.length(),lclhost,sendport-1000);
            ds.send(dp);
            ds.close();
        }

        void recData()throws Exception
        {
            DatagramSocket ds;
            DatagramPacket dp;
            byte[]  buf = new byte[256];
             String msgstr;

            ds = new DatagramSocket(recport);
            dp = new DatagramPacket(buf,buf.length);
            ds.receive(dp);
            ds.close();

            msgstr = new String(dp.getData(),0,dp.getLength());
            System.out.println(msgstr);

            if(msgstr.length() == 9)
            {
                recctr++;   
                recdata = Integer.parseInt(msgstr);
                dataarr[ctr++] = recdata/1000000;       
               
                recdata  = recdata % 1000000;
                dataarr[ctr++] = recdata / 1000;

                recdata = recdata %1000;
                dataarr[ctr++] = recdata;
               
                if(recctr == 3)
                    maxval();
            }
           
            if(vecdata ==false)
            {
                vecstr = vecstr.concat(msgstr);
                System.out.println("Vector Data "+vecstr);
            }
        }           
           

        void  maxval()
        {
             int ctr1,ctr2,i,j;
            boolean gentwo=false,genthree=false,genfour=false;
           
            for(ctr1=0;ctr1<9;ctr1++)
                {
                    i=0;
                    j = dataarr[ctr1];
                    if(dataarr[ctr1]!=0)
                    {
                        for(ctr2=0;ctr2<9;ctr2++)
                        {
                            if(j==dataarr[ctr2])
                            {
                                i++;
                                dataarr[ctr2] =0;
                            }
                        }
                   
                    if(i==2)
                   
                        finalarr[fnctr++] = j;
                    }
                }   
           
                Arrays.sort(finalarr);
                System.out.println("Final Vector");
                   
                for(ctr1 = 0 ;ctr1<3 ; ctr1++)
                    System.out.println(finalarr[ctr1] + " ");
               
                for(ctr1 =0 ; ctr1<3 ; ctr1++)
                    {
                if(finalarr[ctr1] >=100 && finalarr[ctr1] <200)
                {
                System.out.println("General Number one is
                Loyal");
                gentwo = true;
                }
   
        else if(finalarr[ctr1] >=200 && finalarr[ctr1] <300)
            {
            System.out.println("General Number two is Loyal");
            genthree = true;
        }

        else if(finalarr[ctr1] >=300 && finalarr[ctr1] <400)
            {
                System.out.println("General Number three is
                Loyal")
genfour = true;
            }

            }
            if(gentwo ==false)
             System.out.println("General Number one is Not Loyal");
           
            if(genthree ==false)
             System.out.println("General Number Two is Not Loyal");
           
            if(genfour ==false)                                        System.out.println("General Number three is Not
            Loyal");
   
            }

        }

OUTPUT

ByzGenOne.java

C:\Documents and Settings\Admin\Desktop\Byzantine>java ByzGenOne
Enter the Data
111
222
Hello
Length =  3
Vector Data 222
Enter the Data
111
333
Hello
Length =  3
Vector Data 222333
Enter the Data
111
444
Hello
Length =  3
Vector Data 222333444
Enter the Data
1
111333444
Hello
Length =  9
Enter the Data
1
111222444
Hello
Length =  9
Enter the Data
1
111222333
Hello
Length =  9
Final Vector
222
333
444
General Number two is Loyal
General Number three is Loyal
General Number four is Loyal

ByzGenTwo.java

C:\Documents and Settings\Admin\Desktop\Byzantine>java ByzGenTwo
111
Vector Data 111
Enter the Data
222
Enter the Data
222
333
Vector Data 111333
Enter the Data
222
444
Vector Data 111333444
222333444
Enter the Data
111333444
Enter the Data
2
111222444
Enter the Data
2
111222333
Final Vector
111
333
444
General Number One is Loyal
General Number three is Loyal
General Number four is Loyal

ByzGenThree.java

C:\Documents and Settings\Admin\Desktop\Byzantine>java ByzGenThree
111
Vector Data 111
Enter the Data
333
222
Vector Data 111222
Enter the Data
333
Enter the Data
333
444
Vector Data 111222444
222333444
Enter the Data
111222444
111333444
Enter the Data
111222444
Enter the Data
3
111222333
Final Vector
111
222
444
General Number one is Loyal
General Number two is Loyal
General Number four is Loyal

ByzGenFour.java

C:\Documents and Settings\Admin\Desktop\Byzantine>java ByzGenFour
111
Vector Data 111
Enter the Data
444
222
Vector Data 111222
Enter the Data
444
333
Vector Data 111222333
Enter the Data
444
222333444
Enter the Data
111222333
111333444
Enter the Data
111222333
111222444
Final Vector
111
222
333
General Number one is Loyal
General Number two is Loyal
General Number three is Loyal
Enter the Data
111222333