rdv live from Tokyo

New Paper Dance: Recursive Quantum Repeater Networks

2011-04-14T18:43:00.000+09:00

I've been neglectful of this blog lately, but this paper has what I think are some ideas that are a good fit for quantum networking. We're just beginning the discussion about QRNA (Quantum Recursive Network Architecture), though, and comments are very welcome!

Our paper Recursive quantum repeater networks is part of a special issue of Progress in Informatics on quantum information technology.

Thanks to Joe Touch (and his Recursive Network Architecture (RNA) project), and Clare Horsman for their work on the paper. Wouldn't have happened without them.

#Quakebook

2011-04-14T18:01:00.000+09:00

"2:46" is now available on Amazon. 100% of the proceeds go to the Japanese Red Cross. Buy your copy today!
http://www.quakebook.org/

Abstracts for Systems Papers

2011-04-12T20:34:00.002+09:00

Generic advice on abstract writing for systems papers:

6 sentences in an abstract:

1. Define the problem you're solving
2. Give the key idea for how you solved it
3. Describe how you demonstrate the success of your solution
4. Give key results, preferably numerically
5. Describe how this impacts the world/industry/whatever (big picture)

Next, go back and reread it, and figure out which of those topics
needs a second sentence, and fill that in. Most often, it's the data
or experiment. Viola! Six sentence abstract!

...now go back and think about whether you really need that first
sentence. Often the first two can be combined, if what you are
working on is a well-understood "hot topic". But be *very* careful
about eliminating it, lest you appear to be doing empty-headed "cool
prototype" building. This is also one of the key places your paper
needs to be timeless; people will hopefully read your abstract for
years to come, but they won't read the paper if they don't like the
abstract!

The abstract *must* be clear about whether your results are analytic,
simulated, or measurements of a real-world system or lab prototype.

Not a perfect formula, and formulas shouldn't be over-used anyway, but
it's a pretty good way to do it. The abstracts of 90% of the papers I
read could be improved by following this approach.

Diary From the Last Couple of Days in Japan

2011-03-13T09:44:00.000+09:00

Dave, others:

This is a collection of notes, lightly edited, compiled over the last
two days, so the voice and time line move around a bit. Apologies.

OK, first impressions:

1. The earthquake was by far the biggest I've ever been in (or hope to
be in), but the building we are in is brand new and very well built,
so it swayed a lot but never felt dangerous.
2. Being a refugee is both stressful and boring at the same time, even
when you're with friends in a place you know is safe. The biggest
thing, of course, is the lack of reliable information; several
people around me have 1seg keitai which give a *very* poor TV image,
enough to be scary but not provide a lot of detail.

Observations:

1. It's a rule of mine not to leave the house without clothing warm
enough for the possiblity of being stuck outside for hours; I think
I'll keep that rule.
2. I carry millions of transistors in my pocket, billions in my
backpack. One would be enough for an AM radio, but no one around me
seemed to have one.

Rolling back to 14:45 Friday...

"Earthquake," I said quietly. Nobody noticed, Kei-san kept on
talking. Even I wasn't completely sure at first, and I'm pretty quick
to pick up on them.

"Earthquake, we're having an earthquake," I said, a little louder.

Kei-san said, "Earthquake?...You're right..."

Osamu-san said, "Earthquake? Really?"

By this time, it had already been swaying for several seconds.

"It's getting bigger," someone said.

Kusumoto-san got up and walked across the room and peeked through the
blinds. "Electric poles are swaying," he said. I got up and walked
across the room to join him.

"It's getting even worse," someone said. "Better get away from the
windows."

"Wow, it's big...this is far away and big..."

Comments like that continued for what seemed like two minutes, before
it calmed down. The electricity went out.

Shortly, the announcement came to evacuate the building, so we grabbed
our jackets and went out. Several of us helped a man in an electric
wheelchair, lifting him down the stairs.

This building includes a gym and pool; dozens of kids in speedos and
googles were forced out into the cold. I handed out a shirt and
fleece I was carrying (which haven't come back, but if that's my
biggest loss, I'm fine).

While we were outside, I got email on my cell phone (DoCoMo mail)
from my wife, letting me know that she was okay, had one of our
daughters, and was getting the other. It would be fifteen hours
before we would be able to connect via voice or SMS, but DoCoMo mail
and their 3G packet service operated sporadically from the beginning.
I was able to access Gmail, Facebook and Twitter, enough to get a
message to friends who relayed it to my parents.

Eventually, they announced that they would inspect the building top to
bottom, starting on the 7th floor, before we were allowed back in the
building. A few minutes later, it started to rain, and a stream of
people went back into the building -- with permission or without, I
don't know.

With power out, we had some emergency lights; our local blackout
continued until 11pm, eight hours after the first shock (but when it
got dark, we could tell that surrounding areas still had power). We
grabbed our stuff, and were herded into a few rooms on the lower
floors, where sat on classroom chairs or stretched out on the floor.
Decks of cards and various drinks, including Dad's Root Beer (which
some student literally mistook for a type of beer -- to her disgust
and my delight) and some sort of avowedly foul Korean liquor, and
snacks materialized, and the students and younger folks quickly
settled into a social mood. I'm fighting either allergies or a bit of
a cold, so I stretched out on the floor to rest.

About a half a dozen faculty were in the early part of an overnight
retreat, here on Keio's Hiyoshi Campus rather than at SFC, so I had
extra shirts and some bread and cheese on hand.

Most of the other faculty that I came with have gone home to check on
their own families, moving via car, but none were going in my
direction, so I elected to stay here. Some of the faculty and staff
and a fair number of students from this campus remain; some live close
enough to walk, but have no power or simply prefer to be with friends
here.

Fighting a cold and stress, and with nothing but emergency lights,
didn't feel like reading. Little information coming in; we were safe,
with nothing particular to do. No one around needed immediate help,
and simply adding people to the streets and stations was clearly a bad
idea. I now understand the empty look on the faces you see in refugee
camps.

Eventually, the campus security and general affairs folks came around
and handed out canned water, crackers, and rather musty blankets.

Some people had keitai (cell phones) with one-seg (1seg) receivers,
very low-bandwidth digital TV. The images we could see were
appalling, with fires burning across broad areas, in the dark.

