The invitation election algorithm
The invitation election algorithm is a method used in distributed systems whose task is to choose a coordinator between a series of processes, each with it's corresponding identifier, to organize them into larger groups made possible through invitations. Discovered by Hector Garcia-Molina in 1982.[1]
Definition and context[edit]
This algorithm is based on two principles:
- Recovery: the processes, which detect that the coordinator of their group has failed, create a new group of one member (themselves), of which they are coordinators. It also happens when a process is incorporated or after failing, it is activated again.
- Large groups: each group coordinator asks the rest of the processes for coordinators to invite them to join his group and make it bigger.
We also assume that the algorithm meets a series of conditions to be able to apply it.
Compared to other algorithms like the bully algorithm or ring based algorithm, the invitation algorithm is thought to work in an asynchronous system in which communication failures and processes stops can happen. Each process is responsible for performing the tasks for their group, making it more appropriate in this situation because in this environment, service failures or partitions in the network may occur, causing communication failures between processes. Therefore, we avoid leaving tasks unfinished and in each partition we will have different subgroups doing them until the network or service is restored.
Messages[edit]
- Invitation message: sent by the coordinator of one group to the coordinator of another group to join him.
- Accept message: sent by the coordinator in response to the invitation message to join the new group.
- Coordinator to member message: sent by the coordinator of the old group to let members know they are going to join a new group.
- Confirmation coordinator message: sent by the coordinator of the new joined group to confirm the new group 'id' to it's members.
- Confirmation members message: sent by members accepting the new group 'id' or group change.
Algorithm[edit]
Initially, each process has it's own group in which it is itself the coordinator. These processes have an 'id' and a group identifier.
Periodically each coordinator will look for other coordinators to ask if they want to join their group through the invitation message. So that there are no problems with multiple invitation requests and a process receives many of them and crashes the following mechanism is used:
Priority is given to each process according to his id, for example higher 'id', higher priority. Then, the time to send his invitation request will be inversely proportional to that priority. That is, the processes with more priority will send their invitation requests before and those with lower priority will wait a while. Probably does not eliminate all the conflicts that can be generated, but it do reduce the probability that they will happen.
Once a coordinator receives an invitation message, the coordinator will accept it if it has a lower priority than the transmitter and will notify with a coordinator message to members to all of his group (if there is any) the change of group and they will accept with a confirmation message.
The coordinator of this new group will be the coordination process that has sent the invitation request. When all the processes are already in this group, the coordinator sends a confirmation message with the 'id' of the new group to all members and they reply with a confirmation message.
Every change in the group structure means that a new group 'id' is assigned each time.
This procedure will be repeated until the largest possible group is achieved or until another group is required for some another function.
In the event that there is some type of failure in any process, the procedure will be restarted, each process involved being the coordinator of itself.
Characteristics[edit]
- Liveness: it is fulfilled since at the end of the algorithm the processes know their coordinator or, failing that, they have fallen.
- Safety: it is fulfilled since there will always be a coordinator with a higher priority, either as a group or himself in each group.
- Performance: depending on the situation, in the worst case the lowest priority process that has been sent invitation message will have to wait a long time until get a response if the rest that are above do not confirm or fail.
See also[edit]
References[edit]
- ↑ GARCIA-MOLINA, HECTOR (January 1982). "Elections in a Distributed Computing System" (PDF). vis.usal.es. Unknown parameter
|url-status=ignored (help)
This article "The invitation election algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:The invitation election algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
