Spelunking CACM, Vol. 23 (1980): Pilot and Medusa

The structure of the magazine is changing, but not the covers, which are still primarily black and blue, with some abstract design. The articles are longer and more in-depth, and each issue has only a few articles. Some of the older types of notices and articles, such as short algorithm descriptions, have been retired. And then rather suddenly around August or perhaps a little earlier, the article format itself changed and became more modern, with a nicer header and a three-column, large-magazine format.

Apparently there was a thing called the IBM Programmer Aptitude Test, which I have never heard of.  A quick check didn't find a copy of it online, but some discussion seems to indicate that it was a lot of math word problems. A couple of researchers tested it rigorously, and found, surprise, very weak correlation between the test result and grades in an introductory FORTRAN programming course. They also found an even weaker correlation between gender and performance.

Harold Abelson and Peter Andreae wrote about tradeoffs in VLSI design. Interestingly, this is the first time I recall seeing the term "VLSI", though maybe it just didn't catch my eye before. The term itself should have been only about three years old at the time (according to Lynn Conway's reminiscences), and yet the article doesn't bother to expand the acronym.

Not only was there a chess tournament featuring a dozen programs at a 1979 ACM conference, there was also an early attempt at a man-machine team, what we might now call "centaur" or "advanced" chess, playing against (in this case) a lone human. The article authors were relieved that the lone human won.

Xerox Business Systems (not PARC?) authors published about Pilot (the figure below), an OS for personal computers complete with a single 32-bit virtual address space.  (In fact, we might call it a 33-bit address space today, since addresses were to 16-bit words.) Pilot used a flat (non-hierarchical) namespace for files, each of which had a 64-bit unique identifier they refer to as a capability. The capability is supposed to be unique in space and time, across all machines. Frustratingly, the article doesn't contain much on the hardware required to run Pilot, but it's implemented in Mesa and very closely tied to that language.  Inter-process communication can be either via shared memory or the communication libraries provided, which primarily focused on the PUP protocol suite, though the describe similarities to the ARPANET protocol suite. Like TCP/IP, PUP includes internetworking concepts in it.

As long as we're talking operating systems, maybe the more interesting one technically is Medusa, which ran on the Cm* multiprocessor   (the figure at the top of this posting), developed at Carnegie Mellon University. The article by Ousterhout et al. describes an extremely sophisticated OS running on a distributed shared memory system. The hardware, like a NUMA system today, can directly access local or remote memory, with up to about a 10x latency penalty. The processors are LSI-11s, a version of the workhorse PDP-11 that was used for so many things over two decades and several hardware and OS iterations.

A task force includes activities, with the former roughly resembling a modern process and the latter corresponding to threads, where each activity has a specific role in the overall program/utility -- except that each activity is bound to a processor, but a task force can apparently consist of activities on many processors. One approach, shown below, is to have the many utilities (daemons, in modern terms) of the OS each running on a separate processor.

Arguably DCS echoes some aspects of Farber's DCS and in turn influences things like VAXclusters, though neither of those systems had direct hardware access to remote memory, as far as I know/recall.

Guy Steele and Gerald Sussman described a LISP microprocessor.  Interestingly, despite the fame of that pair, this article hasn't been cited much; perhaps the commercial LISP machines of just a few years later don't really owe much to it?

Also, I hadn't realized that there were formal attempts to verify security in an OS that far back -- and using capabilities, to boot.

Enough for now. Once again, this is turning into a catalog rather than a dive into one or two pleasing papers, but it's intriguing to see so much on distributed OSes showing up. What a time it was, and I was still too young to participate at all, even though some of this major work was taking place driving distance from my parents' house, in Pittsburgh. If I had known then about that work, and that I wanted to do computing systems, I might very well have gone to CMU instead of Caltech, and how different my life would have been then. Although my life later converged with many good people from CMU!

Cross-validating Quantum Network Simulators

 New paper on the arXiv. I'll be presenting this one at an INFOCOM workshop in London next month.

During this cross-validation process, we not only fixed bugs in both simulators, but we gained a deeper understanding of the performance differences caused by protocol design differences.

Cross-Validating Quantum Network Simulators

Joaquin Chung, Michal Hajdušek, Naphan Benchasattabuse, Alexander Kolar, Ansh Singal, Kento Samuel Soon, Kentaro Teramoto, Allen Zang, Raj Kettimuthu, Rodney Van Meter

We present a first cross-validation of two open-source quantum network simulators, QuISP and SeQUeNCe, focusing on basic networking tasks to ensure consistency and accuracy in simulation outputs. Despite very similar design objectives of both simulators, their differing underlying assumptions can lead to variations in simulation results. We highlight the discrepancies in how the two simulators handle connections, internal network node processing time, and classical communication, resulting in significant differences in the time required to perform basic network tasks such as elementary link generation and entanglement swapping. We devise common ground scenarios to compare both the time to complete resource distribution and the fidelity of the distributed resources. Our findings indicate that while the simulators differ in the time required to complete network tasks, a constant factor difference attributable to their respective connection models, they agree on the fidelity of the distributed resources under identical error parameters. This work demonstrates a crucial first step towards enhancing the reliability and reproducibility of quantum network simulations, as well as leading to full protocol development. Furthermore, our benchmarking methodology establishes a foundational set of tasks for the cross-validation of simulators to study future quantum networks.

https://arxiv.org/abs/2504.01290

Open Faculty Positions at Keio's Shonan Fujisawa Campus

 We have five, count 'em, five, open faculty positions in Keio's Faculty of Environment and Information Studies. If you are a researcher looking for a tenure-track position, please consider applying.

This call is very open; people of all stripes are encouraged to apply. As chair of the Cyber-Informatics Program, of course, I am hoping we will have the opportunity to hire some first-rate people in computing (defined very, very broadly).

Applications are due the end of March, I believe.

https://www.sfc.keio.ac.jp/en/employment/

Africa and Foreign Aid Today

A week or so ago, as the scale of the USAID cuts was becoming clear, an acquaintance on Facebook gleefully posted a meme about Africa. At best it callously suggested that U.S. aid to Africa is having no effect. A more critical interpretation of the intent was the racist message that Africans have always lived in grass huts and always will, that it's a basket case not worth caring about.

I'm no expert on Africa; I have never set foot on the continent (unlike a number of friends here, some from the continent itself). I know only what I learned in college four decades ago (where I studied under the brilliant Ned Munger and the equally brilliant Thayer Scudder), what I read, and what I hear from working with students, postdocs and collaborators from Egypt, Eritrea, South Africa and Senegal. But if I don't speak up, who will?

First off, of course, Africa is not just one thing. Those four countries I just named are probably at least as different as Finland, Romania, Greece and the U.K. But Africa is often roughly divided into sub-Saharan Africa and North Africa (often lumped in with the Middle Eastern Islamic countries), and the links I include below follow that division.

Africa today is a dynamic and growing place. Over the last three decades, GDP across the continent has tripled, outpacing the growth of the U.S. economy, which doubled over the same period. An increasing number of countries have reached World Bank middle income or upper middle income status; check the links at the bottom of this post.

Africa is urbanizing rapidly. Currently around 45% of the continent lives in cities. This comes with its own problems of sanitation, water, electricity, pollution, transportation and general governance; no one would pretend it's perfect. But the idea of Africans all living in huts is...well, you know.

Life expectancy is also growing rapidly in many countries. Some countries have levels that rival those of some European countries.

These metrics vary dramatically across the continent and correlate strongly with the quality of governance. This is an area where European and American countries are particularly responsible, thanks to centuries of colonial rule and suppression of local voices, and the devastation to West African societies caused by the slave trade (yes, that ended long ago, and the effects persist today). Colonialism has only ended within our lifetimes. The colonies were set up by Europeans without regard to existing cultural, political and economic structures, and some African countries that were amalgams of various cultures were left unprepared to deal with the issues of governance.

Africa is full of ambitious, smart, creative, hardworking people. To get a glimpse, check out the CNN programs Inside Africa and African Voices Changemakers. (I wish CNN had programs as good on Asia!)

How much of all of this progress is due to U.S. foreign aid, I can't say. But PEPFAR alone has saved the lives of millions of Africans, and work done by NGOs on topics such as guinea worm eradication have improved quality of life for all.

We should all celebrate when any country or region grows and improves on these metrics, and worry and offer a hand when they don't.

We are all in this together. If you don't know how to care about other human beings, I don't know how to explain it to you.

https://data.worldbank.org/indicator/NY.GDP.MKTP.CD...

https://www.worldbank.org/en/country/mic/overview

Research is Winning the War Against Cancer

 Do I have any friends whose lives have not been touched by cancer?

If your life has been touched by cancer -- your own, a family member's, a friend's -- then you are probably aware of how difficult a disease it is, but you may or may not know this:

"The country’s cancer death rate has declined 33 percent since 1991, thanks largely to cancer research that has led to new treatments, gains in early cancer detection and, most significantly, a sharp decline in tobacco use, according to a new American Cancer Society (ACS) report."

In addition, five-year survival rates for many types of cancer have improved, and the treatments themselves have fewer side effects.

The research that leads to these improvements is a global effort, but the biggest funder of research (across all fields, from astronomy to zoology) in the world is the United States National Institutes of Health.

This kind of work takes DECADES. It is not work that can be started and stopped on the whims of individuals; an unplanned-for pause can literally destroy decades of work. It takes dedicated researchers, clinicians, and hospital staff; drug development science and chemical engineering; complicated distribution and testing systems; work to understand and mitigate tradeoffs in the effects on the body, work to sort out differences in effectiveness for people with different body types, current health and genetic backgrounds; and above all a system that is built to create AND SUSTAIN the workforce we need, including universities.

