Thursday, December 17, 2009

Lecture on Systems for Distributed Quantum Computing

Systems for Distributed Quantum Computing on Keio's YouTube Channel, where you will find other videos from the Spintronics group at Keio, as well.

Introduction of my research, targeted at physicists, primarily at a qualitative level, no equations but no stopping to explain vocabulary.

Thursday, October 15, 2009

IJQI Acceptance

Our paper Distributed Quantum Computation Architecture Using Semiconductor Nanophotonics has been accepted for the International Journal of Quantum Information special issue on Distributed Quantum Computation. Huzzah!

This paper was very collaboratively written, thanks to Skype. Thaddeus and Austin both deserve full measures of credit for this one. Thanks, guys!

Wednesday, July 29, 2009

Help Me With My Summer Reading

I'm feeling the need to recharge my store of ideas, and I have the
nagging feeling that my lack of currency in a bunch of fields is
causing me to miss some connections I could use in my own research.

So, I'm looking for a reading list of, say, the one hundred most
important papers of the decade. It doesn't have to be an even
hundred, but I'm looking for a good summer's reading. (Given that
it's mid-2009, now would be a good time to start composing such a list
anyway, depending on where you want to place the "decade" boundary.)

I want these papers to cover *ALL* fields of computer science and
engineering; I am by nature catholic in my reading.

You probably know that my current field is quantum computing, but prior to
that I did network-attached storage. The 1990s were a very creative,
ambitious decade in that area; I admit I read much less there now than
I used to, but I haven't seen anything really earthshaking in storage
in the last few years. (Friends still in the area will no doubt
correct me.)

If such a list already exists, I'm happy to use it as-is, otherwise
I'm willing to manage a conversation and create such a list.

Since this list will be very broad, I want only a few "MUST READ"
papers in each field. What are the new ideas in your field? If you
had a short meeting with, say, an NSF god descended from Olympus, what
ideas would you cite to convince him/her that your *field* (not your
pet idea) is a vibrant field with real-world impact, worthy of
large-scale support? What papers or ideas have changed the way you
think?

So, if your field is:

Theory:
* complexity theory
* algorithms
* data structures
* automata/Turing machines/FSMs, etc.
Systems:
* hardware technology (Moore's Law, etc.)
* processor architecture
* systems architecture
* operating systems
* storage systems
Programming languages
Software engineering
Networking
Artificial Intelligence
Search
Databases
Security
Human-computer interaction
Network or systems operations
Ubiquitous systems/sensor networks
Computer Science education (please help me learn to teach!)
etc.

please send me your suggestions.

I'm even willing to go as far afield as robotics and bioinformatics,
if you can convince me it's worth my time to go read. I'm also
willing to accept old ideas that are finding new urgency;
transactional memory would be a good example, virtualization another.

I will leave it to you to balance newness of idea with real-world
impact, and to decide whether to recommend the key original paper(s)
or a survey paper, if one exists already.

(I'm doing this a tad ad hoc; I really should reconcile against, say,
the ACM computing curricula or a journal keyword list, but I probably
won't bother. Some may also object to the categorizations above;
don't worry about it, just send me the papers/ideas you think are
critical, and we will work on the categorization and balance of the
list later.)

(Yes, the choice to limit this to the last decade is arbitrary; there
are plenty of old ideas I'm not familiar with, too -- I recently ran
across R-trees for the first time, for example -- but, generally
speaking, I'm after ideas too new to have made it into textbooks,
otherwise I'd just pick up a recent text.)

(And on these grounds let me say that I'm enjoying the revitalized
CACM, which seems to be helpful in focusing on new, important ideas,
with more timely and accessible review articles than Computing
Surveys.)

A few thoughts to get started:

* The hierarchy of limits in computing technology:
An outstanding synthesis of Moore's Law, Landauer's principle, etc.
Dense, but well-written and worth the effort to understand. I don't
care if the ideas are old, this one is critical.

@Article{meindl01:_terascale-si,
author = {James D. Meindl and Qiang Chen and Jeffrey A. Davis},
title = {Limits on Silicon Nanoelectronics for Terascale
Integration},
journal = {Science},
year = 2001,
volume = 293,
pages = {2044--2049}
}

* proper network topology analysis:
A clear-eyed look at mathematical analysis of and understanding of the
Internet.

@article{JohnCDoyle10112005,
author = {Doyle, John C. and Alderson, David L. and Li, Lun and Low, Steven and Roughan, Matthew and Shalunov, Stanislav and Tanaka, Reiko and Willinger, Walter},
title = {{The "robust yet fragile" nature of the Internet}},
journal = {Proceedings of the National Academy of Sciences},
volume = {102},
number = {41},
pages = {14497-14502},
doi = {10.1073/pnas.0501426102},
year = {2005}
}

* distributed hash tables (DHTs):
Just barely makes my "decade" cutoff, but one of the most influential
ideas of recent years; fault-tolerant, truly distributed,
loosely-coherent key-value pairs, useful for managing e.g. a lookup
system for P2P networks. (You can argue for another choice of
paper.)

@inproceedings{stoica2001chord,
title={{Chord: A scalable peer-to-peer lookup service for internet applications}},
author={Stoica, I. and Morris, R. and Karger, D. and Kaashoek, M.F. and Balakrishnan, H.},
booktitle={Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications},
pages={149--160},
year={2001},
organization={ACM New York, NY, USA}
}

* Peer-to-peer (P2P) networks:
No recommended paper here yet. I've read a few, but none really stand
out in my mind. Suggestions?

* Delay-tolerant networks (DTNs):
No recommended paper here yet. Might not make the decade cutoff.

* Network coding:
Just barely makes the decade cutoff. This is the seminal paper,
AFAIK, but the writing in it is poor; recommendations for an easier
read gladly accepted. A highly theoretical idea that seems to be
gaining surprising traction in real-world systems.

@article{ahlswede2000nif,
title={Network information flow},
author={Ahlswede, R. and Cai, N. and Li, S.Y.R. and Yeung, R.W.},
journal={Information Theory, IEEE Transactions on},
volume={46},
number={4},
pages={1204--1216},
year={2000}
}

* Ajax:
I haven't seen any good papers on it, and it's a philosophy rather
than a technology, but surely it's important enough to rate
here...suggestions?

* Transactional memory:
One possible route to effective parallel programming. The right one?
Good question!

@Article{larus07:_trans_mem,
author = {James Larus and Christos Kozyrakis},
title = {Transactional Memory},
journal = cacm,
year = 2008,
volume = 51,
number = 7,
pages = {80--89},
doi = {10.1145/1364782.1364800}
}

* MapReduce:
One of a set of very good ideas to come out of Google in the last few
years. The right way to get to real parallel programming on very
large datasets? Good question! The database community seems to think
not. But having done a little MPI programming, I can assure you that
MPI is not for the masses, at least not in its current form.

@article{dean:mapreduce-cacm,
author = {Jeffrey Dean and Sanjay Ghemawat},
title = {{MapReduce}: simplified data processing on large clusters},
journal = {Commun. ACM},
volume = {51},
number = {1},
year = {2008},
issn = {0001-0782},
pages = {107--113},
doi = {http://doi.acm.org/10.1145/1327452.1327492},
publisher = {ACM},
address = {New York, NY, USA},
}

* Rethink the Sync:
Recommended by a friend, who called it his favorite paper of the
decade.

@inproceedings{nightingale2006rethink,
title={Rethink the sync},
author={Nightingale, E.B. and Veeraraghavan, K. and Chen, P.M. and Flinn, J.},
booktitle={Proceedings of the 7th symposium on Operating systems design and implementation},
pages={1--14},
year={2006},
comment ={Best paper; Honey's favorite paper of the last decade.}
}

* Disk MTTF:
An analysis rather than idea paper, but important for anyone who does
large-scale systems or cares when their laptop disk is likely to
fail.

@article{schroeder2007dfr,
title={{Disk failures in the real world: What does an MTTF of 1,000,000 hours mean to you}},
author={Schroeder, B. and Gibson, G.A.},
journal={Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST)},
year={2007}
}

That's eight papers on eleven ideas that have changed the way I think
about computing systems in the last few years, mostly in the
networking area (a couple may have to get deleted to hold the final
list to 100 papers). There are many other topics, of course (chip
multiprocessors and radical new architectures such as TRIPS;
hypervisors and virtualization of systems and networks is another
old/new idea), but I'll leave them to others to promote. I've read
hundreds of papers in the last decade, but I'm interested in what
*you* consider important, not my own biases here. And while IP is a
heavily network-oriented list and will no doubt expand on that set of
ideas above, please look as far abroad as you comfortably can -- or
forward on to colleagues in other areas who might be interested in
such a list.

Please help educate me!

Friday, May 15, 2009

Mountain Music

I do like mountain music, though I wouldn't qualify myself as a "big" fan.

Today's discovery:
WMMT, broadcasting from Whitesburg, KY (about an hour from my parents' place), using 15,000 watts, a decent Internet service, and an all-volunteer staff.

The mountain version of "All My Loving" was nice, though I'm actually partial to instrumentals. I like the traditional mountain music, with dulcimer, fiddle, banjo, including the gospels. Bluegrass is okay, but I'm not a big fan of modern country. I'm not wild about steel guitar and, despite (because of?) being a drummer, I don't like the heavy drums and simple 4/4 beat of a lot of commercial country.

Just to blow my mind, after three hours of "Bluegrass Express", they wedged some Latin jazz in between "I Need You Like a Train Needs a Track" and "He Got You, I Got the Dog" (how can you go wrong with a song that starts, "He's sleeping in my double-wide, hunting on my land" and proceeds to conclude that getting the dog was the better end of the deal?).

I commented recently that the problem with a lot of Internet music services is that they are predictable, and hence have no personality. This one - and my favorite, KCSM - definitely have personality.

And every WMMT announcer I've heard so far sounds like someone I went to high school with. Ah, the sounds of home...

Saturday, April 11, 2009

Kabuki Driving

After more than five years of living here in Japan, and with the expiration of my California driver's license looming (now only days away), I finally decided to get a Japanese driver's license.

Six weeks, six trips to the testing center (more than an hour away), innumerable, insufferable hours spent in plastic chairs crammed too close together to be comfortable, three actual chances sitting in the driver's seat with an inspector, and more than three hundred bucks later...

I still don't have a license.

In fact, given that the effort and expense have already exceeded the license's value to me, I'm thinking about just giving up. For Japan, this is more of an inconvenience to Mayumi than to me; once a year or so, we rent a car and go somewhere, and since I don't have a license, she does all the driving, while I look out the window, fiddle with the radio, read or nap. For most business trips, I'm actually *forbidden* from renting a car (regardless of how realistic a restriction that is for the city I'm travelling to), so it's not a big deal there, either. The only time I *really* need a license is when we're in West Virginia, visiting family, or the far-too-rare occasions when we get to California for pleasure.

(I am told by friends that I *can* renew my California driver's license, even though I no longer live there, but you have to appear in person and get a retinal scan -- and the CA DMV has cut hours and closed offices as a result of the financial crisis.)

There would be a certain satisfaction in taking the moral stand that we actively oppose the use of private cars. But I'm really not in that camp. I think the world would be a better place -- and Americans healthier -- if Americans drove less, used less oil, and ate less beef, and Japanese actually attempted to manage ocean fish stocks rather than simply exterminate them, but I'm not advocating the complete banishment of cars, beef, and sushi. We choose not to have a car here, since we think it's healthier and better for the environment, but don't press that choice on others. (I admit, we still eat sushi, though I'm talking about the fish more, and slowly working toward lowering the catch limit on our take at a sushi restaurant.) And I'd be lying if I said that economics didn't figure into it -- we couldn't afford to buy a car right now if we tried (we have a house and annual trips to the U.S. instead).

Anyway, I've been driving for more than a quarter of a century now. How could I possibly flunk a driving test, you ask? Ah, naive one, let me instruct you in the ways of this country...

First off, flunking is not unusual, it's the norm. The pass rate, I am told, is less than 30%, even among Japanese, and most of those who pass are clearly on their second or third (or fourth or fifth) attempt. In three attempts, in which I sat with groups of foreigners and Japanese returning from living overseas attempting to transfer their license to Japan, I have not yet seen a SINGLE person actually pass the driving test. One Japanese woman drove for years in California, and had driven more than 5,000 kilometers back in Japan using an international license that was about to expire, flunked it three times.

So, if each test were a random, independent variable (they're not) with a failure rate of 70%, about 35% of the people would flunk at least three tests.

The thing you have to understand is that it's not actual driving, it's Kabuki Driving: it involves exaggerated motions, long pauses for dramatic effect, an obscure vocabulary, and improbable sub-plots, and has only the most oblique relationship to everyday life. There's even an audience (they stick another testee in the back seat while you drive). The only thing it doesn't have is exotic costumes. (In fact, if I read the sign right, along with flip-flops, wooden "geta" sandals, and excessively high heels, you are not allowed to take the test while wearing a kimono. Go figure.)

The rules for getting a license differ depending on how you're going about it. Most Europeans can simply take a written test and be issued a license on the spot. Americans and most other Asians have to take the written test *and* a driving one. America is not a signatory to some international treaty (the Geneva Convention on treatment of prisoners of war, I believe), and even if it were, there is no central authority in the U.S. Japan would have to decide whether or not to accept licenses from at least fifty-one different jurisdictions.

But still, for Americans with a license, the process is much easier than starting without any license at all. The written test is ridiculously easy -- ten true/false questions (in both English and Japanese) with 70% being a pass. Close your eyes and guess, and you've got a 17% percent chance of passing -- almost as good as passing the driving part with your eyes open. And the driving test is difficult, but easier than the one Japanese people go through.

For Japanese people with no license, the first thing they do is sort you based on whether or not you have a certificate from a driving school. Without one, they give you a harder driving test, which apparently no one ever passes, so in effect, you have to attend driving school first.

Driving schools here are a HUGE business. (I'm convinced that the schools themselves are run by ex-inspectors, making out like bandits after decades of civil servant penury.) There is no learner's permit here, so the only way you get enough experience to pass the test is by going to a driving school. At a cost of three thousand dollars, and sixty (yes, sixty!) hours of instruction.

And they wonder why the number of young Japanese people getting driver's licenses is declining.

The Japanese taking the regular route are herded through the system like cattle, and given a registration number, made to wait, made to drive, made to wait (okay, that part is the same for foreigners). After finishing the test, they are NOT TOLD whether or not they passed. After another round of waiting, the registration numbers of the people who passed are posted on a giant LED signboard. A cheer goes up from the hundred or so people who passed, and groans from the other hundreds who didn't.

Once you get to the actual driving part (which is run on a closed course about the size of two American football fields), the kabuki starts. They tell you that you start with 100 points, and as long as the penalties are less than 30 points, you'll pass. But at the end they won't tell you how many points you have, just whether or not you passed; modulo a few major fauxes pas, ultimately I'm sure it's up to the judgment of the inspector. Most of the tests I have seen actually ended before the course was completed, with an "Okay, you're done, you flunked, please return to the start." But getting all the way through the course doesn't mean you passed; I didn't this last time. For the foreigners, at least, they do have some pity, and the inspector will usually give you an oral summary of what you did wrong.

There are minus points for failing to adjust the position of the driver's seat and mirror. There are minus points for holding the steering wheel wrong, including turning your hand palm up and sticking it through the wheel, turning it from the inside. The easiest one for the inspector to use is, "You didn't do enough safety checking," by which he means that your head stopped swiveling on its neck for several seconds at some point.

The one that got me twice is turning too wide. It's a fair cop, as Monty Python would say: I'm not accustomed to driving on the wrong side of the road, so I pull too far out into the road as I turn, in order to avoid hitting the curb. That was the first and third tries. On the second, I was careful about that -- and wound up hitting a curb, which is an automatic fail. There is a tight spot called the "Crank", with two right-angle turns and tight walls, that the car just barely fits through. I cleared that easily -- then clipped the curb on the corner as I turned out of it into the wider street. Dang. That experience pushed me too far back the other way for the third try, apparently.

Before trying the first time, I read up on the process on the web. That taught me that you need to stop at stop signs for three full seconds, which is an eternity. In California, you could watch a stop sign all day, and the *total* amount of time cars spent stopped at the sign might not be three seconds.

But just reading someone's advice on the web will give you a false confidence that you can pass the test. The course is really not that difficult in terms of where you're asked to drive, but there are many small points the inspector is looking for and they grade quite harshly. After flunking the first time, I did a one-hour practice session with one of the inspectors, one Saturday morning.

It was a revelation. Before doing that, I had NO IDEA that they want you to take turns at 10km/hour -- about six miles an hour! That's the speed at which you pull into a parking spot, fer cryin' out loud! Likewise, there is one place on the course with a "caution" sign, and caution means 10km/h. The one "high speed" part of the course is 40km/hour, about 25mph. After learning this, I laughingly told my lead-footed sister that she could never pass the test, since you have to drive slow. It's probably true.

So, I am contemplating whether or not to give this one last shot. They gave me a test slot for the afternoon of my birthday, which is when my CA license expires. I may simply not go.

I no longer have any ego bound up in my driving abilities, though I certainly used to take pleasure in a sunset cruise on an open road. Now I feel that if I was told that I could never drive again, my reaction would probably be to simply shrug. My father's midlife crisis was a red Toyota Supra. My mom joked that the car was fine, as long as he didn't get the blonde to go with it. My midlife crisis arrived earlier, and has resulted so far in a Ph.D. and a faculty position.

Flunking is something of an embarrassment for me in the lab, though. Murai Lab hosts the "iCar" project, which has been working since the early 1990s on connecting cars to the Internet. We have a lot of car enthusiasts, including one student who reportedly used to race professionally, and several others who own sports cars (Beemers, Alfas, a Lotus, an RX-8) and take them out to Mount Fuji Speedway on weekends.

Speaking of which, one of our faculty members (late forties, has an Alfa and two Beemers, one of which was brand new...) lost his license last year. 55km/h OVER the speed limit. License yanked (not suspended, canceled outright), forbidden to reapply for a year. His year is almost up, so he is now back in driving school, spending sixty hours and three thousand bucks to enjoy the company of eighteen-year-olds hearing for the first time that a car usually has four tires and a steering wheel, so he can get back in the brand new Beemer two-seater. He and the others spend a fair amount of energy discussing "license tourism", taking the three grand and going to Europe and getting a license instead (European ones translate more easily than American ones). Sounds like a win to me.

No one I know will defend the system. It's clearly ridiculous. But in a larger social engineering context, maybe it makes sense. If it's not in Japan's interest to have too many people on the roads, maybe it *should* be hard to get a license, and it doesn't really matter whether it's difficult for a good reason or if it's the equivalent of reading Shakespeare while standing on your head. As a liberal with a belief that government should actively work toward creating the society we would like to have, this could be exhibit A. Hmm. Let me think about that.

Tuesday, January 20, 2009

Happy Birthday!

A day late, but yesterday was Edgar Allan Poe's two hundredth birthday! Happy birthday to one of my favorite writers.

Tonight's midnight (well, two a.m., Tokyo time) promises to be anything but dreary, as I ponder (perhaps weak and weary due to a cold I've contracted) the inauguration. Obama's TODO list is infinitely long, but hope dawns across the land. Hmm, there are lots of comparisons to Lincoln, King, and Kennedy; I wonder if there's an appropriate Poe quote?

Wednesday, January 14, 2009

Monday, January 12, 2009

Anniversary of Two Eras

This past week was the anniversary of two important eras in Japanese history, one symbolic and high profile, the other of enormous practical impact but much lower profile.

January 7th was the twentieth anniversary of the death of Emperor Hirohito, the end of the Showa Era, and the start of the Heisei Era with the ascension of the current occupant to the throne.

That same day, Jun Murai was at Narita Airport, on his way to Washington, D.C., for some rather obscure technical work. On about January 11th, he got it running: Japan was connected to the Internet, via IP over X.25, for the first time.

Several years later, when I left Japan for the first time, I gave my email address to many Japanese (and foreign) friends. Most said, "What's this?" I replied, "Hang onto it, in a few years you'll know." And indeed, I occasionally am contacted by friends from that time, though I suspect they come upon my address now via Google, Facebook, LinkedIn, or another, mutual friend.