Machinations


SFI Summer School
June 24, 2011, 6:07 pm
Filed under: Uncategorized | Tags: , , , ,

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 🙂

Advertisements

1 Comment so far
Leave a comment

[…] recently posted slides from one of my own recent talks on this nice randomized MIS algorithm here. […]

Pingback by Bertinoro Addendum « Machinations




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: