Filed under: Uncategorized | Tags: algorithms, distributed computing, theory
It’s always nice when a former student does good. Amitabh Trehan, who got his PhD with me at UNM, recently received the best paper award at ICDCN for his paper “Sublinear Bounds for Randomized Leader Election” (joint with Shay Kutten, Gopal Pandurangan, David Peleg and Peter Robinson).
Amitabh is currently a post doc at Technion with Profs. Shay Kutten and Ron Lavi. Rumor has it that he is looking for a academic position…
Filed under: Uncategorized | Tags: 3D printing, algorithms, distributed computing, theory
So this is where the distributed computing community can interact with the interesting new world of “3D printing”…
“Imagine that you have a big box of sand in which you bury a tiny model of a footstool. A few seconds later, you reach into the box and pull out a full-size footstool: The sand has assembled itself into a large-scale replica of the model.
That may sound like a scene from a Harry Potter novel, but it’s the vision animating a research project at the Distributed Robotics Laboratory (DRL) at MIT’s Computer Science and Artificial Intelligence Laboratory. At the IEEE International Conference on Robotics and Automation in May — the world’s premier robotics conference — DRL researchers will present a paper describing algorithms that could enable such “smart sand.” They also describe experiments in which they tested the algorithms on somewhat larger particles — cubes about 10 millimeters to an edge, with rudimentary microprocessors inside and very unusual magnets on four of their sides….
Algorithmically, the main challenge in developing smart sand is that the individual grains would have very few computational resources. “How do you develop efficient algorithms that do not waste any information at the level of communication and at the level of storage?” asks Daniela Rus, a professor of computer science and engineering at MIT and a co-author on the new paper, together with her student Kyle Gilpin. If every grain could simply store a digital map of the object to be assembled, “then I can come up with an algorithm in a very easy way,” Rus says. “But we would like to solve the problem without that requirement, because that requirement is simply unrealistic when you’re talking about modules at this scale.” Furthermore, Rus says, from one run to the next, the grains in the heap will be jumbled together in a completely different way. “We’d like to not have to know ahead of time what our block looks like,” Rus says.”
http://web.mit.edu/newsoffice/2012/smart-robotic-sand-0402.html
There’s a nice article on Eric Demaine’s work on origami in Nature recently, along with some beautiful pictures. I like the fact that it’s probably the only article in Nature that has ever contained the phrase “balloon animals”.
Filed under: Uncategorized | Tags: algorithms, secure multiparty computation, security, theory
Attached is a paper on a problem we’ve been working on for a while: an efficient algorithm for Secure Multiparty Computation (SMPC) against a static adversary.
In the SMPC problem, n players each have a private input, and their goal is to compute the value of a n-ary function, f, over the inputs, without revealing any information about the inputs. The problem is complicated by the fact that a hidden subset of the players are controlled by an adversary that actively tries to subvert this goal.
SMPC abstracts several important problems in distributed security, and so, not surprisingly, there have been thousands of papers written
in the last several decades addressing it. However, there is a striking barrier that prevents wide-spread use: current algorithms to solve SMPC are not resource efficient. In particular, if there are n players involved in the computation and the function f can be computed by a circuit with m gates, then most algorithms require each player to send a number of messages and perform a number of computations that is
We describe scalable algorithms for SMPC against a static adversary. We assume a partially synchronous message passing communication model, but unlike most related work, we do not assume the existence of a broadcast channel. Our main result holds for the case where there are $n$ players, of which a 
Below is the last problem on a midterm for my graduate algorithms class. A few years ago, I started creating problems for this class that were based on (simplifications of) research problems. There’s a subset of the students that really like these problems and do well on them, but I worry sometimes that they hurt the students who are struggling in the class. I’m curious if others assign these types of problems for general graduate classes?
Today I want to talk about an interesting result in Pippenger’s paper “Networks of Noisy Gates” for the Von Neumann noisy gates model. Recall that in this model, each noisy gate fails independently with some fixed probability \epsilon. We are given a circuit to compute a function with m regular gates and our goal is to compute the same function with probability great than 1/2 with as few noisy gates as possible.
In previous posts, we showed that n \log n gates are always sufficient and we showed that for the exclusive-or function, n \log n gates are necessary. This implies that in the worst case, there is a log n blowup in the number of gates required.
There is another result by Pippenger that shows that for *most* boolean functions, only a *constant* blowup is required. Today I want to focus on the first part of this result, which is to show that a multiplexer (MUX) over 2^r signals can be computed with only O(2^r) noisy gates. Recall that a MUX over 2^r signals is a circuit that takes as input both 1) 2^r possible signals; and 2) an r bit selector. The MUX outputs exactly one of the 2^r possible signals, specifically the one that is specified by the r bit selector.
For example, a MUX for r=1 has as input 1) 2 signal bits; and 2) a single selector bit. If the selector bit is 0, the MUX outputs the first signal bit and if the selector bit is 1, the MUX outputs the second selector bit. Let G be a gate that computes the MUX for r=1. Then it’s easy to create a MUX for any r by wiring up O(2^r) copies of G (try it). In particular, a MUX for r requires at least 2^r noise free gates.
Pippenger shows that you can create a MUX for any r using only O(2^r) noisy gates. Clearly this is just a constant blowup over the number of noiseless gates needed to create such a MUX. The construction used to prove this result is sketched in the figure below. See also this pdf: pipp-mux
Note that any boolean function over x inputs can be computed using a MUX, where r=x (the computation is done essentially by table lookup). This means that we can now compute any boolean function over x inputs with O(2^x) noisy gates. It turns out that most boolean functions over x variables require 2^x/x noise-free gates. In my next post, I’ll show how we can shave off this factor of x in the noisy gate world.
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, data structures, theory, workshops
Bertinoro is a small town near Bologna, with a castle on a hill, a monastery just below it and a beautiful view of farmland and the Mediterranean. It’s now a popular site for workshops (kind of like Dagstuhl), which are held in the castle.
This summer was the second time that I attended the Algorithms and Data Structures (ADS) workshop at Bertinoro. There were many interesting clusters of talks. I’m just going to touch on a very biased sample of some of the talks I remember below:
- Andrew Goldberg talked about new algorithms for solving the single-source shortest path problem on graphs with low “highway” dimension. Intuitively a graph has small highway dimension if for every positive r, there is a “sparse” set of vertices S_r such that every shortest path of length r passes through S_r, where sparse means that every ball of radius O(r) contains a small number of elements in S_r. Renator Werneck and Daniel Delling talked about additional aspects of the SSSP problem, namely 1) handling arbitrary metrics quickly in order to handle, e.g. real-time traffic updates (Weneck); and 2) showing a connection between highway dimension and VC-dimension, and showing that a labeling algorithm coming out of the distributed computing community improves theoretical and practical performance (Delling). This research on fast single source shortest paths algorithms has been going on for years at MSR – it’s nice to see a practical problem so thoroughly investigated.
- For research in data structures, you can’t do much better than Sleator and Tarjan. Bob Tarjan talked about a way to maintain search trees so that rebalancing occurs only on insertion, not deletion (thereby significantly simplifying the rebalancing process). Daneil Sleator talked about, Skip-Splay, a BST data structure that nearly achieves the unified bound (intuitively a data structure that satisfies the unified bound has good performance for sequences of operations where most accesses are near a recently accessed element). On a more practical note, Michael Bender talked about work done at his company on designing a data structure for membership queries that is optimized for 1) space, and 2) writes. Like a Bloom Filter, the data structure trades off space for a false positive rate. However, the new data structure scales beyond main memory, and is optimized for writes and for flash memory. The talk was titled: “Don’t Thrash: How to Cache Your Hash on Flash”
- Distributed computing was represented by Faith Ellen, Sid Sen, Valerie King and me. Faith talked about a communication model conjecture with applications to proving superpolylogarithmic lowerbounds for dynamic data structures. Sid talked about the cost of equivocation in Byzantine agreement – namely what happens if we have partial broadcast channels among sets of 3 processors. Valerie talked about our work “Conflict on a Communication Channel” that I’ve blogged about here previously. I talked about our recent work on scalable rational secret sharing (slides are here).
All in all this was a great workshop. Lot’s of smart people, beautiful scenery, and 4-hour Italian-style dinners (3 courses of alcohol!) in which to think about the big problems in algorithms and data structures.
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 🙂
Last week, I visited Iowa City to give an invited talk at U. of Iowa. Iowa City is a surprisingly hip place with amazing food (after all they’re close to lots of farmland). It’s a town where you can get a matcha&blueberry waffle, a pretty decent machiatto and a t-shirt reading “I was into Iowa before Iowa was cool”.
Sriram Pemmaraju was my host there. We talked a bit about his PODC ’11 paper “Distributed Coloring in Few Rounds”, which describes a distributed algorithm that quickly colors graphs with small arboricity, and some of his recent work on epidemiology. The other theoretician I talked to in the department is Kasturi Varadarajan who told me a bit about his work on planar sensor cover – a STOC ’09 paper describes some of his older results on this problem.
My talk (new slides at this link) surveyed recent work on scalable Byzantine agreement, along with some new work on a game theoretic analysis of conflict on a communication channel. The questions from the audience were interesting and seemed to divide equally between making the work more practical (reducing constants, relaxing assumptions about the adversary), and making the work more theoretical (finding matching lower bounds).
Machinations 