PODC 2011 Accepted papers
March 9, 2011, 6:54 pm
Filed under: Uncategorized | Tags: , , ,

Accepted papers for PODC 2011 are now up on the web here.  There are many interesting papers – here are a few that immediately catch my eye:

  • Error-Free Multi-Valued Consensus with Byzantine Failures by Guanfeng Liang and Nitin Vaidya.  This paper gives a deterministic algorithm for solving multi-valued consensus with Byzantine faults that has asymptotically optimal bandwidth when the number of bits in the input values are large.  The cool thing about the paper is that it uses network coding and an interesting amortized analysis.  Essentially there are multiple runs of  a single bit consensus algorithm.  The single bit consensus algorithm has lightweight checks and is 1) very efficient when the checks detect no malicious behavior; and 2) able to “kick out” a Byzantine processor whenever the checks do detect malicious behavior.
  • “Xheal: Localized Self-Healing Using Expanders” by Amitabh Trehan and Gopal Pandurangan.   Amitabh, my former PhD student, and periodic guest blogger on this blog, is now a postdoc at Technion working with Shay Kutten and Ron Lavi.  This paper is still very secret as Amitabh won’t even send me a copy of the submitted version.  However, we can guess that the paper describes an algorithm that ensures an overlay network 1) keeps paths between nodes short; and  2) keeps degrees of nodes small.  That word “localized” is very tantalizing as it suggests that, unlike previous work, this new self-healing algorithm requires only local communication.
  • “Adaptively Secure Broadcast, Revisted” by Juan Garay, Jonathan Katz, Ranjit Kumaresan and Hong-Sheng Zhou.  Again this paper doesn’t seem to be up on the web and I didn’t get to read it as a member of the PC.  However, the problem itself, described in the paper Adaptively Secure Broadcast by Martin Hirt and Vassilis Zikas, looks interesting: basically the goal is secure broadcast in a scenario where an adaptive adversary can corrupt up to a 1/3 fraction of the players, including the sender.  The original paper by Hirt and Zikas shows that past results on the secure broadcast problem are not secure under composition, and they then present a new protocol that is secure under composition, along with a new simulation-basted security notion for the problem.
  • “Fault-Tolerant Spanners: Better and Simpler” by Michael Dinitz and Robert Krauthgamer.  This paper shows how to create spanners of general graphs that are tolerant to vertex failures.  They give a transformation for k >= 3 that converts every k-spanner construction with at most f(n) edges into a k-spanner construction that can tolerate r faults and uses O(r^3 log n)*f(2n/r) edges.  For the case k=2, they improve the approximation ratio from O(r log n) to O(log n).  Bonus: This last result uses an LP relaxation and the Lovasz Local Lemma.
  • There are several papers that did not make it as regular papers that I hope to see as brief announcements.  Privacy concerns keep me from mentioning anything in particular here, but there were some nice lower bound results that were invited to be resubmitted as brief announcements.  I hope the authors will accept.

Question: Are there no game theory papers this year except the two that we submitted?  This seems surprising.


3 Comments so far
Leave a comment

Jared, many thanks for the ‘tantalizing’ mention 🙂
There is nothing very secret, really, just a few typos!
So, to clarify, what this new work does is maintain expansion/spectral properties to a certain extent (Expansion deteriorates at worse to constant if it was higher) alongwith stretch and degree. The model is rather similar to the Forgiving Graph model [PODC2009]. Of course, we go a step further by putting spectral properties in the mix. However, in the distributed implementation we could come up with so far, we have to use amortized analysis and larger messages.
Two points here:
1. We point out that the algorithm maintains global properties/invariants by doing only local actions and using local information, which is an extension of the theme of our earlier work (i.e. my PhD thesis, ForgivingTree[PODC2008], ForgivingGraph[PODC2009]).
2. By certain reasonable relaxations in the constraints i.e. adversary, costs etc. we are sometimes able to additively maintain more useful invariants. Some invariants may be impossible for certain constraints. Thus, there maybe a possible suite of constraints vs invariants to choose from, depending on the actual application envisaged. Is there a good way to characterize/tabulate this?

Comment by Amitabh Trehan

Jared – Thanks for the mention! Just to clarify our result: Hirt and Zikas showed that adaptively secure broadcast (with a PKI) is *impossible* when 1/2 or more of the parties can be corrupted. But their result assumed an (unrealistic?) corruption model where a party can be corrupted in the middle of sending its messages in some round.

We showed that if messages are sent “atomically” in any given round, then adaptively secure broadcast is achievable for any number of corrupted parties. Moreover, we can achieve a strong simulation-based notion of security (universal composability) without any setup beyond the PKI.

Comment by Jonathan Katz

Amitabh, Thanks for the info. I guess I was overly optimistic about the local communication possibility. However it’s neat that you’re able to maintain expansion at a constant. As far as exploring the tradeoff between constraints and invariants, I think you’re suggesting a broad research program. Probably the best place to start is at the extreme endpoints in the design space. We should talk about this over a conference call at some point…

Jonathan, I must have been confused about the Hirt and Zikas result. I thought they show that simulatable broadcast is possible for t <= n/2 if there is a PKI. Isn't this what they state in the second to last sentence of their abstract? That's quite interesting that your result can tolerate *any* number of corrupted parties. Looking forward to reading the paper!

Comment by Jared

Leave a Reply

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

You are commenting using your 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: