Monday, July 08, 2024

Spelunking CACM's Second Decade

 As you know, I am working my way through Communications of the ACM, beginning to end, stopping to read a handful of articles from each year. These aren't necessarily the papers with the highest citations, but instead things that catch my eye from the point of view of the 2020s.  A full two years ago I finished the first decade of CACM; now I have finished the second, so let's index them. (Hmm, I've fallen out of the habit of giving them descriptive names, I should go back to that.)

Sunday, July 07, 2024

Spelunking CACM, Vol. 20 (1977)


I have finally reached my twentieth article in this series! It's probably time for another summary, but first let's do the things that caught my eye in 1977. This was the year that "Star Wars" (with the simple title) came out. I was eleven. I probably wasn't yet particularly aware of computers and computing, but I was already a fan of "Star Trek" and of the space program (which was in the Apollo-Soyuz/space shuttle interlude at the time).

When I first skimmed the contents for 1977, I flagged eighteen articles for further investigation. For a systems person like me, there was a lot to catch the eye. I've winnowed it down, but if you look there are still more good papers than just these.

If you're interested in data about demographics and numbers of students in CS, there is a report following on from the previous year.  What's depressing is not how bad it was in 1976, but how bad our diversity remains today.

As long as we're on the topic of education, it was already possible in 1977 to put together a survey of 200 publications on CS ed. ACM's first curriculum committee issued its report in 1968, though, and SIGCSE was founded in 1970, so it should be no surprise. The CS GRE was also introduced recently and analyzed in CACM.

Dorothy Denning and Peter Denning give an elegant description of how to certify information flow in programs for security purposes. Consider, for example, the simple statement



If the variables y and x are in separate security classes, then there is a potentially unauthorized information flow between the classes. After the execution of this statement, the value of y will equal the value of x, whether we considered that acceptable or not. The Dennings go on to discuss a complete method for static, compile-time analysis of this information flow.

Morgan and Levin provided a mathematical means of assigning files to network nodes to optimize overall system performance. The eye-catching hypercube with cut planes at the top of this blog posting is taken from the article. They even consider multiple copies of the files in the networks, and divide traffic into "query" and "update" and consider them separately. They recognize that assigning the files to the nodes is an exponentially complex problem, and provide some heuristics for avoiding searching the entire space.

Speaking of networks, Tajibnapis developed a routing protocol for the MERIT network in Michigan. His article on TIP was originally submitted in 1974, and finally published in 1977. To me, the NETCHANGE protocol specifying the message contents for routing protocols sounds a lot like RIP, which was developed quite a bit later. However, TIP doesn't seem to have had a lot of impact; I'm not sure why. Of course, even by 1974 Dijkstra's shortest path first algorithm was fifteen years old, and there was quite a flowering of work on routing in the mid-1970s, so it's likely that there was other, similar work. MERIT would go on to be a pivotal place for networking research for decades to come.

In operating systems work, Lamport wrote about readers and writers, which I still teach about in my OS class today. Fundamental stuff, though this article is a little...rococo in its notation, I think.

Parallel computing was in its earliest phase of trendiness. While I associate a lot of theory of correctness in parallel programming to K. Mani Chandy, there is a paper here on how to prove parallel programs correct, using Susan Owicki's techniques and an implementation of Dijkstra's on-the-fly garbage collector as the example. As author David Gries says,

Building a program with little regard to correctness and then debugging it to find errors is even more folly for parallel programs than it is for sequential programs.

Word.

And finally, if you want some history to go with your history, there are Rabin's and Scott's Turing Award lectures, given for their work on nondeterministic automata some years prior.


Monday, June 24, 2024

Lynn Conway

I was in a Starbucks when I saw Dave Farber's message on his IP mailing list saying that Lynn Conway had passed away, and I said out loud, "Oh, no!" and started crying. She was a hero and an icon, and stands high in our technical pantheon.

Of course, every person has the fundamental human right to live as they are, as they understand themselves to be, and the rest of us get no say in who they are. Saying, "It's okay that Freddie Mercury was gay, he was an amazing singer and artist," fundamentally misunderstands this. The vast majority of LGBTQ+ people are perfectly ordinary people, and that is perfectly fine. Margo Selzer said, "It is not the job of the underrepresented to solve underrepresentation," and the same is true for other aspects of life as a minority. It's the job of the majority to change ourselves to be accepting; no minority should be required to step up and be a hero. So, Lynn "owed" no one her work as an activist; it was a role she chose late in life, and we should be grateful for it.

FWIW, it took IBM 52 years to get around to apologizing for firing her (falling just short of the 55 years it took the UK government to apologize for chemically castrating Alan Turing for being gay).
https://www.nytimes.com/2020/11/21/business/lynn-conway-ibm-transgender.html

As it happens, I was talking to a couple of students yesterday about citation counts for researchers in computer science and electrical engineering, and we found a website where the top researcher has half a million citations. You won't find Lynn's name on a list like that, and yet I would put her contribution far above almost everyone on such a list. She received dozens of awards, but far fewer than she deserved, IMO. There would BE no "chip industry" without her.  Pretty much everything else in our research field and our entire industry...is secondary.

Wikipedia tells me that IEEE Solid-State Circuits Magazine published a special issue on her career in 2012. I didn't know that, but it was well deserved. Her own reminiscences are worth reading -- every sentence.
https://ieeexplore.ieee.org/document/6392995
https://ai.eecs.umich.edu/people/conway/Memoirs/VLSI/Lynn_Conway_VLSI_Reminiscences.pdf

We all owe her a tremendous debt. Write her name in the history books, and then go and pay it forward. I'll tell my Computer Architecture class and my quantum computing research group about her tomorrow. I didn't know her in person, but I probably won't be able to keep my eyes dry.

[written right after hearing about her passing, posted a couple of weeks later.]

[edit: obituaries:

]

Tuesday, June 04, 2024

Gordon Bell



 Gordon Bell has passed away.

Gordon was one of the most important computer architects of all time. He designed, co-designed or was executive lead in charge of most of Digital Equipment Corporation's key machines in its heyday, from the initial PDP-1 to the VAX-11, in two stints working for the company. Although he wrote the seminal description of the PDP-11, perhaps the most influential minicomputer of all time, I don't think he had much to do with that design or with the PDP-10, and by the time of the Alpha he had already left DEC for good. But still, much of the company's design sensibilities grew from him.

I learned a great deal from the book he coauthored on computer engineering, using all of the DEC machines as examples. Most of the chapters were coauthored by Gordon and other members of the various technical teams. (Wow, I paid ten bucks for my copy at a DECUS in 1986, but even the Kindle version now goes for a hundred bucks?!?)

He also established the Gordon Bell Prize for accomplishments in parallel computing. One of the recent prizes was for simulation of quantum mechanics, though nothing to do with quantum computing.

RIP Gordon, thanks for the machines and for being such an important advocate of parallel computing.



Thursday, May 30, 2024

Questions about QKD

 I think quantum key distribution is fascinating, but unlikely by itself to serve as reason enough to build a Quantum Internet. Keeping in mind that I am not directly a QKD researcher, in my opinion there are several major hurdles limiting adoption of QKD today:

  • Range of QKD is limited (until we build a multihop, long-distance network).
  • Boxes are expensive, not robust, and require a lot of operational expertise.
  • Attacking QKD deployments is trivial; it's designed to detect eavesdroppers, so by its very nature acting as an eavesdropper is equivalent to launching a DoS attack.
  • Interoperability, standards and global operational confidence are still works in progress.
  • Market pull is still limited, because the problem it solves -- generating shared random or near-random bits secure enough to be used as encryption keys(*) -- still isn't tops on the list of pain points for Chief Security Officers, AND there is a classical solution in the offing (PQC) that requires "only" software and protocols, no new hardware.
  • Latency to start up a connection is orders of magnitude too high to be useful at e.g. the HTTPS level, so it has at best a specific and limited role in systems, e.g. network-to-network IPSec tunnels.
With that in mind, I recently had a discussion with a QKD researcher about how to evaluate new ideas in the area. We came up with about thirteen questions/concerns/metrics answering the question, "What do we want to improve?":
  1. Steady-state key generation rate
  2. Robustness against noise
  3. Fraction of raw resources dedicated to detecting an eavesdropper
  4. Robustness against some known attack (e.g., detector blinding or entangling with qubits)
  5. Required classical communication bandwidth/latency
  6. Simplicity of quantum hardware implementation
  7. Startup time
  8. Preconditions (e.g., pre-shared key for authentication)
  9. Classical resources required, esp. randomness
  10. Ease of integration into classical security systems
  11. Ability to use in a heterogeneous quantum network environment (e.g., full end nodes with memory v. measurement-only end nodes)
  12. Demands on or benefits to quantum network operations (e.g., link tomography or network routing)
  13. Extension to multi-party protocols
Simply playing with ideas, such as "I found this cool thing while looking at quantum graph states...", is great, and important, and that's where highly original stuff comes from. But if you bring me an idea about QKD, I'm pretty likely going to ask which of the above things it improves, or if you think it has value for some additional reason.

(*) John Mattsson of Ericsson pointed out on the QIRG mailing list that it's not accurate to say the bits are used as keys. Instead, bits from any TRNG (true, or hardware, random number generator) are actually further processed through a KDF (key derivation function) or CSPRNG (cryptographically secure pseudo-random number generator), which is then fed to AEAD (authenticated encryption with associated data) before the key that is actually used is complete and finalized. He recommends a German government document on the topic.

Some Technical Women I Admire

I frequently have need of a list of women whose technical work I admire, so I finally decided to list some of them here. I'm not going to do all of your homework for you; you'll need to look them up yourself. Most of the older ones are fairly obvious names, and have Wikipedia pages. A few aren't famous...yet.
  • Fran Bilas
  • Anne Broadbent
  • kc claffy
  • Lynn Conway
  • Agnes Meyer Driscoll
  • Deborah Estrin
  • Elizabeth Smith Friedman
  • Yvonne Gao
  • Mary Hall
  • Margaret Hamilton
  • Betty Holberton
  • Grace Hopper 
  • Mary Jackson
  • Mae Jemison
  • Betty Jean Jennings
  • Katherine Johnson
  • Kanchana Kanchanasut
  • Elham Kashefi
  • Hedy Lamar
  • Ruth Lichterman
  • Barbara Liskov
  • Ada Lovelace
  • Margaret Martonosi
  • Kay McNulty
  • Maryam Mirzakhani
  • Mio Murao
  • Kae Nemoto
  • Emmy Noether
  • Poppy Northcutt
  • Keiko Okawa
  • Jennifer Rexford
  • Sally Ride
  • Jacquiline Romero
  • Mary Shaw
  • Eve Schooler
  • Donna Strickland
  • Dorothy Vaughn
  • Marlyn Wescoff
  • Suzanne Woolf
  • Lixia Zhang
  • and, of course, my own women students and colleagues!

Note that, of course (as with men), it's possible for someone to do amazing, important technical work but still not be a good person. However, of the ones here I know personally, I will say I admire almost all of them as people as well as scientists/technologists.

Saturday, May 18, 2024

A Bundle of New Quantum Internet / Interconnect Papers

A whole pile of our #QuantumInternet engineering papers hit the arXiv yesterday! I'll try to give just a short summary of each paper, so this post doesn't get insanely long. We are currently building a testbed quantum network, so a lot of this material addresses problems we are facing now or will in the very near future. We have three papers on use of entangled photon pair sources (EPPS nodes, in our lingo), a low-level engineering paper on getting the timing right, a paper on how to construct and use efficient switches, and a paper looking a little farther into the future at advanced techniques using complex, many-photon entangled states.

First up, a paper by Soon (all of these papers were highly collaborative in both research and writing, but I will identify each of them by the first author) on design and simulation of a particular link type, using entangled photon pair sources in the middle of the link as above. We call these MSM, or memory-source-memory, links. This kind of link was explored by Cody Jones back in the day, but not fully simulated (or implemented), which of course leaves holes in the needed protocol design and the possibility of dynamic effects that don't show up in an initial analysis. Interestingly, carefully throttling the entanglement attempt rate results in better throughput, a rather unexpected effect. We call the problem the mutual latch-fail phenomenon.
https://arxiv.org/abs/2405.09861

Soon followed that up immediately with a second paper on how longer, multi-hop paths behave when the links are different types. Reassuringly, paths where most of the links are one type but one is different seem to perform as well as completely homogeneous paths. This boosts our confidence that heterogeneous networks will work, and that introducing new technologies won't be a forklift/flag day upgrade.
https://arxiv.org/abs/2405.09862

Those first two apply pretty broadly to different types of network deployments: data center, LAN, WAN. In a third, related paper, Paolo Fittipaldi of Frédéric Grosshans' group simulated a particular subtype of MSM links: satellite! The figure above is probably too small to read here, so I recommend you actually read the paper. But with what we believe are realistic parameters, distribution of several entangled Bell pairs per second while the satellite is visible seems achievable. Performance is largely driven by the photon loss and latency (of course), but also (perhaps less obviously) by the amount of memory available at the ground stations. Extending this to examine the behavior of applications that use such a link, satellite-to-satellite connections, and networks that extra into metropolitan areas around the ground stations will make for interesting work.
https://arxiv.org/abs/2405.07589

Those first three make a pretty good set if you are interested in how entangled photon pair sources will behave in networks.

Since we are talking about preparing for heterogeneity, let me stick in a placeholder here for another paper that should appear momentarily. Poramet has done good work on how to combine purification and error correction in networks. Stay tuned for the paper.

Photons are most useful in our plans when they are entangled with something else (a memory or another photon), and come together in pairs so that we can measure them together, a technique known as entanglement swapping achieved via Bell state analysis or Bell state measurement. To accomplish this, we need good overlap of the arrival times of the photons, which we achieve by changing the length of the path that one photon follows. The basic idea is obvious, but it takes work to get the details right, and our team with Mori-san as first author worked them out. Rob Thew's gang is doing related work; see Secs. VII & VIII of a paper of theirs. We weren't aware of this particular paper before writing ours, but I think there is still value in the engineering analysis we present on tradeoffs in different possible configurations, both for single-hop and multi-hop paths.
https://arxiv.org/abs/2405.09881

Given that we are trying to bring photons together in pairs, in order to connect more than two nodes we need some sort of switch, a problem that Marii has taken charge of. I have been interested in topologies for interconnections since first being exposed to the Caltech Cosmic Cube, back in the days of stone tablets. It turns out that the problem of matching pairs is different enough from the ordinary all-to-all reordering of inputs to outputs to give us the opportunity to optimize the design compared to Clos, Beneš, and other interconnects and sorting networks. Every optimization we can make will reduce photon loss, which is our biggest enemy. We have reduced the number of switch points by about a factor of two compared to basic designs, focusing on layouts restricted to a plane for photonic chip implementation, and we think our designs are optimal. The only related work we could find was Drost et al., who used exhaustive search to solve the problem up to 10x10, but without a general solution and without considering whether the network can be reduced to a plane. Next, we need to extend our results to include non-planar designs suitable for connecting discrete switches, and prepare to implement this in a photonic chip.
https://arxiv.org/abs/2405.09860

Finally, the most technically obscure of the topics on the menu, Naphan's work on repeater graph states (RGSes). The challenge is that photons get lost, but the no cloning theorem and work related to quantum error correction tells us that we can't successfully reconstruct a quantum state if we lose more than half the photons. But with RGS, originally found by Azuma-san and with extensive work by the group of Sophia Economou, if you create a complex entangled state and can make quick decisions about the choice of what to do with the photons you do get, then you can handle losing certain subsets of photons. The theory is great, but implementing networks using these states isn't going to be easy, even aside from the physics problem of generating them correctly. Naphan has found ways to reduce the required classical communication by three (decimal) orders of magnitude. We continue to make progress toward practical implementation!
https://arxiv.org/abs/2405.09876

Whew! That's a ton of work, and we hope that it all helps bring closer the day when we can deploy quantum networks for production use, as a system interconnect for a multicomputer, in the data center, and in LANs, MANs, WANs and ultimately intercontinental quantum networks.

Oh, did I mention that the first authors of three of the above papers are undergraduates who just entered their third (junior) year? Bet you'll have trouble picking out which ones. Our students are amazing (both the undergrads and grad students).

Thanks for reading this long posting, and let us know if you have comments!

Monday, May 13, 2024

Important CS/CE Papers of Recent Years

What are your nominations for papers of the last decade (or so), ones that will show up in textbooks or change the fabric of what we do and how for decades to come?

Here are a few candidates my team (mostly quantum folks) and I came up with. Although I initially phrased it as "of the last decade", some took the liberty of going back a little farther, and I personally followed on from that with a few suggestions of my own.


(n.b.: I consider this to still be an open discussion, but am publishing so that people can comment)