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 exists an edge $e$ of the ring such that in $\sigma$ no message is delivered over the edge $e$ in either direction; $e$ is an open edge of $\sigma$.
There is lots more, but I don't know if I should type it all out if only for copyright reasons. I hope this is enough to help clarify my question and get an explanation.