The bully algorithm is a method in distributed computing for dynamically electing a coordinator by process ID number. The process with the highest process ID number is selected as the coordinator.

Assumptions

• The system is synchronous and uses timeout for identifying process failure.
• Allows processes to crash during execution of algorithm.
• Message delivery between processes should be reliable.
• Prior information about other process id's must be known.

Message types

• Election Message: Sent to announce the election
• Answer Message: Respond to the election message
• Coordinator message: Sent to announce the identity of the elected process

Compare with Ring algorithm:

• Assumes that system is synchronous
• Uses timeout to detect process failure/crash
• Each processor knows which processor has the higher identifier number and communicates with that^[1]

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:

1. P broadcasts an election message (inquiry) to all other processes with higher process IDs, expecting an "I am alive" response from them if they are alive.
2. If P hears from no process with a higher process ID than it, it wins the election and broadcasts victory.
3. If P hears from a process with a higher ID, P waits a certain amount of time for any process with a higher ID to broadcast itself as the leader. If it does not receive this message in time, it re-broadcasts the election message.
4. If P gets an election message (inquiry) from another process with a lower ID it sends an "I am alive" message back and starts new elections.

Note that if P receives a victory message from a process with a lower ID number, it immediately initiates a new election. This is how the algorithm gets its name - a process with a higher ID number will bully a lower ID process out of the coordinator position as soon as it comes online.

Learn more »

In computer science, the prefix sum, scan, or cumulative sum of a sequence of numbers x₀, x₁, x₂, ... is a second sequence of numbers y₀, y₁, y₂, ..., the sums of prefixes (running totals) of the input sequence:

y₀ = x₀

y₁ = x₀ + x₁

y₂ = x₀ + x₁+ x₂

...

For instance, the prefix sums of the natural numbers are the triangular numbers:

input numbers	1	2	3	4	5	6	...
prefix sums	1	3	6	10	15	21	...

This problem can be solved by using divide and conquer method. The pseudo-code for this is given below:

1. if (n==1) do nothing and return
2. Do in parallel
1. make recursive call for prefix_compute(A[1], A[n/2])
2. Make recursive call for prefix_computer(A[n/2+1],A[n])
3. for each A[n/2+1] do A[i] = A[i] + A[n/2]

Here, Step 1 takes O(1) and Step 2 takes T(n/2) since two recursive calls are made to two subsets. Also, in step 3, second half of the processor, i.e. subset 2 reads the global value of A[n/2] concurrently and update their answer. This takes O(1).

Hence, Time complexity is given by T(n) = T(n/2) + O(1). Solving this my Master theorem method, we have,

T(n) = T(n / 2) + O(1)

Since the Master Theorem works with recurrences of the form

T(n) = aT(n / b) + n^c

In this case you have

• a = 1
• b = 2
• c = 0

Since c = log_ba (since 0 = log₂ 1), you are in case two of  the Master Theorem, which solves to Θ(n^c log n) = Θ(n⁰ log n) = Θ(log n).

Learn more »