[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

1. Synchronous case

See LynchBook Section 4.4.

1.1. The quick sketch

1.2. The bookkeeping

1.3. Running time analysis

To improve message complexity, we have to avoid extra edge probes. Trick is to (a) throw out edges once the endpoints are in the same component and (b) probe edges leaving each component one at a time in order of increasing weight. This gets message complexity down to O(N log N + E) since each edge is probed at most once. But (b) may require Omega(E) steps in the worst case, e.g. if we end up with two large components at the end most of whose edges are self-loops.

1.4. Applications

2. Asynchronous case

Essentially the same algorithm works, but we have to deal with latecomers by absorbing low-level components into high-level components; see LynchBook Section 15.5.


2014-06-17 11:58