Wednesday, April 11, 2007

Electronic voting systems & other NSDI 07 fun and games

NSDI07 in Cambridge, MA, USA,
is very good. I just saw a neat talk at NSDI by Ron Rivest on the problems and some suggested solutions for electronic voting systems - seemed to me his ThreeBallot system (and some others) are amenable to horrible denial of service attacks on the integrity check (brings whole new power to the ballot spoiler) but I need to go check this more carefully.

On the other hand, why prop up an outmoded form of government like democracy? its like trying to build computer systems that use 25% less power, when we are still expanding the number of cars on the planet at the same rate as PCs:)

Meanwhile, I notice a surprising number of people here are
1) not using MACs
2) are using Windows (XP!)
for an allegedly "systems" conference!!!

wouldn't it be cool to survey OSDI, NSDI, PLDI, HOT*, SOSP, SIGCOMM, INFOCOM for OS/laptop preferences...

First paper
Do Incentives Build Robustness in BitTorrent?

Michael Piatek, Tomas Isdal, Thomas Anderson, and Arvind Krishnamurthy
is clueful work on fixing incentives more carefuly in p2p systems like bittorrent.(won student paper award) - very solid work - bittyrant client well worth a looksee.
anyone using up v. down link strategies should look at this work (e.g. also applies in MANET, DTN, as well as pdp)...

2nd paper
Exploiting Similarity for Multi-Source Downloads Using File Handprints

Himabindu Pucha, Purdue University; David G. Andersen, Carnegie Mellon University; Michael Kaminsky, Intel Research Pittsburgh
is on finding common sub-parts of common downloads for multi-source download using handprints - looking like rabin fingerprint things done elsewhere...but applied to source selection - solid engineering research. This paper also made the
bbc news website the same day!

3rd paper
Cobra: Content-based Filtering and Aggregation of Blogs and RSS Feeds
Ian Rose, Rohan Murty, Peter Pietzuch, Jonathan Ledlie, Mema Roussopoulos, and Matt Welsh,
on aggregating blog/rss feed (argh - am I being aggregated as I speak:)
peter pietzuch was a co author, so essentially this is a mash up of blog/rss with pub/sub/event/notify, and nicely done...very large reduction in bandwidth (as you'd expect given how daft RSS is and how good systems like Siena are) - useful to fix the naivite of RSS, though - either to reduce server load, or improve latency/timeliness!

4th paper
Information Slicing: Anonymity Using Unreliable Overlays
Sachin Katti, Jeff Cohen, and Dina Katabi,
looks rather like Eternity done via Ron with onion routing...! but nice systems paper - definitely worth a read if you want to see how to put all the ideas together in an elegant fashion - Sachin did his usual very fine laid back, but humerous and clear presentation which is a relief from the typical rather over zealous and aggresive MIT thang:)

5th paper is

SAAR: A Shared Control Plane for Overlay Multicast
Animesh Nandi, Rice University and Max Planck Institute for Software Systems; Aditya Ganjam, Carnegie Mellon University; Peter Druschel, Max Planck Institute for Software Systems; T.S. Eugene Ng, Rice University; Ion Stoica, University of California, Berkeley; Hui Zhang, Carnegie Mellon University; Bobby Bhattacharjee, University of Maryland

is what to do if no-one deploys multicast ever (unlike now, then:-), and everyone wants 1 way to do multicast (unlike now, then:-) workmanlike proposal/eval...I'm still waiting for someone to do a decent architecture that uses wide area native IP multicast AND P2P, where appropriate - its non trivial due to the potential overlap

Ricochet: Lateral Error Correction for Time-Critical Multicast
Mahesh Balakrishnan and Ken Birman, Cornell University; Amar Phanishayee, Carnegie Mellon University; Stefan Pleisch, Cornell University

moving to a new model of time critical....this was a sideways look at the Reliable Multicast space - PGM has hooks in it to do this sort of thing, but was never (to my knowledge) engineered to use them so its nice to see how to, especially from folks that have been doing quality RM work since day zero!

Next, wireless networky stuff:-

WiLDNet: Design and Implementation of High Performance WiFi Based Long Distance Networks
Rabin Patra and Sergiu Nedevschi, University of California, Berkeley, and Intel Research, Berkeley; Sonesh Surana, University of California, Berkeley; Anmol Sheth, University of Colorado, Boulder; Lakshminarayanan Subramanian, New York University; Eric Brewer, University of California, Berkeley, and Intel Research, Berkeley

so the reason this is cool is that they basically bring together a number of modest changes to 802.11, which all combined let you run it over 100km (40m) and sort out a few problems with interference and fairness...its based on a real empirical set of results so pretty much more than plausible, but is probably not the kiss of dfeath to Wimax just yet...of course, I joked that this only works in california as the air is so rarified, and it wouldn't have a hope in the East Coast:)

S4: Small State and Small Stretch Routing Protocol for Large Wireless Sensor Networks
Yun Mao, University of Pennsylvania; Feng Wang, Lili Qiu, and Simon S. Lam, The University of Texas at Austin; Jonathan M. Smith, University of Pennsylvania

this really does what it says on the tin - use theory in practice...worth a read if you've seen the small stretch theory papers and want to see how to use them in anger - also nice to see JMS is back in action!

A Location-Based Management System for Enterprise Wireless LANs
Ranveer Chandra, Jitendra Padhye, Alec Wolman, and Brian Zill, Microsoft Research

nice practical results for the problem statement in the title...I guess this will show up in Vista SP2:-)

Poster session:- ones I talked to:

The Case for Conditional Link Metrics and Routing
Saumitra M. Das, Purdue University; Yunnan Wu and Ranveer Chandra, Microsoft Research, Redmond; Y. Charlie Hu, Purdue University

neat way of unifying several ideas under one hat! inclouded network coding and interference (as effective shadow price routing) - several of the ideas are well known, but combining them in thie iead (metric for a link is metric conditional on some other link metric - useful for MANETs, Net Coded, multi-path etc etc - main question is how do you actually know the priors, i.e. in many cases the implication is that there is additional link state info distributed (ok if your routing protocol is a link state flooding protocol, but not so great for distance vector...or proactive manet)

Lighweight OS Support for a Scalable and Robust Virtual Network Infrastructure
Sapan Bhatia, Marc Fiuczynski, Andy Bavier, and Larry Peterson, Princeton University and

Network Troubleshooting: An In-band Approach
Murtaza Motiwala, Georgia Institute of Technology; Andy Bavier, Princeton University; Nick Feamster, Georgia Institute of Technology

were both Vini related ones and i talked about using xen/xorp instead of quagga/click...we (CAM CL ) need to talk to these guys about our xen/xorp work...

there were a lot of other good posters but i didn't manage to talk to them much aside from Marcel Dischinger (who interned in the lab 2 years back, and is now at MPI with Peter Druschel) - his poster was on DSL measurements:

day 2:-
Tolerating Faults and Misbehavior

Beyond One-Third Faulty Replicas in Byzantine Fault Tolerant Systems
Jinyuan Li, VMware, Inc.; David Mazières, Stanford University

defines a new model of consistency ("Fork* consistency") which allows one to consider execution sequences with more than 1/3 of replicas being malicious - requires careful consideration of separation of concerns of consistency, correctness, and eventual completion, under certain specific partition cases....don't have time to think it through here - sounds important and useful (can we use it in p2p/manet/dtn too = not sure we need to as we can triangulate bad guys geographically and contain them?).

Ensuring Content Integrity for Untrusted Peer-to-Peer Content Distribution Networks
Nikolaos Michalakis, Robert Soulé, and Robert Grimm, New York University

attestation based system (viz reputations) in decentralised way...

TightLip: Keeping Applications from Spilling the Beans
Aydan R. Yumerefendi, B

not h/w, not language, and not taint track - but slight change to OS to have shadow process....which is a doppelganger...sounds a lot like what Sugih Jamin did way back for shadowing execution in game servers (with compresed execution state) and also how the euro black hat guys deconstructed skype. also, the assertaion on slowness of tain is a bit outta date i think..

Network Measurement

Peering Through the Shroud: The Effect of Edge Opacity on IP-Based Client Identification
Martin Casado and Michael J. Freedman, Stanford University

next gen NAT detection, writ large

A Systematic Framework for Unearthing the Missing Links: Measurements and Impact
Yihua He, Georgos Siganos, Michalis Faloutsos, and Srikanth Krishnamurthy, University of California, Riverside

Emulation and Virtualization

The Flexlab Approach to Realistic Evaluation of Networked Systems
Robert Ricci, Jonathon Duerig, Pramod Sanaga, Daniel Gebhardt, Mike Hibler, Kevin Atkinson, Junxing Zhang, Sneha Kasera, and Jay Lepreau, University of Utah

hybridized planetlab + emulab - i.e. use besxt of both worlds - seems sensible...

An Experimentation Workbench for Replayable Networking Research
Eric Eide, Leigh Stoller, and Jay Lepreau, University of Utah

Very amusing talk! and sensible....not sure if its the tool - but we should give them benefit of the doubt...

how many papers on the meta agument "we should do reproduceable research" can be accepted before we start to accept papers that reproduce results ? :-)

Black-box and Gray-box Strategies for Virtual Machine Migration
Timothy Wood, Prashant Shenoy, and Arun Venkataramani, University of Massachusetts Amherst; Mazin Yousif, Intel, Portland

Debugging and Diagnosis

Life, Death, and the Critical Transition: Finding Liveness Bugs in Systems Code
Charles Killian, James W. Anderson, Ranjit Jhala, and Amin Vahdat, University of California, San Diego

model checking - peter sewell might like to look at this !!!

X-Trace: A Pervasive Network Tracing Framework
Rodrigo Fonseca, George Porter, Randy H. Katz, Scott Shenker, and Ion Stoica, University of California, Berkeley

spoke to george porter who has some interesting other work with Randy on energy saving in clusters which is pretty much like Anthony Hylick's stuff, but at a higher level...I guess x-trace is a sort of Magpie type project...

for both these papersmight have been nice to have seen them before the pervasive debugging project!!!

Friday: Global Comprehension for Distributed Replay
Dennis Geels, Google, Inc.; Gautam Altekar, University of California at Berkeley; Petros Maniatis, Intel Research Berkeley; Timothy Roscoe, ETH Zürich; Ion Stoica, University of California at Berkeley

Just caught the tail end of this - seems very neat - again, quite like the replay/rewind stuff in Tim Harris' first version of PDB

Friday, Day 3

Network Localization

Network Coordinates in the Wild
Jonathan Ledlie, Harvard University; Paul Gardner, Aelitis; Margo Seltzer, Harvard University

This reminds me of the work when people looked at how bad early akamai cache selection was at finding the right "locality" releative to a particular client.
But I guess the point here is that they've looked at all the recent techniques and gone a lot further in a "heroic scale" big science way that is a sign of good systems papers these days. As with other recent work on coordinates, the idea is not to get an actual coordinate (in the sense of mapping node location onto the surface of the planet geographically, via some embedding), but to get a system that is useful. So they use a spring model with ageing. Unsurprisingly a DHT is also used. Eval is very thorough.

Octant: A Comprehensive Framework for the Geolocalization of Internet Hosts
Bernard Wong, Ivan Stoyanov, and Emin Gün Sirer, Cornell University

so this paper is actually trying to get a real mapping from IP to geo-location. This is worrying, as we know lots of reasons why this actually only possible for a subset of the net with any degree of reality. So what they do is to interatively reduce errors (i.e. not embedding as primary approach). having done this, they get remarkably good results - although they use planetlab (usual warning) for some eval:(

dFence: Transparent Network-based Denial of Service Mitigation
Ajay Mahimkar, Jasraj Dange, Vitaly Shmatikov, Harrick Vin, and Yin Zhang, The University of Texas at Austin

I really wanted to say "Looking over dFence at networking research" basically this is a midbox approach (as opposed to an arbornet front end, or a re-architect the application to be distributed...) and is as such perfectly reasonabl, but there's the deployment argument...worked example was attack mitigation of syn flood. the midboxes need dynamic state management. the eval used IXPs and Xorp:)

R-BGP: Staying Connected in a Connected World
Nate Kushman, Srikanth Kandula, and Dina Katabi, Massachusetts Institute of Technology; Bruce M. Maggs, Carnegie Mellon University

is about pre-cumputing a failover path so that you can forward data WHILE the BGP convergence is happening - i.e. de-couple forwarding and route computation. Gosh, where's that happened before (phone networks? :-) of course, you do need to think about how you install forwarding state for failover path without a routing update...question for me is precisely why there is any outage in a path (or distance)-vector protocol...they look at that - for me, it shouldn't happen.

Mutually Controlled Routing with Independent ISPs
Ratul Mahajan, Microsoft Research; David Wetherall, University of Washington and Intel Research; Thomas Anderson, University of Washington

So I really like this work since it incoproates a very subtle understanding of what revelation is allowed between "competing" ISPs to permit necessary, but sufficient cooperation to get more fine grain control (and convergence) in a policy routing system. As the speaker/author pointed out, the idea applies across many other networked systems (p2p, e-mail, multiple wireless nets) and so is well worth paying attention to - Sid Chau's work in the area is related...

Tesseract: A 4D Network Control Plane
Hong Yan, Carnegie Mellon University; David A. Maltz, Microsoft Research; T.S. Eugene Ng, Rice University; Hemant Gogineni and Hui Zhang, Carnegie Mellon University; Zheng Cai, Rice University

Every aspect of networking that isn't just forwarding the end user data is control. All control is just another problem for distributed computing. This is a mantra in Cambridge, and other places seem to be buying into this - you don't have to go quite so far as Active Nets or Programmable Networks, but treating every aspect (fault diagnosis, routing, traffic engineering, etc etc) as just distributed computing problems like anyhting else (web serving, CDN, email, p2p) is a step in the right direction.