WEBVTT
Kind: captions
Language: en
00:00:13.480 --> 00:00:17.560
.
Leader election in the rings; Classical distributed
00:00:17.560 --> 00:00:22.340
algorithms. In this lecture we will discuss
leader election problem in a message passing
00:00:22.340 --> 00:00:26.669
systems .
Especially, for the ring topology in which
00:00:26.669 --> 00:00:33.230
the group of processors must choose one of
them to be the leader. Different algorithms
00:00:33.230 --> 00:00:41.449
for leader election, different scenarios such
as anonymous non anonymous rings, uniform
00:00:41.449 --> 00:00:46.260
non uniform rings, synchronous and asynchronous
rings.
00:00:46.260 --> 00:00:50.940
Leader election problem; the leader election
problem has several variants, leader election
00:00:50.940 --> 00:00:58.290
is for each processor to decide either it
is the leader or a non-leader; subject to
00:00:58.290 --> 00:01:01.070
the constraint that exactly one processor
decides to be a leader .
00:01:01.070 --> 00:01:08.520
So, leader election problem represents a general
class of symmetry breaking problems. For example,
00:01:08.520 --> 00:01:13.610
when a deadlock is created one of the processors
waiting in a cycle for each other, the deadlock
00:01:13.610 --> 00:01:20.090
can be broken by electing one of the waiting
processes as a leader and removing it from
00:01:20.090 --> 00:01:24.450
the cycle.
That is breaking up the deadlock. So, the
00:01:24.450 --> 00:01:35.740
leader election problem definitions , definition
each process or each processor has a set of
00:01:35.740 --> 00:01:42.450
elected and a non-elected states.
Once an elected state is entered the processor
00:01:42.450 --> 00:01:48.380
always in the elected state. And similarly
for non-elected, that is irreversible decisions.
00:01:48.380 --> 00:01:55.739
So, in every admissible execution every processor
eventually enters either as elected or non-elected
00:01:55.739 --> 00:02:01.590
state exactly one processors; are exactly
one processor that is the leader enters into
00:02:01.590 --> 00:02:06.379
the elected state.
Now there are different uses of leader election
00:02:06.379 --> 00:02:10.910
algorithm. So, leader election can be used
to coordinate the activities in the system.
00:02:10.910 --> 00:02:19.770
For example, to find out the spanning tree
in a system requires a leader to be known
00:02:19.770 --> 00:02:25.950
which is called a root. Hence, if a root is
given finding a spanning tree becomes easier.
00:02:25.950 --> 00:02:34.239
Similarly, in a token ring system if a token
is lost; that means, there is no leader so,
00:02:34.239 --> 00:02:39.510
it can elect a leader and restart the system
with a token.
00:02:39.510 --> 00:02:47.109
So, in this lecture we will study the leader
election in in a ring . So, let us define
00:02:47.109 --> 00:02:54.450
different terms which are used in the leader
election problem, that is the ring problem.
00:02:54.450 --> 00:02:58.780
So, the first definition is about the ring
networks.
00:02:58.780 --> 00:03:06.390
So, in an oriented ring, the processors have
a consistent notion of left and right . So,
00:03:06.390 --> 00:03:17.209
in this particular example, we can see here
the label one called as a left side, if it
00:03:17.209 --> 00:03:22.750
is used to forward the message in this particular
direction that is called a clockwise direction
00:03:22.750 --> 00:03:33.920
. Then this particular way the ring will be
oriented in a clockwise manner. Similarly,
00:03:33.920 --> 00:03:45.689
if let us say that if p 0 and other processes
they basically use the right side, that is
00:03:45.689 --> 00:03:51.689
the label number 2, always then it will be
a counter clockwise and the ring will be oriented
00:03:51.689 --> 00:03:56.330
in that manner such rings are called oriented
rings.
00:03:56.330 --> 00:03:59.029
now another definition is about anonymous
rings.
00:03:59.029 --> 00:04:08.569
So, if the processors do not have the unique
ids; that means, they are not given an ids,
00:04:08.569 --> 00:04:15.450
then that particular ring is called anonymous
rings . So, in that situation each processor
00:04:15.450 --> 00:04:20.440
is like same running state machine there is
no distinction.
00:04:20.440 --> 00:04:30.260
Third definition is about uniform anonymous
algorithms. So, uniform algorithm means that
00:04:30.260 --> 00:04:39.260
it does not use the information of the ring
size ; that is n the number of nodes in the
00:04:39.260 --> 00:04:51.320
ring. So, formally every processor in every
size ring is modeled with the same state machine.
00:04:51.320 --> 00:04:59.240
So, the algorithm which is called a non-uniform
algorithm will use the size of the ring that
00:04:59.240 --> 00:05:03.720
is an n the algorithm .
There is a impossibility result which says
00:05:03.720 --> 00:05:09.970
that about the leader election anonymous rings
theorem. There is no leader election algorithm
00:05:09.970 --> 00:05:17.350
for anonymous rings even if the algorithm
knows the ring size that is for the non-uniform.
00:05:17.350 --> 00:05:26.880
And also the model is synchronous model, why?
Because every processor begins in the same
00:05:26.880 --> 00:05:34.880
state with the same outgoing message. Since
it is anonymous, and each processor when receive
00:05:34.880 --> 00:05:41.420
the message will also be in the same state
transition, and sends the message in a round
00:05:41.420 --> 00:05:47.190
one.
So, there is no distinction and there is all
00:05:47.190 --> 00:05:57.360
symmetry looking up in this particular way.
So, it shows that either the safety or the
00:05:57.360 --> 00:06:04.900
liveness is violated here in this case. Hence
the theorem was proved for non-uniform and
00:06:04.900 --> 00:06:10.890
synchronous rings. The same result hold for
a weaker model that is for the uniform and
00:06:10.890 --> 00:06:20.930
the asynchronous model. So, rings with the
ids. So, we will assume that each processor
00:06:20.930 --> 00:06:29.980
has the unique ID, ok. Let us see a example
of a ring.
00:06:29.980 --> 00:06:37.100
Here we see that every processor in the ring
is having different Ids. For example, 3, 37,
00:06:37.100 --> 00:06:46.580
19, 4 and 25.
So, uniform algorithms means that the algorithm
00:06:46.580 --> 00:06:53.930
is not using the size of the ring. So, no
matter what is the size of a ring the algorithm
00:06:53.930 --> 00:06:58.240
in the algorithm.
Similarly, non-uniform rings shows that it
00:06:58.240 --> 00:07:04.340
uses the size of the ring. Let us see the
algorithm.
00:07:04.340 --> 00:07:12.650
Which is called a Lelann-Chang-Roberts algorithm,
LCR algorithm for leader election problem.
00:07:12.650 --> 00:07:18.590
This is also called as a order n square leader
election algorithm. Here algorithm says that
00:07:18.590 --> 00:07:32.590
every processor will send it is id to the
left. When it receives an id from the right,
00:07:32.590 --> 00:07:41.880
and if j is greater than it is id, then it
will forward to the left . If less than id,
00:07:41.880 --> 00:07:47.400
then it will not do anything it will not forward
it will swallow. And if id is equal to the
00:07:47.400 --> 00:07:56.750
j then it will elect itself as the leader.
We will see through an example. As far as
00:07:56.750 --> 00:08:06.730
a correctness is concerned, it will always
elect a processor with a largest id in the
00:08:06.730 --> 00:08:12.530
time of the order n.
And the message complexity is order n square,
00:08:12.530 --> 00:08:28.230
let us see through an example the, let us
see that the processor p 3 will send it is
00:08:28.230 --> 00:08:39.339
id to the left p 4 on receiving 0. It will
not forward it further. Whereas, p 4 will
00:08:39.339 --> 00:08:46.769
send it is own id, and when it reaches to
p 0, it is id is greater than 3. So, it will
00:08:46.769 --> 00:09:00.199
be forwarded further . When it reaches to
p 1 it will also be forwarded. And it will
00:09:00.199 --> 00:09:05.889
be forwarded, and when it reaches to this
particular point because this is the highest.
00:09:05.889 --> 00:09:15.529
So, it will see it is own message so, hence
this will be elected as a leader.
00:09:15.529 --> 00:09:28.189
Whereas, the other messages having lower ids
will be absorbed. So, let us see when this
00:09:28.189 --> 00:09:37.079
order n square algorithm will arise.
Let us see that the messages are being forwarded
00:09:37.079 --> 00:09:46.759
here in this particular scenario . Let us
see this particular method of analyzing the
00:09:46.759 --> 00:09:49.220
worst case scenario, that is of the order
n square.
00:09:49.220 --> 00:09:59.519
We will consider the ring where the identifiers
of the processor 0 1 2 and so on up to n minus
00:09:59.519 --> 00:10:13.670
1. And are ordered in this particular manner.
Here the identifier i is send exactly i plus
00:10:13.670 --> 00:10:24.019
1 times. So, for example, 0 will be send 0
plus 1 that is only one time it will be observed
00:10:24.019 --> 00:10:35.839
here. 1 that is i plus 1 times it will forwarded.
1 will be forwarded by 0; that means, it will
00:10:35.839 --> 00:10:46.589
be forwarded 2 times and so on. So, 2 will
be forwarded 3 times, 3 will be forwarded
00:10:46.589 --> 00:10:54.611
4 times and so on.
So, this is the orientation of the ring. How
00:10:54.611 --> 00:11:04.790
many number of messages are being forwarded
? Here so, we will see that for i it will
00:11:04.790 --> 00:11:17.899
be forwarded i plus 1 times. So, if we sum
for the nodes from 0 to n minus 1. So, these
00:11:17.899 --> 00:11:22.600
are the total number of messages which will
be forwarded in this particular worst case
00:11:22.600 --> 00:11:31.399
scenario in the ring. And when a leader is
elected then the highest id will circulate
00:11:31.399 --> 00:11:39.379
it is message that is n.
Now, this particular summation is of the order
00:11:39.379 --> 00:11:44.870
n square.
So, it requires n square number of messages
00:11:44.870 --> 00:11:52.850
in the worst situation we have shown in this
analysis. Algorithm which is of the order
00:11:52.850 --> 00:11:59.329
n square algorithm is simple and works in
both synchronous and asynchronous model. Another
00:11:59.329 --> 00:12:07.310
good thing about this algorithm is does not
use the value of n or the size of n. Hence,
00:12:07.310 --> 00:12:20.069
it is non uniform , hence it is uniform . So,
it as it is shown that it it will work in
00:12:20.069 --> 00:12:30.329
both the situation either for the synchronous
model or for asynchronous model , anonymous
00:12:30.329 --> 00:12:40.480
order n square leader election algorithm.
Now, can we do with a lesser message complexity
00:12:40.480 --> 00:12:45.160
then order n square?
We will see an algorithm which is given by
00:12:45.160 --> 00:12:51.579
Hirschberg and Sinclair HS algorithm, it is
called it is order n log n leader election
00:12:51.579 --> 00:13:03.570
algorithm. This algorithm uses the concept
of k neighbourhood for any processor p i in
00:13:03.570 --> 00:13:15.320
the ring. That is nothing but distance of
at most k. It is and this is k, and this is
00:13:15.320 --> 00:13:27.110
one that is 2 k plus 1 nodes for the processors
in the k neighbourhood of a processor.
00:13:27.110 --> 00:13:35.459
So, k neighbourhood of a processor includes
exactly 2 k plus 1 processors. This algorithm
00:13:35.459 --> 00:13:44.670
operates in the phases. Therefore, it is convenient
to start numbering the phases starting from
00:13:44.670 --> 00:13:50.769
the phase 0. So, the kth phase of a process
will try to become the winner, for that phase
00:13:50.769 --> 00:13:58.059
to be the winner it must have the largest
id in it is 2 k neighbourhood . So, only the
00:13:58.059 --> 00:14:07.540
processor that are the winners of kth phase
will continue to to participate in k plus
00:14:07.540 --> 00:14:17.459
1th phase. Thus, fewer processor proceeds
to a higher phase until at the end only one
00:14:17.459 --> 00:14:23.490
processor is the winner and is elected as
the leader of the whole ring .
00:14:23.490 --> 00:14:31.399
So, let us see the phase 0, in more detail
phase 0 each processor attempts to become
00:14:31.399 --> 00:14:43.839
of a phase 0 winner, and sends a probe message
containing it is id to it is one of neighbourhood
00:14:43.839 --> 00:14:55.269
to each of the 2 neighbours. So, for example,
if this is the neighbourhood, and to one neighbourhood
00:14:55.269 --> 00:15:05.000
on both the sides in phase 0 if the, .
.
00:15:05.000 --> 00:15:14.110
, if the id identifier of the neighbour receiving
the probe is greater than the identifier in
00:15:14.110 --> 00:15:19.309
the probe, it swallows the probe, otherwise
it sends back the reply.
00:15:19.309 --> 00:15:26.540
So, if it gets the replies back from both
the end; that means, it has become the winner
00:15:26.540 --> 00:15:36.850
of phase 0 and it will continue to the phase
one. So, in the phase one the neighbourhood
00:15:36.850 --> 00:15:44.860
size will basically double . If it is let
us say that it is phase k; that means, all
00:15:44.860 --> 00:15:53.110
the winners of phase k minus 1 will send it
is probe message with it is id to it is 2
00:15:53.110 --> 00:16:00.639
raised power k neighbourhood one in each direction.
Each message traverses 2 raised power k processor
00:16:00.639 --> 00:16:05.329
one by one and the probe is swallowed by the
processor if it contains an id that is smaller
00:16:05.329 --> 00:16:10.199
than it is own id.
If the probe arrives at the last processor
00:16:10.199 --> 00:16:13.709
on the neighbourhood without being swallowed,
then the last processor will send back the
00:16:13.709 --> 00:16:19.550
reply as we have seen in the first or the
0th phase.
00:16:19.550 --> 00:16:30.119
So, this is the complete algorithm for the
processor i and this algorithm will be for
00:16:30.119 --> 00:16:34.429
all the processor that is from 0 to n minus
1.
00:16:34.429 --> 00:16:41.860
So, here we will see that the algorithm , it
will send this particular probe to the left
00:16:41.860 --> 00:16:53.350
and right, and it will do the election it
will initiate multiple elections in the k
00:16:53.350 --> 00:16:57.519
neighbourhood; that means, the entire ring
is divided into k neighbourhood and this elections
00:16:57.519 --> 00:17:08.179
will parallely run for the kth neighbourhood.
So, we see that that the size of the neighbourhood
00:17:08.179 --> 00:17:14.880
will double in each phase. So, if a probe
reaches a node with a largest larger id the
00:17:14.880 --> 00:17:18.100
probe will stop.
If the probe reaches the end of the neighborhood,
00:17:18.100 --> 00:17:25.680
then the reply will be sent back to the initiator.
So, this can be seen through this particular
00:17:25.680 --> 00:17:49.059
diagram that this is phase 0 ; that means,
this particular one half neighbourhood will
00:17:49.059 --> 00:17:54.330
perform the elections. And whose over will
be the winner then the size will be doubled
00:17:54.330 --> 00:18:04.880
that is 2 raised power one neighbourhood.
So, that means, 2 this was earlier one node
00:18:04.880 --> 00:18:08.580
neighbourhood, now it is having 2 nodes in
the neighbourhood.
00:18:08.580 --> 00:18:16.240
And whosever and if it is able to win for
2 raised power one neighbourhood, then the
00:18:16.240 --> 00:18:21.010
neighbourhood size will double, that is 2
raised power 2 neighbourhood; that means,
00:18:21.010 --> 00:18:28.990
1 2 3 4 different so, the neighbourhood size
will keeps on growing in this particular manner.
00:18:28.990 --> 00:18:35.860
Now we will count what is the depth; that
means, how long how many different phases
00:18:35.860 --> 00:18:47.789
will be there , how many phases will be there
? And in each phase, you know that it will
00:18:47.789 --> 00:18:56.740
be 2 raised power k neighbourhood.
So, in each phase how many such elections
00:18:56.740 --> 00:19:08.960
will happen ? And these particular information
is required to compute the message complexity.
00:19:08.960 --> 00:19:16.269
So, the message complexity, that means, here
the probe distance is in a phase k is 2 raised
00:19:16.269 --> 00:19:22.830
power k. So, the number of messages initiated
by a process in a phase k is at most 4 times
00:19:22.830 --> 00:19:31.350
2 raised power k; that means, if this is the
k phase it is neighbourhood. So, the message
00:19:31.350 --> 00:19:38.100
will go one times, the reply will come back
2 times, then message will go on the right
00:19:38.100 --> 00:19:46.809
side third time and it will come back to the
4 times. So, 4 time 2 raised power k in every
00:19:46.809 --> 00:19:53.679
phase 4 times these probes will be sent in
counting the message complexity .
00:19:53.679 --> 00:20:01.850
Now, the question is how many such processor
will initiate the probe in the phase k. Meaning
00:20:01.850 --> 00:20:13.529
to say that if this is the k hop. So, how
many such packing of k hops will be initiated
00:20:13.529 --> 00:20:22.950
at a particular phase k . Now for k is equal
to 0 every processor will be participating
00:20:22.950 --> 00:20:31.070
in this particular election process when k
is greater than 0; that means, the winner
00:20:31.070 --> 00:20:40.720
of phase k minus 1 only participate in kth
phase.
00:20:40.720 --> 00:20:49.950
So, the winner of k minus 1th phase means
that the largest id in 2 raised power k minus
00:20:49.950 --> 00:20:58.580
1 neighbourhood which is being seen . So,
the maximum number of phase k minus 1 winner
00:20:58.580 --> 00:21:02.470
occurs when they are packed as densely as
possible.
00:21:02.470 --> 00:21:08.380
So, let us see that here it is phase k minus
1 winner and another phase k minus 1 winner.
00:21:08.380 --> 00:21:16.980
So, how many number of processors which are
in between 2 extreme phase k minus 1 winner
00:21:16.980 --> 00:21:27.299
is nothing but 2 raised power k minus 1 winner.
We can see through an example that if this
00:21:27.299 --> 00:21:39.649
is phase 0 so, it will have the one neighbourhood.
So, this particular 0, this particular another
00:21:39.649 --> 00:21:48.210
node will also have this kind of neighbourhood.
So, the number of nodes involved is basically
00:21:48.210 --> 00:21:57.299
2 raised power k minus 1. So, the total number
of phase k minus 1 winner will be n divided
00:21:57.299 --> 00:22:04.520
by 2 raised power k minus 1 plus 1 .
That means this is the packing, this is the
00:22:04.520 --> 00:22:14.870
packing of so many k minus 1. So, n divided
by 2 raised power k minus 1 plus 1, this will
00:22:14.870 --> 00:22:23.940
be total number of such k minus 1 winners
who are participating in kth round. Now the
00:22:23.940 --> 00:22:34.630
question is how many phases are there. Now
you know that every phase the number of winners
00:22:34.630 --> 00:22:44.760
is cut in a half that is from n raised power
2 k minus 1 plus 1 .
00:22:44.760 --> 00:22:58.039
It will now go to n divided by 2 k plus 1
in the kth phase. So, we will see that we
00:22:58.039 --> 00:23:07.080
will continue in this manner so that finally,
there will be only one such neighbourhood
00:23:07.080 --> 00:23:14.760
remains that is the entire ring. And if we
compute then it becomes it comes out to be
00:23:14.760 --> 00:23:20.250
log of n minus 1 plus 1 total number of phases
.
00:23:20.250 --> 00:23:40.669
So, again we can see n divided by 2 k 2 k
minus 1 plus 1. Let us say this becomes 1
00:23:40.669 --> 00:24:02.610
if we take the log of n , then it will become
k minus 1. So, this k is equal to log n minus
00:24:02.610 --> 00:24:10.899
1 plus 1. So, this is how this particular
formula is being obtained.
00:24:10.899 --> 00:24:15.990
Now plugging up all the values we will find
out the total number of messages in all the
00:24:15.990 --> 00:24:23.649
phases , that comes out to be this is the
phase 0 messages, 4 times n and this is the
00:24:23.649 --> 00:24:33.409
termination message. And as far as this formula
is concerned, this formula says that how many
00:24:33.409 --> 00:24:43.620
different messages are there for the phases
one to log n minus 1.
00:24:43.620 --> 00:24:51.590
So, this is the summation of different phases,
and every phase will require 4 times 2 raised
00:24:51.590 --> 00:25:00.581
power k times n raised power n divided by
2 raised to power k minus 1 plus 1. So, if
00:25:00.581 --> 00:25:09.179
you compute it comes out to be 8 n log n plus
5 plus 2 plus 5 n. That comes out to be of
00:25:09.179 --> 00:25:16.100
the order n log n. So, we have seen that this
particular algorithm will work both for synchronous
00:25:16.100 --> 00:25:22.269
and asynchronous case. So, the question is
can we reduce the number of messages even
00:25:22.269 --> 00:25:29.110
further than order n log n.
So, we will we have seen that not in asynchronous
00:25:29.110 --> 00:25:39.581
model you can do this better than order n
log n; that for that we can show that this
00:25:39.581 --> 00:25:45.570
is the lower bound for the leader election
problem that is of the order n log n.
00:25:45.570 --> 00:25:51.799
So, the theorem says that any leader election
algorithm for asynchronous rings whose size
00:25:51.799 --> 00:26:00.190
is not known a priori has the lower bound
of n log n message complexity, holds also
00:26:00.190 --> 00:26:07.779
for the unidirectional rings. Both LCR and
HS are comparison based algorithm; that is,
00:26:07.779 --> 00:26:14.549
they use identifiers only for the comparison.
In synchronous algorithms order of n message
00:26:14.549 --> 00:26:21.279
complexity can be achieved if general arithmetic
operations are permitted, non-comparison based
00:26:21.279 --> 00:26:31.820
and if the time complexity is unbounded.
So, overview of leader election in rings with
00:26:31.820 --> 00:26:39.070
the ids, there exist algorithm when the nodes
have unique ids. We have evaluated them according
00:26:39.070 --> 00:26:45.230
to their message complexity, and we found
out that in the case of asynchronous ring
00:26:45.230 --> 00:26:53.059
the message complexity of the algorithm the
best known algorithm gives n log n messages.
00:26:53.059 --> 00:26:59.880
Similarly, for synchronous rings we have seen
that of the order n messages under certain
00:26:59.880 --> 00:27:09.889
conditions. Otherwise, the complexity is the
same that is n log n messages in the comparison
00:27:09.889 --> 00:27:14.360
based algorithms.
So, all these bounds are asymptotically tight
00:27:14.360 --> 00:27:20.620
conclusion. This lecture provided an in depth
study of the leader election problem in the
00:27:20.620 --> 00:27:23.230
message passing system for the ring topology
.
00:27:23.230 --> 00:27:28.360
We are also presented different algorithm
for the leader election by taking different
00:27:28.360 --> 00:27:36.590
cases . Such as anonymous oblique non anonymous
rings, uniform oblique non uniform rings,
00:27:36.590 --> 00:27:46.960
synchronous oblique asynchronous rings.
Thank you .