Bully algorithm: Difference between revisions

Revision as of 15:10, 30 June 2015

Revision as of 15:21, 30 June 2015

Line 7:

The '''bully algorithm''' is a programming mechanism that applies a hierachy to nodes on a distributed system making them Coordinator or Slaves.

This is used as a method in [[distributed computing]] for dynamically electing a [[Distributed Computing#Coordinator Election|coordinator]] by process ID number. The process with the highest process ID number is selected as the [[Distributed Computing#Coordinator Election|coordinator]]. This, is one optimized solution from The Byzantine Generals Problem in order to improve ( for some Distributed Sistems ) the [[Distributed Computing#Coordinator Election|coordinator]] or "General" election.

==Assumptions==

As this algorithm is part from other algorithm we need some assumptions as the whole point of the algorithm is to make a distributed system free from arbitrary failures (even from processing ones) while saving some computational costs.

* The system is synchronous and uses timeout for identifying process failure.

* Allows processes to crash during execution of algorithm.

* The system is synchronous and uses timeout for identifying process failure. (so you can have Delta and Cmax in order to calculate timeout as opposed to asynchronous systems)

* Message delivery between processes should be reliable.

* Allows processes to crash during execution of algorithm. (To=2*Delta+Cmax so timer knows when omision fails happens)

* Prior information about other process id's must be known.

* Message delivery between processes should be reliable. (Coordinator dilema, ¿is it trustworthy?)

* Prior information about other process id's must be known. (This works as Leslie Lamport solution for Byzantine dilema, where coordinator needs a key and id for each process and where processors hierachy stipulates nodes as Generals, Commanders and Liutenants)

==Election type==

This is how we apply the Bully-algorithm:

* Election Message: Sent to announce faster election

Line 23 ⟶ 27:

Compare with Ring algorithm:

* Assumes that system is synchronous (so you can have Delta and Cmax in order to calculate timeout as opposed to asynchronous systems)

* Uses timeout to detect process failure/crash (To=2*Delta+Cmax so timer knows when omision fails happens)

* Each processor knows which processor has the higher identifier number and communicates with that<ref>Jean Dollimore, Tim Kindberg, George F. Coulouris, "Distributed systems : concepts and design (Third Edition)," in ''Distributed systems : concepts and design (Third Edition)''. Addison-Wesley, 2003.</ref> (This works exactly as Leslie Lamport solution for Byzantine dilema, where coordinator needs a key and id for each process and where processors hierachy stipulates nodes as Generals, Commanders and Liutenants)

When a process P determines that the current coordinator is down because of message timeouts or failure of the coordinator to initiate a handshake, it performs the following sequence of actions: