Bully algorithm - Revision history

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:54:38Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:54, 12 October 2024
Line 52:		Line 52:

	[[Category:Distributed algorithms]]		[[Category:Distributed algorithms]]
	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:21:53Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:21, 12 October 2024
Line 52:		Line 52:

	[[Category:Distributed algorithms]]		[[Category:Distributed algorithms]]
	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]

Materialscientist: Reverted edits by 182.19.35.89 (talk) (HG) (3.4.11)

2023-01-07T08:59:27Z

Reverted edits by 182.19.35.89 (talk) (HG) (3.4.11)

← Previous revision		Revision as of 08:59, 7 January 2023
Line 13:		Line 13:
	==Algorithm==		==Algorithm==
	The [[algorithm]] uses the following message types:		The [[algorithm]] uses the following message types:
	* Election ~~Messag~~		* Election Message: Sent to announce election.
			* Answer (Alive) Message: Responds to the Election message.
			* Coordinator (Victory) Message: Sent by winner of the election to announce victory.

	When a process {{var\|P}} recovers from failure, or the failure detector indicates that the current coordinator has failed, {{var\|P}} performs the following actions:		When a process {{var\|P}} recovers from failure, or the failure detector indicates that the current coordinator has failed, {{var\|P}} performs the following actions:

	# If {{var\|P}} has the highest process ~~sage~~ to all other processes and becomes the new Coordinator. Otherwise, {{var\|P}} broadcasts an Election message to all other processes with higher process IDs than itself.		# If {{var\|P}} has the highest process ID, it sends a Victory message to all other processes and becomes the new Coordinator. Otherwise, {{var\|P}} broadcasts an Election message to all other processes with higher process IDs than itself.
	# If {{var\|P}} receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.		# If {{var\|P}} receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.
	# If {{var\|P}} receives an Answer from a process with a higher ID, it sends no further messages for this election and waits for a Victory message. (If there is no Victory message after a period of time, it restarts the process at the beginning.)		# If {{var\|P}} receives an Answer from a process with a higher ID, it sends no further messages for this election and waits for a Victory message. (If there is no Victory message after a period of time, it restarts the process at the beginning.)
Line 25:		Line 28:

	====Safety====		====Safety====
	safety property expected of [[leader election]] protocols is that every non-faulty process either elects a process {{var\|Q}}, or elects none at all. Note that all [[process (computing)\|processes]] that elect a leader must decide on the same process {{var\|Q}} as the leader. The Bully algorithm satisfies this property (under the system model specified), and at no point in time is it possible for two processes in the group to have		The safety property expected of [[leader election]] protocols is that every non-faulty process either elects a process {{var\|Q}}, or elects none at all. Note that all [[process (computing)\|processes]] that elect a leader must decide on the same process {{var\|Q}} as the leader. The Bully algorithm satisfies this property (under the system model specified), and at no point in time is it possible for two processes in the group to have
	a conflicting view of who the leader is, except during an election. This is true because if it weren't, there are two processes {{var\|X}} and {{var\|Y}} such that both sent the Coordinator (victory) message to the group. This means {{var\|X}} and {{var\|Y}} must also have sent each other victory messages. But this cannot happen, since before sending the victory message, Election messages would have been exchanged between the two, and the process with a lower process ID among the two would never send out victory messages. We have a contradiction, and hence our initial assumption that there are two leaders in the system at any given time is false, and that shows that the bully algorithm is safe.		a conflicting view of who the leader is, except during an election. This is true because if it weren't, there are two processes {{var\|X}} and {{var\|Y}} such that both sent the Coordinator (victory) message to the group. This means {{var\|X}} and {{var\|Y}} must also have sent each other victory messages. But this cannot happen, since before sending the victory message, Election messages would have been exchanged between the two, and the process with a lower process ID among the two would never send out victory messages. We have a contradiction, and hence our initial assumption that there are two leaders in the system at any given time is false, and that shows that the bully algorithm is safe.

182.19.35.89: /* Safety */

2023-01-07T08:58:33Z

Safety

