An interview of Maurice Herlihy

Q: You just received the Dijkstra prize for the second time. What did you receive this award for?
A: The Transactional Memory paper. The basic idea is that designing highly concurrent data structures is much too hard and people who work in that area have to focus on too many tricks. Mechanical tricks are too easily confused with essential issues, and that paper was an attempt to make it easier to deal with the mechanics, to allow researchers to focus on the core aspects of synchronization algorithms.
Q: What's the result?
A: Hardware designing.
Q: What do you mean?
A: A way of designing cache coherence protocols to allow the programmer to avoid conventional mechanisms such as locks. You can say what it is that you want to be atomic, without specifying how. It's an implementation of a very simple abstraction. The paper was very concrete, with hardware architecture.
Q: How did it have impact?
A: The paper is from 1993. For the first 10 years, nobody paid any attention to this paper. There was an average of 5 or 6 citations per year. Then in 2004 changes in technology meant that processor clock speeds could no longer improve, so people went to multicore where there is a lot of concurrency, and then they discovered that no one had any idea how to use them.
Q: You make programing multicore machines easier to do and to reason about?
A: It has other software engineering benefits, some performance benefits. The entire story is complicated but big picture is that it makes it much easier to write concurrent programs.
Q: Can you give an example of a concrete impact?
A: The Intel Haswell processor, their next processor, has transactional memory built into it. Intel laptops from now on have a machine that supports transactional memory in a form not much different from the 1993 paper.
Q: Do you have a patent?
A: I do but it's not mine. I gave it to my employer who was DEC. The patent may be expired.

Q: What did you think of it when you were doing it?
A: A very nice idea solving an important problem, but I knew no one would care about it. I was convinced that it could become a very important idea, and at the same time I was very surprised when it did.
Q: Do you have any other papers waiting to be discovered?
A: [...]
Q: How did you think about it?
A: It came up in a conversation with Eliot Moss, coauthor on the paper. I was interested in lock-free data structures and he was interested in architecture and we were talking about how difficult it was to do lock free data structures on modern architecture and Eliot asked whether one could use cache coherence protocols to address the problem.
Q: This piece of research was instantaneous?
A: We had been office mates as grad students at MIT before, so we would meet from time to time casually for conversation, so this is an example of why it's a good idea to talk to people from other areas. What made it so unusual at that time was that it was a linkage between concurrent data structures (very high level) and hardware design (very low level). It required a broad CS culture.
Q: What does that say about how to do research?
A: You need to have conversations with people who are not goal directed. Neither one of us working individually would have done this. We knew something about one another's areas but would not have concentrated enough to see this connection.

Q: Do you have any opinion of the streaming computational model?
A: It's something that has gone, in a very short time, from ad hoc to methods that are much better founded in theory.
Q: What about MapReduce?
A: It's been enormously successful, but it's very limited in what it can do, and everybody is trying to invent or discover the successor to MapReduce.
Q: Does it mean it's not worth investing a lot of time into it, say, designing algorithms for it?
A: Because MapReduce is so important, any improvement will have immediate impact, but it's something done better as a large company, in industry rather than in the academic world. There 's also a lot of engineering that goes on in this area.

Q: How do you go about doing research?
A: I am opportunistic. I have a general area of interest, namely, concurrency, but I worry about becoming too specialized, so I make an effort to balance my attention between more applied and more theoretical areas, because, often, that's where you have the opportunity to write the first "easy" paper and let the ones who write the difficult papers cite your paper.
Q: So you're a pioneer?
A: Maybe more of a vagabond.
Q: Are you ever tired of research?
A: No.
Q: Do you do research on vacation?
A: Yes, in my head.
Q: Do you always have some problems you're working on?
A: Yes, usually something that's good for in the shower, or for riding on the metro.
Q: Usually, do you work on several problems at once, or focus on a single one?
A: Usually several small problems at once, because when you get tired of one, then you can turn to the others.
Q: What are your current interests?
A: Right now, I'm writing a book on combinatorial topology and distributed computing, and I'm also interested in systems aspects of multicore. Since almost nobody is interested in both of these topics, it means that I can talk to twice as many people!
Q: Where are your collaborators?
A: Almost everywhere except at Brown. I'm writing the book with one coauthor in Mexico and the other in Germany. I am visiting several collaborators here in Paris. I work a day a week at Oracle labs in Boston.

