patternMinor
What is a "wasteful" execution? And a "schedule"?
Viewed 0 times
whatwastefulandscheduleexecution
Problem
I'm trying to understand what this text means in my textbook about distributed leader election algorithms, but I can't make any sense of it. Either they didn't explain what was meant, or I missed it somewhere.
In this section, we show that the leader election algorithm of Section 3.3.2 is asymptotically optimal. That is, we show that any algorithm for electing a leader in and asynchronous ring sends at least $\Omega(n\log n)$ messages. The lower bound we prove is for uniform algorithms, namely, algorithms that do not know the size of the ring.
We prove the lower bound for a special variant of the leader election problem, where the elected leader must be the processor with the maximum identifier in the ring; in addition, all the processors must know the identifier of the elected leader. The proof of the lower bound for the more general definition of the leader election problem follows by reduction.
Assume we are given a uniform algorithm $A$ that solves the above variant of the leader election problem. We will show that there exists an admissible execution of $A$ in which $\Omega(n\log n)$ messages are sent. Intuitively, this is done by building a "wasteful" execution of the algorithm for rings of size $n/2$, in which many messages are sent. Then we "paste together" two different rings of size $n/2$ to form a ring of size $n$, in such a way that we can combine the wasteful executions of the smaller rings and force $\Theta(n)$ additional messages to be received.
Although the preceding discussion referred to pasting together exections, we will actually work with schedules. The reason is that executions include configurations, which pin down the number of processors in the ring. We will want to apply the same sequence of events to different rings, with different numbers of processors. Before presenting the details of the lower bound proof, we first define schedules that can be "pasted together".
A schedule $\sigma$ of $A$ for a particular ring is open if there exis
In this section, we show that the leader election algorithm of Section 3.3.2 is asymptotically optimal. That is, we show that any algorithm for electing a leader in and asynchronous ring sends at least $\Omega(n\log n)$ messages. The lower bound we prove is for uniform algorithms, namely, algorithms that do not know the size of the ring.
We prove the lower bound for a special variant of the leader election problem, where the elected leader must be the processor with the maximum identifier in the ring; in addition, all the processors must know the identifier of the elected leader. The proof of the lower bound for the more general definition of the leader election problem follows by reduction.
Assume we are given a uniform algorithm $A$ that solves the above variant of the leader election problem. We will show that there exists an admissible execution of $A$ in which $\Omega(n\log n)$ messages are sent. Intuitively, this is done by building a "wasteful" execution of the algorithm for rings of size $n/2$, in which many messages are sent. Then we "paste together" two different rings of size $n/2$ to form a ring of size $n$, in such a way that we can combine the wasteful executions of the smaller rings and force $\Theta(n)$ additional messages to be received.
Although the preceding discussion referred to pasting together exections, we will actually work with schedules. The reason is that executions include configurations, which pin down the number of processors in the ring. We will want to apply the same sequence of events to different rings, with different numbers of processors. Before presenting the details of the lower bound proof, we first define schedules that can be "pasted together".
A schedule $\sigma$ of $A$ for a particular ring is open if there exis
Solution
I'm not completely sure of my answer since I don't have the book but I think that:
By "wasteful" execution they mean an execution that follow $A$ but with a lot of messages. There are trying to prove that for $n$ processes you may need $\Omega(n\log(n))$ messages. So they consider a ring with $n/2$ processes and the worst execution and they want to combine two of this rings and of those executions to prove that for $n$ processes you will need a least $n\log(n)$ messages.
By scheduler I think the mean a function $\sigma$ that a each state of your system associate a process and an action to be performed. A fixed system and a scheduler are equivalent to an execution (since you can see it as $s\xrightarrow{\sigma(s)}s_1\xrightarrow{\sigma(s_1)}s_2\xrightarrow{\sigma(s_2)}\dots$ But schedulers are often more easy to work with since they are functions so in the proof you don't need to manipulate indexes of where you are in the execution.
I hope it helps, please ask if I missed something.
By "wasteful" execution they mean an execution that follow $A$ but with a lot of messages. There are trying to prove that for $n$ processes you may need $\Omega(n\log(n))$ messages. So they consider a ring with $n/2$ processes and the worst execution and they want to combine two of this rings and of those executions to prove that for $n$ processes you will need a least $n\log(n)$ messages.
By scheduler I think the mean a function $\sigma$ that a each state of your system associate a process and an action to be performed. A fixed system and a scheduler are equivalent to an execution (since you can see it as $s\xrightarrow{\sigma(s)}s_1\xrightarrow{\sigma(s_1)}s_2\xrightarrow{\sigma(s_2)}\dots$ But schedulers are often more easy to work with since they are functions so in the proof you don't need to manipulate indexes of where you are in the execution.
I hope it helps, please ask if I missed something.
Context
StackExchange Computer Science Q#12435, answer score: 2
Revisions (0)
No revisions yet.