Service (Recruiting)
September 27, 2010, 8:06 pm
Filed under: Uncategorized | Tags: ,

One small, and usually not very exciting, part of the job of a professor is departmental service. This year, I’m on the graduate recruitment committee, something I’ve been enjoying much more than the usual jobs.  As part of our recruitment efforts, I designed the flyer below with the help of our alumni, and a real great graphic designer at UNM.  Part of the fun of this was working with some of our excellent alumni.  I even resisted the standard solipsistic impulse to include my own past students – who, of course, are exceptional – and instead focused on students I knew less well.

These are really a great group of researchers, with great things to say about out department.  It’s nice to be in a job where we were (hopefully) able to help them succeed.

Job opening
September 21, 2010, 8:19 pm
Filed under: Uncategorized | Tags: ,

This one is for a senior researcher.  Please contact me if you decide to apply.

The UNM CS department is looking for a new Chair.  The search is now
officially open.  We would really like to get a strong researcher who can raise the profile of the department, as opposed to just someone moving into administration.

We are an up-and-coming department, with a Theory group consisting of
me (distributed computing), Tom Hayes (Markov chains and on-line
algorithms), Cris Moore (quantum computing), Shuang Luan (approximation
algorithms and computational geometry) and Deepak Kapur (automated
reasoning, and recent recipient of the Herbrand Award).  We also have
strengths in biologically-inspired computing (Stephanie Forrest,
Melanie Moses), molecular computing (Darko Stefanovic), security (Jed
Crandall), high-performance computing (Dorian Arnold), machine
learning (Terran Lane), graphics (Joe Kniss), and other areas as well.
And, New Mexico is a great place to live.

Details are at (click on faculty jobs).  The deadline for best consideration is 11/15.

September SIGACT Distributed Computing Column
September 9, 2010, 4:20 pm
Filed under: Uncategorized | Tags: , ,

The September SIGACT distributed computing column is now available at Technion and at MIT.  This month Valerie and I contributed a survey on scalable Byzantine Agreement – Marko Vukolic considers BA for cloud computing providers.  Idit’s intro to the column is below.

“After almost 30 years of research on Byzantine Agreement (BA), the problem continues to be relevant and to re-invent itself in new ways. This column discusses two new research directions that further push the scale of BA. It suggests new domains where BA can, and perhaps should, be deployed.  First, our main contribution, by Valerie King and Jared Saia, argues for running BA in setting with a large number of nodes (or processors). Valerie and Jared survey new BA protocols whose communication complexity is scalable in the number of participating processors. This, they argue, enables their deployment in larger-scale domains for which BA was considered infeasible before. The second contribution, by Marko Vukolic, considers another emerging domain for BA. It calls for wider-scale deployment of BA protocols, not among many processors, but rather over multiple cloud computing providers.

The column ends with a short announcement about Morgan Claypool’s new monograph series on Distributed Computing Theory, edited by Nancy Lynch.

Many thanks to Valerie, Jared, and Marko for sharing their insights!”

Conflict in Communication Networks
September 2, 2010, 1:51 pm
Filed under: Uncategorized | Tags: , , ,

Imagine that Alice wants to send a message to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is periodically able to block this channel. Further, it costs Alice $a dollars each time she sends on the channel, Bob $b dollars each time he listens on the channel, and Carol $c dollars each time she blocks the channel. If Alice, Bob and Carol all play this game optimally, how much more will Carol need to spend than Alice and Bob in order to block the message?

This problem abstracts many types of conflict on information networks including: web censorship by nation-states, denial of service attacks on the Internet, and jamming  attacks on wireless networks, where the costs to Alice, Bob and Carol can represent expenditure of both computational and human resources. The problem allows us to quantitatively ask: Does information really “want” to be free?

In a new result, Max Young, Valerie King and I answer this question in the affirmative by showing that under optimal play, it is significantly harder for Carol to block the message than for Alice to communicate it to Bob. Specifically, if a,b and c are fixed constants, and Carol spends $X dollars to try to block the message, then Alice and Bob need spend only proportional to $X^{phi – 1} or about $X^{.62} dollars to transmit the message, where phi = (1+ sqrt(5))/2 is the golden ratio. Surprisingly, this result holds even if Alice and Bob do not know the value X, and there are no cryptographic assumptions.