Election Algorithms

When an algorithm needs that a process acts like a coordinator, how is the coordinator dynamically selected?

In many cases, the coordinator is fixed (single point of failure).

If the coordinator is dynamically selected, can we say that the system is centralized?

Will a completely distributed system (without any coordinator) always be more robust than a centralized one?

Initial assumptions

Every process has a unique id.

Every process knows about every other process id.

Elect means identifying the process with the larger id, that is running.

Bullying

Consider N processes {P0, ... PN-1} and that id(Pk)=k. When a process Pk notices that the coordinator no longer responds to requests, it initiates an election:

1. Pk sends an ELECTION message to every process with ids greater than its own: Pk+1, Pk+2, ...PN-1.

2. If none responds, Pk wins the election and becomes the coordinator.

3. If one of the processes with a greater id responds, this one assumes the position and the Pk work terminates.

Ring

A process priority is obtained by the arrangement of processes in a logical ring. The process with the greater priority is elected as coordinator:

• Any process initiates an election by sending a message to its successor. If the successor is turned off, the message is passed on to the next successor.

• If the message is passed on, the sender adds himself to the list. When the message returns to the sender, everyone has had the chance to annunciate themselves.

• The one that initiates, sends a coordination message through the ring with the list of every process presumed to be turned on. The process with the greatest priority is elected coordinator.

Large Scale System

It is the case for the super-nodes in P2P networks.

Normal nodes need low latency to access super-nodes.

Super-nodes should be distributed uniformly on the overlay.

Should exist in a fixed proportion in relation to the size of the network.

One super-node should not serve more than a fixed number of nodes.

Positioning nodes

In a large-scale distributed system, where the nodes are dispersed in a WAN, it is common for the system to take into account the proximity or distance between nodes.

For that, it is necessary to determine the location of a node.

Calculating the position of a node

A P node needs d+1 marks so it can calculate its own position in a dimensional space.

• GPS?

• AP signal (WiFi, Bluetooth, ...)?