Java 中的 Bully 算法

2025年6月16日 | 阅读 4 分钟

Bully 算法是一种选举算法，主要用于选择一个协调者。在分布式系统中，我们需要一些选举算法，例如Bully 和Ring，来选择一个执行其他进程所需功能的协调者。

选举算法从充当协调者的进程中选择一个进程。当选定的协调者进程因某种原因崩溃时，会选择一个新的进程。为了确定新协调者副本应该从哪里重新启动，会使用选举算法。

它假设系统中的每个进程都有一个唯一的优先级编号，因此具有最高优先级的进程将首先被选为新的协调者。当当前使用的协调者进程崩溃时，它会选举一个具有最高优先级编号的新进程。我们记录优先级编号并将其传递给分布式系统中的每个活动进程。

Bully 选举算法如下：

假设P 是一个向协调者发送消息的进程。

当在时间间隔T 内未收到协调者的任何响应时，它将假设协调者进程已失败。
进程P 将向所有活动进程发送一个选举消息，其中包含最高优先级编号。
如果在时间间隔 T 内未收到任何响应，则当前进程 P 会将自己选举为协调者。
在将自己选举为协调者之后，它会向所有优先级较低的进程发送消息，表明进程P 已被选为他们的新协调者。
如果在时间T 内，进程P 从另一个进程Q 收到任何响应：
1. 它会再次等待时间 T 以接收另一个响应，即它已被进程Q 选举为协调者。
2. 如果在时间T 内未收到任何响应，则假定其已失败，并且算法将重新启动。

BullyAlgoExample.java

// import required classes and packages
packagejavaTpoint.javacodes;

import java.io.*;
importjava.util.Scanner;

// create class BullyAlgoExample to understand how bully algorithms works
classBullyAlgoExample{
	
	// declare variables and arrays for process and their status
staticintnumberOfProcess;
staticintpriorities[] = newint[100];
staticintstatus[] = newint[100];
staticintcord;

    // main() method start
publicstaticvoid main(String args[])throwsIOException	// handle IOException
    {
	// get input from the user for the number of processes 
System.out.println("Enter total number of processes:");

        // create scanner class object to get input from user
        Scanner sc = newScanner(System.in);
numberOfProcess = sc.nextInt();

inti;

        // use for loop to set priority and status of each process
for(i = 0; i<numberOfProcess; i++)
        {
System.out.println("Status for process "+(i+1)+":");
status[i] = sc.nextInt();
System.out.println("Priority of process "+(i+1)+":");
priorities[i] = sc.nextInt();
        }

System.out.println("Enter proces which will initiate election");
intele = sc.nextInt();

sc.close();

        // call electProcess() method 
electProcess(ele);
System.out.println("After electing process the final coordinator is "+cord);
    }

    // create electProcess() method 
staticvoidelectProcess(intele)
    {
ele = ele - 1;
cord = ele + 1;

for(inti = 0; i<numberOfProcess; i++)
        {
	if(priorities[ele]<priorities[i])
            {
System.out.println("Election message is sent from "+(ele+1)+" to "+(i+1));
if(status[i]==1)
	electProcess(i+1);
            }
        }
    }
}

BullyAlgoExample2.java

// import required classes and packages
packagejavaTpoint.javacodes;

importjava.util.Scanner;

// create process class for creating a process having id and status
class Process{
	// declare variables
	publicint id;
	public String status;
	
	// initialize variables using constructor
	public Process(int id){
		this.id = id;
		this.status = "active";
	}
}
// create class BullyAlgoExample2 for understanding the concept of Bully algorithm
publicclass BullyAlgoExample2 {
	
	// initialize variables and array
	Scanner sc;
	Process[] processes;
	int n;
	
	// initialize Scanner class object in constructor
	public BullyAlgoExample2(){
		sc= new Scanner(System.in);
	}
	
	// create ring() method for initializing the ring
	publicvoid ring(){
		
		// get input from the user for processes
		System.out.println("Enter total number of processes of Processes");
		n = sc.nextInt();
		
		// initialize processes array
		processes = new Process[n];
		for(inti = 0; i< n; i++){
			processes[i]= new Process(i);
		}
	}
	
	// create election() method for electing process
	publicvoidperformElection(){

		// we use the sleep() method to stop the execution of the current thread
		try {
			Thread.sleep(1000);
		} catch (InterruptedException e) {
			
			e.printStackTrace();
		}
		
		// show failed process
		System.out.println("Process having id "+processes[getMaxValue()].id+" fails");
		
		// change status to Inactive of the failed process
		processes[getMaxValue()].status = "Inactive";
		
		// declare and initialize variables 
		intidOfInitiator = 0;
		booleanoverStatus = true;
		
		// use while loop to repeat steps 
		while(overStatus){
			
			booleanhigherProcesses = false;
			
			// iterate all the processes
			for(inti = idOfInitiator + 1; i< n; i++){
				if(processes[i].status == "active"){
					System.out.println("Process "+idOfInitiator+" Passes Election("+idOfInitiator+") message to process" +i);
					higherProcesses = true;

				}
			}
			
			// check for higher process
			if(higherProcesses){
				
				// use for loop to again iterate processes
				for(inti = idOfInitiator + 1; i< n; i++){
					if(processes[i].status == "active"){
						System.out.println("Process "+i+"Passes Ok("+i+") message to process" +idOfInitiator);
					}

				}
				// increment initiator id 
				idOfInitiator++;
			}

			else{
				// get the last process from the processes that will become coordinator
				intcoord = processes[getMaxValue()].id;
				
				// show process that becomes the coordinator
				System.out.println("Finally Process "+coord+" Becomes Coordinator");
				
				
				for(inti = coord - 1; i>= 0; i--){
					if(processes[i].status == "active"){
						System.out.println("Process "+coord+"Passes Coordinator("+coord+") message to process " +i);
					}
				}
				
				
				System.out.println("End of Election");
				overStatus = false;
				break;
			}
		}

	}
	
	// create getMaxValue() method that returns index of max process
	publicintgetMaxValue(){
		intmxId = -99;
		intmxIdIndex = 0;
		for(inti = 0; i<processes.length; i++){
			if(processes[i].status == "active" && processes[i].id >mxId){
				mxId = processes[i].id;
				mxIdIndex = i;
			}
		}
		returnmxIdIndex;
	}
	
	// main() method start
	publicstaticvoid main(String[] args) {
		
		// create instance of the BullyAlgoExample2 class
		BullyAlgoExample2 bully = newBullyAlgoExample2();
		
		// call ring() and performElection() method
		bully.ring();
		bully.performElection();

	}

}

输出

下一主题Java 中的 Collection、Stream、forEach 与 Collection.forEach 区别

Java 中的 Bully 算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的 Bully 算法

相关帖子

Java 中的单体应用

盒子堆叠问题

Java 中的环形复杂度

Java 程序查找和为零最接近的两个元素

Lead Number in Java

Java TDD

Infix to Postfix Java

How to Enable Java in Chrome

Pair Sum Closest to 0 Problem in Java

DoubleBuffer flip() methods in Java with Examples

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器