PODC 2012 accepted papers are out (and have been for a while). This looks like a great collection of papers, with many focusing on problems in distributed reliability/security. It’s also nice to see some of my former students represented (Maxwell Young and Amitabh Trehan). Some papers that caught my eye:
Adi Akavia, Shafi Goldwasser, and Carmit Hazay
Distributed Public Key Schemes Secure against Continual Leakage
James Aspnes
Faster Randomized Consensus with an Oblivious Adversary
Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip Gibbons
The Cost of Fault-Tolerance in Multi-Party Communication Complexity
Seth Gilbert and Maxwell Young
Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks
Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen
On the Price of Equivocation in Byzantine Agreement
Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues
On the (Limited) Power of Non-Equivocation
Guanfeng Liang and Nitin Vaidya
Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen
Faster than Optimal Snapshots (for a While)
Stephan Holzer and Roger Wattenhofer
Optimal Distributed All Pairs Shortest Paths and Applications
Michael Backes, Fabian Bendun, and Aniket Kate
Brief Announcement: Distributed Cryptography using TrInc
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan
Brief Announcement: Maintaining Large Dense Subgraphs on Dynamic Networks
The following is a guest post by Mahnush Mohavedi. Mahnush is a first year PhD student at UNM. She got her Masters degree from Amirkabir University of Technology in Iran and I believe this was her first conference in the U.S.
In the third day of PODC conference, there were several interesting talks including:
- “Stability of P2P Communication Systems” by Ji Zhu and Bruce Hajek. This paper discussed the missing piece syndrome in which one piece becomes very rare in a network like Bittorrent, leading to instability in the system. They calculate the minimum amount of help needed from the seed nodes in an information dissemination game in order to stabilize the system, and ensure that all nodes receive a file.
- “Tight Bounds on Information Dissemination in Sparse Mobile Networks” by Pettarin, et al. is a study of the dynamics of information dissemination between k agents performing independent random walks on an n-node grid. They assume communication is determined by a dynamic communication graph process G_t, where two agents are connected in G_t iff their distance at time t is within a specified broadcast radius. They assume that a rumor travels completely throughout a connected component of G_t during round t. They study the broadcast time, T_B, of the system, which is the time it takes for all agents to know the rumor. They study the sparse case for the broadcast radius, where, whp, all components are of size log n. Their main result is that T_B is soft-Theta(n/\sqrt(k)). In particular, for this sparse case, the broadcast time does not depend on the broadcast radius.
- “Rationality Authority for Provable Rational Behavior” by Dolev et al. considers the games in which players are not totally rational and smart. They define a game inventor agent that is able to find the best response of the game and present it to the players. The inventor is rational and may gain revenues from the game. Thus, they introduce verifiers as trustable service providers that can verify inventor’s advices using formal methods. During dinner on Tuesday, I had a chance to talk to Elad who presented the talk. He believes separation of interest, benefits, and goals is the key idea of the work.
- “Distributed Computing with Rules of Thumb” by Jaggard et al. indicates that a large and natural class of simple algorithms fails to guarantee convergence to an equilibrium in an asynchronous setting, even if the nodes and communication channels are reliably failure-free. In particular, they consider algorithms like “best replying” to other player’s actions and minimizing “regret”. They show that these algorithms fail to ensure convergence, in the asynchronous setting, for problems in routing, congestion control, social networks and circuit design.
Several interesting talks today including the following
“Compact Policy Routing” by Revtvari et al. considered the problems of designing small routing tables for routing when the optimization criteria is not necessarily path length. In particular, they note that Internet routing doesn’t use shortest paths, but instead is policy routing: making use of economic and political concerns. Their paper defines routing algebras and explores compressibility of routing tables for different types of optimization functions. A main result of the paper shows that BGP policy routing essentially must give rise to very large routing tables.
“Locally Checkable Proofs” by Goos and Suomela classifies various graph problems according to their local proof complexity. For example, locally checking whether a graph is bipartite requires each node to hold a proof of just 1 bit (the node’s color in a 2-coloring of a graph). In contrast, locally showing that a graph is *not* bipartite requires each node to hold a proof of size Theta(log n) (shown in the paper). The paper categorizes a dozen or so graph problems in terms of locally checkable proof sizes. Possibly interesting connections exist between this paper and the “Toward More Localized Local Algorithms” by Korman, Sereni and Viennot on Day 1. The proofs from this paper could possibly be plugged in as the “pruning algorithms” required by Korman et al.
“Fault-tolerant spanners” by Dinitz and Krauthgamer ” builds spanners that are robust to deletion of r nodes. Specifically, any algorithm that can create a k spanner (k>= 3) with f(n) edges can be converted to a k spanner with O(r^3 log n)*f(2n/r) edges that is “robust” to deletion of r nodes. “Robust” here means that for any set of F nodes, |F| <= r, the original spanner with F deleted is still a k-spanner of the original graph with F deleted. The algorithm is technically quite interesting, making use of a clever LP relaxation and the Lovasz Local Lemma.
“The Round Complexity of Distributed Sorting” by Patt-Shamir and Teplitsky considers a fully connected network where in each round, each node can send a O(log n) bit message to every other node (This is the CONGEST model with diameter 1). They first show that sorting in this model, when each node has at most n items can be done in O(log log n) rounds and selection can be done in O(1) rounds. Then, using a concurrent result by Lenzen and Wattenhofer on routing in the same model (in STOC), they further reduce sorting to O(1) rounds. The interaction between this paper and the result by Lenzen and Wattenhofer is neat, an the model itself is interesting (sort of diametrically opposed to LOCAL), and seems very powerful.
A quick final mention of two papers presented today that I was a co-author on. Varsha Dani gave a nice talk on our “Scalable Rational Secret Sharing” paper, and Maxwell Young gave a nice talk on our “Conflict on a Communication Channel paper.
.
FCRC is happening right now at the San Jose conference center. The following is a guest post by Maxwell Young on Day 1 of PODC.
A nice opening talk was given by Rotem Oshman on the paper “Coordinated Consensus in Dynamic Networks” which is joint work with Fabian Kuhn and Yoram Moses. Many consensus models assume that direct communication is possible between any pair of nodes (ie. a clique communication graph G). Furthermore, the graph topology is typically assumed to be static. Here, the authors studied a more generalized problem setting where the G is connected, but not necessarily a clique, and the topology can change over time to reflect unreliable links and connectivity failures. Eventual, simultaneous, and Delta-coordinated consensus are all examined with Rotem spending more time discussing lower bounds for the last two variants. Indeed, when it comes to simultaneous consensus, the news is bad as the authors show a lower bound of n-1 rounds. Relaxing this to Delta-coordinated consensus does not provide much relief. Here, *in the worst case*, the round complexity is n-Delta-1. However, under certain (still fairly general) circumstances, one can do much better — for instance, in the “clear-majority” case where the fraction of identical inputs is bounded away from 1/2. Rotem also provided an overview of an intricate argument involving a static line graph that yields a lower bound of similar form to the clear-majority result, although not quite tight with the upper bound.
Another interesting morning talk was given by Guanfeng Liang on the topic of achieving consensus in the presence of Byzantine faults (joint work with Nitin Vaidya). Of course, there has been an enormous amount of work done in this area. The main contribution by Liang and Vaidya is demonstrating an *error-free* consensus algorithm for L-bit messages that improves quadratically (in n) on the bit complexity of previous work when L is large. This is achieved by running consensus on chunks of the input message in combination with error-detection codes and the use of an “accusation” graph. In terms of practical utility, Guanfeng (seated next to me in this session) mentioned that the utility of larger messages in consensus is that they ameliorate the overhead that one would get from using other protocols that handle a single bit at a time. From a performance perspective, this facet of the problem, in combination with their improved round complexity, would obviously yield higher network thoughput.
Particularly interesting was David Ferrucci’s presentation of the work he and his team did at IBM on developing the JEOPARDY!-winning system “Watson”. At first glance, this challenge may seem solvable through brute force. Why not categorize and store the top questions (and their possible permutations) in a format that allows standardized queries? Then parse asked questions correctly, throw enough computational power at the setup in order to get it to work in game-show time, and voila! Unfortunately, this approach immediately encounters problems – binning the questions by topic yields a heavy-tailed distribution. Therefore, storing the most frequently-asked questions would leave Watson grasping at straws for much of the show. Over the course of an hour, Ferrucci managed to convey the massive scope of the problem and IBM’s solution which spans the areas of natural language processing, machine learning, algorithmics, massively parallel architectures and more.
Something closer to home was Calvin Newport’s afternoon talk “Structuring Unreliable Radio Networks ” which is joint with Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn and Nancy Lynch. The talk centered around a model of wireless sensor networks where the communication graph consists of both reliable and unreliable links. Here, each node has access to information about the reliability of its links to neighbors via a detector. In practice, this information is obtained through algorithms running low in the protocol stack. Given this setting, the authors studied the problem of building a connected constant-degree dominating set (CCDS) which can provide an efficient communications backbone in a sensor network. For a detector that never misclassifies links, the authors show that CCDS can be solved in time roughly O(polylog n) rounds given reasonable bounds on the maximum degree (in terms of reliable links) and the message size. But of particular interest is the lower bound: If the detector misclassifies even *one* link, CCDS requires Omega(D) rounds, clearly separating this class of problems from more optimistic setting where sure knowledge of reliable links yields polylogarithmic behaviour.
The theory-oriented literature (a lot of it from PODC) reports on lower bounds in the context of wireless sensor networks. An interesting question was asked at the end of Calvin’s talk regarding how the lower bound in the paper plays out in the real-world. Calvin’s response, and one that I asked him more about later on, was that current sensor network deployments are typically small in size; consequently, the costs implied by such a lower bound result (and other lower bound results regarding efficiency) are likely not an issue. However, as systems grow in size, practitioners may see such results manifest – although, which lower bounds will be applicable remains to be seen.
Along similar lines, during one of the coffee breaks, I had the opportunity to talk with Christian Scheideler about how theoreticians have been prompted by practitioners to address more realistic models. Contending analytically with the kind of wireless interference that occurs in real-world deployments can be messy. One approach is to work with the SINR model; however, certain issues, such as addressing the RSSI threshold in the context of receiver-side collision detection, seem difficult to resolve satisfyingly. As another example, in terms of jamming attacks, going back a few years we see many papers that address oblivious adversaries who make their jamming decisions independently of the good parties. However, more challenging reactive adversaries have been demonstrated and, consequently, recent work by the theoretical community tends to address this attack model. In any event, if Calvin’s prediction bears out, the implications for large wireless sensor networks may be somewhat gloomy – depending on which lower bounds hold true – but, as a silver lining, it would also validate some of the efforts made by the theoretical community.
This year PODC has done 10 podcasts on papers that will be appearing in the upcoming conference. There are several minute interviews with an author of each paper. The interviews I’ve listened to are very well-done, although definitely geared to a technical audience. Valerie King does a nice interview on our own upcoming paper “Conflict on a Communication Channel”.
Filed under: Uncategorized | Tags: distributed computing, game theory, PODC, security
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.
Filed under: Uncategorized | Tags: algorithms, cryptography, game theory, PODC, security, theory
Decisions for PODC 2011 (in San Jose) have just been mailed out this morning. In a later post, I’ll talk about some of the interesting accepted papers this year – there are many. For now I wanted to mention two of my own papers that were accepted and are now up on my web page.
Conflict on a Communication Channel. This is a paper that I had previously blogged about here. I’m still very excited about the idea of maintaining security invariants while spending asymptotically less than an adversary that is trying to break them. In this paper, we were able to do this for a few problems related to jamming in sensor networks and denial of service attacks. However, the application of this kind of game theoretic analysis to security problems is still wide open. Many interesting problems remain.
Scalable Mechanisms for Rational Secret Sharing. This is a paper that I had not previously talked about in this blog. The paper considers the problem of secret sharing when each player is rational. In particular, we assume that each player prefers to learn the secret over not learning it, but prefers to be the only player learning the secret over being one of many players learning it. Much interesting work has been done on this problem in the last few years, with the main goal being to design a mechanism that ensures that ensures that all players learn the secret (thereby maximizing social welfare). The new problem we focus on in this paper is designing mechanisms that both reveal the secret to all players and are scalable in the sense that they require each player to send just a constant number of messages in expectation. Secret sharing is a subroutine for many cryptographic protocols, so one motivation is to develop a scalable tool for problems like rational multiparty computation and implementation of a mediator.
Too many good talks on this last day of PODC to do them all justice. Just a smattering of what I found interesting:
- “Deterministic Distributed Vertex Coloring in Polylogarithmic Time” by Barenboim and Elkin. This is the other vertex coloring paper at PODC (with which we shared the best paper award). The main result is a deterministic algorithm that runs in polylog time and uses only O(Delta^(1+epsilon)) colors. In face, in polylog time, O(alpha^(1+epsilon)) colors are possible where alpha is the arboricity of the graph. I won’t go into technical details of the talk here, but I do want to point to a nice primer on distributed vertex coloring with applications. It’s neat that after the question of improving the number of colors needed for polylog vertex coloring had been open for a quarter of a century, two papers at this PODC, gave significant improvement over the old O(Delta^2) result.
- “Optimal Gradient Clock Synchronization in Dynamic Networks” by Kuhn, Lenzen, Locher and Oshman studies clock synchronization in networks where communication links can appear and disappear at any time, rate of hardware clocks can vary arbitrarily, and estimates a node can get of the clock time of another node are inherently inaccurate. They are able to output a logical clock for each node such that the logical clocks of any two nodes are not too far apart, and nodes that remain close to each other in the network for a long time are better synchronized than other nodes. I know very little about this area, but I definitely enjoyed the talk and am particularly intrigued by this follow-up paper to appear in FOCS ’10. It shows how to use the PODC result to perform arbitrary computation over dynamic networks in which the network topology changes from round to round, provided that the network is T-interval connected. “A network is T-interval connected if for every T consecutive rounds, there exists a stable connected spanning subgraph. For T=1, the graph is connected in every round, but can change arbitrarily between rounds.”
- “How to Meet when you Forget: Log-Space Rendezvous in Arbitrary Graphs” by Czyzowicz, Kosowski and Pelc. This paper shows how deterministic agents with only log space can either 1) rendezvous in a graph or 2) determine that the graph is constructed in such a way that rendezvous is not possible. The assumption is that the nodes of the graph are indistinguishable and the agents, on visiting a node only become aware of the immediate neighbors of that node. It took me a while to realize that rendezvous may be impossible, this occurs when the graph is symmetric to the degree that any two deterministic agents will chase each other around indefinitely (for example, I think a cycle will cause this), and is an artifact of the lack of randomness for symmetry breaking. The paper makes use of results from the famous paper by Reingold on “Undirected Connectivity in Log-space”
- “Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary” by King and Saia. I’m biased of course but I think Valerie gave a great talk on our paper! Slides are here.
Thanks to everyone for a great PODC. See you next year in San Jose!
Filed under: Uncategorized | Tags: algorithms, distributed computing, PODC, theory
In the invited talk, Pierre Fraigniaud pointed out a dichotomy in the PODC community: one community (the reds) is mostly interested in timing issues: asynchrony, link delays, crashes, etc.; the other community (the blues) is mostly interested in spatial issues: network structure, memory requirements, local computation, etc. His analogy was with the political divisions in the U.S. – Can’t we all just get along? In my own research, I think the problems are from the red community (Byzantine agreement, consensus) but the techniques used are from the blue (expanders, samplers). It’d be nice to have more mathematical techniques in our community that are of use to both the reds and the blues.
Talks I found particularly interesting follow:
- Great talk by Gopal Pandurangan on “Efficient Distributed Random Walks with Applications”. Their work returns a random walk of k steps in much less than k time. Essentially they can get down to about square root of kD time in a distributed setting, where D is the diameter of the network. The do this by pasting together short walks that are run in parallel at each node – however the “pasting together” and generation of the walks has to be done in a smart way to avoid congestion. It does not work to have the length of each short walk be deterministic. Attention Students: Gopal has a post doc position available. How a post doc position with a great researcher can still be open in this economic climate is mind boggling to me.
- Nice brief announcement by Lasse Kliemann on distributed network formation in an adversary model – basically an adversary removes one edge from the network after it is formed by selfish agents. Surprisingly, this game seems to have a small price of anarchy.
- Nice talk on distributed vertex coloring by Johannes Schneider: “A New Technique for Distributed Symmetry Breaking”. There are two papers at this PODC that have solved a very old problem (> 10 years old?): Can we color a graph with O(Delta) colors in polylog parallel time? This is the paper that solves the problem with a randomized algorithm. The other paper solves it deterministically (and won the best paper award – see below).
- Great talk by Sriram Pemmaraju on “Rapid Randomized Pruning for Fast Greedy Distributed Algorithms”. He presented a general “market based” technique for pruning in greedy algorithms. The technique is powerful enough to provide good greedy algorithms for many types of problems. I asked Sriram after the talk if he had a characterization of the types of problems for which his technique applied. Nothing formal, but he suggested that problems that have a kind of “local” flavor to them (can be solved or approximated locally) may be amenable to his approach.
The conference banquet was at a restaurant on the top of Zurich’s backyard mountain. Valerie and I were thrilled there to receive the best paper award, for our paper on “Breaking the O(n^2) bit barrier: Scalable Byzantine agreement with an Adaptive Adversary”. We shared the award with Barenboim and Elkin and their paper “Deterministic Vertex Coloring in Polylogarithmic Time”. Many people afterward asked me if our paper was a red one or a blue one. I decided that I like to think of it as purple. This was really a great night! It’s so nice to get this recognition after years of hard work on this problem.
Greetings from Zurich and the morning of the second day of PODC! Went for a short hike when I arrived on Sunday in the mountains above the city: m
eadows, mountain views, cowbells, great chocolate for a snack, lots and lots of very healthy looking blond people – a complete Swiss experience! Pictured on the right is the Swiss National museum next to lake Zurich which abuts the city.
Yesterday Hagit Attiya gave an invited talk on Transactional Memory. The tone of the talk was pessimistic about the benefits of transactional memory, arguing that it has significant theoretical and practical limitations, and that it weakens either consistency or progress guarantees (or simplicity). The talk called for a post-Transaction memory era where we should use techniques like “mini-transactions” that don’t over-promise to the programmers who are facing the difficult challenge of programming in a parallel environment.
Two other talks I enjoyed:
- “Partial Information Spreading with Application to Distributed Maximum Coverage” by Keren Hillel and Haden Shachnai. This talk introduced a nice generalization of the property of graph conductance and then showed how this generalization could be useful for approximating the maximum coverage problem in a distributed setting. I like the generalization of conductance, weak conductance, that was presented since I think many real-world networks may tend to have high weak conductance even though they have low conductance
- “Adaptive Randomized Mutual Exclusion in Sub-Logarithmic Time” by Danny Hendler and Phillip Woelfel. A very nice talk covering many mathematical details of what seems like a subtle proof of correctness for a randomized mutual exclusion algorithm. I know very little about mutual exclusion but felt the talk gave me a good flavor of the mathematical techniques used in the area.
Quick business meeting summary: brief announcements are good, they boost attendance; attendance is up at the least couple of PODCs; to rebuttal or not to rebuttal?; PODC 2011 will be in San Jose, CA; PODC 2012 will be in Madeira, Portugal, known for its bananas, sweet wine and warm waters.
