Filed under: Uncategorized | Tags: distributed computing, shared memory, theory, workshops
Last week, I attended a great workshop in Banff, Canada on “Probabilistic versus Deterministic Approaches to Shared Memory Computation”. The following is an extremely biased, incomplete and watered down summary – also it only includes morning talks because I was too sleepy in the afternoon to take notes – reader beware.
On Monday morning, Jennifer Welch and I gave back-to-back talks on emulating shared memory objects in “weird” communication models. Jennifer talked about maintaining shared memory consistency under probabilistic churn in a peer-to-peer network. In particular, she described recent work that created a shared read-write register in such a model that loses its state only with some small probability. The technical proofs of correctness relied on careful analysis of continuous time Markov processes. I believe that this paper describes some of their results in this model.
My own talk was on emulating a single writer, multi-reader in a wireless communication model subject to adversarial jamming (link to slides) – this was based on work with Valerie King and Maxwell Young from last PODC. I’ve blogged about this somewhat before so won’t repeat myself. However, if you’re a fan of the golden ratio (and who isn’t?) then you should read the first half of the slides. I had a lot of good feedback at the talk on how to extend these results including: 1) determining what happens when there are multiple communication channels available; 2) what happens if one can use signal processing in the event of a jam to determine what the underlying message was in the case where many processors broadcast the sam underlying message; and 3) determining if one can reduce the power consumption necessary to in order to maintain the state of the shared object, perhaps expending more energy only when there is a need to change state.
On Tuesday, Keren Censor-Hillel and Danny Hendler gave excellent back-to-back talks on restricted use shared objects. Keren started with upper bounds – in particular how to implement a max count register in the restricted use model and Danny followed up with lower bounds from a paper joint with Aspnes, Attiya, and Censor-Hillel. A restricted use object is essentially one where some restriction exists on the number of operations that may be applied to an object. There are two common types of restrictions: 1) m limited use: at most m ops may be applied; and 2) b bounded: at most b values supported by the object. An old result by Jayanti, Tan and Toeg in ’00 shows that Omega(n) work and space is needed for history-less primitives [Jayanti, Tan, Toueg, '00], but these lower bounds don’t apply to restricted use objects. There have been several exciting results showing the possibility of implementing such objects in polylog step complexity (see the talk by Gilbert and Bender below for an example of cool applications of these new results). How can we devise lower bounds for this new type of restricted use object? Danny discussed the notion of L perturbable objects that intuitively can be perturbed at most L times. He gave details of a result (joint with Aspnes, Attiya, and Keren) showing that a L perturbable object must have step complexity Omega(min(log L,n)) and space complexity Omega(min(L,n)). This lower bound is for deterministic objects only; randomized lower bounds are still relatively open (lower bound of Omega(log log m/ log log log m))
On Wednesday, Lisa Higham and Wojciech Golab gave talks on the notion of strong linearizability. I will just touch on the problem they address. When a shared object is linearizable, it intuitively means that the history of invocations and responses to that object can be ordered in time in a way that 1) the total order extends the “happens before” partial order over all the operations; and 2) the ordering obeys correctness properties for the shared object. (I’m probably missing something important here – maybe someone will correct me in the comments). Many (most?) people think that if operations on an object are linearizable, then everything is great: the object acts like it is atomic in the sense that it appears to the rest of the system as if operations on it occur instantaneously.
Lisa and Wojciech showed that these people are sadly mistaken. In a recent STOC result, joint with Wojciech Golab and Philipp Woelfel, it’s shown that linearizability does not suffice in the case where processes can use randomization. They introduce a new concept strong linearizability that is sufficient (and more or less necessary) to ensure correctness of randomized algorithms. Unfortunately, as discussed by Wojciech, it seems that to ensure strong linearizability for most shared objects requires significantly higher resource costs than to ensure linearizability. Valerie King brought up an interesting question about whether for certain types of randomized algorithms, a somewhat weaker notion may work (for example, if the algorithm is Monte Carlo and it’s ok if the scheduler can slightly tweak the probability of “bad” events, so long as this probability never gets too large).
[Note from Wojciech: you said “it seems that to ensure strong linearizability for most shared objects requires significantly higher resource costs than to ensure linearizability." Is your impression based by any chance on the impossibility results I gave during my presentation? Those actually pertain to first-step and first-update linearizability, one of which is strictly stronger than strong linearizability, and the other is incomparable. For strong linearizability itself, there are several upper bounds that Lisa and I didn’t mention as prominently as we should have. In particular, known universal constructions for lock-based objects and wait-free objects tend to be strongly linearizable. Thus, the message we wanted to get across is that strong linearizability is a practical property because it’s readily attainable, and in several important cases it comes at no additional cost beyond the cost of ordinary linearizability. (That’s in contrast to first-step and first-update linearizability.)]
Next, Hagit Attiya led an interesting discussion on how to motivate our work in distributed computing, pointing out that other CS areas, like Machine Learning, are frequently better at “selling” their results. Maurice pointed out that many results that originated in the PODC community (like Byzantine agreement) have been “rediscovered” by the systems community, frequently without significant attibution/homage to the distributed algorithms community. How can we more effectively advertise these results outside our own community? Hint: it may help to have fewer models.
On Wednesday afternoon, we took a road trip to Lake Louise where we saw a great collection of ice sculptures, walked around a beautiful snow covered lake, and learned that penny loafers aren’t the best footwear for a glacial approach.
On Thursday, Seth Gilbert and Michael Bender gave a great joint talk on their recent FOCS paper on “Mutual Exclusion with O(log^2 log n) Amortized Work”. A recent algorithm for this problem was by Danny Hendler and Phillip Woefel (one of the workshop organizers), which showed that it was possible to breakthrough a Theta(log n) barrier (shown by Attiya, Hendler and Woefel); this previous algorithm achieved Theta(log n/ (log log n)) work against an adaptive adversary (in the shared memory world, this essentially means an adversary in the full information communication model). Seth and Michael’s work assumes a weaker adversary that is oblivious in that it can’t see past coin flips by the processors. Their new algorithm is also Monte Carlo in that it ensures each processor gets into the critical section only with high prob.
Some key technical ideas behind their new result are: 1) to use a dense array to store processors that are waiting to enter the critical section; and 2) to create and use clever approximation and work-efficient counters (remember you can only afford O(log^2 log n) work per counter) in order to dynamically manage the array of processors that are waiting. An interesting open problem: Can we prove that an adaptive adv. (i.e. one that has full information) can force at least Omega(log n/log log n) work even if the algorithm ensures access to the critical section only with high prob; or alternatively can we design an algorithm in this model that does better?
Valerie King gave a nice talk in the afternoon, half of which was on connections between the shared memory model and the message passing model for a consensus problem. We’re likely writing a paper on this problem so I’ll probably blog about it later here.
Friday was overcast and cold, which made it a little bit easier to say goodbye to beautiful Banff.
[Thanks to Wojciech Golab for helpful corrections]
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.