When we work for the common good, without thought of profit or politics, the U.S. makes the world a better place.

https://www.cancercenter.com/community/blog/2023/01/cancer-survival-rates-are-improving

Spelunking CACM, Vol. 22 (1979): Cheriton and Denning

 Maybe it's just me, but after the huge set of world-changing things in 1978's CACM, it seems like not so much in 1979. Also, in minor grumbles, I didn't find a picture I liked in either of the papers I decided to cover.

One that inevitably caught my eye because of the first author is David Cheriton's Thoth. It's a complete, though fairly simple, OS, designed and built with the goal of being portable across machine architectures. It includes (and depends on) a compiler for a custom language. The language is apparently named "Eh", but they refer to it as "the base language" throughout the paper. It's a descendant of B & BCPL, which should put it closer to C than not, but the syntax is actually rather different. It assumes that integer pointers are themselves consecutive integers; the language doesn't support the notion of a byte pointer, because at least one of the machines they wanted to target didn't support byte pointers.

The file system is a tree that supports UNIX-like mount points, cleverly called "grafts", but otherwise the file naming seems like something from a parallel universe, when viewed from 2025. Among other things, the root of the FS is called "*", so "*/src" refers to what in UNIX terms would be "/src".

There is a function for creating a "process", but its first argument is a pointer to a function. Their "processes" are actually closer to modern threads, and share an address space. The OS includes support for multiple address spaces; the set of "processes" in one address space is a "team". Support for multiple teams can be compiled in or out, assuming the hardware has an MMU and virtual memory.

There is no support for multiprocessors, though they claim and I believe that it wouldn't be too hard in the OS itself. A process runs until it blocks, so multitasking is cooperative.

They achieved the goal of portability of software and the OS; Thoth ran on both the Data General Nova 2 (released in 1973, already not a new machine by the time of this paper) and the TI 990/10, both 16-bit machines, and so Thoth was designed around those limitations despite the goal of portability. I think it's arguable whether the system would meet the goal of portability to a later architecture; I would say it was focused on that pair of specific systems rather than truly working toward a system with open-ended future portability.

Overall, maybe not so much to write home about, though Cheriton's later work on V is claimed to be a "successor" to Thoth, and is of huge importance in the history of distributed systems.

Of note for similar reasons is Dorothy Denning's proposal for a hardware gadget that does RSA encryption and allows a PC to encrypt data it sends to a centralized file server (CF), as well as to securely exchange files with another PC via the CF. Some of the functions appear to be transparent to the PC, others don't. Ultimately using RSA as the only encryption mechanism is computationally intensive, although at the time, according to Denning, Rivest himself claimed there would soon be high-performance hardware implementations.

There were a few other things here in there in 1979, but nothing that really compels me to talk about. As always, of course, my primary strength is the systems work; I can't comment as fluidly or recognize the importance as clearly when dealing with algorithms and theory.

(On a personal note, I think 1979 was the year I got my TRS-80 Model 1, using a Zilog Z80 16-bit CPU. A simple and interesting machine.)

Happy New Year!

 

Sunset over fishing boats, Zaimokuza, Kamakura, Dec. 29, 2024

First, goodbye to 2024. What an amazing year globally in quantum! More to say about that in a future posting (or editorial for TQE). It was also a great year for AQUA. Highlights were going seven-for-seven for QCE2024 papers (well, 5 directly from AQUA and 2 led by collaborators) and Q-Fly. I also managed to visit the (European) Alps twice and southern Thailand once, for conferences.

I also did a thing or two for my soul; the most important was a nine-day road trip with my wife through western Honshu. Longest two-person vacation since our first kid was born more than a quarter-century ago.

However, I don't think I saw any live music, opera, theater or performing arts last year, except for an hour of Irish music in a pub in Dublin. That needs to be corrected in 2025!

I think I read thirty books this year, which is my goal each year, a very achievable number. (How many books you read doesn't really matter; there's no way to read any detectable fraction of the good books published in a year. Just read and enjoy.) In 2023, Kettle Bottom and Demon Copperhead (both coincidentally set in Appalachia) hit me hard.  But I don't think any of this year's readings will leave a mark on my soul.

Im movies, "Past Lives", "Perfect Days" and "Dune Part 2" are very different films, and each will stay with me for a long time. The first two were officially released in 2023, but I think I saw them both in 2024. "Past Lives" is about the ache for the paths not taken, while still acknowledging that the path taken is who we are. I sobbed all the way through it. "Perfect Days" likewise is about the choices we make and the life we make for ourselves. "Dune" is, well, Dune.

And of course we can't ignore the cataclysmic event of November 5. It's incumbent on us all to do what we can to help keep the world together.

On to 2025. Hoping I can find (well, make myself find) better work/life balance, while achieving the things I want. Let's roll!