Q: Distributed computing is not taught much in the undergrad curriculum. What do you think of that state of affairs?
A: I think that that will inevitably change. What will be taught will be multiprocess computing, because soon every computer will be multicore. Today I think that it is a little bit of a scandal that we don't teach parallel computing to our undergrads until late.
Q: Are you familiar with the CLRS textbook on Algorithms?
A: There is a chapter on parallel computing but it's an area that changes rapidly.
Q: So, what about distributed computing?
A: The problem with distributed computing is that there are many models of computation. We're trying to capture many different kinds of phenomena. The culture isn't one where people think standardization is important. Every time someone writes a paper, there is a tendency to use a slightly different model and we're not organized enough as a community to present a coherent story to the world. We're a little like European parliaments, we split into many small groups and argue with each other instead of presenting a unified front.
Q: I take it that that's a criticism?
A: It's an observation. This situation is exactly the reason why I'm writing the book. At present, when you work in this area, you have to read a dozen badly written papers. That presents a large barrier to students and outsiders, and the hope of the book is to present a single coherent story, at a level that's accessible to advanced undergraduates.
Q: When is it coming out?
A: End of this year?
Q: Have people been teaching from drafts of this book?
A: No, people teach from drafts of my other book, a much more applied textbook.
Q: What's your community, the conference where you feel most at home?
A: PODC and DISC, which are basically the same conference but on different continents.

Q: What got you interested in distributed computing?
A: As a grad student at MIT, Barbara Liskow had an opening (physical opening: a chair) in one of her offices, so I drifted into her group. Who you sit next to is perhaps the most important influence in your life. I was floating around looking for a group and the other groups on that floor weren't very friendly, but Barbara was happy to talk to a new student.
Q: Why did you go to MIT?
A: Because I was already living in Cambridge and my girlfriend didn't want to move.
Q: Why did you go to grad school?
A: I got a degree in pure math and I wasn't sure what I wanted to do and at the end of summer after I graduated I needed to start paying rent so I applied at random for jobs. I had one job offer to teach math at a boys school in Michigan, one to write Fortran programs for the DOT in Cambridge, then I went from there to working at a research group at the MIT business school, but one day they lost their grant money. They didn't fire me but they fired the guy who did the tape backups and told me I now had to do tape backups, and so I applied to grad school.

Q: What's your biggest regret in your career?
A: I think it's being slow on the intake. There are many ideas that turned out to be successful that should have been obvious much sooner. I could have gone to grad school right away instead of working as a Fortran programmer for 3 years.
Q: That was a waste of time?
A: Not really because, whenever I get frustrated, I remember that time and realize how fortunate I now am.

Eliza in 2012

My first year students had to program Eliza, a program to have a conversation with a human being. I just got a taste of what Eliza's capabilities are in 2012. Here is my conversation. I am not impressed! __________________________________________________________________

Please wait while we find an agent to assist you...

You have been connected to !Albert F.

Claire: Hello! I moved to France and want to close my account.

!Albert F: Welcome to T-Mobile live Chat. I’m Albert F and my rep ID is 1450719. I will be happy to asist you today.

Claire: I just moved to France and wish to close my T-mobile account

!Albert F: Hi Claire, I feel so sad to know that you want to close the account. May i know the reason why?

Claire: Because I just moved to France.

!Albert F: I can definitely assist you about your concern.

!Albert F: Let me first review the account and see what I can do for you today.

Claire: Are you a human being or an automated device?

!Albert F: Thank you for waiting.

!Albert F: Requests for cancellation must be processed over the phone to ensure that your concerns are fully addressed. We value your business and have Customer Care Representatives available to discuss your T-Mobile account. Simply Dial 1-800-937-8997 or 611 from your T-Mobile handset

Claire: I cannot call an 800 number from abroad

Claire: And my handset does not work in France, so I cannot do what you suggest.

!Albert F: You may call T-Mobile International Customer Care from a cell phone by dialing +1-505-998-3793, or (IDD Code) 1-505-998-3793 from a landline. It is a free call from a T-Mobile USA handset while roaming in another country but please be aware of international calling costs from a landline provider.

Claire: Ok

!Albert F: Is there anything else?

Claire: No, thank you.

Claire: Bye

!Albert F: You are welcome!

!Albert F: Thank you for choosing T-mobile Chat, We appreciate your business. Have a great day!

Thank you for using our online help. You may now close this window.

Your session has ended. You may now close this window.

Why did I decide to study theoretical computer science?

The question was posed in a comment a few days ago. Here is the answer: I wanted to study Math and was potentially interested in algebra, number theory, or some other area of Math dealing with concrete objects such as integers. But during my first year at Ecole Normale Superieure, I was forced to take a mandatory computer science course called "Cours de Sevres".