About 10pm, the Toyoko Line reopened to Shibuya, and people began
filtering out. I stuck with my resolution to stay put until morning,
or JR began running again. (I later heard that some faculty took more
than ten hours to get home; those of us who stayed warm, fed and
comfortable certainly didn't regret that decision the next morning.)

Overnight there were a number of aftershocks, and the second major
quake in Nagano, which they asserted was not related.

I was beside myself with worry about the possibility of tsunami coming
to Kamakura. Our house sits 800 meters from the beach. A couple of
years ago, they handed out a community disaster handbook that included
a tsunami map, which suggested that 7m is a high enough altitude.
Friday's events clearly show that to be false. Our house sits right
on the isoline at 7m, but clearly would have been swept away.

The lights came back on at 11pm. About 1am, I laid down to sleep for
a while; when I woke up at 2:30, many of the students had gone.

More earthquakes, more worries, watching NHK on a big projector screen
until 430am, then slept until 6.

When they announced the reopening of some of the JR lines at 700, I
left. Getting to Yokohama was easy, from there was slow as they kept
trains running at 35km/hr and stopping at every intersection. The
platforms and trains were crowded, but not intolerably so.

From Kamakura Station, it's a ten-minute walk home. I detoured
through the area I think my family should use as an escape route in
the event of a tsunami. The official map recommends that we make our
way to one of the nearby junior high schools, on higher ground, but
their recommended route passes through a stretch of very low ground
several hundred meters long, and crosses the river. I'm revising ours
to what I think is a less-exposed route, though we have to cross a
branch of the river somewhere and there's still one low stretch in
it.

That takes us up to the start of the nuclear reactor concerns, which
will have to be a separate post. I'm struggling with the technical
explanations in Japanese, anyway, so those reading the
English-language press may be better informed.

Over time, as the information flow peaks, my posts will probably lack
originality and insight, but I hope this gives you some idea of what
it's like here on the ground, for a typical family in the Kanto area,
well away from the most seriously hit areas.

Will mine my FB posts and tweets for further material at some point.

Comments and reassurances always welcome; if I seem abrupt via email,
it's just trying to handle the flood of check-in emails from both
people here locally and those from outside asking about us.

We *definitely* appreciate the concerns! Keep us in mind not just
today but over the coming months; recovery here is going to take time.

New Paper Dance

2010-04-07T10:29:00.000+09:00

Austin G. Fowler, David S. Wang, Thaddeus D. Ladd, Rodney Van Meter, and Lloyd C. Hollenberg,
Surface code quantum communication, arXiv:0910.4074 [quant-ph], accepted to Phys. Rev. Letters! Congrats to Austin and the rest of the team. We are gradually illuminating some of the possible corners in the space of quantum repeater system design.

The New GIGA Program at SFC

2010-04-02T22:00:00.000+09:00

The web site for Keio's new undergraduate program, Global Information and Communication Technology and Governance Academic Program (GIGA), is now up and running.

Starting in fall 2011, we'll be accepting freshmen into GIGA to study networking, novel computing systems, international relations, and all of the other fun things we do (including computer architecture and quantum computing, two of the things I teach), with the language of instruction to be English.

Associate Professor

2010-04-01T14:36:00.001+09:00

First day of work as Associate Professor Rodney Van Meter. No foolin'!

New Factoring Record

2010-01-08T07:14:00.002+09:00

New factoring record: 768 bits, about 1500 CPU-years on 2.2GHz AMD CPUs, 10^20 operations, 2^67 instructions (for some definition of "operation" and "instruction". Claims a 1024-bit number would only be about 1,000 times as hard.

Brought to you by Kleinjung, Aoki, Franke, Lenstra, Thome', Bos, Gaudry, Kruppa, Montgomery, Osvik, te Riele, Timofeev, and Zimmerman.
http://bit.ly/8xXSgy

Just FYI.

Lecture on Systems for Distributed Quantum Computing

2009-12-17T07:12:00.002+09:00

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.

IJQI Acceptance

2009-10-15T10:56:00.003+09:00

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!

Help Me With My Summer Reading

2009-07-29T14:45:00.003+09:00

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!

Mountain Music

2009-05-15T12:39:00.004+09:00

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...

Kabuki Driving

2009-04-11T07:34:00.002+09:00

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.

Happy Birthday!

2009-01-20T21:07:00.002+09:00

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?

Single Best Geek Comic Ever?

2009-01-14T14:45:00.001+09:00

I don't often read xkcd, but this one might be the single best geek comic ever...

Anniversary of Two Eras

2009-01-12T11:03:00.003+09:00

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.

ToN Quantum Paper Online

2008-12-24T00:28:00.004+09:00

Our Transactions on Networking paper, "System Design for a Long-Line Quantum Repeater," is now available in final form in the IEEE's Digital Library. Print edition is not due until August 2009. Thanks as always to Thaddeus, Bill and Kae for their hard work on it.

MARA in Infocom!

2008-12-23T12:03:00.003+09:00

Congratulations to Yasu Ohara and Shinji Imahori! Yasu's paper (on which Imahori-san and I are coauthors), "MARA: Maximum Alternative Routing Algorithm", was accepted to INFOCOM 2009, one of 282 acceptances out of 1,435 submissions. This work is follow-through on Yasu's Ph.D. thesis, completed and defended in our lab last academic year. It's good work on how to do route calculations to support multipath forwarding in a network.

A trip to Rio for Yasu next April!

New Campus Web Site

2008-12-22T13:47:00.001+09:00

For those who aren't allergic to Flash, our campus has a new website for faculty & research profiles. Check it out, let me know what you think.

Tell Me a Story

2008-12-20T13:15:00.003+09:00

What he said. Robert Krulwich, you da man.

Now, if only I could write like that...I can't, but sign me up, I'm willing to give it a shot.

Sustainable Sushi

2008-12-16T10:53:00.001+09:00

...is largely a hopeless prospect in this country (let alone the rising appetite for it world-wide, especially in China) for the foreseeable future, but: the Monterey Bay Aquarium's sustainable sushi guide is a win.

A translation to both Japanese language and Japanese market availability would be a plus...

FWIW, a sushi bar here is actually a reasonable place to take a non-squeamish vegan. At a good place, there are a number of pure vegetable rolls. Not clear how much goodwill you earn with the sushi chef that way, but it's a much better menu bet than a tonkatsu (deep-fried pork) restaurant.

I can't promise perfection, but I can promise to do my best to follow the guide.

Now, how to popularize the ideas here?

Give Us This Day Our Daily Banana

2008-11-28T10:43:00.002+09:00

In English, "bread" can be a synonym for "meal" or "food" (and for "money", though that's a later innovation), as evidenced by the line from the Lord's Prayer, "Give us this day our daily bread."

In Japanese, "gohan" is both (cooked) "rice" and "meal": "Gohan wo tabeta?" "[Have you] eaten a meal?" (Transliterated; a more natural rendering would be "Have you eaten?")

An article in a recent issue of Science, talking about bananas, informs me that in Uganda the word for "banana" is the same as the word for "food". Sadly, the article didn't give the word for it, or even name the language (presumably Swahili).

I read the article on the train on the way home yesterday, and when I got home I was dying for a banana. Fortunately, Mayumi had bought bananas. Unfortunately, my girls managed eat all of them before I got home :-).

That's perhaps an allegory for what's happening worldwide: the Cavendish banana, the most common around the world, is under attack by a fungus all over the planet. The plant can be grown only by cloning (it's sterile) and since all the plants are genetically identical, they are all equally susceptible.

Other strains of bananas might be less vulnerable, but are suffering from neglect. (The most fragrant bananas I've ever had were in Nepal, some small variety that smelled of cinnamon.) Let's not let the world's fourth-most-important staple crop (behind rice, wheat and corn) get away from us, people!

guGUttara?

2008-11-28T09:33:00.001+09:00

"To google" is now a verb in English (at least, the American (correct) form of the language, not sure about other parts of the diaspora). "He googled it," "I'm googling it now...," "Why don't you google it?" and more.

The same thing is true in Japanese. "Google" in Japanese is "GUUguru" (or "GU-guru"), written in katakana, the syllabary used for "loan" (imported) words, with a long "uu" and the unfortunate but necessary mangling of the pronunciation. (Not that Americans can come close to pronouncing Chinese or even French correctly, but that's not the point here.)

By fortunate coincidence, "-ru" is the common ending for verbs in Japanese, so conjugating it is natural and trivial, but the emphasized syllable changes: "guGUrimasu", "guGUrimashita". You almost never hear the formal form of it, though, you usually hear the informal form "guGUtta" ("googled") or "guGUtte iru" ("am googling/is googling"). Japanese has a verb form (not sure of the technical name in either Japanese or English) for "why don't you..." or "if you...", which usually ends in "-ttara".

And if you don't believe me, guguttara?

ORF: QKD with IPsec

2008-11-24T16:42:00.000+09:00

Our campus (Keio's Shonan Fujisawa Campus) just finished our Open Research Forum, the annual two-day big exhibit of students' work. It was a blast, a lot of interesting people show up (including, if I understood him right, the director of "Godzilla versus Hedora", and it's great to see the work being done by students in other "kenkyuukai" (research groups), as well.

At our campus, undergrads, usually, starting in their second year, join the "lab" or kenkyuukai of a professor, and by the end of their four years, I would say that many students have done a third to a half of their total learning in the context of the kenykyuukai. Classes provide breadth and theory, the kenkyuukai provides depth.

My students in the AQUA group integrated IKE, the Internet Key Exchange protocol, with QKD (quantum key distribution), so that traffic between two networks can be encrypted using a key created via QKD. I'll post more about the technical work on it a little later, but thanks to Satoh and especially Nagayama for the hard work on both the implementation and the display.

Thanks to NEC for the loan of the QKD devices! We look forward to continuing to work with you.

Keio: Astronauts, Princes, Emperors, and Postage Stamps!

2008-11-10T13:46:00.001+09:00

So, Saturday was the Keio University 150th anniversary ceremony. I didn't get to attend (there were only a few thousand tickets), and I found out about the live webcast after it was over. Oh, well.

I'm told that the Emperor made very nice remarks about the history of Keio.

Prince Charles also dropped by the Mita Campus on his visit to Japan a couple of weeks ago. There is a good photo of him examining a bamboo sword during a kendo demonstration. I heard that his talk was nice, as well.

Just as exciting, to me, was the talk that Akihiko Hoshide gave a few weeks ago. He was on the team that delivered the Kibo Laboratory module to the International Space Station this summer. He also took an aluminum soroban with him, made for him by our engineering department. Oh, Hoshide is a Keio grad -- at least the second to fly in space, after Chiaki Mukai. Hoshide-san gave a great, inspirational talk targeted at kids, and accessible to all ages. It was broadcast over the Internet, and translated into several languages in real time.

More to my surprise, the Japan Post Office has issued a commemorative stamp set. Now I know what I'm getting my great-aunt, the stamp collector, for Christmas.

New Papers

2008-09-26T08:39:00.003+09:00

It occurs to me that I'm behind in doing the obligatory paper dance, as our pontiff would say. All from collaborators, one already published and two new submissions:

Byung-Soo Choi and Rodney Van Meter,
Effects of Interaction Distance on Quantum Addition Circuits,
submitted;
available from the arXiv as quant-ph:0809.4317.

Liang Jiang, Jacob M. Taylor, Kae Nemoto, William J. Munro, Rodney Van Meter, and Mikhail D. Lukin,
Quantum Repeater with Encoding,
submitted;
available from the arXiv as quant-ph:0809.3629.

W. J. Munro, R. Van Meter, Sebastien G. R. Louis, and Kae Nemoto,
High-Bandwidth Hybrid Quantum Repeater,
Phys. Rev. Letters 101, 040502, July 2008;
available from the arXiv as quant-ph:0808.0307.
Selected for Virtual J. Quantum Inf. 8(8), Aug. 2008.

More to come in the next couple of months, I hope, on both repeaters and arithmetic circuits; there is also a pile of systems work from last year's QEC conference and other places that needs to be polished up and submitted, as well as a stack of half-completed things...

...ah, for a trio of clones! Then one of us could teach, one could spend time with the family, one could do research, and one would have to do the drudge work. I suppose we'd have to rotate; I love all three of those first topics, but no one would want to be stuck with the paperwork forever :-).

Biden's Travels

2008-09-24T10:19:00.000+09:00

I'm not going to get into politics on this blog, but one note: Joe Biden's team released a list of heads of state he has met with.

Now, the team claims the list is incomplete, but as an expat living where I do, there is a conspicuous hole: um, Japan? I realize that prime ministers here change often enough that it's difficult to keep up, but Japan is still the second biggest economy on the planet, and one of the U.S.'s top trading and defense partners.

Has Biden really not met with any Japanese leaders, or is the absence an oversight? It's not that he's shunning East, South, or Southeast Asia; he's met with leaders from almost every Asian country you can name, except Bangladesh and Thailand. Okay, he's allowed to not hit every single one; but still, Japan?

Likewise, another near the top of any U.S. list should be that Neighbor to the North, Canada. Hmm.

No Koike

2008-09-22T17:55:00.000+09:00

Well, looks like no woman prime minister this time.

No comment?

2008-09-21T15:48:00.001+09:00

I'm a little disappointed that my glamorous new profile photo here hasn't drawn the attention of Paris, Milan and New York runway talent scouts.

I'm also a little surprised by the lack of comments from the peanut gallery.

The Candidate of Change

2008-09-21T10:32:00.000+09:00

No, for you myopic Americans, I'm not talking about Obama, McCain, or anyone else on that continent. I'm talking about Yuriko Koike, a candidate for president of the Liberal Democratic Party here in Japan. She has held several cabinet positions, and is fluent in both Arabic and English, having received her degree from Cairo University. She's a bit of a long shot, but is supported by Koizumi, the former prime minister, who is still very popular. And, she has been dubbed the candidate of change, which many people would agree is desirable in Japanese politics.

The LDP's internal presidential election is tomorrow (Monday), Japan time. The rules for that election are apparently variable from election to election, but involve mostly members of parliament, and some local leaders, I believe. Taro Aso is expected to win.

Because the LDP is still the largest and strongest political party here, the person elected president normally becomes prime minister. Could Japan wind up with a woman chief executive before America does? Stay tuned.

Quantum Arithmetic

2008-09-21T10:07:00.000+09:00

I get occasional mail from people asking me about quantum arithmetic. I usually point them to the Qwiki page on arithmetic I created a couple of years ago, which is a list of useful papers, rather than an actual technical description.

Most of the papers there are about specific arithmetic circuits, building from binary integer addition to modular exponentiation, and include some examples of actual experimental implementations.

This morning, I ran across some lecture notes by Ekert, Hayden, and Inamori on "Basic concepts in quantum computation," at Quantiki. The notes contain a nice intro to the theory behind reversible, binary, modular arithmetic.

Competitiveness

2008-09-17T07:47:00.001+09:00

BusinessWeek asks, "Is the U.S. Losing Its Edge in Tech?"

But their online article doesn't include an obvious link to the actual report from the Economic Intelligence Unit, sponsored by the Business Software Alliance. It's titled, How technology sectors grow: benchmarking IT industry competitiveness 2008", which tells you a little about their mindset.

Both the detailed data and their chosen methodology are interesting, though I haven't had time to digest them yet. The top 21 in their total index:

1. U.S.
2. Taiwan
3. U.K.
4. Sweden
5. Denmark
6. Canada
7. Australia
8. South Korea
9. Singapore
10. Netherlands
11. Switzerland
12. Japan
13. Finland
14. Norway
15. Ireland
16. Israel
17. New Zealand
18. Austria
19. Germany
20. France
21. Hong Kong

India, Russia, and China are 48, 49, and 50.

The disparities in "human capital" and "R&D environment" are interesting.

Even more telling are the drops from last year's index -- Japan fell from 2nd to 12th, South Korea from 3rd to 8th, due at least partly to shifts in their methodology. As always in some ranking system, you can engineer the results to fit your intuition :-).

Happy Anniversary

2008-09-09T07:47:00.000+09:00

Today is the twentieth anniversary of the Morris Worm. At the time, I had recently moved from ISI's computing center into the MOSIS Project, giving up my position as a sysadmin and becoming a regular programmer on the research staff.

I did get called back in to help a little, but since we were using VMS, the fix for MOSIS was pretty easy: unplug the network, and go back to work. Other folks I worked with, including Dale Chase, Jim Koda, Tom Wisniewski, had a much rougher day, dealing with several BSD VAXen and a large number of Suns.

No Colbert on Linux, No Olympics on Windows

2008-09-06T21:23:00.001+09:00

So, I'm trying to watch "The Colbert Report", which features Flash video, on my Fedora 9 laptop.

No joy. npviewer.bin, the Firefox plugin for Flash video, crashes reliably. A little googling turns up that I'm not the only one with this problem -- it has been The Daily Show's Developers' Blog. (Whine: why is it always me?)

A few weeks ago, I wanted to watch the Olympics in some fashion besides Japanese broadcast. Went to MSNBC.com...dang, Silverlight. I only run Linux on my laptop. Grumble. Dig out the Windows XP laptop I have at work for doing the obligatory Word documents. Download Silverlight. Install. Crashes. Reliably. (Whine: why is it always me?)

Have I mentioned that I hate computers?

Ten Million Bucks to Learn to Program...

2008-08-19T15:09:00.000+09:00

...molecules.

Erik Winfree's DNA and Natural Algorithms Group at my alma mater is arguably already the best in the world at programming DNA; they publish in Nature and Science like clockwork. I don't know the U-Dub guys, but I assume they're good, too.

So, over the next few years, I expect marvelous advances. Good luck to them! We'll be watching and waiting.

Internet-connected Windshield Wipers

2008-08-19T10:16:00.000+09:00

A couple of days ago, Vint Cerf appeared on The Guardian, talking about the future of the Internet (what else?). He mentioned that "Researchers in Japan recently proposed using data from vehicles' windscreen wipers and embedded GPS receivers to track the movement of weather systems through towns and cities with a precision never before possible. It may seem academic, but understanding the way severe weather, such as a typhoon, moves through a city could save lives."

That's the iCar project, headed by Kei Uehara, here in the Internet Research Lab at Keio's Shonan Fujisawa Campus. The project has been running for more than a decade, and has strong ties to industry groups. Current work includes industry standardization of the privacy aspects of information uploaded by probes attached to vehicles, and the like.

The particular tidbit about the windshield wiper info goes back to about the year 2000, I'm told. It has even been featured in short TV segments about the project.

The WIDE folks are visionaries, I tell ya :-).

Tom Sawyer in Tokyo, via Karachi

2008-08-17T07:59:00.000+09:00

Hiya bibliophiles,

I bought an old, red, hardback copy of Tom Sawyer in Jimbocho, the famous used book district of Tokyo, and have been reading it to my nine-year-old daughter. (To my intense delight, she begs me not to stop reading.)

It's undated, and unillustrated, and includes a few typographic mistakes or omissions (such as saying, "See the next page" for some illustration which doesn't exist).

Mine appears to use the same chapter headings as the Random edition, according to Mark West. It does not, btw, say "complete and unabridged" anywhere, but it certainly feels complete.

My guess, based on the age and condition, is that it was printed in the 1920s or 30s. Here's the title page:

It also includes an embossed seal, which I'm guessing is a bookseller's:

Pan-American Commercial, Inc.
Elphinstone Street
Karachi

According to Wikipedia, the name of Elphinstone Street was changed to Zaibunnisa Street in 1970, so presumably my copy passed through Pakistan in the 1960s or earlier, before coming to Japan. Quite a trek for a book.

Thought you would enjoy the tale.

(Yes, I tinkered with the lighting on the second image using Gimp. Apologies for the generally poor image quality; those were taken hand-held in low light. The camera and lens are fine, but I didn't have a tripod available last night, and didn't mess with the in-camera choice of lighting adjustment.)

25th MSST

2008-08-05T09:43:00.000+09:00

Don't forget to register for the 25th IEEE Symposium on Massive Storage Systems and Technologies!

This conference series has a long history, and has produced some fascinating discussions, especially about very large datasets (particle physics and the like). This year, the symposium is moving to a different format. See the web site for details.

Boost graph bundle + write_graphviz

2008-07-30T17:37:00.000+09:00

I couldn't find a decent example of using the new Boost Graph library "bundle" functionality with write_graphviz, so I created one:

foo.cpp

// first, the standard libraries #include <fstream> #include <iostream> #include <sstream> #include <string> #include <set> #include <map> #include <cmath> #include <iterator> #include <vector> #include <queue> // boost and other semi-standards should go here #include <boost/scoped_ptr.hpp> #include <boost/shared_ptr.hpp> #include <boost/shared_array.hpp> #include <boost/scoped_array.hpp> #include <boost/graph/graphviz.hpp> #include <sys/times.h> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> using std::string; using std::vector; using namespace boost; using std::ostream; using std::ofstream; using std::multiset; using std::pair; using std::multimap; using std::map; struct City { string name; int population; vector<int> zipcodes; }; struct Highway { string name; double miles; int speed_limit; int lanes; bool divided; }; typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, City, Highway> Map; void outputgraph(Map&); main() { Map map; // load the map bool inserted; Map::vertex_descriptor v = add_vertex(map); Map::edge_descriptor e; map[v].name = "Troy"; map[v].population = 49170; map[v].zipcodes.push_back(12180); tie(e,inserted) = add_edge(v, v, map); if (inserted) { map[e].name = "I-87"; map[e].miles = 10; map[e].speed_limit = 65; map[e].lanes = 4; map[e].divided = true; } vector<double> distances(num_vertices(map)); Map::vertex_descriptor from = *vertices(map).first; dijkstra_shortest_paths(map, from, weight_map(get(&Highway::miles, map)) .distance_map(make_iterator_property_map(distances.begin(), get(vertex_index, map)))); graph_traits < Map >::vertex_iterator vi, vend; for (tie(vi, vend) = vertices(map); vi != vend; ++vi) { std::cout << "name " << map[*vi].name << ", " << "population " << map[*vi].population; } std::cout << std::endl; outputgraph(map); } struct my_node_writer { // my_node_writer() {} my_node_writer(Map& g_) : g (g_) {}; template <class Vertex> void operator()(std::ostream& out, Vertex v) { out << " [label=\"" << v << "\"]" << std::endl; }; // bleah. I can't get references right... // according to http://www.knowledgesearch.org/doc/examples.html // it should be a reference here, not the type itself. // but g++ either barfs, or the program segfaults. Map g; }; struct my_edge_writer { my_edge_writer(Map& g_) : g (g_) {}; template <class Edge> void operator()(std::ostream& out, Edge e) { // just an example, showing that local options override global out << " [color=purple]" << std::endl; out << " [label=\"" << e <<":" << g[e].miles << "\"]" << std::endl; }; Map g; }; struct my_graph_writer { void operator()(std::ostream& out) const { out << "graph [bgcolor=lightgrey]" << std::endl; out << "node [shape=circle color=blue]" << std::endl; // just an example, showing that local options override global out << "edge [color=red]" << std::endl; } } myGraphWrite; void outputgraph(Map& map){ std::ofstream gout; gout.open("graphname.dot"); write_graphviz(gout,map,my_node_writer(map),my_edge_writer(map),myGraphWrite); // std::cout() << "done writing graph" << std::endl; }

Dr. Bono

2008-05-27T22:39:00.001+09:00

Sir Paul David Hewson was at Keio's Mita Campus today, picking up an honorary doctorate for his humanitarian work. He is in town for the TICAD IV conference on African development.

I caught only a few minutes of his talk, but he talked about the new ONE Campaign and about bringing it to Japan. He singled out Tadao Ando and a couple of others by name as artists with a conscience whom he admires. He also talked about how wonderful the young Japanese people are, humble and wanting to help the world (he must have been talking to SFC students :-).

Bono is smart, dedicated, inspired, and inspiring. With leadership like him, and enough inspired young people, we can make the world a better place.

Rikei Banare

2008-05-18T09:13:00.000+09:00

Presented without comment, for the moment.

Japan is running out of engineers.

Recruiting Students

2008-05-13T14:30:00.001+09:00

At our campus, Ph.D. students are admitted twice a year -- to start in September or in April. Although the official title is the "Graduate School of Media and Governance", we have many high-quality students (and faculty!) working in a wide variety of technical areas, some of which are showcased in the fall each year. There is spectacular work on electric vehicles, bacterial computing, smart fabrics, ubiquitous computing, and on and on.

The Internet Research Lab, of which I'm a part, does a variety of things, including iCar, mobile systems, SOI, and more.

I supervise or co-supervise students in those areas, but I especially focus on:

Distributed Quantum Computing Systems (Japanese or English)
- Architectures for quantum multicomputers
- Quantum repeaters (physical simulation and especially network protocols and network architectures)
- Quantum arithmetic
- Entangled Quantum Internet
- Quantum computer design tools
All-IP Computer Architecture
- iSCSI
- USB/IP
- Caching in wide-area computer systems
- IP-based system bus architectures
- Security and resource management
- Human-centric dynamic system architectures

At SFC, recruiting of Ph.D. students is done very carefully, and in a very personal fashion. Prospective students are expected to find a faculty member they wish to work with and discuss possible research plans before completing the application process.

It's already very late to be starting that process if you are interested in starting this September; the application deadline is in just a week or so. But if you, or a student or acquaintance of yours, is interested in studying almost any networking-related topic, or quantum computing systems, drop me a line and let me know.

ASPLOS 2009

2008-05-07T13:14:00.000+09:00

The ASPLOS 2009 CFP is out! Full papers due Aug. 7, 2008, conference Mar. 7-11, 2009, in Washington, DC.

Quantum Repeaters in ToN

2008-05-07T11:32:00.001+09:00

A few hours ago, I received word that our paper System Design for a Long-Line Quantum Repeater has been accepted to IEEE/ACM Transactions on Networking, which, it could be argued, is the second-most influential venue in the computer networking community. I have updated arXiv:0705.4128v2 [quant-ph] with a paper that closely matches the accepted version.

Ostensibly, the paper presents some simulation results on cavity QED repeaters using our banded purification algorithm for scheduling purification operations. In the bigger picture, I think it points out the importance of scheduling (we picked up a factor of fifty over our prior results) as separate from the actual choice of physical operations for purification. It also provides, to the best of my knowledge, the first attempt to organize the behavior of repeater networks into protocol levels and divisions of responsibility, in the fashion that networking people are accustomed to.

Shor's Algorithm in Danger?

2008-04-29T20:46:00.001+09:00

I wasn't going to post about this, planning to just sort of let it slide, but it has appeared on at least one crypto mailing list, and I feel like someone should address it before the meme that Shor's algorithm has been discredited takes root. So, here goes...

A paper titled Operator Imprecision and Scaling of Shor's Algorithm, by Hill and Viamontes, appeared on the arXiv about ten days ago. Naturally, I snapped it up and quickly read it. Here's what I think. Take it with an entire shaker full of salt...

If you want to cut to the chase and keep your workload down, there's a really good reason to postpone reading the paper: it hasn't been refereed yet. If you work in the area, you might care enough to read it anyway (and might even get asked to referee), if you don't, the simplest form of triage is to wait and see what expert opinion says, then decide whether you want to agree with the experts or not :-).

Anyway, in one sentence, my position on Shor's algorithm:

There are very good reasons for taking a Missouri "show me" attitude toward Shor's algorithm, but this paper probably does not change the arguments, and a variety of people much smarter than me have analyzed the algorithm in more detail and are pretty convinced it's going to work with acceptable scaling.

And, a one-sentence summary of the paper:

Quantum error correction doesn't work.

To believe that Shor's algorithm can't be run in the real world, you have to believe either that the algorithm doesn't really scale, or that quantum error correction doesn't work. (Scott Aaronson reduces the argument further to, "Either the Extended Church-Turing Thesis is false, or quantum mechanics must be modified, or the factoring problem is solvable in classical polynomial time." Personally, I think he's leaving out important real-world cheats, such as "Shor has a bug" and "There was a gotcha in QEC that no one had spotted" and "Noise turned out to be more of a problem than we thought". But, in theory, he's right, and he's a theorist, so there you go :-).)

Taking the concerns in order, Shor first:

I'm not a mathematician, cryptographer, theoretical computer scientist, or physicist; I'm a computer systems guy who happens to be working in quantum computing. I have written a series of papers (including my Ph.D. thesis) on how to implement Shor's algorithm, though I am far from satisfied with the depth of my understanding of the interaction of the algorithm with either noise or systematic errors. See, for example,
my thesis or some of
my
other
papers.

My reasoning for studying Shor's algorithm is the following: I am interested in quantum computer architectures, and I need a well-defined workload. Shor's is the most cleanly defined and potentially important (not to mention famous) of the existing algorithms. Moreover, Shor uses two very important building blocks, arithmetic and the quantum Fourier transform (QFT), that are likely to prove generally valuable, so studying their behavior is useful. I consider myself to have given "provisional assent" to the hypothesis that Shor's algorithm works with reasonable scalability, subject to the caveats in my thesis and other papers.

There have been a number of papers addressing the scalability of Shor's algorithm, and unfortunately, this paper doesn't really seem to discuss any of the other arguments, as presented by Barenco, Fowler, and others. The paper references a few of them, but doesn't really say why their analysis is different from those papers, so it's impossible to thoroughly assess if the authors understand what the arguments are, pro and con.

The success probability of Shor's algorithm is believed to decline with the length of the number being factored. The Barenco and Fowler papers arrive at different conclusions on the scalability of Shor, though both are some variant of sub-exponential (logarithmic or polynomial, actually, if memory serves, though it's been a while since I read the papers). They start from different assumptions about the mathematical relationships of, essentially, the parameters to the algorithm. The focus of both those papers is the behavior of the system with perfect gates but an incompletely-run QFT, the "approximate QFT", which is considered to be the preferred form,
avoiding exponentially-precise gates. The results seem related to the general problem of imperfections and Shor's algorithm, though.

Anyway, on to the paper:

I have read it, but not studied it in major detail yet. I don't know either of the authors personally, but the second author has done good work; he is certainly no dummy.

The argument is pretty straightforward, arguably naive. That doesn't mean it's wrong, but there are a lot of assumptions and simplifications in the work, and they need to be examined carefully.

Essentially, what they have done is a simple simulation of an imperfect inverter and extrapolated from that to the performance of a complete system. They suggest that logical states drift linearly from the desired state, given a certain over-rotation of the physical gates. That is inherently plausible, but I think they have under-estimated the ability of quantum error correction (QEC) to suppress those errors, and they haven't accounted for ordinary noise.
(One would hope that the first author understands the impact of measurement on the system, but it's not clear from the rather terse paper that he does.)

See Sec. 2.3.5 (p. 73 or 56, depending on which numbering you're looking at) of my thesis:
http://arxiv.org/abs/quant-ph/0607065/

I think, if the argument in my thesis is right (which is certainly open to question), that systematic over-rotation is suppressed to O(sin^2(epsilon)) where epsilon is the amount over-rotated by all of the gates.

So, a 1% error in rotation (Pi+2*Pi/100 rotation) would result in
Pi+2*Pi/10000 logical rotation, I think. Then the *second* level of QEC would result in 10^-8 logical error, if I've done it right -- the double-exponential suppression.

A physical over-rotation of 10^-3, then, would be 10^-12 with two layers, if I did that right. Thus, based on this analysis, QEC is capable of suppressing errors quite well.

The argument in my thesis is probably naive, but QEC has a *lot* of work behind it; if you are interested, there are tons of references in my thesis and elsewhere. Moreover, last December there was an entire conference dedicated to the topic.

Returning to Shor:

It's not possible to simulate the system for large enough cases to really confirm the validity of the derived expressions, and we're still a number of years from a system large enough to experimentally prove or disprove the proposition. Personally, I don't think the analysis considering noise, systemic errors, and the approximate QFT is complete yet. Most of the theoreticians are pretty satisfied, but we all know about the difference between theory and practice.

In summary, the paper in question (arXiv:0804.3076) would have broad implications for the ability of quantum computers to maintain state accurately enough to provide real-world acceleration over classical computers. It's a very legitimate concern, which gets raised occasionally by very smart people, and usually ends in a stalemate with the preponderance of quantum information people on the side of "don't worry, QEC works". But it's not yet clear that this paper really pushes the argument forward in either direction. The paper is also not yet refereed, and it will be interesting to see how it changes as a result of any referee's comments.

Useful references:

@Article{barenco:approx-qft,
author = {Adriano Barenco and Artur Ekert and Kalle-Antti Suominen
and P\"aivi T\"orm\"a},
title = {Approximate Quantum {Fourier} Transform and Decoherence},
journal = {Physical Review A},
year = 1996,
volume = 54,
pages = {139--146}
}

@Article{fowler04:_limited-rotation-shor,
author = {Austin G. Fowler and Lloyd C. L. Hollenberg},
title = {Scalability of {Shor's} algorithm with a limited set
of rotation gates},
journal = pra,
year = 2004,
volume = 70,
pages = 032329
}

@ARTICLE{devitt-2006-6,
author = {Simon J. Devitt and Austin G. Fowler and Lloyd C.~L. Hollenberg},
title = {Robustness of Shor's algorithm},
journal = {QUANT.INF.COMP.},
volume = {6},
pages = {616},
url = {http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/0408081},
year = {2006}
}

(There are more, including some very early ones from before QEC was invented. Homework for the interested reader.)

Anyway, I hope this at least short-circuits any rush to burn Peter Shor in effigy. He's way too smart and sweet for that.

Congrats, Inaba-san!

2008-04-24T05:40:00.000+09:00

Inaba-san, from our lab (specifically, Auto-ID Lab Japan) won Best Paper at IEEE International Conference on RFID 2008.

Moore's Law: Moving the Goalposts?

2008-04-09T21:59:00.000+09:00

This posting at NextBigFuture has a fantastic set of slides from Intel about the "long" run, up to 2029 (which will still be before I retire, even optimistically).

There is a lot of material for thought in there, but the big picture is that they are shooting for a million-fold improvement in FLOPS applied to a single problem by 2029, to about a zettaFLOPS, 10^21 FLOPS. I haven't been through the numbers yet, but that seems plausible if you postulate a 1000x improvement in VLSI density (which is around the upper bound where you're building out of individual atoms), one to two orders of magnitude improvement in clock cycle, and make up the rest in increasing parallelism. Overall, it seems to be about the upper bound postulated by deBenedictis, but a detailed check (of both) is in order.

As the article notes, communication is the big deal, all throughout the system. I refer to it as, quite directly, a problem in special relativity. Networks exist both inside and outside the chip, making the physical boundary almost meaningless. This is part of what we are researching as an "All-IP Computer" here in the Murai Lab. (Sorry, the web pages are undergoing revision right now, and you might run into some rough spots; noticeably, the All-IP project doesn't have a web page at the moment...)

At any rate, Intel seems intent on keeping the goalposts as far away as possible, and continuing to grind downfield, a few yards at a time, so that progress over years is astonishing. Leapfrogging their progress is probably impossible, but I hope to be sitting by the side of the road (to mix a few metaphors) with a road sign pointing the way to some interesting areas when they get to atomic and quantum levels...

New Japanese Ambassador

2008-04-02T21:41:00.000+09:00

The Japan Times reported today that Ichiro Fujisaki has been appointed to be the new ambassador from Japan to the United States, taking over from Ryozo Kato, who has been there six years.

At a faculty party this evening, I chatted with two faculty members who know Fujisaki-san personally. I'm told that he is a Keio graduate. Although he seems to (currently) have a low profile in the press, his resume is impressive, and includes time in Geneva and Washington since joining the Foreign Ministry in 1969.

Ion Trap Toffoli Gate

2008-04-02T13:49:00.000+09:00

Whoo-hoo, an interesting looking paper from Reiner Blatt's group:

Realization of the quantum Toffoli gate with trapped ions.

Start of the Year

2008-04-01T09:33:00.000+09:00

The new school year effectively starts today, though classes don't start for another week.

One of the first items on the agenda: searching for new members of your "circle", if you're a student. It's the equivalent of freshman rush at many colleges, or "Rotation" at Caltech, except that it's centered on particular activities.

So this week, there will be students packing the quad, wearing American football uniforms (complete with pads), karate gi, cheerleader uniforms, kendo getups, anything you can name. There will be concerts by the many music groups, frisbees flying overhead, many fliers handed out. And, as you can see, the sailplane flying club (and the race car club and yachting club) will parade their toys around for people to ooh and aah over. (The young man holding the wing is one of my students.)

It's an exuberant time, full of the enthusiasm of youth. I love it.

In a Japanese university (and, I think, high school), there are no "tryouts" for the basketball team. Anyone can join. So, the basketball team might have a hundred members. The difference is whether you're good enough to get picked to suit up for the actual games, and, when you're at the bottom of the heap, whether you're willing to put up with the long practices (and the usual forms of senior/junior reminders that you're at the bottom, carrying bags, fetching water, etc.). Those who don't get to suit up for the games are presumably expected to be in the stands, leading organized cheers. I have no idea how you manage practice for a basketball team with a hundred members...probably "varsity", "JV", and "dregs" have separate practice sessions, I would guess.

Speaking of which, in Japan, flying gliders is a competitive sport. The Keio team this year took second in the nationals, losing out to perpetual rival Waseda. Dang. I think we won the championship last year...

Ueno

2008-03-30T20:13:00.000+09:00

Kamakura Cherry Blossoms in the Rain

2008-03-30T19:33:00.000+09:00

Graduation!

2008-03-29T01:57:00.001+09:00

Today was graduation for the graduate school (the undergrads had theirs earlier in the week). This evening, Murai Lab and Tokuda Lab had a shared party for all our graduates. Congratulations to everyone, but especially to the seven newly-minted Ph.D.s:

funya
kwkt
yasu
ako
mitsuya
hitomi
yoko

We're all extremely proud of you (though I had little to do with the success of most of you, having been here only a year). We have an extraordinary variety of Internet-related theses this year, covering the gamut from "soft" uses of technology to "hard-core" networking: one on preservation of anonymity in medical systems, one on distance learning, one on mobile networking, one on RFID, one on improving the robustness of the packet forwarding plane of the Internet through appropriate tweaks to the routing protocols coupled with a mechanism for path selection...I'll try to post links to the theses later...

Apologies for the absolutely terrible pictures, taken with my keitai (cell phone) in low light and without the ability to tell how bad they are until I uploaded them. There were many real cameras present, I'm sure there are hundreds of good pictures floating around...

The present from the students to Murai-san was an effects pedal for his guitar, which was of course demonstrated.

For those of you still to come, I'm looking forward to the coming academic year, starting week after next.

Remembering Howard

2008-03-18T06:31:00.000+09:00

Howard Gobioff, a prominent storage researcher and early Google employee, died last week at a tragically young age.

Howard was a friend of mine, though we didn't get to see each other as often as I would have liked.

He will be missed.

WIDE Area Director

2008-03-03T16:25:00.001+09:00

I was just elected as an Area Director of the WIDE Project. WIDE is Jun Murai's umbrella organization for Internet research, education and operations here in Japan (with tendrils extending through much of Asia, and even the U.S.). Having just been elected, I still have no idea what kind of trouble I've gotten into :-).

WIDE has, I believe, more than 800 active members, about 200 of whom show up for any given WIDE Camp. WIDE Camps happen twice a year, and we are in the spring one right now. Unfortunately, on the shinkansen down here today, it was cloudy, and we couldn't see Mount Fuji. Too bad.

Anyway, it's a two-year term as an AD, and I'm very much looking forward to contributing to the growth and maintenance of WIDE.

NANOARCH

2008-03-03T16:22:00.000+09:00

NANOARCH has its call for papers out. Papers are due March 28.

I attended NANOARCH in 2006, and it was intriguing, I'm really glad I went. There are a lot of ideas floating around for what to do when Moore's Law ends, or when we get to the atomic scale for computer architectures. The field is still young, but will become incredibly important in the next decade.

Not sure if I'm going to have a submission or not...

Caveat on the AR5418

2008-02-16T14:01:00.001+09:00

A couple of days ago, I posted about success with the AR5418 and the madwifi driver. That initial success was with 802.11a and 802.11g networks.

This morning, I got it working with an 802.11b network, but not with NetworkManager. NetworkManager could see the access point, but for some reason was unable to actually get an IPv4 address via DHCP. I killed the NetworkManager (/etc/init.d/NetworkManager stop), and ran dhclient ath1 by hand (as root, of course), and it had absolutely no problem picking one up. Not sure why yet, but if you're using NetworkManager and having trouble, try it by hand and see what you get.


[root@localhost Desktop]# cd /etc/init.d
[root@localhost init.d]# ./NetworkManager stop
NetworkManager デーモンを停止中:                           [  OK  ]
[root@localhost init.d]# dhclient ath1
Internet Systems Consortium DHCP Client V3.0.6-Fedora
Copyright 2004-2007 Internet Systems Consortium.
All rights reserved.
For info, please visit http://www.isc.org/sw/dhcp/
wifi0: unknown hardware address type 801
wifi0: unknown hardware address type 801
Listening on LPF/ath1/00:19:7d:a:b:c
Sending on   LPF/ath1/00:19:7d:a:b:c
Sending on   Socket/fallback
DHCPDISCOVER on ath1 to 255.255.255.255 port 67 interval 7
DHCPOFFER from 210.x.y.z
DHCPREQUEST on ath1 to 255.255.255.255 port 67
DHCPACK from 210.x.y.z
bound to 10.0.1.3 -- renewal in 1402 seconds.

Hmm, actually, it occurs to me that I have my network at home set up with the same ESSID as the one here, just for simplicity's sake. It's possible that NetworkManager has cached some info (netmask, AP MAC addr, channel, modulation scheme, something) that doesn't match between the two. Worth looking into...

MadWifi, Fedora 8, AR5418 (Lenovo X60)

2008-02-14T14:21:00.002+09:00

Okay, the WLAN is working now!

After finding something similar (not exact, as you'll) on the MadWifi forums, and finally figuring out that I needed madwifi-trunk (as distinct from "most recent release"), the instructions here worked like a charm.

It even works with NetworkManager. Haven't tried WEP yet...

This is with kernel-2.6.23.15-137.fc8 and a yum update as of Valentine's Day, with livna enabled as a yum repository.


[rdv@dhcp-148 ~]$ iwconfig
lo        no wireless extensions.

eth0      no wireless extensions.

irda0     no wireless extensions.

wifi0     no wireless extensions.

ath1      IEEE 802.11a  ESSID:"redacted"  Nickname:""
          Mode:Managed  Frequency:5.21 GHz  Access Point: redacted 
          Bit Rate:36 Mb/s   Tx-Power:13 dBm   Sensitivity=1/1  
          Retry:off   RTS thr:off   Fragment thr:off
          Power Management:off
          Link Quality=37/70  Signal level=-59 dBm  Noise level=-96 dBm
          Rx invalid nwid:113352  Rx invalid crypt:0  Rx invalid frag:0
          Tx excessive retries:0  Invalid misc:0   Missed beacon:0

Reversible/Quantum Arithmetic

2008-02-12T21:06:00.000+09:00

Just noticed that Qwiki has moved to Stanford, dragging with it the page on quantum arithmetic. (As long as we're talking moving arithmetic pages, mine moved last year, too.)

As a Caltech alum, it saddens me that Hideo has moved. Ah, well, Pasadena's loss, Palo Alto's gain. As long as good research keeps rolling out of his lab, his team's making the world a better place. Good luck, Hideo.

Microcell at Home?

2008-02-09T22:17:00.000+09:00

An article in the Feb. 8 Daily Yomiuri, which unfortunately appears not to be online, says that the government is considering rules to allow people to small cell phone base stations into their houses without a license, to improve reception in basements and houses where the signal is weak. My mother-in-law's house could certainly use one for FOMA...

Jazz in Tokyo

2008-02-09T21:56:00.000+09:00

I don't get out to hear live music often enough, but I'm excited by the discovery of Tokyo Jazz Site nonetheless. It was profiled in the Japan Times the other day.

I have only a small fraction of the experience of James Catchpole, but I'll put in a plug for the Blue Note anyway. I happen to think that the food is pretty good; dinner of that quality will cost you 4-7,000 yen anywhere in Tokyo, about what it costs you at the Blue Note. Yes, the shows are expensive and the sets short; but the names are top drawer, and hearing oh, say, the late Oscar Peterson cost us $75 a head in New York ten years ago, and he was sold at $100 a head at Yoshi's Oakland a few years ago, so the difference in price doesn't seem as outrageous to me as it otherwise might. Yes, hearing live jazz is expensive, but even at that, the artists and clubs are mostly making a modest living.

Besides, even going out to the second-tier clubs is Tokyo ain't cheap most of the time. Cover charge for people you've never heard of can be 3-4,000 yen at an obscure club, where a mediocre dinner and overpriced drinks still run the tab to 6-8,000 yen a head. Yes, that's a big difference from the 10-12,000 yen you'll spend at the Blue Note, but the jazz and food will be a lot better. Catchpole gets out much more often than I do, and can afford to trade time for money looking for the exciting, obscure players in the good-for-the-money clubs, but I don't want to waste one of my few trips to a club a year on something disappointing.

Of course, now that I know about his web site, I should be able to improve my hit rate and economize at the same time. Looking forward to reading up on it!

Speaking of such things, a little hole in the wall here in Kamakura named Tipitina has bossa nova tonight. Hmm. I'm at home for the evening with my girls, though.

Traffic Monitoring Using Ubiquitous Computing

2008-02-09T21:43:00.000+09:00

The most ubiquitous computing device in the world at the moment is probably the cell phone. Certainly it's the most common network connected device in the world, and it's pretty much always on.

One of the dreams of recent years has been to take advantage of that latent capability. Now Nokia and Berkeley are turning cell phones into traffic monitors.

Nice work.

Arithmetic on a Distributed-Memory Quantum Multicomputer

2008-02-09T18:25:00.000+09:00

Huzzah, our paper in JETC is now available!

This paper is an extended version of our ISCA paper from 2006, and is also available on the arXiv.

More Snow in Kamakura

2008-02-05T00:38:00.000+09:00

...or more pictures of yesterday's snow, anyway. This one is Honkouji. My great-aunt loves jigsaw puzzles, I may see if I can get this one printed onto a puzzle for her.

Doing Science on a Quantum Computer

2008-02-03T21:19:00.000+09:00

Last week was The Third Workshop on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2008), held here in Tokyo. One of the invited speakers was Ignacio Cirac.

I asked the following question (first in dinner conversation, then during my presentation):

When will the first Science or Nature paper appear in which the results are calculated on a quantum computer, but the point of the paper is not the quantum computer?

That is, when will a quantum computer do science, rather than be science?

Ignacio answered, "If you include quantum simulations, within five years."

[In quantum simulation, which is something like Feynman's original vision of quantum computers, you set up your device so that it emulates the behavior of a different physical system -- like simulating a set of mechanical oscillators using an RLC circuit.]

Call me an optimist, but I'm with Ignacio.

Maybe we need a LongBet on this...

Snow in Kamakura!

2008-02-03T16:01:00.000+09:00

Apparently a light dusting of snow happens most years, but today we're getting a substantial accumulation (15cm or more) of heavy, wet snow.

I used to look at ukiyo-e of snow in this country, or watch jidai-geki (period piece, meaning samurai) movies and wonder why people in this country used umbrellas in the snow, rather than putting on a decent coat and leaving it at that. In America, it's sort of rare for people to use umbrellas in the snow, but I now get it. Here, even up in Yuki-guni (Snow Country) parts of Japan, most of the time it's not really cold. It's right around freezing, which is not actually uncomfortable unless you're wet -- and the snow here will soak right through many a winter coat, where in a colder, drier climate you could brush the snow right off.

The Great Buddha has been sitting outside in the sun and snow for 510 years, now. He doesn't seem to mind, though in the snow I suspect it takes more willpower to remain so stoic.

Weird Real-World Pipeline

2008-01-25T16:48:00.000+09:00

One of the things I asked my students to do when we studied pipelining was to find a real-world pipeline. I'm thinking, you know, the Model A assembly line, that kind of thing.

One of my students came up with this one.

A little context: this "Algorithm taisou" (exercise), invented here in Japan, as far as I know, is normally done by a couple of young guys in suits who go out into the real world and find a half a dozen people (firemen, factory workers) to do this little rhythmic routine with them to music. It's used as an interlude during an NHK kid's program.

You can argue pretty easily that this is a real, eight-stage pipeline. It even has structural hazards: the air between the people ("instructions") flowing through is a shared resource, and the pipeline is carefully constructed so that collisions ("pipeline stalls" or incorrect operation) never occur (as long as the dance is done right :-). I don't see any data or control hazards, though.

More on ZCAV

2008-01-25T15:44:00.000+09:00

Disk zoning gets you a nice boost in both transfer rate and capacity, but it doesn't get enough attention as a factor in things like file system design. Russell Coker has written some nice utilities and even blogged about it. To be immodest for a second, I wrote a USENIX paper about the topic more than a decade ago.

What prompted the post was spotting a beautiful ZCAV (disk zoning) effect.

You can see the nice little arc in it, and looks like 16 zones for the Seagate drive.

I've been thinking about this recently, since I lectured about disks last week...and my own hard drive crashed. Yow. I'm think I'm cool, though. Not sure if it was hardware or software. My best guess is unwritten cache writes, but the logical volume manager info got trashed, and it shouldn't have been touched...

Spam From ISI?

2008-01-16T17:02:00.000+09:00

No, not USC's Information Sciences Institute, where I used to work, but the other ISI. Did I sign up for this, or are they actually spamming people?

From:  ISI Research 
Reply-To:  ISI Research 
To:  R Van Meter 
Subject:  Breaking news for publishing authors
Date:  Wed, 16 Jan 2008 01:43:16 -0500 (15:43 JST)

As a publishing author represented within Current Contents (R),
Biosis Previews (R) and Web of Science, from ISI, you require 
the latest news and resources to stay current in your research. 
That's why we think you'll benefit from getting valuable research 
information right at your desktop -- for free.

>From time to time, you'll receive e-mails with:

* "Call for Papers" requests from scholarly publishers
* News related to your field of scholarly research
* Information about journals and books in your areas of interest
* New product information connected to your field of research

The information you receive will help you discover groundbreaking
ideas and track the progress of the latest developments. And it will
give you opportunities to try important, new resources that can
change the way you conduct research.

We hope you will find this information convenient and essential to
your work.

Sincerely,

George Kowal
Marketing Manager
Scientific Direct
3501 Market Street
Philadelphia, PA 19104

-----------------------------------------------------
You have received this e-mail in the genuine belief that its contents
would be of interest to you. To not receive these messages from
Scientific Direct or other carefully selected organizations, please go
to our preference page.

Anybody got George Kowal's address? ISI should be a better company than that...

Ryo "Oscar" Sakaguchi

2008-01-09T20:33:00.000+09:00

As long as I'm singing the praises of our graduates, congratulations are definitely in order for Ryo Sakaguchi, who is sharing a Scientific and Technical Academy Award (Oscar) with Dr. Doug Roble and Nafees Bin Zafar for their work at Digital Domain (where they work with my pal Wook, who recently got married) on fluid simulations used in effects for e.g. "Pirates of the Caribbean".

Congratulations, Ryo!

You Go, Girl

2008-01-09T20:18:00.000+09:00

I just found out that Yukari Yoshihara (nee Yukari Umezawa, the name she still uses on books and whatnot) is a graduate of Keio University's Shonan Fujisawa Campus, where I teach. Yukari is a 5-dan professional go player and holds the Women's Kisei title, making her one of the best women players in the country, indeed, probably the world.

Pro go players rarely graduate from college; they usually become "insei" (apprentice go players) at about fifteen, and some don't even bother to finish high school. She, like most pros, was recognized early for her genius.

Yukari is the official technical adviser to the "Hikaru no Go" series of manga. Reportedly, she likes teaching, which is one of the reasons she elected to graduate from college.

Although Keio is Japan's oldest (and, of course, best :-) private university (150 years old this year, making it older than either of my other two alma maters, Caltech and USC), but the SFC campus is only about 17 years old. Yukari, no surprise, was one of the founders of the SFC go club.

I must hang my head in shame that I haven't played a game at all in over six months. Moving, commuting, three trips to the U.S., piano lessons, and that minor thing called work got in the way of more important things, like family and go.

Fungible Reality

2007-12-09T19:41:00.000+09:00

One thing I have been saying for at least a decade (in more depth; I'll keep this short) is that technology makes reality fungible. In particular, your reality can be different from my reality.

Of course, we all always bring our own bias, experience, and self to the interpretation of every event; my wife sees Shakespeare very differently than I do. And in the current day, almost everyone spends time looking for information that reinforces their own preexisting world view -- hence the political blogosphere. But, up through the era of the three major television networks, TV was a shared experience: you could talk on Friday about that Thursday evening episode of "Little House on the Prairie".

But, starting more than a decade ago, it became possible for broadcasters to modify your visual experience so that it didn't directly correspond to, for example, the reality that a baseball fan saw at the stadium. It started with "ad inserts" into the background, behind the batter. At first, they were all the same for a given network, but there's no reason at all that they can't be different for different viewers -- and, indeed, I believe that the inserts that Japanese broadcasters put into Major League baseball games are different from what the U.S. broadcasters insert.

Carried to its extreme, almost anybody anywhere in the chain can modify the viewing experience of the end user, on an individual basis. In fact, I think TiVo did this years ago -- selling personal demographic information, or at least promising to show the Cadillac ad to wealthy viewers and the Jeep ad to sportsmen. Thus, TV is no longer a shared experience.

For data carried over IP networks, it's even more trivial. Any web cache or network box can, in theory, modify your personal experience of the web (or any other form of data carried over the Internet, as long as it's not encrypted). And now, via Lauren Weinsein's blog, we find out that Google is no longer a shared experience.

Of course, in one important sense, Google never was; they can (and do, I believe) modify search results to be personally relevant. The difference in this case is that the reality funger is not someone you planned to trust (Google), but someone you didn't (Rogers Telecom).

Twenty-odd years ago, it caused a stir when National Geographic magazine digitally moved one of the pyramids, and the movie "Clue" was considered clever because it had different endings in different theaters. Now, it's within the realm of possibility for someone with enough processing power and the right position in the network to tailor the results of a ball game -- I see the Red Sox win, you see the Yankees win.

What happens when political censors in some authoritarian country get ahold of this technology? Election results, indeed, most of reality, can change. Reality, or at least its perception, has become fungible, "reality-based community" be damned.

Or will Feynman be right in the end?

IP Storage Mailing List Archive

2007-12-07T00:29:00.000+09:00

The only link Google could produce (to my queries, anyway) to the IP Storage Mailing List archive was broken. A query to the fine folks at CMU was quickly answered, and you can find the archives here.

My principal impression, some years later, is one of an enormous amount of work: the key players worked very hard to build a high-quality spec. By the time the IPS effort got underway, I was buried in work at the now-nonexistent Network Alchemy. I don't regret any of the time I spent at Alchemy or Nokia (which bought Alchemy), but after having broken some of the initial technical ground, I do wish I could have been more directly involved in the iSCSI effort.

Why am I ruminating about this now? Well, the basic concept of network-attached peripherals, or network-centric system architectures, seems to be percolating back to the surface. It will be interesting to see how it plays out.

Netstation "Renewal", and the Genesis of iSCSI

2007-12-05T09:31:00.000+09:00

The Netstation web site has moved (click the link). Actually, the page partially moved a while back, but some links broke in the process; it should now be complete.

Netstation was a project at USC's Information Sciences Institute, focusing on the re-architecting of systems around a network instead of a bus. Greg Finn came up with the idea (independently arrived at by others at Cambridge and MIT) in 1991 or earlier, and the project was funded by ARPA 1994-7, if I recall correctly. We did a network-attached display, keyboard, and disk. Arguably, the work that came from Netstation, members of the National Storage Industry Consortium's working group on Network-Attached Storage (notably Garth Gibson, John Wilkes, and Richard Golding), and later work at Quantum Corp. in collaboration with 3com and Adaptec were the genesis of iSCSI.

The idea of network-attached peripherals goes back at least to the early 1980s, and mainframe architectures employ a switched I/O infrastructure that looks like a network if you squint. A number of these are documented in my OSR paper, available from the Netstation page. But I'll take some of the credit for insisting that the protocol be IP-based; see my 1998 ASPLOS paper, "VISA: Netstation's Virtual Internet SCSI Adapter". Simply googling for "iSCSI" doesn't turn up that paper, because it was written before the term "iSCSI" was coined.

When you first bring the idea of IP-attached peripherals up, hardware folks are negative because of the performance implications, but the really difficult problems are security, device discovery, and sharing. The most interesting change is that the boundary of the system disappears. These problems remain research challenges, a decade later, despite a few forays in that general direction, many of them by Garth Gibson and his students, co-workers and collaborators.

(On a side note, one paper that we wrote that was never published was "NXS: X on a Network-Attached Frame Buffer". We submitted it to the 10th X Conference, but it was rejected, and we never revised and resubmitted. I no longer have a copy of the paper; if anyone out there reading it was on the program committee for that conference and is a compulsive pack rat, I'd love to have one back. That was the single hairiest piece of coding I've ever done...)

I should write up a little more on the history and prehistory of iSCSI. The brief timeline on IBM's web page doesn't go into any of that prehistory...

Links for Distributed Quantum Computation

2007-10-12T11:52:00.000+09:00

The paper has been available on the arXiv for a while, and is now available through IEEE Computer Society's Digital Library.

@Article{van-meter07:_commun_links_distr_quant_comput,
author = {Rodney Van{ }Meter and Kae Nemoto and William J. Munro},
title = {Communication Links for Distributed Quantum
Computation},
journal = "IEEE Transactions on Computers",
volume = 56,
number = 12,
month = dec,
pages = {1643--1653},
year = 2007,
doi = {10.1109/TC.2007.70775}
}

Congrats Ryuji!

2007-10-12T11:49:00.000+09:00

Keio's Ryuji Wakikawa just won one of Ericsson Japan's Young Scientist Awards for 2007. I haven't found an announcement in English, just the Japanese one.

Congratulations!

The Story's Not Over

2007-08-28T10:38:00.000+09:00

Yeah, yeah, yeah, I haven't been posting lately. Being an assistant professor is a lot of work :-).

The Williamson Daily News, my hometown newspaper, just published a nice profile of me.

Yes, life is always an adventure, though reading the article makes my life sound a lot more exciting, and my accomplishments more important, than they actually feel.

A Sad Note: Obituary for Ron Ayres

2007-01-25T08:37:00.000+09:00

I'm devastated. Ron is the guy who brought me from Caltech to ISI. He was the sweetest guy on the planet -- and one of the smartest.

Ron was Caltech's very first CS Ph.D. I think there were two the year he graduated, and he came earlier in the alphabet, so he was the first to receive his diploma.

Not mentioned in the obituary is that Ron was the pivotal technical figure in the early days of the MOSIS project (now MOSIS.com). MOSIS, many of you know, is the microchip prototyping service originally run by USC's Information Sciences Institute. When started in the early 1980s, the idea that you could email or FTP a VLSI chip design somewhere and receive several (hopefully) working pieces of silicon ten weeks later was extremely radical, and transformed VLSI research in the U.S. Ron and Danny Cohen were, if memory serves, the cofounders of the project.

Ron was an early proponent of silicon compilation, taking a text program description of desired functions and creating a chip layout to match. His Integrated Circuit Language (ICL), a strongly-typed, polymorphic, garbage-collected, interactively compiled system, was perfect for the task. Unfortunately, Ron wasn't interested in playing the academic publishing game, and his influence is smaller than I think it ought to be.

Ron was also very interested in computer graphics. His Ph.D. adviser was Ivan Sutherland, who essentially invented the field of computer graphics. In the early 1970s, Ron did some clever and beautiful wire-frame stereograms of mathematical functions (including a Klein bottle) and printed them on a large plotter. In Ron's story, Ivan was unimpressed, and he later discovered that Ivan lacked stereoscopic vision -- apparently a common trait.

Ron may not (or may) have been as smart as Feynman, but he shared an intellectual trait: he thought *differently* from other people. He arrived at questions and solutions in a different fashion.

He also had an impressive collection of Hawaiian shirts, and was a lousy but enthusiastic volleyball player, an incorrigible punster, and an unrepentant TECO user into at least the mid-1990s. One thing I remember is the clatter of his HP graphics terminal -- Ron could type at an incredible rate and attacked the keyboard ferociously.

Ron was my boss, and a good one: he knew how to get the most out of someone like me. He told me, "You will spend a third of your time working on the main project I'm hiring you for, a third of your time on other unrelated tasks I ask you to do, and a third of your time doing what you want. I know I'll get something good out of it." I believe he got that management style from Danny. What Ron got out of my "free" time was a rewritten garbage collector and variable-size memory management -- ICL up to that point used Lisp cons cell-like memory management. I also helped edit a book he wrote on language design which was never published. I think I still have my copy somewhere...

Ron worked very hard but also knew how to have some fun -- more than once he looked at me and said, "It's a beautiful day, let's go to the beach." And we knocked off work and went body-surfing.

Below is the obituary as it appeared in the L.A. Times:

AYRES , Dr. Ronald F.
(53); Child Cello Virtuoso, Computer Scientist
and Cal Tech Faculty Instructor.
Dr. Ron Ayres, former Computer Science Lecturer
at the California Institute and Technology,
Computer Scientist at the University of Southern
California/Information Sciences Institute and
holder of numerous software patents, passed away
from natural causes at his home in Marina District on January 9, 2007.
Ron was the son of J. Marx Ayres, Consulting
Mechanical Engineer and Anita Lauda, Concert
Pianist. They raised their three children:
Denise, Ron and Gary in the Carthay Circle
District at 611 San Vicente Blvd., Los Angeles.
They all became musicians, playing the violin,
cello and viola respectively. Ron studied with
Naum Bendinsky and was a child protege student
of cellist icon, Gregory Priatagorsky. Denise and
Ron became teenage concert musicians, winning
numerous competitions, scholarships and rewards.
They performed in youth symphony orchestras, as
soloists and in trios. They were members of the
University of Southern California Junior Symphony
Orchestra and the Young Musicians Foundation
Debut Orchestra under the direction of Michel Tilson Thomas.
Ron was a brilliant student, completing Los
Angeles High School in 11/2 years and entering
Cal Tech at age 17. He set the cello aside to
concentrate on math and physics as a student of
Nobel Laureate, Dr. Richard P. Feyman. Ron lived
in Blacker House at Cal Tech for his first two
years, 1971-1972. He received his Bachelors,
Masters and PhD degrees from Cal Tech. His 1979
PhD research in Integrated Circuit Language was
later used to define and implement languages.
Dr. Ayres's groundbreaking work was first
published in his 1983 book, "VLSL Silicon
Compilation and the Art of Automatic Microchip
Design". He has numerous additional publications
on the enhancements and applications of his work.
He became a Founder and Vice President of Silicon
Compilers, Inc. along with Dr. Carver Mead for
the period 1981-1983. When the firm was sold, he
joined USC/Information Sciences Institute for the
period 1984-1995. In the last decade, Dr. Ayres
provided expert consultation services to others
and greatly enhanced his patented software. His
latest development efforts resulted in a 2003
Java compiler written in ICL, and a 2004
Type-centric ICL with modular implementation.
Ron Ayres lived in Venice, California for 29
years. He wanted to be close to the ocean and he
loved the creative activities and spirit of the
Venice Community. He liked to be known as a
beach bum who deeply loved his cat Precious.
Ron was never married and is survived by his
sister Denise, brother Gary, and father, Marx.

Anecdotal Warming

2007-01-16T10:16:00.000+09:00

One season (or half a season) doesn't make much of a trend, but the Daily Yomiuri today has an article on how warm things are in parts of Japan that are normally covered by snow this time of year. In Niigata, it's raining. In Gunma, ice fishing hasn't started yet because the lake hasn't frozen over. In parts of Niigata, they're golfing instead of skiing. In Aomori, they've had to postpone a series of ski competitions because there's no snow (and it's too warm to make any).

Most of those parts of Japan are generally just below freezing in the winter, getting lots of snow but not really being bitterly cold. The paper says temperatures are 0.8 to 1.0C higher than average, but that sounds like an underestimate to me; 2-3C is what I would expect it to take to completely kill snow in those parts, but maybe it's more marginal than I think.

And on the news last night, they said that Moscow is 10C warmer than typical this time of year.

The article attributes the warming to El Nino. Make of it what you will...

Communication Links for Distributed Quantum Computation

2007-01-15T21:37:00.000+09:00

R. Van Meter, K. Nemoto, W.J. Munro, "Communication Links for Distributed Quantum Computation," is now available as quant-ph/0701043.

Combined with papers such as "Arithmetic on a Distributed-Memory Quantum Multicomputer" (which is an extended version of our ISCA paper available on my publications page), we are gradually building a complete picture of a machine that will run quantum programs effectively in a distributed fashion.

Caltech, the Basketball Powerhouse

2007-01-14T16:04:00.000+09:00

After last week's by the men's team over Bard College -- the first NCAA win in eleven years -- the women topped it with their first NCAA win ever, beating Pomona Saturday night. Go Beavers!

Rick Greenwald has made a documentary called Quantum Hoops about the Caltech basketball team, which will premiere at the Santa Barbara International Film Festival in a few weeks. Good timing, Rick! It's too far a commute from Tokyo, but I certainly hope to see the film.

Winny Defense Breaches

2007-01-10T09:26:00.000+09:00

Winny, the popular Japanese file sharing program, has been linked to at least 27 cases of data exposure from the GSDF (Ground Self-Defense Forces) since 2002. According to sources, no classified data has been compromised.

Last February a big incident was discovered, which led the Defense Agency (as of yesterday, upgraded to the Defense Ministry, giving it a cabinet position for the first time since the war) to procure 56,0000 PCs to be used by SDF personnel. Why? Because they were using their home PCs for SDF-related work, due to lack of access to computers at work. Presumably it will be easier for them to prevent the installation of software such as Winny on ministry-owned computers, though repeated security breaches elsewhere via company-owned computers shows it to be no panacea.

This is the same Winny whose author was recently convicted of knowingly supporting piracy of music and movies, but as far as I know, these kinds of data leaks are unintentional. I haven't followed the details of these breaches, but I suspect it's mis-setting of the controls resulting in accidental sharing, though it's also possible that there are security holes in Winny itself.

New Beginnings

2007-01-07T08:45:00.000+09:00

Mount Fuji at dawn on New Year's Day, taken near the border between Yamanashi and Nagano prefectures. Not a bad photo for a little cell phone camera.

I'll be taking up a position as Assistant Professor of Environmental Information at Keio University's Shonan Fujisawa Campus. I plan to focus my research broadly on post-Moore's Law computer technologies, with emphasis on quantum computing, and on large-scale distributed storage systems.

World's Oldest Computer to Keep on Calculatin'

2006-12-21T11:53:00.000+09:00

The FACOM 128B, first placed in service in 1959, has a new lease on life. Fujitsu plans to keep it running until 2019, when it will be 60 years old.

Relay-based, it does an 8-decimal-digit add or subtract in about 0.15 seconds, and a multiply in about 0.3 sec. I don't see anything mentioning storage capacity (primary or secondary) or even technology, but the article does say the machine covers 65 square meters, which is probably larger than the average Japanese apartment. The machine apparently has some fault-tolerance mechanisms including automatic reexecution of some faulty instructions. One of the articles says the machine is not a stored-program machine, but doesn't mention how you actually did program the thing -- plugs? switches?

The people who know how to maintain the thing are all retired, but have agreed to teach some youngsters how to do it. They also plan to digitize the circuit diagrams for it.

The article speaks somewhat in the future tense, "to be restored", but it also says the computer is actually still in use.

Numazu is south of Mount Fuji; it takes a little over an hour to get there from Tokyo Station via shinkansen and local train. Seeing this thing would be a fun field trip.

See the Daily Yomiuri article and IPSJ's online computer museum.

Winny Developer Convicted

2006-12-14T08:24:00.000+09:00

Isamu Kaneko, the guy who wrote Winny, one of the most popular peer-to-peer file sharing programs here in Japan, has been convicted of enabling users to violate the Copyright Law act. The Kyoto District Court fined him 1.5 million yen (about $13K). He plans to appeal.

Winny was released in May 2002, while Kaneko was a research assistant at Todai (University of Tokyo), and Kaneko was arrested and indicted in May 2004. Two men who used his software to distribute copyrighted movies have already been convicted and given suspended jail sentences of a year.

Apparently the case hinged on some comments Kaneko made indicating that he knew his software was being used for illegal purposes.

One estimate is that Winny users still violate copyright at a rate that represents 10 billion yen (almost $100M) every six hours. There are also malware programs out there that leak information from PCs onto Winny, which has been the source of some of the serious data privacy breaches in the last few years.

One thing that seems remarkable about this case to me is that Japan has often seemed to have a rather laissez faire attitude toward copyright violation. American music afficianados know that imported Japanese CDs often sell for $30, and assume that someone is making a killing doing the importing, but in fact, that's the common sale price here. In response, sales are actually low; CD rental shops are more common than sales. Sales of blank minidiscs are correspondingly high -- guess what happens when that rented CD goes to someone's home? Copy-protected CDs are becoming more common here as a result.

Trademarks, especially of foreign companies, likewise are erratically protected. Fake goods are common, and near-imitations of trademarks that probably wouldn't past muster in the U.S. abound. Recently a very popular series of "one coin" 500 yen DVDs has appeared, containing bad transfers of bad prints of old movies (I admit, I watch them). The movies are all 50 years old or older, which is the copyright limit here, so they're technically not illegal, but I suspect in the U.S. the original studio would still attempt to make the DVD producers' lives difficult.

Until they pull them down, the Daily Yomiuri's articles on this are here, here, and here. (the editorial is titled, "Winny ruling spotlights engineers' moral duties").

Robots Galore

2006-12-13T13:42:00.000+09:00

The Yomiuri Shimbun reported on Tuesday that there is a new robotics association here, with Kyoji Takenaka to be its first chairman. It includes about 210 manufacturers, universities and local governments (no idea if Keio is involved).

According to the Japan Robot Association (JARA, which is an older organization), 690 billion yen worth of robots (about six billion dollars) were sold in Japan in 2005, up almost twenty percent from the year before.

DoCoMo Subscribers Drop

2006-12-10T09:26:00.000+09:00

DoCoMo reported a couple of days ago its first-ever drop in subscribers to its mobile phone service. In the month of November,17,500 more people canceled their service than signed up for it. KDDI and Softbank both had increases, of 324,900 and 68,700, respectively.

This is probably due to the start of number portability. It's now possible to change providers and keep your phone number, though of course not your keitai's email address.

A Change in Attitude Toward Corruption?

2006-12-10T09:05:00.000+09:00

It often comes as a surprise to people who think of Japan as an orderly society, but there's a lot of corruption here. One of the biggest forms is contracting out government construction projects. In the last month and a half, three of Japan's 47 governors have been arrested on bid-rigging charges. The government decides on a project, decides on a maximum budget, then puts it out to bid. In theory, the government's pre-decided ceiling is secret. But in Miyazaki-ken, for example, the winning bid was an average of 95.8% of the government's ceiling. The governor was arrested yesterday. The governors of Fukushima and Wakayama have been arrested, too.

That's just an example; there are many others. The government and press have been on an anti-corruption campaign the last couple of years, attacking interests including those that led to poor oversight of large apartment complexes, which are now believed to not be earthquake-safe. But this seems to happen every few years; the governors of Ibaraki and Miyagi were arrested in 1993, during my first tour of duty in Japan. So I figured this one would blow over, too, but now I'm starting to think they're serious about cleaning things up.

This problem extends even to research; professors of Todai (U. Tokyo), Keio, and Waseda have all gotten caught with their hand in the cookie jar in the last three years or so. This has resulted in intense scrutiny of all research-related expenses. Every expense report I file gets gone over with a very fine-toothed comb. At the macro level, the funding of grants has slowed down due to the addition of more checks.

Part of the problem comes from a "you scratch my back, I'll scratch yours" cooperativeness. Especially in government construction contracting, many of the government officials expect to Descend From Heaven (amakudari) to a cushy advisory role for the construction companies they nominally supervise. Not exactly conducive to strict oversight.

"I Am My Own Rival"

2006-11-26T21:49:00.000+09:00

Yokozuna Asashoryu finished off the year with a 15-0 zensho yusho (all-wins championship) in the Kyushu basho (tournament). He sewed up the trophies yesterday, so the only question today was whether he would get his fifth perfect record or not. He was up against Chiyotaikai an ozeki with a solid tournament going. (Not sure what the heck I'm talking about? Click the links, should be obvious.) Chiyo blasted out of the tachiai, had Asa back on his heels and reeling, and stuck his elbow in Asa's throat and starting pushing. Asa slid all the way back to the bales at the edge of the ring, teetered there... and for some inexplicable reason, Chiyo pulled his elbow out of Asa's neck and tried to wrap his arm around Asa's shoulders. That was all the opening Asa needed. He slipped under Chiyo's arm, came around the side, and picked Chiyo up and put him down outside the ring. Chiyo, at 160kg (350 pounds), is probably intermediate weight for a sumo wrestler, but picking up a guy that size who doesn't want to be picked up is quite a trick.

Asashoryu is the perfect sumo wrestler. If I could pick one adjective to describe him, it would be "fierce". He hates to lose, concentrates incredibly well, is never intimidated, and goes all out, every match. He has technique, he has strength -- his shoulders and legs are incredible. He has unreasonable amounts of speed for a guy 148kg -- lose contact with him for a fraction of a second, and he's around your side, and it's all over. But above all, he has that fierce will to win.

He said yesterday, after his win guaranteed him the Emperor's Cup, "I am my own rival." Some say he does so well because he has no competition; the ozeki are all bumblers, over the hill, or injured most of the time. I say Asa is just plain better than they are. I've watched Konishiki, Takanohana, Wakanohana, Musashimaru, and Akebono many times, and while it would be entertaining to watch Asa go up against one of them in his prime, my money right now is on Asa as the best wrestler of the last fifteen years. Koni-chan and Maru had that immovable bulk (and Maru a fierceness of his own), Taka that beautiful technique, Ake that long, long leverage -- but I'll take Asa. His strength is a clear step above Taka, who is perhaps next on the list, and I think his technique is as good (that page above lists nineteen techniques used in his last six tournaments (67 wins) -- great versatility, since the ozeki run nine to fifteen, albeit for smaller win totals). Both know how to win the big matches; Taka perhaps had more of them that Asa has had so far, but I think Asa is his equal in ability to win them.

In 2005, Asa's record was 84-6, and he won all six tournaments. In my opinion, he was sportsman of the year for the entire planet. 2006 has not gone quite as well due to an injury mid-year, but when healthy (as he usually is -- nothing seems to nag at him) he has no rivals. Except, of course, himself.

Beautifying Kyoto

2006-11-26T09:55:00.000+09:00

Today's Daily Yomiuri contains evidence of the visual blight of Japan that Alex Kerr talks about in his fantastic book Dogs and Demons. A front page article says that Kyoto will ban flashing neon signs atop buildings, starting next year and going into effect over the next six years. Kerr has watched the decay of Kyoto's beauty since the 1960s, and must be saying that this move is far overdue. The city should, by all rights, be a charming, quiet place, good for strolling narrow streets with old houses and traditional restaurants. Instead, except for the neighborhoods of Pontocho and the Philosopher's Walk, most of it is rather garish, especially at night, combined with some world-class ugly buildings. The Japan advertising association naturally says it's not the only ones to blame, as if that's a good enough reason not to fix one of the worst problems. Kyoto will also lower the maximum allowable height of new buildings, especially around Kyoto's world heritage sites.

Then, on page 3 of the DY, there is a picture of the proposed New Tokyo Tower, to be the world's tallest transmission tower when it is finished in 2011. Designed by Tadao Ando (arguably Japan's best and most famous architect, and deservedly so -- he does some beautiful things with curved concrete that work wonderfully in their environment, rather than simply destroying it) and sculptor Kiichi Sumikawa. The tower will be triangular at the bottom, round at the top. Personally, I'm not sure it's needed.

IIJ "Improves" Their Service

2006-11-24T09:55:00.000+09:00

IIJ, Internet Initiative Japan, is one of the oldest and most respected ISPs in the country. I've never used anyone else. But the day before yesterday, they implemented an "improvement" to their network that has me looking for another ISP.

With no prior announcement that I saw, they started blocking outbound SMTP. This means that, all of a sudden, I can't send email from my house, except by using some web-based mail system such as Gmail.

I use three different email accounts that I need outbound SMTP access for. I called their service line, and the woman I talked to suggested that I get them to open up SMTP on another port. Ugh. Like that would solve anything, even if I could get them to do it.

I threatened to cancel my service, and she said that any other ISP I can find will likely either already have port 25 blocked, or be doing so in the near future. It's an anti-spam measure recommended by the Japan Email Anti-Abuse Group (JEAG).

I haven't been this angry about some utility in a long time...

Tsunami

2006-11-15T22:11:00.000+09:00

I'm watching a news press briefing right now about the tsunami. It was triggered by an 8.1 earthquake several hundred km northeast of the northeastern tip of Hokkaido, the northernmost of the four major islands of Japan.

The earthquake was felt only mildly in Hokkaido and not at all in Tokyo; I wouldn't even have known about it except that I happened to check a news website before going to bed.

The threat is quite serious, and is being treated so, but at this particular moment the only reports of activity are in the 20-40cm range. That's big enough to create serious water coming onshore; they said that the height can be amplified two to ten times that when it hits land, depending on conditions.

All of the TV stations except the shopping channels (which probably run only canned material) have a map of Japan with flashing coastline covering most of Hokkaido and the eastern coast of Honshu all the way down from Tohoku, past Chiba and Tokyo down to about Nagoya. But they are saying that the size and threat are smaller down here.

We live high enough and far enough inland that we're in no danger, and neither are our friends, but there are plenty of people close enough to the coast to worry about.

The predicted time of the earliest arrival has come and gone for the northern part of the country with no major waves reported, but we're not out of the woods yet...

Someone (the head?) of the meteorological agency is giving a briefing at this moment...

IPW2200 on FC6

2006-11-14T12:09:00.000+09:00

Sorry, I still haven't written up my full notes on getting Fedora Core 6 running on my Sony Vaio Type T laptop, but one tidbit:

Sometimes when I boot, the initialization of the IPW2200 builtin WLAN interface doesn't happen properly. This symptom is this:


[rdv@localhost ~]$ iwconfig
lo        no wireless extensions.

__tmp1804289383  IEEE 802.11g  ESSID:"xxxx"  
          Mode:Managed  Frequency:2.462 GHz  Access Point: 00:07:40:xx:xx:xx   
          Bit Rate:54 Mb/s   Tx-Power=20 dBm   Sensitivity=8/0  
          Retry limit:7   RTS thr:off   Fragment thr:off
          Power Management:off
          Link Quality=62/100  Signal level=-63 dBm  Noise level=-85 dBm
          Rx invalid nwid:0  Rx invalid crypt:0  Rx invalid frag:0
          Tx excessive retries:0  Invalid misc:482   Missed beacon:20

eth0      no wireless extensions.

sit0      no wireless extensions.

and networking fails to work. This condition sometimes persists over reboots, it seems, though as far as I can tell it's just a random phenomenon, so I don't know why it would persist.

The solution is:


[root@localhost rdv]# rmmod ipw2200
[root@localhost rdv]# modprobe !$
modprobe ipw2200
[root@localhost rdv]# iwconfig
lo        no wireless extensions.

eth0      no wireless extensions.

sit0      no wireless extensions.

eth1      IEEE 802.11g  ESSID:"xxxx"  
          Mode:Managed  Frequency:2.462 GHz  Access Point: 00:07:40:xx:xx:xx   
          Bit Rate:54 Mb/s   Tx-Power=20 dBm   Sensitivity=8/0  
          Retry limit:7   RTS thr:off   Fragment thr:off
          Encryption key:off
          Power Management:off
          Link Quality=67/100  Signal level=-60 dBm  Noise level=-86 dBm
          Rx invalid nwid:0  Rx invalid crypt:0  Rx invalid frag:0
          Tx excessive retries:0  Invalid misc:0   Missed beacon:10

Hope this helps somebody; meantime, if any of you know why it's happening and how to stop it from happening, let me know.

Hello, Dali

2006-11-09T06:10:00.000+09:00

I had the day off yesterday, and went to the Ueno Go Club (first time) and the Salvador Dali Centennial Exhibition at the Ueno Mori Museum. The exhibit is well worth seeing, something like a hundred of his works, starting from his teens and going into the 1980s. I was surprised to see some Cubist works (in both form and palette) in his early period. If this exhibition is any judge, surrealism sprang from his head full-blown in about 1927; I didn't see anything I'd consider a "transitional" work.

The logistics aren't perfect. His pencil sketches are dimly lit, presumably to protect the paper, but that makes them difficult to appreciate. And he painted a couple of stereo pairs which are very large; it's impossible to get far enough away from them to cross your eyes and see the stereo effect without a crowd gathering between you and the paintings.

Speaking of which, though it was a Wednesday afternoon, the museum was crowded. Go early.

The catalog appears to be only in Japanese, though the works were all titled in both English and Japanese. Some of the quotes on the wall were in English, some in Spanish, all translated into Japanese. But for paintings, at least, an English explanation is optional; we recently went to see the exhibit of Chinese terra-cotta warriors at the Tokyo-Edo Museum, and that also had no English, which would definitely leave you lost if you couldn't read Japanese. "What the heck is that? When was it made?" Those are important questions for historical artifacts.

Anyway, Dali is there until Jan. 4. Don't wait!

Fedora Core 6 on a Sony VAIO Type T Laptop

2006-11-07T12:56:00.000+09:00

One of the most popular entries on my blog right now is the one on getting cpuspeed working right on a Linux laptop. I am almost done with my upgrade to Fedora Core 6 (FC6), and it was significantly painful. I'll give you the gory details in a few days (assuming I get around to it), but for the moment you probably need to know this: anaconda (the Fedora installer) sometimes installs the wrong kernel. My eventual solution involved installing the .src.rpm for the kernel and recompiling to get the p4-clockmod module to regulate CPU speed properly, but just as I was getting that process really under way a friend pointed out a note on livna.org which leads to the bug description.

I had considered removing the running kernel from my machine and installing (or just forcing) the right package off of the DVD, but worried that it had the potential to trash my machine, so I elected to do a kernel rebuild instead (always good practice, anyway). However, others are reporting that the remove and install works for them.

I also took the opportunity to do things like specify that the console resolution is 1280x768 on my machine, but AFAICT, that had no effect.

More later, but this may help somebody right away...

Zen 747

2006-11-05T10:06:00.000+09:00

I look at this in a different light after reading Alex Kerr's Dogs and Demons, but it's still one of the cool things about living in Japan, running into unexpected things tucked into corners, like a zen rock garden on the roof of an internal structure in the terminal at Narita Airport.

Caltech's 100 CS Questions

2006-11-05T09:24:00.000+09:00

Caltech, like most U.S. universities, has a qualifying exam that you must pass during your Ph.D. studies, generally around the time you finish classes and begin serious research. At Caltech, it's an oral exam, and the examiners can ask you anything. Adam posted the 100 key questions from 1998. They cover graphics; numerical analysis; continuous math; theory; algorithms; predicate calculus, program semantics and complexity; concurrent systems; hardware; databases and directories; and programming languages.

And, as Adam says, "The candidate should be able to leap tall buildings, outrun speeding bullets and be able not only to forsee [sic] the future, but control it."

The list very definitely represents the interests of the faculty. If you're not interested in one of those topics, you shouldn't be at Caltech; it's still a small, eclectic place (which, IMHO, is to its benefit). There are a couple of questions on the Internet, and some of the basics of operating systems are incorporated into concurrent systems, but there's very little that's directly related to the last twenty years of my life: the words virtual, disk, storage, memory, cache, file, mobile, and even architecture appear nowhere in the list (though some of them could plausibly appear in the answers to some questions).

The list is intimidating, but you have about two years to prepare for the exam, and much of that two years will be spent in classes that will answer most of those questions. In preparing for the test, you've probably already covered half the material or more, so an hour for each of those questions should be plenty of review; the other half you probably need a half a day to a day in the library for each question. Total, 2-3 months of hard prep work for your quals seems like a reasonable expectation.

This is roughly the era my pal Eve Schooler, who was a student of Mani Chandy's, was probably taking her quals. I should ask her how much of an ordeal it was...

Floating-Point Addresses

2006-10-31T06:15:00.000+09:00

Last week during the Wild & Crazy Ideas session at ASPLOS, I mentioned floating point addresses, and several people asked me about it later. I partially incorrectly attributed it to Jim Kajiya; the CS Tech Report on the Caltech Object Machine (COM) is by Dally and Kajiya (in that order).

The basic premise is that segmented architectures with fixed-size segments are always a pain because the segments are never the right size -- either the segment is too small, or if they're large, you can't have enough of them to be useful. In COM, the exponent of a floating-point number can be considered the object identifier, and the mantissa can be considered the offset within the object. Since the boundary between the exponent and the mantissa is flexible, you can have lots of small objects, or a few large objects, under system & compiler control.

It's been a while since I looked at it; I think objects are limited to a power of two in size, so bounds checks on them will prevent gross memory allocation violations, but not necessarily subtle off-by-one bounds errors. Other obvious questions I don't recall the answers to include how memory fragmentation is avoided.

I'm curious how this concept could be melded with modern compiler array privatization techniques. COM seems, offhand, to be very good for arrays but less useful for heterogeneous objects, and privatization could certainly help there.

The link above is to a Caltech technical report, but I believe they also got an ISCA paper out of it; I don't know if the two are the same. The TR talks about a machine simulation; as far as I know, no prototype was actually built, but I could easily be wrong there.

The Gates of Hell

2006-10-31T05:59:00.000+09:00

I don't know a lot about sculpture, but in my humble opinion, Rodin's "The Gates of Hell" is the greatest sculpture in the history of the Universe. Stanford has dozens (hundreds?) of Rodin sculptures (including early maquettes of "The Burghers of Calais"), both inside and outside the Cantor Center for the Visual Arts, as well as scattered around campus. The museum is well worth a visit if you have the chance; it's open late on Thursdays and admission is free, so you really don't have an excuse not to go. The museum is medium-sized, and sort of eclectic, but contains a number of powerful pieces.

Analog Computing Papers

2006-10-18T07:54:00.000+09:00

Three I've run across, but not fully digested yet:


@article{vergis1986cac,
  title={The Complexity of Analog Computation},
  author={Vergis, A. and Steiglitz, K. and Dickinson, B.},
  journal={Mathematics \& Computers in Simulation},
  volume={28},
  pages={91--113},
  year={1986},
  comment = {Claims a digital computer can efficiently simulate an
                  analog one, and an analog one can't solve NP
                  problems if a digital one can't.}
}

@article{turan1994cbf,
  title={{On the computation of Boolean functions by analog circuits ofbounded fan-in}},
  author={Turan, G. and Vatan, F.},
  journal={Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on},
  pages={553--564},
  year={1994},
  comment = {Haven't read yet...}
}


@article{maass1998ean,
  title={{On the effect of analog noise in discrete-time analog computations}},
  author={Maass, W. and Orponen, P.},
  journal={Neural Computation},
  volume={10},
  number={5},
  pages={1071--1095},
  year={1998},
  publisher={MIT Press Cambridge, MA, USA}
}

The Turan paper requires an IEEE Digital Library subscription to get, the others are available free on the web if you look.