Just getting back from a great visit to Ann Arbor to work with Maxwell Young, Seth Pettie and Valerie King. Perhaps the most important discovery at Ann Arbor for several of us was the existence of sour beer.

I also gave a talk on our polynomial time Byzantine agreement result. The talk went well with many questions and ideas. Unfortunately, though it seems like an hour is the bare minimum to convey the problem and ideas of our algorithm – kind of worried about what to do in 20 minutes at STOC.

Talk slides are now up on my web page. Comments welcome!

Roger Wattenhoffer shares with me slides from his talk on “local looking” distributed algorithms that I think will be interesting to the distributed computing community. This talk was given at **another** workshop at Bertinoro this summer – a workshop on sublinear algorithms (blogged by Piotr Indyk here). Roger’s talk particularly focuses on lowerbounds and upperbounds for many “local looking” distributed problems like Maximal Independent Set, Minimal Vertex Cover, Minimum Dominating Set and Maximal Matching. The talk discusses the known lowerbounds for these problems: they are all known to require a number of rounds that is Omega(sqrt(log n)) and Omega(log Delta).

The talk also discusses upperbounds – in particular it also discusses a beautiful randomized algorithm for Maximal Independent Set that takes O(log n) rounds in expectation (I’ve recently posted slides from one of my own recent talks on this nice randomized MIS algorithm here. )

Finally, the talk illuminates many interesting open problems in distributed algorithms for these types of problems:

- Is there a deterministic algorithm for Maximal Independent Set (MIS) that takes polylog n rounds?
- Can we close the gap for randomized algorithms for MIS between the best lowerbound O(sqrt(log n)), and the best upperbound, O(log n)?
- What are the problem boundaries between O(1), O(log*n), O(log n) and O(diameter)? A nice picture illustrating what is open on these boundaries is given in the last couple slides of the talk.

Filed under: Uncategorized | Tags: algorithms, complex systems, distributed computing, talks, theory

If you don’t live in New Mexico [1], you’ve probably never heard of a mangonada. Basically, it’s frozen mango pulp on a stick, served in a cup that contains lime juice, chili and salt. You dip the mango popsicle in the cup as you eat it. A mangonada is simultaneously too sweet, too salty, too spicy and too sour, but somehow, after a few licks, it starts to make sense.

At its best, the Santa Fe Institute is kind of like a mangonada. It’s aplace where people simultaneously do research in economics, physics, sociology, biology and computation. The research agenda is ridiculously broad and ambitious, but sometimes it works out.

This summer, I had the pleasure of lecturing at the Santa Fe Institute Complex System Summer School – a program that brings together about 100 graduate students in many disciplines from all over the world.

This was a great chance for me to think about what is fundamental about distributed algorithms, what are some of the key ideas and problems that students in economics, math, biology, physics, and sociology need to know. The links below give the material that I chose to talk about. Basically I spent the first lecture on “traditional” distributed computing problems, where we can tell each node exactly what algorithm to run. Then I spent the second lecture on the harder models where only some of the nodes run our algorithm, or worse, no node will run our algorithm unless it’s in that nodes best interest.

The students seemed particularly engaged in the second lecture, and I was surprised about the level of interest in Byzantine agreement, which I almost didn’t include at first, since it seemed a bit esoteric. I talked to several students after the lectures, including a biologist and sociologist who were interested in connections between these types of problems and the problems faced by social insects and social groups. I always find it very energizing to talk to bright young scholars and I’m looking forward to next summer.

Here are my lectures:

Special thanks to Sriram Pemmaraju who helped me out with the distributed graph coloring material, and to Roger Wattenhoffer for his excellent class notes on distributed graph coloring.

[1] or old Mexico I assume 🙂