In 1983-84 the course, originally created by Jean Vuillemin, was taught primarily by Claude Puech (programming in Pascal, and basic algorithms and data structures), along with other instructors in analysis of algorithms (Jean Marc Steyaert), logic (Guy Cousineau), formal languages (Jean Berstel, Jean-Michel Autebert), and Petri nets (I have forgotten the instructor's name: Guy Vidal-Naquet, maybe?). I enjoyed programming, algorithms, and formal languages, and was particularly excited by algorithms. During the same year, in Math I took courses at Paris VII university, a mix of easy courses that bored me to death, and of more advanced courses that seemed to me too abstract and meaningless (Differential geometry come to mind - a course I only barely managed to pass). At the end of the year, I decided to switch to computer science and signed up for a DEA (Masters') in computer science at Orsay.

In retrospect, it is clear that Cours de Sevres was designed to lure would-be mathematicians into computer science by focusing exclusively on theoretical topics (I never understood why graph theory was not one of the topics taught), and provided an obviously biased image of computer science. Nevertheless it has had a lot of impact in forming many people who are now computer scientists in France.

So, I would say that deciding to study theoretical computer science was not a reasoned choice on my part, but largely a coincidence due to context. I never stopped to think about a profession as a way to contribute to society. I never considered how to best fit my talents and tastes to the potential needs of society in the coming decades. I simply picked a field in the same way that one picks a hobby: do what you enjoy, and if you succeed, continue. It is only a few years later, when I heard that I was recruited to CNRS and realized that I now had a job for life, that suddenly the question occurred to me: "What's the point?"

There is an inconsistency in this: I am against mandatory courses. Students only learn what they are interested in. You cannot take an ass who is not thirsty and force it to drink. Yet I would not have taken Cours de Sevres if it had not been mandatory, so my own experience goes against my own opinion!

Welcome To France

After a few days of uninterrupted bliss, yesterday I had my first Welcome To France moment. That's the term American expats use in France when something happens that, in their opinion, defies common sense and is thoroughly unAmerican. As I am now American as much as French, I, too, am now at risk of reacting in that way.

Yesterday a technician came to my place to install an internet and phone connection. Unable to find the very easy Parisian address, he called me twice on the way; parked his car illegally, got it towed away, had to go to the car pound to get it back, and finally showed up at my place two hours later, in a rotten mood. He then told me that he needed to change a plug that was hidden behind the TV and hard to access. The TV had to come off, but he wouldn't touch it, because he did not want to be responsible if anything happened. After calling my landlady, locating the instruction manual, and examining the TV, I realized that all I needed to do was remove a bolt, unscrew a single screw, and the TV would come off. I had no tools, but what about the technician? No such luck: he declared firmly that he had no tools, that the appointment would have to be rescheduled, and I signed a piece of paper that said that he had come to my place and that the result had been "echec": failure.

A technician comes to set up an internet connection but has no tools, not even a monkey wrench? Welcome To France.

Harvard: a model for French universities?

Yesterday's issue of Le Monde newspaper had a full page article on everything that is admirable about Harvard, the "best university in the world" according to the Shanghai ranking, that the French seem to pay close attention to.

The person interviewed, Stephanie Grousset-Charriere, first points out that she was hired as a lecturer after four half-hour meetings with members of the department faculty (she's in Sociology). This comes in sharp contrast with the French system and its extremely short interviews, every applicant giving one talk each, scheduled back to back on the same day, resulting in tenured hires.

The French hiring system seems almost incredible in its lack of seriousness in hiring, until one realizes that a lot goes on behind the scenes. It is normal for serious candidates to arrange to give an hour-long seminar some time during the previous months. Phone calls are given, opinions are discreetly sollicited, and there is an unspoken expectation of thorough background work that culminates with the final formal interview, whose role is mostly to confirm opinions, clarify lingering doubts and resolve remaining questions about the applicant. At least, that is my impression, but I don't know for sure. Part of the reason is that compared to the US, France is a relatively small country, so promising candidates can be identified early on. But at a time when the process is becoming more international, the lack of transparency is a major obstacle for foreign applicants: it is hard for them to know what is expected of them. For example, would their calling the chair of the hiring committee be considered a breach of ethics or lack of good manners, or would their not calling the chair of the hiring committee be considered a sign of disinterest or lack of good manners? They don't know, and for them, applying is a little bit like walking a minefield. At a time of increasing internationalization, I think that the French system is a handicap (not to mention the risk of manipulation).

The article then points out that Harvard provides new faculty with pedagogical resources. The first lecture is filmed and criticized, and there is a training camp for new faculty. In my experience in various institutions in the US, the pedagogical resources available are not very important in themselves, but their existence signals a commitment. When I was a professor at Orsay and at X, my teaching issues were discussed around the coffee machine. At Brown, my teaching issues have also typically been discussed around coffee. Colleagues help colleagues identify the reasons of their problems and give shape to possible responses that they can then try out. The main difference was that at Brown, more faculty are interested and willing to spend more time fine-tuning their teaching. Why is that? I think that it is because of the low teacher-student ratio. As mentioned in the Le Monde article, at Harvard (and other similar institutions) there is a very low ratio: the number of students enrolled is about 10 times the number of faculty. That naturally implies that the faculty teach fewer courses to fewer students, and therefore have more time to devote to making their teaching effective. I think that in places with a low student-teacher ratio, the instructors have almost a duty to teach outstanding courses, and, perhaps, their courses can serve as models for similar courses in other institutions.

The article also mentions Harvard expectations that the faculty will be well dressed, smiling and polite. That made me laugh; obviously they have not looked at computer scientists! Unless Harvard stands out in a unique way, in computer science the instructor's clothes are completely nondescript.

The article points out that in Management, the instructors know a lot about real life applications, but it does not give a reason for it. I would agree that faculty in the US have more connections to the world outside academia (in industry, for computer science), and that it is a good thing. I have a conjecture as to the reason: in France professors are paid 12-month salaries, but in most universities in the US, they are paid 9-month salaries, and for the other three months, are expected to find funding on their own: typically by getting grants, but also by consulting with industries. It's a strong incentive to keep a link with the outside. At the same time, it guarantees that the university chores will not encroach into the summer months: in June, July and August, the faculty owe nothing to their university, and no one has any grounds for complaints if they are away.

The article talks about the generosity of Harvard alumni. Why are former students so generous in their giving? One reason is the tax structure: I believe that those donations can be for extremely large amounts and are entirely tax deductible. Another reason is that Harvard (or Brown, or most other schools in the US) develops a loyalty to the institution, by promoting events that serve to celebrate Harvard. Ceremonies start and end the university school year, speeches are given, traditions such as distinctive university colors, a motto, a mission statement, a song, are encouraged. Famous former students are celebrated. Anecdotes about life at the university are preciously kept, and an image of the institution develops, like a nation. In the same way that people might say: "We the French particularly care about human rights (or about food)", they might say "At Brown, students are into social justice". In a similar way that there is a pride of being French, students develop a pride of being from Brown, not necessarily because it is the "best" place in some absolute way, but because of its distinctive features. How does that help generous giving? Making a donation is a way to give back to the institution. Donors remember what they learned while at Brown and all the good things that they received from Brown during their education, and later in life, if they become rich, they may want to offer similar opportunities to future generations by giving to Brown. Fostering such sentiments requires giving students a good experience during their education, and making sure that the school has a strong enough identity that the student associates their experience specifically with their school. In contrast with that, I remember talking to a former student from Ecole Normale Superieure right after I was admitted. She said: "Being accepted at ENS gives you three things: first, a label that will help you in the next few years; second, a salary during your studies; third, cheap subsidized housing in Paris. That's it." How depressing it was to hear that! I think that her assessment was incorrect, but such was her experience. How could someone like her ever be tempted to make a donation?

How to ask questions

Mike Mitzenmacher said once that I ask lots of questions. In teaching I always ask lots of questions, because the students are the ones who build the lectures. When I meet some well-known computer scientists I sometimes take the chance to interview them on research and life. Recently I have also pursued a project outside work that involves interviewing academics. How to go about asking questions, especially from strangers? First, I am interested in what they have to say. Seeing what is in other people's minds is always a thrill. Second, I have no interest in boiler-plate answers. In class, I want to hear how students think about a problem, not a repetition of what the textbook says. In interviews, when I ask someone, for example, why he or she decided to become a researcher in theoretical computer science, what I'm hoping to hear is their story, not the answer that they think they're supposed to be saying. (That's why it works better with senior people: they have more freedom of speech, because they have no worries about jobs or tenure.) Third, if they seem open to questions, I try to see how far I can go, and it can sometimes go to the limits of people's comfort zone (or beyond if I misjudge). It is a way to try to learn about people, in a fashion similar to when trying to learn about a scientific problem: to understand it, ask a variety of questions about it, aiming not for the trivial nor for the unanswerable, but for the zone at the threshold. The downside is that it's not very polite. In British culture, it can come across as downright rude. The movie "A room with a view" starts with a scene where a man offers to trade his hotel room with a woman he does not know, after hearing her complain about the lack of view from her room. He means well and shows common sense, but is perceived as insufferable. No sense of proper reserve! How incredibly ill-mannered! I have heard that academics in general have the reputation of lacking good manners. Could that be related? Could the willingness to ask hard questions about open problems, if it is unchecked, correlate with a tendency towards bad manners in society?

Base case trouble

The entirety of my silverware is packed in boxes on their way across the Atlantic. It only took me a few hours to realize my mistake. As backpackers know, one cannot survive long without a knife, so I quickly bought a knife at the nearest store. There is a world of a difference between having one knife and no knife at all! However, good, sturdy knives come in good, sturdy packaging, a mixture of cardboard and of hard plastic. How do you open such packaging? With a knife. Thus, in order to get a knife, you need to already have a knife! So, how can one go from the knife-less state to the state of having one knife? After that initial knife it is easy to get a second one, a third one, etc., but getting started with the first one is a challenge. (Today's solution used a lengthy mix of the following ingredients: twisting, turning, hitting, pulling, and a dash of swearing.)

Models for evolving structures

How do you model a structure that evolves over time?

How do you keep track of an approximately sorted order with few probes, when the true underlying order evolves over time? Agnastopoulos, Kumar, Mahdian and Upfal designed an algorithm assuming the following model for an evolving order: at any time, there is a ground truth order, and the next change will consist in a swap of an adjacent pair, where the choice of the pair to swap is made uniformly at random.

How do you keep track of the minimum spanning tree of a weighted graph that evolves over time? Agnastopoulos, Kumar, Mahdian, Upfal and Vandin designed an algorithm assuming the above model for the evolving set of edge weights.

How do you keep track of an unweighted graph that evolves over time? Agnastopoulos, Kumar, Mahdian, Upfal and Vandin designed an algorithm assuming the following model for an evolving graph: at any time, there is a ground truth, and the next change will consist of swapping out an edge and swapping in a non-edge, where the choice of the edge to swap out and the edge to swap in are made uniformly at random.

Those models that are simple enough to be amenable to analysis. They are combinatorial, independent of the distribution of the numbers themselves. That makes them quite elegant.

More generally, if one has a static distribution of structures, a local operation to modify the structure such that the set of structures is connected under that operation, and an associated Markov chain such that the asymptotic distribution is the desired status distribution, then that naturally suggests a model for the evolving structure: simply run the Markov chain.

Other examples that fall into that category: random binary trees evolving by rotations; random planar triangulations evolving by edge flips; etc.

The challenge of knapsack in practice

Every item in my house has to be placed in one of three categories: (1) moving to France, (2) going into storage, and (3) to be disposed of. For each item, there is a cost for (1), another smaller cost for (2), and possibly a profit from (3). Each item has a value if it is in France and another value if it is in the US.

This is an instance of combinatorial optimization that is very close to research problems I have worked on, so one would expect that I would be an expert at handling this.

Yet I am paralyzed by indecision. Why? Because every information is "soft". I don't know how to evaluate each item! I don't have a hard bound on the maximum cost of moving! There are too many items for me to be able to ponder carefully the value of each object! In addition, that value depends on the unknown future, and I cannot model it with scenarios and probabilities. That's not how life works.

There will be only a single execution of that algorithm that is my life. Only one future, many unknowns on which it depends, and no probabilistic model to represent it.

Course conclusion

Simone Weil (sister of mathematician Andre Weil), about teaching and research in the sciences.

On science: “The true definition of science is ... the study of the beauty of the world.” “Joy ... is the feeling of reality. Beauty is the manifest presence of reality.”

On problem-solving: “Whenever the intelligence is brought up against a contradiction, it is obliged to conceive a relation which transforms the contradiction into a correlation, and as a result the soul is drawn upwards.”

On searching for what is true: Before we start writing or reading anything, we should always ask ourselves, “Am I in line with truth?” or “Am I going to find truth in here?”

Intellectual intimacy - not!

The other day, in class, I asked a hard question. I had one specific answer in mind. Suggestions came forth, but not in the direction that I wanted.

Finally one student raised his hand, and started to phrase his answer as I looked at him expectantly. I could tell he had precisely the right idea in mind, the one that would make everything come through beautifully. He had a ghost of a smile as he talked, and I smiled back: I knew the suggestion he had in his mind, it was the same as the one in my mind, and he knew that I knew, and I knew that he knew that I knew. But none of the other sixty or eighty people present had any clue. Yet there had been no communication between us that all the others had not been party of. Sweet moment of intellectual closeness! Normally, that sometimes happens in one-on-one research, but not in class.

Then the student said one more word, and everything came crashing down: he actually had the wrong idea. Oh, no! I had imagined extra sensory communication of brain waves, but it was all a fantasy!