← Previous revision		Revision as of 08:58, 7 January 2023
Line 25:		Line 25:

	====Safety====		====Safety====
	~~The~~ safety property expected of [[leader election]] protocols is that every non-faulty process either elects a process {{var\|Q}}, or elects none at all. Note that all [[process (computing)\|processes]] that elect a leader must decide on the same process {{var\|Q}} as the leader. The Bully algorithm satisfies this property (under the system model specified), and at no point in time is it possible for two processes in the group to have		safety property expected of [[leader election]] protocols is that every non-faulty process either elects a process {{var\|Q}}, or elects none at all. Note that all [[process (computing)\|processes]] that elect a leader must decide on the same process {{var\|Q}} as the leader. The Bully algorithm satisfies this property (under the system model specified), and at no point in time is it possible for two processes in the group to have
	a conflicting view of who the leader is, except during an election. This is true because if it weren't, there are two processes {{var\|X}} and {{var\|Y}} such that both sent the Coordinator (victory) message to the group. This means {{var\|X}} and {{var\|Y}} must also have sent each other victory messages. But this cannot happen, since before sending the victory message, Election messages would have been exchanged between the two, and the process with a lower process ID among the two would never send out victory messages. We have a contradiction, and hence our initial assumption that there are two leaders in the system at any given time is false, and that shows that the bully algorithm is safe.		a conflicting view of who the leader is, except during an election. This is true because if it weren't, there are two processes {{var\|X}} and {{var\|Y}} such that both sent the Coordinator (victory) message to the group. This means {{var\|X}} and {{var\|Y}} must also have sent each other victory messages. But this cannot happen, since before sending the victory message, Election messages would have been exchanged between the two, and the process with a lower process ID among the two would never send out victory messages. We have a contradiction, and hence our initial assumption that there are two leaders in the system at any given time is false, and that shows that the bully algorithm is safe.

182.19.35.89: /* Algorithm */

2023-01-07T08:58:17Z

Algorithm

← Previous revision		Revision as of 08:58, 7 January 2023
Line 13:		Line 13:
	==Algorithm==		==Algorithm==
	The [[algorithm]] uses the following message types:		The [[algorithm]] uses the following message types:
	* Election ~~Message: Sent to announce election.~~		* Election Messag
	* Answer (Alive) Message: Responds to the Election message.
	* Coordinator (Victory) Message: Sent by winner of the election to announce victory.

	When a process {{var\|P}} recovers from failure, or the failure detector indicates that the current coordinator has failed, {{var\|P}} performs the following actions:		When a process {{var\|P}} recovers from failure, or the failure detector indicates that the current coordinator has failed, {{var\|P}} performs the following actions:

	# If {{var\|P}} has the highest process ~~ID, it sends a Victory message~~ to all other processes and becomes the new Coordinator. Otherwise, {{var\|P}} broadcasts an Election message to all other processes with higher process IDs than itself.		# If {{var\|P}} has the highest process sage to all other processes and becomes the new Coordinator. Otherwise, {{var\|P}} broadcasts an Election message to all other processes with higher process IDs than itself.
	# If {{var\|P}} receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.		# If {{var\|P}} receives no Answer after sending an Election message, then it broadcasts a Victory message to all other processes and becomes the Coordinator.
	# If {{var\|P}} receives an Answer from a process with a higher ID, it sends no further messages for this election and waits for a Victory message. (If there is no Victory message after a period of time, it restarts the process at the beginning.)		# If {{var\|P}} receives an Answer from a process with a higher ID, it sends no further messages for this election and waits for a Victory message. (If there is no Victory message after a period of time, it restarts the process at the beginning.)

2601:547:B05:30A9:4D1F:BC6E:1B52:3603 at 01:31, 24 November 2022

2022-11-24T01:31:39Z

← Previous revision		Revision as of 01:31, 24 November 2022
Line 1:		Line 1:
	In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.		In [[distributed computing]], the '''bully algorithm''' is a method for dynamically [[Leader election\|electing]] a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.

	==Assumptions==		==Assumptions==

188.208.122.45 at 10:55, 3 November 2022

2022-11-03T10:55:42Z

← Previous revision		Revision as of 10:55, 3 November 2022
Line 1:		Line 1:
	In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.~~Sasati la pidari~~		In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.

	==Assumptions==		==Assumptions==

188.208.122.45 at 10:55, 3 November 2022

2022-11-03T10:55:18Z

← Previous revision		Revision as of 10:55, 3 November 2022
Line 1:		Line 1:
	In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.		In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.Sasati la pidari

	==Assumptions==		==Assumptions==

46.166.46.146 at 10:54, 3 November 2022

2022-11-03T10:54:54Z

← Previous revision		Revision as of 10:54, 3 November 2022
Line 1:		Line 1:
	In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator~~.Boris a pierdut in belot.md~~.		In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.

	==Assumptions==		==Assumptions==

46.166.46.146 at 10:54, 3 November 2022

2022-11-03T10:54:25Z

← Previous revision		Revision as of 10:54, 3 November 2022
Line 1:		Line 1:
	In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.		In [[distributed computing]], the '''bully algorithm''' is a method for dynamically electing a [[Distributed computing#Election\|coordinator]] or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.Boris a pierdut in belot.md.

	==Assumptions==		==Assumptions==