<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Hydra: distributed computing conference on Medium]]></title>
        <description><![CDATA[Stories by Hydra: distributed computing conference on Medium]]></description>
        <link>https://medium.com/@hydraconference?source=rss-8f40aa214273------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*fpEV6rEhWJWx4s1E.png</url>
            <title>Stories by Hydra: distributed computing conference on Medium</title>
            <link>https://medium.com/@hydraconference?source=rss-8f40aa214273------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 13:46:56 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@hydraconference/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Big Interview with Michael Scott — research career, global trends in programming and mathematics…]]></title>
            <link>https://medium.com/@hydraconference/big-interview-with-michael-scott-research-career-global-trends-in-programming-and-mathematics-2dda5cc7d244?source=rss-8f40aa214273------2</link>
            <guid isPermaLink="false">https://medium.com/p/2dda5cc7d244</guid>
            <category><![CDATA[michael-scott]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[distributed-computing]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[conferences-2019]]></category>
            <dc:creator><![CDATA[Hydra: distributed computing conference]]></dc:creator>
            <pubDate>Tue, 02 Jun 2020 11:09:29 GMT</pubDate>
            <atom:updated>2020-06-02T11:09:29.322Z</atom:updated>
            <content:encoded><![CDATA[<h3>Big Interview with Michael Scott — research career, global trends in programming and mathematics, the connection between business and academia (part 2)</h3><p>Michael Scott has been teaching Computer Science at the University of Rochester for more than thirty years. Previously, he was a graduate student at the University of Wisconsin — Madison. Prof. Scott’s research mainly addresses parallel and distributed programming, as well as language design, which he also teaches to his students.</p><p>Michael is widely known for his textbook, <em>Programming Language Pragmatics</em>, which has become a leading text in programming language design and implementation.</p><p>Michael’s research paper, “<a href="https://bit.ly/2NJOlrn">Algorithms for scalable synchronization on shared-memory multiprocessors</a>,” co-authored by John Mellor-Crummey, received the Edsger W. Dijkstra Prize in Distributed Computing. You may also know Michael as a co-creator of the widely used Michael &amp; Scott concurrent queue algorithm.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2qi7Vn5UdSxvn0YovEsVWg.png" /></figure><p>Together with his student Bill Scherer and with Prof. Doug Leа of the State University of New York at Oswego, Prof. Scott developed several of the non-blocking algorithms in the Java standard library. The introduction of dual data structures in JavaSE 5, in particular, allowed a 10-fold improvement in the performance of ThreadPoolExecutor.</p><p>Last year, Michael Scott visited the Hydra conference in St. Petersburg and gave a talk about <a href="https://www.youtube.com/watch?v=nz6fASCVmT8&amp;list=PLC5OGTO4dWxYuuASJMj1xePLQjNg05HzT&amp;index=16&amp;t=0s">dual data structures</a>. In the interview that follows, Michael spoke of his research career, global trends in programming and mathematics, the connection between business and academia, and other related topics.</p><p>The interview is quite big, that is why we separated it into two parts. You can <a href="https://medium.com/@hydraconference/big-interview-with-michael-scott-research-career-global-trends-in-programming-and-mathematics-488317b8d022">read the first part elsewhere</a>. In this part, you will find Michael Scott’s opinion about the connection between business and academia, among other issues in the field.</p><h3>The interview was conducted by:</h3><p><strong>Vitaly Aksenov, </strong>currently a postdoc at IST Austria and an employee of the Department of Computer Science at ITMO University. Vitaly’s research addresses theory and practice in the field of concurrent data structures. Before joining IST, he earned his Ph.D. at Paris Diderot University and ITMO under the supervision of Prof. Peter Kuznetsov.</p><p><strong>Alexey Fedorov,</strong> a producer at JUG Ru Group, a Russian company that organizes conferences for developers. Overall, he has helped to organize more than fifty events. Prior to co-founding JUG Ru Group, Alexey worked in various roles starting from a software engineer at Oracle (JCK, Java Platform Group) and ending with the position of a Dev Rel consultant at Odnoklassniki.</p><p><strong>Vladimir Sitnikov,</strong> an engineer at Netcracker. For the last ten years, he has been working on the performance and scalability of NetCracker OS, the software used by telecom operators to automate network and network equipment management processes. His professional interests revolve around Java and Oracle Database performance issues. Vladimir is the author of more than a dozen performance improvements for the official PostgreSQL JDBC driver.</p><h3>The connection between business and academia</h3><p><strong>Vitaliy: I have a question about the relationship between academia and business. I saw some of your papers on cache coherence. My guess was that cache coherence algorithms were not stable or widespread. Do you think your ideas could be easily implemented practically?</strong></p><p>Michael: I’m not sure which paper specifically you were looking at. I did a fair amount of work with my students, <a href="https://dblp.uni-trier.de/pers/hd/b/Bolosky:William_J=">Bill Boloski</a> and <a href="https://dblp.org/pers/hd/k/Kontothanassis:Leonidas_I=">Leonidas Kontothanassis</a>, back in the early 1990s on memory management for NUMA machines. At that time, the industry was still figuring out what was the right way to build a multiprocessor, and if there would be any hardware support for accessing remote memory, or if the memory would even be distributed, or if it would be a sort of dance-hall architecture. Questions like, could you do cache fills from remote memory, or did you have to move pages in the operating system, were fairly common because we didn’t know what was the right way to build the machines. Bill and Leonidas both worked in that area and explored designs that did not have remote cache fills. So that wasn’t exactly cache coherence work, but it was work on NUMA memory management that has over the years evolved into the strategies that modern operating systems use for page placement. I think that work has had some influence, although it’s certainly not the seminal work in the area. It was part of the work being done by a lot of people at that time. More recently, I’ve done work that touched on cache coherence in the context of hardware transactional memory. We have a couple of patents in that area that come from the group at Rochester and are jointly invented with me and some other people. I don’t necessarily expect that they’ll get picked up by industry. I think they’re really interesting, they’re really cool, but I’m not in the best position to evaluate whether they’re commercially viable or not.</p><p><strong>Alexey: Now, then, more personal question: Is it important for you that your ideas are implemented in real life?</strong></p><p>Michael: This is one of my favorite interview questions to ask other people when I’m talking to prospective graduate students or faculty members. I don’t think there’s a right answer. I think people can do really cool work for lots of different reasons. Personally, I’m motivated more by the desire to build something that I think is cool than I am by the desire to see if it’s used in the world. But when it <em>is</em> used in the world — I really like that! So, it’s kind of a mix. It’s not the end-use in the real world that motivates me in the beginning. What motivates me, in the beginning, is — this is an idea that strikes me as unusually elegant, and I want to explore it and see where it goes. If it turns out to be practical — that’s really cool.</p><p><strong>Alexey: Your background allows you to make estimates about the viability of someone else’s ideas. I’m sure that you have your personal opinion on what’s better or what technologies should be used. For example, Intel or any other large corporation, do you have an opinion on the course the company undertook and if it’s right?</strong></p><p>Michael: The real world is about building things that are commercially successful, which generally means making money. There’s a lot of people out there who are better at evaluating it than I am. In terms of publishing papers, which is mainly how my work gets out, papers in systems get published based largely on performance results. You want to know if something is faster, does it use less energy, does it reduce code size — you’ve got to have some metric that you can measure. I have always had the impression that many people publish papers with the empirical results in them because that’s how they can get them published, but the reason they’re doing the work is aesthetic. They have really an artistic sense of what is elegant and what is less so, and they’re driven to produce things that are more elegant than what they’ve had before for personal, subjective, aesthetic reasons. But you can’t really put those in a paper. That’s not how you’re going to convince the program committee to publish it. Fortunately, things that are elegant also often turn out to be fast or cheap or low energy or whatever. So there’s often a happy coincidence there. There’s a group of us who had a conversation about this probably 15 years ago. It turned into a paper. So if you look for it, there’s a paper that I’m a co-author on along with about a dozen other people with the title something like <a href="https://www.usenix.org/legacy/event/hotos05/final_papers_backup/red_team/red_html/paper.html">“How to evaluate systems research”</a>. It’s the only paper I’ve co-authored with <a href="https://dl.acm.org/profile/81100440291">Sasha Fedorova</a>, so if you search for her name in my pub list, you’ll find it. That’s a paper that talks about how to evaluate systems research and the place where elegance fits and how it all matters.</p><p><strong>Alexey: I assume, there must be a difference between what the scientific community calls a good result, and what the business community or hardware industry calls a good result. Speaking of academia, I believe, what matters is performance, energy consumption, TDP, if the implementation is easy or complicated. Do you have an opportunity to do all those above-mentioned at your university? Do you have some sort of lab with different machines and architectures?</strong></p><p>Michael: Sure. Our department has a lot of different interesting machines that we work with. We’ve got a modest-sized cluster and a bunch of small multiprocessors of different kinds with different kinds of accelerators. We have access on campus to a very large computational center, which serves the needs of computational scientists who work across a couple of dozen different disciplines. It has a 1,000-node, 20,000-core cluster of Linux machines, and if we need to, we can buy more cycles at AWS or something. So access to the hardware is not really a problem for us.</p><p><strong>Alexey: What about, say, thirty years ago? Have you always had access to all the necessary resources?</strong></p><p>Michael: It has changed some. Back in the mid-to-late 1980s, there was a general sense in the US that the computational resources in academia were weak, and the National Science Foundation in the US stepped in to do something about that. They had this thing called the Coordinated Experimental Research (CER) program, which evolved into a couple of other things over the years. But it was designed to provide hardware infrastructure for CS departments, and it was really transformative at the time. At the University of Rochester, we used money from that program to buy a 128-node BBN Butterfly machine in 1984 — the year before I joined the faculty. When I came to Rochester, that was the largest shared-memory multiprocessor anywhere in the world. It was located in the department at Rochester, purchased with the National Science Foundation money. It had 128 processors, every one of them on a separate motherboard. It occupied four racks. Every one of those processors had a whole megabyte of memory. We had a whole 128 megabytes of RAM on that machine, which was just an unbelievably huge quantity at the time.</p><p><strong>Alexey: Am I right to presume that all hardware access problems in academia are solved as of now?</strong></p><p>Michael: Largely, with a couple of caveats. One is that if you’re sort of a circuit and device-level computer architect, it’s challenging to work in academia because the chip building tools are so much better in industry. If you want to build anything below 10-nm feature size in academia, it’s challenging. You can do designs and send them out and have them produced, but it’s much easier to be a researcher in that field if you’re at Intel. If you’re working on other devices, if you’re working on optical interconnects on chip, if you’re working on new solid-state memory technologies — there are things going on in the industry that we can’t really duplicate very well in academia, and so people build partnerships. I’m thinking, for instance, about the partnership that <a href="http://swanson.ucsd.edu/">Steven Swanson</a> at UCSD has built with a number of places on emerging memory technologies. That kind of partnership can’t be done everywhere, but it’s been very successful in some places. So that’s one place where the industry has a huge advantage. The other place where academia is sometimes at a disadvantage is at the very high end. If you’re looking at the most ambitious supercomputer applications, then there’s a small number of places in the world, in the US or in Japan or elsewhere — China certainly today — where there’s big iron that just isn’t available to academics.</p><h3>Practical realization of ideas. MCS, MS, CLH, JSR 166, working with Doug Lea, among other things</h3><p><strong>Vitaliy: You’ve already mentioned how you started to work on synchronization algorithms. You have two famous pieces, one on </strong><a href="https://doi.org/10.1145/103727.103729"><strong>MCS lock</strong></a><strong> and the other on </strong><a href="https://doi.org/10.1145/248052.248106"><strong>queue</strong></a><strong>, which, in some sense, were implemented in Java. The MCS lock was implemented with some modifications (like the </strong><a href="https://www.cs.rochester.edu/research/synchronization/pseudocode/ss.html"><strong>CLH lock</strong></a><strong>). The queue was directly implemented in Java. There’s a huge time difference between the publication of those papers and when the ideas were actually implemented in practice.</strong></p><p><strong>Alexey: Yeah, in the case with the queue, it took about 10 years, I think.</strong></p><p>Michael: Before it showed up in the Java Standard library.</p><p><strong>Vitaliy: What did you do for that?</strong></p><p>Michael: There’s actually a story about how the M&amp;S queue ended up in Java 5. A couple of years before it showed up I had a collaboration going with <a href="https://labs.oracle.com/pls/apex/f?p=labs:bio:0:86">Mark Moir</a> at Sun Microsystems at their lab outside of Boston. Mark organized a workshop of people he knew who were doing interesting things in concurrency because he was trying to build up his group, find interesting topics, and sell them to the company. He invited a bunch of people to that meeting, and that was the time when I first met <a href="https://en.wikipedia.org/wiki/Doug_Lea">Doug Lea</a>. Doug was at that meeting, as was I and a bunch of other people — maybe 25 of us around the table at Sun. Doug gave a presentation about the work that he was starting to do on <a href="https://jcp.org/en/jsr/detail?id=166">JSR 166</a>, the work that became java.util.concurrent. He mentioned that he was interested in using the M&amp;S queue. But one of the things that he needed in the interface was a count of elements that were in the queue. So he wanted a method that you could call to determine how much was in the queue at the moment. He was trying to determine how to make it atomic, accurate, and fast, and didn’t have a good idea about that. I said: “Well, if you just put serial numbers into the nodes, then you can just take a look at the first node and the last node and subtract, you’ll have the number.” And he replied: “Gosh, of course,” and that’s what he did. That was the point at which I realized that he was planning to put it into the library, and we did talk a little bit about how to implement it at the time. But most of the work was done by Doug. He really did an amazing job of putting solid library support for concurrency into the language.</p><p><strong>Alexey: If I understand this correctly, the size should have belonged to the standard queue interface, and its algorithmic difficulty should have been O(1)?</strong></p><p>Michael: Yes. You want to do that without maintaining a separate count.</p><p><strong>Alexey: If we call the size() method in Java, we expect to get the result immediately, regardless of the size of the collection. Ok, got it.</strong></p><p>Michael: Several years later, when my student <a href="https://www.linkedin.com/in/bill-scherer-904798154/">Bill Scherer</a> and I were working on dual data structures, which I am talking about at the <a href="https://hydraconf.com/">Hydra conference</a>, Doug approached us and said: “This looks like something we could actually use in the Executor Framework in Java.” He and Bill worked together to build the two implementations of what they called in the library fair and unfair queues — synchronous queues. I didn’t have a hand in the actual Java code that went into the library, but I consulted on that some, and it was Doug and Bill who built it. I was delighted with that because it ended up having a really significant impact on the speed of executors.</p><p><strong>Vladimir: Have you ever faced an incorrect implementation of your algorithms or subsequent bugs during their implementations or new feature requests? Suppose you wrote an algorithm, and it worked on paper, but people, who tried to implement it, found that it didn’t or there should be more features to it.</strong></p><p>Michael: I can’t think of an example in which somebody came to me and asked “how do you do this,” other than Doug’s question about .size() and the queue. But I do know several cases where there have been interesting changes made to things in order to make them more practical. For instance, the K42 group at IBM did a really nice job of converting the MCS lock so that it would have a standard interface that didn’t have to pass a queue node to the acquire and release routines. That was lovely work about making something that was nice in theory usable in practice by giving it a standard interface. They never published a paper on it — they <a href="https://patents.google.com/patent/US20030200457A1/en">applied for a patent</a> and later abandoned it. But it was such a beautiful idea! I try to go out of my way to make sure that everybody knows about that idea because it was very clever and very practical.</p><p>Several other people have done things to improve on algorithms that I’ve published. The M&amp;S queue, for instance, has this two-step install mechanism. That means you have two CASes on the critical path of an enqueue. On older machines, CASes were quite expensive. Intel and other manufacturers have done a lot to optimize them in recent years, but once upon a time, they were like a 30-cycle instruction. So it was desirable to have only one CAS on the critical path. <a href="https://www.linkedin.com/in/edya-ladan-mozes-3b24a36/">Edya Ladan-Mozes</a> and <a href="https://en.wikipedia.org/wiki/Nir_Shavit">Nir Shavit</a> did a really nice job of devising a <a href="https://doi.org/10.1007/s00446-007-0050-0">queue</a> that was similar to the M&amp;S queue but had only one atomic operation on the critical path. It did it by introducing the possibility of a timing window where the operation would take O(n) time instead of O(1) time. It was unlikely but possible in practice. Still correct: you did it by kind of “oh, the link is broken, I have to go to the other end of the queue and chase all the way back to where I am in order to figure out where I ought to be.” That was a very clever algorithm. I don’t think it’s very widely used, partly because atomic operations aren’t as expensive as they used to be. But that was a very practical idea. What else? I’m a big admirer of <a href="https://blogs.oracle.com/dave/">Dave Dice</a>’s work at Oracle. Dave has done tremendous work over the years that’s very practice-oriented, and he’s very smart about how he uses the hardware. So a lot of the best work on NUMA-aware algorithms and concurrent data structures, for instance, has got Dave’s fingers on it.</p><p><strong>Vladimir: When you develop algorithms or teach students, it takes a while before you can see the result or reap the benefits. The community needs time to get familiar with an algorithm and adopt it.</strong></p><p>Michael: It can be hard upfront to know whether a paper is going to be important or not. It would be interesting to conduct a study, where you go and look at the things that got the best paper awards at your favorite conferences over the years — where people on the program committee thought, at the time, that that was the best paper at the conference. Then look ten, twenty, twenty-five years later, and see if it’s been influential or not — how many citations it has, whether it has trickled into the industry. I don’t know how much correlation you’d see. You’d certainly see some, but maybe not as much as you might hope. Some ideas lie fallow for a long time. Look at transactional memory. It was a dozen years between the original paper and the point at which people started actually thinking about building machines that used it. Twenty years before it actually appeared in commercial products. That paper was just one of a bunch of papers for a long time, and then suddenly citations spiked. It can be hard to predict. Sometimes things pan out right away. A couple of years ago, <a href="https://www.colorado.edu/ecee/joseph-joe-izraelevitz">Joe Izraelevitz</a> and I had a <a href="https://doi.org/10.1007/978-3-662-53426-7_23">paper at DISC</a> that suggested a new formal definition of correctness for persistent data structures that were designed to survive in usable form across process and machine crashes. I thought it was a good, useful paper, but it became more popular than I had expected at the time. It’s been picked up by several different groups and seems to have become the standard definition for persistent structures — which is very gratifying. I’m glad that that’s happening; I do think that it’s a nice definition.</p><p><strong>Vladimir: Do you have a set of rules to follow when you evaluate your or your students’ papers? In the sense that whether a student you teach goes in the right direction or not.</strong></p><p>Michael: Well, like everybody, I’m focused on what I’m doing now. Like most people, I occasionally go and look at my Google Scholar citations and see how my papers are doing, which ones are moving and which ones aren’t. But that’s more out of curiosity than anything. Mostly, I’m focused on what’s being done by my students now. There’s plenty there to keep me busy. In terms of how I evaluate that work while it’s going on, I guess, partly it’s driven by that aesthetic sense of what’s elegant. Then on a very practical day-to-day basis, it’s driven by open questions. A student comes to me with a graph of the latest results, and we look at it and say: “OK, but why is there a kink in the graph here? What explains that? Why is it performing so much better than this other thing or so much worse? I don’t understand how the gap can be that large.” So it’s always chasing after things that we don’t understand.</p><h3>Transactional memory</h3><p><strong>Vitaliy: Can we talk a bit about transactional memory?</strong></p><p>Michael: I should say just a little bit about transactional memory because I’ve done a huge amount of work in that area. It’s probably the topic that I’ve published more on than any other single topic in my career. I’m in the strange position of having been a skeptic all the way through. I think that <a href="https://doi.org/10.1145/165123.165164">Herlihy and Moss’s original paper</a> on transactional memory was extremely prescient. They suggested, in the early 1990s, that this would be a useful aid for talented programmers who were writing concurrent data structures to go into libraries to be used by ordinary programmers. So it was an assist for the Doug Lea-s of the world who were building the JSR 166-s. It was not a way to make parallel programming easy. When it caught on in the early 2000s, it became that. It was all this marketing buzz about “this is the way we’re going to solve the parallel programming problem.” That always made me nervous, because there didn’t seem to be any chance that this was going to make parallel programming easy. It was going to make writing concurrent data structures easi<em>er</em>. I think it has done exactly that.</p><h3>Difficulties in writing multithreading code</h3><p><strong>Alexey: That sounds interesting. I think there is some sort of mental barrier between regular programmers and those who write concurrent code. Last year, I had an opportunity to talk to people who worked on the implementation of an algorithms framework. For example, I talked to Martin Thompson, the guy behind </strong><a href="https://lmax-exchange.github.io/disruptor/"><strong>Disruptor</strong></a><strong> and </strong><a href="https://github.com/real-logic/Aeron/wiki"><strong>Aeron</strong></a><strong> (Martin Thompson gave a </strong><a href="https://www.youtube.com/watch?v=rKMTsJxYK30"><strong>talk at Joker 2015</strong></a><strong>, where he was also a </strong><a href="https://www.youtube.com/watch?v=0NcLpRMAc7U"><strong>keynote</strong></a><strong> speaker), as well as other developers who worked on a few concurrent libraries. They told me that the main challenge for them was to make algorithms both fast and easy to use. So their main goal, as they said, was to break that barrier and get more people into the field. What do you think about this?</strong></p><p>Michael: This is the biggest open problem in parallel systems: how to get performance without complexity.</p><p><strong>Alexey: When they try to avoid complexity, the algorithms and approaches become less universal.</strong></p><p>Michael: It’s very much about good abstraction design. Which is, in my opinion, the heart of computer systems as a field. This is a term that <a href="https://en.wikipedia.org/wiki/Butler_Lampson">Butler Lampson</a> used. Lampson describes systems of people as “abstraction merchants.” It’s not like anything today is really simple. I mean, we build processors with ten billion transistors today — they aren’t simple. They aren’t anything close to simple. But the ISA is much simpler than the processor is. Because it’s an abstraction that we’ve carefully crafted over time to allow high performance with a comparatively simple interface. We still struggle to get that abstraction right. We’re facing the exact same challenge with all the accelerators coming onto the market. What is the right interface to a GPU or an encryption engine or a media transcoding engine or a linear algebra engine or even a more flexible FPGA? How do we design an interface that makes this thing usable and hides the complexity underneath? Not eliminates it, just hides it from the day-to-day programmer?</p><p><strong>Alexey: Now, I think that we also have a barrier to the understanding of abstractions. Take the memory model, for example, which is the main abstraction at this time in the development of engineering and science. Because of that exact abstraction, we can divide all programmers into two separate groups: those who don’t understand the model and those who do.</strong></p><p>Michael: Yes, it’s a good question whether any of us really understands memory models.</p><p><strong>Vitaliy: Especially for C++.</strong></p><p>Michael: Talk to <a href="https://hboehm.info/">Hans Boehm</a> some time. Hans is one of the smartest people I know and is one of the two or three leading people in the world on memory models, and he will immediately tell you that there are lots of things that he doesn’t understand about memory models. That said, I think — coming back to the notion of abstractions — the most important idea in memory models over the last 30 years has been the <a href="http://sadve.cs.illinois.edu/Publications/thesis.pdf">thesis work of Sarita Adve.</a></p><p><strong>Alexey: Do you think we have this barrier because of the inherent nature of the concept?</strong></p><p>Michael: No. Sarita’s observation was that if you do it right you can get all the performance and complexity you want under the hood, and you give a simple API to the programmer and say: “If you obey this API, you will have the appearance of sequential consistency.” I really believe that that is the right model. Write data race-free code, and you get sequential consistency. Now, of course, we need tools to make it less likely that you will accidentally put races in your programs, that’s another issue.</p><p><strong>Vladimir: Did you have instances in your career when you thought something was a solved problem, and in reality, it turned out to be a complete disaster or something that could not be solved? For example, mathematically you can factor out any number or identify if it is prime. But in practice, it doesn’t really play that well. You can’t really factor numbers efficiently with the current hardware. Did something similar happen to you?</strong></p><p>Michael: Nothing is immediately springing to mind. There have certainly been areas where I thought the area was closed, where I thought we’ve done everything that could be done in the area, and then somebody came along and did something new that was surprisingly good. So for instance, I thought that we’d reached maturity on unbounded concurrent queues. There had been several improvements over the M&amp;S queue, and we’d reached a plateau, and that was the best we were going to do. Then <a href="https://www.cs.tau.ac.il/~mad/publications/ppopp2013-x86queues.pdf">the LCR queue </a>came along — Morrison and Afek. It showed that you can build an unbounded concurrent queue that had just fetch-and-increment on the critical path most of the time. Suddenly you could get an order of magnitude better performance. That’s pretty cool! That was an area where I thought we’d sort of reached the end of what there was, and then somebody came along with a cool new idea. It wasn’t that we didn’t already know that fetch-and-increment was a really useful idea. If you go back to <a href="https://www.utep.edu/cs/people/Freudenthal.html">Eric Freudenthal</a>’s work with <a href="https://cs.nyu.edu/~gottlieb/">Allan Gottlieb</a> on the <a href="https://en.wikipedia.org/wiki/Ultracomputer">NYU Ultracomputer</a> back in the late 1980s, he had already shown how valuable fetch-and-increment was. But that was for bounded queues. Morrison and Afek figured out how to do it for unbounded queues.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BifpQ0Kbemol2voVleDocg.jpeg" /></figure><h3>New architectures. Is the victory of transactional memory closer?</h3><p><strong>Vladimir: Do you keep track of new architectural solutions, which could be potentially beneficial for algorithms?</strong></p><p>Michael: Oh yes. There are all sorts of things I’d love to see the architects build.</p><p><strong>Vladimir: For example? Like what?</strong></p><p>Michael: Well, the thing that’s most immediately of interest to me is a few simple extensions to the hardware transactional memory that we have in Intel and IBM processors today. In particular, I would love to have non-transactional loads and stores that happened immediately available inside transactions. They immediately lead to cycles in the happens-before order, so they’re very hard to reason about. But if you maintain levels of abstraction, there are a dozen different really cool things you can do if you can break out of a transactional context and do things outside in the middle of a transaction. I don’t know exactly how hard those would be to implement, but they would be extraordinarily useful.</p><p>What else? Cache fills from a remote memory. That’s going to happen, I think. That will allow us to build systems with disaggregated memory, where you can have 100 terabytes of non-volatile memory in your rack, and the operating systems can figure out which sections of that memory to map into the physical address space of which processors dynamically. That would be of enormous use for data centers, for cloud computing, where you can provision large memory on a dynamic basis for tasks that need it. I think that’s likely to happen.</p><p><strong>Vitaliy: To finish the discussion on transactional memory, let me ask you one more question. Do you think that transactional memory will eventually wipe out the standard concurrent data structures?</strong></p><p>Michael: No. Transactions are a speculation mechanism. They are atomic blocks at the programming level and speculation under the hood. Speculation works when you guess right most of the time. This means transactional memory is good for cases where threads are almost never really interacting, and you’re just making sure that they aren’t really interacting. But as soon as you have a significant amount of interaction between threads — real sharing — then transactions do you very little good if they are used to wrap an entire atomic operation. But then they would still be very useful as building blocks for concurrent data structures, where basically you want to do a three word CAS. I want to change these three things concurrently in the middle of my really concurrent algorithm that is juggling 20 different threads simultaneously walking their way down a list. So transactional memory would still be useful there, but it will not wipe out the need for people to be very clever about building concurrent data structures.</p><h3>Volatile memory, Optane DIMM, super-fast devices</h3><p><strong>Vitaliy: The final topic I’d like to cover is the subject of your current research, which is a non-volatile memory. What could we expect from the area in the near future? Do you already happen to know about some efficient implementations of hardware nonvolatile memory?</strong></p><p>Michael: I’m not a hardware expert. I know what I read in the news and what I hear from colleagues about what’s coming out of the labs. Everybody knows of course that Intel is selling Optane DIMMs, and they’re 3 times the read latency, 10 times the write latency of dynamic RAM, something like that. And available presumably in very dense, high-capacity versions before very long. So it will be kind of cool having a laptop with several terabytes of byte-addressable RAM in it. It seems to me entirely possible that 10 years from now we may have decided that the best thing to do with this new memory technology is to use it exactly the same way we use DRAM: just have more of it. That’s entirely possible. But the fact that it’s nonvolatile means we can think about doing much more, and reimagining the storage stack, and taking the traditional division between byte-addressable working memory and block-structured persistent memory and fusing the two together — so that it’s no longer the case that anything you want to keep across program runs has to be serialized into a block-structured file. That has all sorts of implications for operating systems and run-time systems and distributed data stores. I think it’s a very exciting area to be working in, and I’m really not in a position to predict how it’s going to work out, but the problems are absolutely fascinating. So I’m excited about how it’s a possibly revolutionary change in systems, and a very natural extension of concurrency work, in that recovery after a failure is a concurrent process with respect to what’s going on during normal operation. So I’m excited about that.</p><p>That’s one of the two main topics that I’m working on right now. The other one is the management of very fast devices and safe access to devices from user space with system control over policy. We have this trend that you’ve seen over recent years of device access being moved to user space — to kernel bypass I/O stacks — because if you have a network interface that needs a new packet every 5 microseconds, then you can’t put a TCP/IP kernel stack on top of it, you just can’t keep up. So vendors all over the place are doing direct access to the devices. But then the operating system isn’t in the loop, and it loses its ability to enforce fair access to the device across competing applications. My group doesn’t believe that trade-off is necessary. We think that we can have our cake and eat it too, as they say. We have a couple of papers about this coming up at USENIX ATC this month that we’re excited about. It connects to the persistence work, because long-lived byte-addressable persistent memory is, essentially, a very fast I/O device that you want to make accessible in userspace. It opens up new approaches to microkernels and exokernels and all these other traditional attempts to move functionality out of the OS kernel and into user space, and to do so safely and while maintaining a high quality of service.</p><p><strong>Vladimir: Byte-addressable memory is great, but because of the physical limit of light speed, there will be some latency talking to that device.</strong></p><p>Michael: Yeah.</p><p><strong>Vladimir: Do you think that processing-in-memory would have enough power to handle new workloads?</strong></p><p>Michael: That’s a really good question, and I don’t have any insights there. Processing in memory is an idea that’s been around a long time. It seems like a really cool idea, it also seems really, really hard. It’s not an area I’ve been working in, but I would love to see some breakthroughs there. I’m afraid I don’t have a whole lot to add.</p><p><strong>Vladimir: They say that much more RAM is needed, but unfortunately this will not fit in the CPU itself. There must be an external processing unit. Thus the required RAM and other components cannot be placed within the core.</strong></p><p>Michael: Yeah, that’s mainly about yield rates in IC manufacture. If you could make whole wafers without defects, then we’d put it all on chip. But we can’t make chips much bigger than postage stamps that have acceptable yield rates.</p><p><strong>Vladimir: But the question of physical limits still remains, we’re probably talking of centimeters like, maybe, ten centimeters cm long. That still impacts latency.</strong></p><p>Michael: Yeah. We’re not likely to get around the speed of light.</p><p><strong>Vladimir: Unfortunately.</strong></p><h3>The next big trend. Dual data structures. Hydra</h3><p><strong>Vitaliy: From what I gather, you catch up with new trends very quickly. You were among the very few first ones who started working with transactional and nonvolatile memory. What do you think will be the next big thing if it’s not a secret?</strong></p><p>Michael: I don’t know — I really don’t. I hope I’ll notice early on, as it starts to emerge, and I can jump on board. I’ve had fun doing that over the years. I can’t really claim to be the person who invented any new field, but I have been lucky enough to jump on board of several new fields when they were very young. I hope I can continue to do that.</p><p><strong>Alexey: And my last question is about your talk at Hydra and lecture at the school. Do I understand correctly that your topic is on non-blocking algorithms?</strong></p><p>Michael: I was planning to talk about dual data structures.</p><p><strong>Alexey: Could you elaborate on that, please?</strong></p><p>Michael: Well, we actually talked about this earlier in this interview. It’s the work that my student Bill Scherer and I started as part of his thesis, and Doug Lea got involved in it and made its way into the concurrent synchronous queues in the Java library. The observation is that if you have a non-blocking data structure that you’re inserting things into and taking things out of, so it’s some sort of a container, and it really is non-blocking, then every operation has to have a finite number of instructions on its critical path — a bounded number. So when you try to take things out of an empty container or try to take a particular thing out of a container that doesn’t have that thing, then you come back right away and say “sorry, it’s not there.” But if that’s not acceptable — if your thread really needs the thing and you need to wait until it’s available — then the natural idiom is to put the operation in a loop and say: “Is it there? Is it there? Is it there?” And that bothers everybody else who’s using the data structure. It’s also not fair, because you could be doing that for ten minutes, and some other thread comes along and says “is it there?”, and it happens to get the item and you don’t.</p><p>Dual data structures are about still being non-blocking, but providing a structured way for threads to wait. The name “dual” means that the data structure contains either data or requests for data — call them “anti-data.” If you try to take something out of an empty container — and obviously, you can’t take something out — you put a request in instead. Now, your thread can wait on a request in a way that doesn’t bother anybody else. The data structure can keep track of priorities among requests so that when data comes along, it knows who to give it to. So you have something that remains non-blocking in a formally specifiable way and has good performance in practice.</p><p><strong>Alexey: Do you have any expectations regarding this data structure, and if it will help improve the performance of all or almost all typical scenarios, or, conversely, only some specific scenarios?</strong></p><p>Michael: It’s useful for cases where you want a non-blocking container, and you need to wait when you want to remove something that isn’t there. To the best of my knowledge, it’s the right thing to do when those conditions hold. So I recommend dual data structures in any situation that matches those two cases. Non-blocking data structures are great primarily because they are immune to performance glitches when somebody gets preempted. Waiting, of course, is essential in many algorithms when you’re trying to pass information from one thread to another.</p><p><strong>Vitaliy: Am I right that you are going to talk about the same thing both at the conference and school?</strong></p><p>Michael: At the school, I will be talking about non-blocking concurrent data structures in general. It will be a class on non-blocking data structures starting from the first principles, assuming that people know what threads are and have some familiarity with lock-based programming. I’ll take them through non-blocking data structures from there — kind of survey the field and the important issues and touch on things like memory management, hazard pointers, hardware primitives, and end up doing things no more complicated than the M&amp;S queue.</p><p><strong>Alexey: Do you plan to cover dual data structures at the end of your school talk?</strong></p><p>Michael: I will mention dual data structures in the class, but I won’t spend significant time on them. The talk at Hydra will focus on them. It will include the work that ended up in Java and will also mention more recent work that I did with Joe Izraelevitz on taking the Morrison and Afek LCR queue and creating dual versions of that and coming up with an almost universal construction for dual data structures.</p><p><strong>Alexey: So, am I right that we can recommend the lecture at school to newbies and the lecture on dual data structure at Hydra for people who already have some experience.</strong></p><p>Michael: I’m assuming — correct me if I’m wrong, please — that the Hydra audience will be a fairly general audience and will include a lot of people who are Java experts or practitioners who aren’t necessarily concurrent programmers.</p><p><strong>Alexey: Right. At least we hope so.</strong></p><p>Michael: Assuming that this is the case, I will be addressing the challenge that we started the interview with, of trying to craft a talk that has enough technical detail to be interesting to the experts in the audience, but also is accessible to everybody.</p><p><strong>Vitaliy: Is there any difference between how you deliver lectures and how you speak at the conferences?</strong></p><p>Michael: Well, for a conference it’s important to have slides, especially if I have an audience that includes people with lots of different native languages, many of whom will be struggling to understand me in English, especially if I talk too fast. The reason I picked these particular topics is that <a href="https://perso.telecom-paristech.fr/kuznetso/">Petr Kuznetsov</a> asked me to talk about non-blocking data structures for the class, and I’m happy to do that. Then when I got asked to do the talk for the Hydra conference I thought: “Well, what do I know that is really going to be of interest to practitioners? OK, it could be the things in the Java library that I had some role in creating, so let me talk about those, and I will create a general audience talk about the stuff that I know that ended up in Java.”</p><p><strong>Alexey: My expectation is that the Hydra audience should already know something about non-blocking programming, and probably most of them have experience with it. At least this is what we expect. But who knows, we’ll figure it out on the spot. Anyway, thank you very much for your time.</strong></p><p>Michael: I look forward to seeing all of you in Saint Petersburg.</p><p><strong>Alexey: We too. Have you been to Saint Petersburg?</strong></p><p>Michael: I have never been to Saint Petersburg. I have never been to Russia! Saint Petersburg has always been on the list of the few places that I haven’t been to that I absolutely want to go, so I was absolutely thrilled to get the invitation.</p><p><strong>Alexey: We’ve prepared a list of excursions. We are waiting for July to meet you in person, thank you very very much!</strong></p><p>We conducted the above interview with Michael Scott for Hydra 2019 St. Petersburg, where he spoke on dual data structures, the subject of some of his most influential research. Michael comes back to the new edition of <a href="https://hydraconf.com/">Hydra</a>, which happens ONLINE on 6–9 July, 2020. The topic is the <a href="https://hydraconf.com/2020/msk/talks/1eketv1d0dkuju7yqykkn4/">safe user-level sharing of memory-mapped resources</a>. Reserve your spot at Hydra 2020 now!</p><p><strong><em>This interview was edited with the assistance of Marina Vorontsova, an editor at </em></strong><a href="http://soshace.com/"><strong><em>Soshace</em></strong></a><strong><em>, a hiring platform for web developers: </em></strong><a href="http://soshace.com/developers"><strong><em>hire a developer</em></strong></a><strong><em> or </em></strong><a href="http://soshace.com/jobs"><strong><em>apply for a job</em></strong></a><strong><em>.</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2dda5cc7d244" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Big Interview with Michael Scott — research career, global trends in programming and mathematics…]]></title>
            <link>https://medium.com/@hydraconference/big-interview-with-michael-scott-research-career-global-trends-in-programming-and-mathematics-488317b8d022?source=rss-8f40aa214273------2</link>
            <guid isPermaLink="false">https://medium.com/p/488317b8d022</guid>
            <category><![CDATA[distributed-computing]]></category>
            <category><![CDATA[conference]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[michael-scott]]></category>
            <dc:creator><![CDATA[Hydra: distributed computing conference]]></dc:creator>
            <pubDate>Tue, 26 May 2020 13:26:18 GMT</pubDate>
            <atom:updated>2020-06-02T11:19:46.861Z</atom:updated>
            <content:encoded><![CDATA[<h3>Big Interview with Michael Scott — research career, global trends in programming and mathematics, the connection between business and academia (part 1)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2qi7Vn5UdSxvn0YovEsVWg.png" /></figure><p>Michael Scott has been teaching Computer Science at the University of Rochester for more than thirty years. Previously, he was a graduate student at the University of Wisconsin — Madison. Prof. Scott’s research mainly addresses parallel and distributed programming, as well as language design, which he also teaches to his students.</p><p>Michael is widely known for his textbook, <em>Programming Language Pragmatics</em>, which has become a leading text in programming language design and implementation.</p><p>Michael’s research paper, “<a href="https://bit.ly/2NJOlrn">Algorithms for scalable synchronization on shared-memory multiprocessors</a>,” co-authored by John Mellor-Crummey, received the Edsger W. Dijkstra Prize in Distributed Computing. You may also know Michael as a co-creator of the widely used Michael &amp; Scott concurrent queue algorithm.</p><p>Together with his student Bill Scherer and with Prof. Doug Leа of the State University of New York at Oswego, Prof. Scott developed several of the non-blocking algorithms in the Java standard library. The introduction of dual data structures in JavaSE 5, in particular, allowed a 10-fold improvement in the performance of ThreadPoolExecutor.</p><p>Last year, Michael Scott visited the Hydra conference in St. Petersburg and gave a talk about <a href="https://www.youtube.com/watch?v=nz6fASCVmT8&amp;list=PLC5OGTO4dWxYuuASJMj1xePLQjNg05HzT&amp;index=16&amp;t=0s">dual data structures</a>. In the interview that follows, Michael spoke of his research career, global trends in programming and mathematics, the connection between business and academia, and other related topics.</p><p>The interview is quite long, so we have separated it into two parts. In this part you will find more about Michael Scott’s work and research and global trends in programming and mathematics.</p><h3>The interview was conducted by:</h3><p><strong>Vitaly Aksenov, </strong>currently a postdoc at IST Austria and an employee of the Department of Computer Science at ITMO University. Vitaly’s research addresses theory and practice in the field of concurrent data structures. Before joining IST, he earned his Ph.D. at Paris Diderot University and ITMO under the supervision of Prof. Peter Kuznetsov.</p><p><strong>Alexey Fedorov,</strong> a producer at JUG Ru Group, a Russian company that organizes conferences for developers. Overall, he has helped to organize more than fifty events. Prior to co-founding JUG Ru Group, Alexey worked in various roles starting from a software engineer at Oracle (JCK, Java Platform Group) and ending with the position of a Dev Rel consultant at Odnoklassniki.</p><p><strong>Vladimir Sitnikov,</strong> an engineer at Netcracker. For the last ten years, he has been working on the performance and scalability of NetCracker OS, the software used by telecom operators to automate network and network equipment management processes. His professional interests revolve around Java and Oracle Database performance issues. Vladimir is the author of more than a dozen performance improvements for the official PostgreSQL JDBC driver.</p><h3>First Steps in Career, Rochester University. Charlotte Project, Lynx Language</h3><p><strong>Alexey: I want to start with an acknowledgment that Russian developers love Computer Science, Data Science, and algorithms. We all read </strong><a href="https://en.wikipedia.org/wiki/Introduction_to_Algorithms"><strong><em>Introduction to Algorithms</em></strong></a><strong> by Cormen, Leiserson, and Rivest. Therefore, we truly believe that the conference, the school lectures, and this interview will be very popular among the Russian audience. Do you have a Computer Science fetish in the US?</strong></p><p>Michael: The field is so diverse, there are so many interest groups and so many impacts on society I would have a really hard time picking out one particular thing. Certainly, the impact on society, business, industry, arts, and everything has been so big over the last 30 years, that computing has moved into a popular culture much more than it had when I started in the field.</p><p><strong>Vitaly: Let’s start from something a bit remote. Many universities have different specializations. CMU is known for parallel computing, MIT is known for cryptography, robotics, and concurrency. Does the University of Rochester have a specialization?</strong></p><p>Michael: Well, to be honest, CMU and MIT are known for everything. Historically our department has been known more for artificial intelligence than anything else. Half of the faculty members in our department do AI or HCI. It’s a larger percentage than it is in most departments, and it has been throughout the department history. So it’s been a little unusual for me because when I was in graduate school, I didn’t take any courses in AI — I’m not an AI person. I’m living in a department that is very heavy on a part of the field that I don’t do. Probably the number two thing that we’re known for is parallel and concurrent programming, which is my area. So I take solace in that.</p><p><strong>Vitaly: You started your research in computer science in the very early days of concurrency. Having looked through your research papers and publications, we noticed that your first works dealt with a broad range of subjects, such as concurrent memory management, distributed file systems, and operating systems. How would you explain such a diversity of interests? Were you trying to find your own place in the research community?</strong></p><p>Michael: As a graduate student, I was part of a project at the University of Wisconsin that was developing one of the first distributed operating systems. I worked with <a href="https://en.wikipedia.org/wiki/Raphael_Finkel">Raphael Finkel</a> and <a href="http://pages.cs.wisc.edu/~solomon/">Marvin Solomon</a> on the <a href="https://minds.wisconsin.edu/handle/1793/58442">Charlotte project</a> at Wisconsin. My thesis work — which no one knows about today for good reason — was on language design for system software for distributed systems. I developed a programming language called <a href="https://doi.org/10.1016/0096-0551(91)90008-W">Lynx</a> that was designed to make it easier to build servers for a loosely coupled distributed operating system. As a core operating systems person, I thought to myself that I would probably end up being kind of an SOSP sort of person throughout my career. But I went to a small school at Rochester, where by nature groups interact a lot. If I wanted to talk to ten different people, they had to be ten people who did very different things. I liked that. That was one of the appeals of going to Rochester — that I needed to be a generalist, I needed to work on a lot of things. I got into concurrent data structures and synchronization algorithms by accident.</p><h3>IEEE Scalable Coherent Interface, MCS lock</h3><p><strong>Vitaly: That seems like an interesting story, can you elaborate, please?</strong></p><p>Michael: There’s a good story behind that, which I enjoy telling. ASPLOS III, the third instance of ASPLOS, was held in Boston in 1989. I attended and sat next to <a href="https://www.cs.rice.edu/~johnmc/">John Mellor-Crummey</a>, of Rice University, who had been a graduate student in our department. I’d known him well, I was on his committee, but I’ve never done any research with him; we had no joint papers. But we were friends and we sat next to each other at the conference. <a href="https://en.wikipedia.org/wiki/Mary_K._Vernon">Mary Vernon</a> from Wisconsin got up to talk about a multiprocessor they were designing at Wisconsin called the <a href="https://dl.acm.org/doi/10.1145/70082.68188">Wisconsin Multicube</a>. One of the things they had in the Multicube design was a hardware synchronization mechanism called Queue on Sync Bit. It was later renamed Queue on Lock Bit, because that could be pronounced “Colby,” which is the name of a kind of cheese; it was a nice pun (Wisconsin is famous for cheese). People who follow concurrency mechanisms may realize that Colby eventually became the synchronization mechanism of the <a href="https://en.wikipedia.org/wiki/Scalable_Coherent_Interface">Scalable Coherent Interface</a> standard from IEEE. At any rate, it was a lock mechanism that, in hardware, created pointers from one cache to another so that each lock holder would know who was next in line. John and I were sitting in the audience, and we looked at each other and said: “Why do you need hardware for that? Can’t we do that with compare-and-swap?” So we pulled out the memo pads that were scattered around the room and on the back of one of those Boston Park Plaza memo pads we sketched out the MCS lock during Mary’s talk. We went and implemented it, experimented with it, and it worked very well. We published a paper about it. I thought: “That was kind of cool, now I’ll go back to operating systems.” Then something else came along and eventually over time, synchronization, concurrency, and data structures became my principal focus. But it wasn’t my plan.</p><p><strong>Vitaly: I knew about locks (MCS, CLH), but I didn’t know it was your work and that the name MCS was an acronym from your last names, Mellor-Crummey and Scott. It caught me by surprise.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B5JLg_3lZDazRd4pKdHmEw.jpeg" /></figure><h3>How to survive in a changeable world?</h3><p><strong>Alexey: I have a question on a related topic. Thirty or forty years ago, you could choose what you wanted to do. If you wanted to start your career in concurrency or distributed systems — that was easy. If you wanted to start your career in operating systems — you were welcome. There were a lot of open questions and very few experts in the fields.</strong></p><p><strong>For the time being, these areas have already been investigated. Now, we have lots of very narrow fields, there’s not just an expert in all of the operating systems, each operating system requires an expert. The same goes for concurrency and distributed systems. Since we don’t live forever, we can only dedicate a few dozen years to CS research if we are lucky. How to survive in this new reality?</strong></p><p>Michael: Well, it’s the world that everybody else inhabits. I had the good fortune to come into Computer Science when the field was kind of a teenager. Foundations had been laid, but it hadn’t matured yet. That doesn’t happen very often, you know. Electrical engineering has been around for a long time, physics has been around a lot longer, math has been around pretty much forever. But it doesn’t mean that nobody does any interesting work in math anymore: they’re doing all sorts of interesting work in math. There remain open problems, but there’s a lot more that one has to learn, and because the field is so deep at this point, you’re absolutely right: people end up specializing more than they used to. This means that we’ve inherited the situation that everybody has been in every other field of human endeavor for a long time.</p><p><strong>Alexey: I am asking because I had a real hands-on experience. I have a background in math, and when I was a student, I attended conferences and worked on some scientific topics. I encountered a problem that nobody in the audience understood the details of what I was doing. The same was true for other people: when they gave a presentation on the topic of their research, nobody had a clue what they were talking about. Of course, there are general high-level topics that are familiar to everybody, but as soon as you go deeper, you lose your audience. How do you handle that?</strong></p><p>Michael: I don’t always manage it well. Fairly recently, I wrote a too-technical talk. I realized very quickly as I was giving the talk that most of the audience didn’t understand what I was talking about. So I tried to adjust as best I could on the fly. I couldn’t do a wonderful job because I couldn’t change my slides. I try not to make that mistake too often. The advice that I always give to my students is to know your audience. Figure out who you’re talking to, what they know, and what they will need to hear in order to appreciate your work.</p><p><strong>Vitaly: Can you tell us what that lecture was about?</strong></p><p>Michael: I would rather not go into that because I don’t want to identify the particular place and people involved. Students are often buried in the details of what they’re working on. The hardest part for them is creating a talk that presents enough of the big picture at the beginning to help the audience understand why the problem is interesting and how it fits into what they already know. That’s the part that I find students most need to work on. It was also the part that was missing in the talk that I gave recently. A really good talk does a nice job of bringing the audience in at the beginning, helping them understand what the problem is, and how it fits into things that they already know about. That can be less or more detailed and technical depending on where the audience is. If you have a really broad audience, you have sort of a staged talk, where the beginning is for everybody, and by the time you get to the end, you may have lost some fraction of the audience, but the people who are more connected to your technical area can get some sense of the detail.</p><h3>Do students become less intelligent? Global trends, Internationalization</h3><p><strong>Alexey: You have been observing your students for the last 30 years. Have students become less or more intelligent? From Russian professors, we usually hear that each year, they have more and more less intelligent students, and they don’t know how to manage that.</strong></p><p>Michael: Yes, this is the lament of old people: we get grumbly. There’s a natural temptation I think to expect students to have somehow absorbed the experience of 30 years that I have. If I have a broader perspective and a better understanding of how things connect now than I did in 1985, then why don’t the students? Well, because they’re 20 years old. The biggest change I’ve noticed at Rochester is the demographics. We have more international students than we did when I started out. (Except for Canadians: we have fewer Canadian students than we used to. We used to have lots of Canadian students because we’re physically located very close to the Canadian border, and it was an attractive place to go to if you wanted to be able to drive home on the weekend. But nowadays there are so many great schools in Canada that the Canadians stay home and don’t come to the US in the numbers that they used to.)</p><p><strong>Alexey: Do you think it’s a local or global trend? Is it globalization?</strong></p><p>Michael: I mean, the world is flat — somebody observed that, right? The field is much more international than it used to be. ACM conferences used to be held entirely in the United States. And then they said: “OK, once every 4 years, we’ll have a version of this conference outside the United States,” and now we spread them around all over the globe. The IEEE even more so, because it’s always been a more international organization than the ACM. You see program chairs from China, India, Russia, Germany, and wherever because there’s so much going on internationally.</p><p><strong>Alexey: Are there any drawbacks to internalization?</strong></p><p>Michael: The dark sides are not technical, they’re all political. Once upon a time, the dark side was that the United States was recruiting the brightest, most talented people from around the world and stealing them from their home countries. Now the dark side is that we have countries playing political games with each other on visas and immigration.</p><p><strong>Alexey: Okay, so there are problems. Barriers, visas, politics. I got it.</strong></p><h3>Working with students effectively</h3><p><strong>Vladimir: I am particularly interested in how you approach the teaching of a new subject to your students. There are several ways of approaching the teaching process and student engagement. You can either inspire them to try new things on their own or you can just explain how things work in detail. What do you prefer? What’s your teaching style?</strong></p><p><strong>Alexey: How do you find the balance between the first and the second approaches?</strong></p><p>Michael: What I prefer is to give reading assignments ahead of time and have students actually read them carefully, understand what they can, come to class with questions about the parts that they didn’t understand, and then spend the class having a conversation about those parts and exploring them together. That’s what I love. But it’s hard to get students with all the constraints on their time these days to actually invest the time ahead of class. So I end up talking more in class about background material and just sort of filling in what was in the reading than I would ideally like. That said, I try as much as I can to run an interactive class. If I’m just going to stand and present, I might as well make a video once and put it online and let them watch it in their dorm room. The reason we have classes that meet in person is so that we can interact as human beings. For the most part, I don’t use slides when I teach — I use chalk and a chalkboard. If I have a complicated diagram, I’ll create a slide for it, because it’s more than I can draw on the board. But not having slides means I don’t have a script. I don’t have a set order in which I have to present the material, and the class can adapt based on what I get questions about. So I work really hard to get an interactive class and to let what I present in the classroom depends on the questions that I get on the fly.</p><p><strong>Vladimir: That’s great to hear, but, in my experience, students don’t usually ask questions even if you say that you don’t care how stupid or irrelevant questions can be. How do you deal with that? Do you have a secret?</strong></p><p>Michael: There is some truth to the fact that if you just stand silently long enough, they’ll get uncomfortable enough to ask a question. Sometimes that works. The other thing that I can do is to ask a simple sort of yes/no technical question that determines whether people understand what just happened in class. “Is there a data race right here, how many people think ‘yes’? How many people think ‘no’?” And “How many people have no clue?”, because I only saw half the hands come up for those two different choices.</p><p><strong>Vitaly: Whoever doesn’t answer correctly, gets automatically expelled from class?</strong></p><p>Michael: The ones who don’t answer have to ask a question. What do you need to know in order to figure out the answer to the question I just asked? Give me some guidance, I’m happy to go wherever you want to go to help you understand this material, but if I don’t know what’s going on in your head, I don’t know how to do that. If I poke and prod enough, I’ll get good questions, and often they take me in an unexpected direction. Not good questions in the sense of a beautifully formulated and worded question, but good questions in the sense that they actually tell me what’s going on with the class.</p><p><strong>Alexey: Have you ever been asked a question that made you look at a problem from a different angle? Do your students ask questions that you have never thought about? If they do, how often does it happen?</strong></p><p>Michael: Occasionally I’ll get a question that illuminates a new way of teaching the material. Often I’ll get a question that brings up an interesting subject to talk about that I hadn’t been planning to talk about. My students will tell you that I have a tendency in response to these questions to go off kind of on a sidetrack in the presentation. That’s often, according to the students — and certainly, in my experience — one of the most interesting parts of the class. A few times I’ve had a student ask a new question that sort of suggests a new research direction or evolves into a paper. That happens much more often in one-on-one interactions with students than it does in a classroom, but it does occasionally happen in the classroom too.</p><p><strong>Alexey: So, students did, in fact, ask questions that led to research papers or involved more investment in the area, right?</strong></p><p>Michael: Yeah.</p><p><strong>Vitaly: How often do you have one-on-one conversations with students who’d like to understand more?</strong></p><p>Michael: Well, with my Ph.D. students, all the time. I have a half-dozen Ph.D. students, and I meet with them individually all the time, weekly. One-on-one with students who are enrolled in a large class, and that’s my main interaction with them — not terribly often. I wish it happened more. But they often feel, I guess, scared to come to visit their instructors during office hours. Every semester, I’ll have some students who’ll sort of get over that psychological hurdle and they’ll come to talk to me outside of class, and it’s fun working with them. But if they all did that, I wouldn’t have enough time, so maybe it’s actually working out well.</p><p><strong>Vitaliy: How do you find time to interact with your students outside the class? I know that in the US, professors don’t usually have a lot of time: there are grants and proposals to take care of, and so on.</strong></p><p>Michael: Well, working with students is probably part of the job that I enjoy the most. So it’s not hard to find the motivation to do it. To a large extent, my time physically in the office ends up being back-to-back meetings, at least during the academic year. In the summer, things are a little bit less scheduled, but during the academic year, my calendar tends to be booked pretty much 9 to 5 every day. Then a lot of that other stuff — doing actual research, writing papers, reviewing, writing grants — ends up being done in the evening or on weekends.</p><h3>Writing books and courses: How not to fall behind?</h3><p><strong>Alexey: Do you have any courses that you started teaching a long time ago and still do? Something like Computer Science 101, maybe?</strong></p><p>Michael: The best example there would be a programming languages course.</p><p><strong>Alexey: Are there any differences to this course compared to, say, a thirty-year-old version of it? If so, how has the course evolved over the years? Are there any particular tendencies?</strong></p><p>Michael: The languages course has a spin or a style at Rochester that was a little bit unusual at the time that I created it. It’s a course I inherited when my colleague <a href="https://dblp.org/pers/hd/b/Baldwin:Douglas">Doug Baldwin</a> left back in the late 1980s. It wasn’t really my research area: it sort of touched on it, but I was the best person to teach the course when he left, and I didn’t like any of the textbooks that were out there, and as you may know, I ended up writing my own textbook for that course (<a href="https://www.amazon.com/Programming-Language-Pragmatics-Michael-Scott/dp/0124104096/ref=sr_1_1?keywords=michael+scott+programming&amp;qid=1562557753&amp;s=books&amp;sr=1-1"><em>Programming Language Pragmatics</em></a>). It’s still used in over 200 different universities around the world at this point. It’s unusual in that it very deliberately mixes language design and language implementation issues, and focuses on how they interact. That theme has remained the same over the years. Many of the fundamental concepts have remained the same — you know: abstraction, naming, modularity, types. The principles that create the units of the course — they’ve pretty much stayed the same. But, say, the set of languages that you use to illustrate concepts has changed completely. When I started teaching the course I gave all sorts of different examples in Pascal. Many of my students today have never heard of Pascal. But they know about Swift, they know about Go, they know about Rust. So I need to be talking about languages they’re using today. They know lots about scripting languages, whereas when I first started teaching this course, it was entirely about compiled languages. Now there’s a huge amount of material that I need to include about Python and Ruby and even Perl, because it’s where people are writing code and doing interesting things. It’s actually where lots of interesting work in language design is being done these days — in dynamic languages and in industry.</p><p><strong>Vitaliy: Then my next question is, how do you catch up with all those things? It takes a huge amount of time to update the course and understand new languages and concepts.</strong></p><p>Michael: Well, I can’t claim to be doing a perfect job… Mostly I do what everybody else does: I read web pages. You know, if I want to know about Rust, I do a Google search about Rust, and there’s the page at Mozilla, and I go there, there’s a tutorial, I click on that and just follow my nose. That’s actually the right answer for things that are happening in industry. For things that are happening in academia on a more pure research front, then the answer is — you follow the papers of the leading conferences.</p><p>Do not miss <a href="https://medium.com/@hydraconference/big-interview-with-michael-scott-research-career-global-trends-in-programming-and-mathematics-2dda5cc7d244">the second part</a> of this interview we conducted with Michael Scott for Hydra 2019 St Petersburg, where he spoke on dual data structures, the subject of his extensive lifetime research. Michael comes back to the new edition of <a href="https://hydraconf.com/">Hydra</a>, which happens ONLINE on 6–9 July, 2020. The topic is <a href="https://hydraconf.com/2020/msk/talks/1eketv1d0dkuju7yqykkn4/?utm_source=medium&amp;utm_medium=488317b8d022&amp;utm_campaign=michaelscotthydra">safe user-level sharing of memory-mapped resources</a>. Reserve your spot at Hydra 2020 now!</p><p><strong><em>This interview was edited with the assistance of Marina Vorontsova, an editor at </em></strong><a href="http://soshace.com/"><strong><em>Soshace</em></strong></a><strong><em>, a hiring platform for web developers: </em></strong><a href="http://soshace.com/developers"><strong><em>hire a developer</em></strong></a><strong><em> or </em></strong><a href="http://soshace.com/jobs"><strong><em>apply for a job</em></strong></a><strong><em>.</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=488317b8d022" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The big interview with Martin Kleppmann: “Figuring out the future of distributed data systems”.]]></title>
            <link>https://medium.com/@hydraconference/the-big-interview-with-martin-kleppmann-figuring-out-the-future-of-distributed-data-systems-28a680d99ae6?source=rss-8f40aa214273------2</link>
            <guid isPermaLink="false">https://medium.com/p/28a680d99ae6</guid>
            <category><![CDATA[conference]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[big-data]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <dc:creator><![CDATA[Hydra: distributed computing conference]]></dc:creator>
            <pubDate>Thu, 27 Jun 2019 16:05:44 GMT</pubDate>
            <atom:updated>2019-06-27T17:04:08.597Z</atom:updated>
            <content:encoded><![CDATA[<h3>The big interview with Martin Kleppmann: “Figuring out the future of distributed data systems”</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*FURE_935zKNBorXLup_Rew.jpeg" /></figure><p><strong>Dr. Martin Kleppmann</strong> is a researcher in distributed systems at the University of Cambridge, and the author of the highly acclaimed <a href="https://www.amazon.de/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321">“Designing Data-Intensive Applications”</a> (O’Reilly Media, 2017).</p><p>Kevin Scott, CTO at Microsoft <a href="https://martin.kleppmann.com/2017/03/27/designing-data-intensive-applications.html">once said</a>: “This book should be required reading for software engineers. Designing Data-Intensive Applications is a rare resource that connects theory and practice to help developers make smart decisions as they design and implement data infrastructure and systems.”</p><p>Martin’s main research interests include collaboration software, CRDTs, and formal verification of distributed algorithms. Previously he was a software engineer and an entrepreneur at several Internet companies including LinkedIn and Rapportive, where he worked on large-scale data infrastructure.</p><p><strong>Vadim Tsesko</strong> (<a href="http://twitter.com/incubos">@incubos</a>) is a lead software engineer at <a href="https://ok.ru/%5C">Odnoklassniki</a> who works in Core Platform team. Vadim’s scientific and engineering interests include distributed systems, data warehouses and verification of software systems.</p><h3>Contents:</h3><ul><li>Moving from business to academic research;</li><li>Discussion of “Designing Data-Intensive Applications”;</li><li>Common sense against artificial hype and aggressive marketing;</li><li>Pitfalls of CAP theorem and other industry mistakes;</li><li>Benefits of decentralization;</li><li>Blockchains, Dat, IPFS, Filecoin, WebRTC;</li><li>New CRDTs. Formal verification with Isabelle;</li><li>Event sourcing. Low level approach. XA transactions;</li><li>Apache Kafka, PostgreSQL, Memcached, Redis, Elasticsearch;</li><li>How to apply all that tools to real life;</li><li>Expected target audience of Martin’s talks and the Hydra conference.</li></ul><h3>Moving from business to academic research</h3><p><strong>Vadim</strong>: The first question I would like to ask you is really important for me. You founded Go Test It and Rapportive, and you had been designing and engineering large-scale systems at LinkedIn for a while. Then you decided to switch from industrial engineering to academia. Could you please explain the motivation for that decision? What have you gained and what have you had to sacrifice?</p><p><strong>Martin</strong>: It’s been a very interesting process. As you seem to be hinting at, not many people make the switch in that direction. A lot of people go from academia to industry, but not so many back. Which is understandable, because I had to take quite a large pay cut in order to go back to academia. But what I really love about research is the freedom to work on topics that I find interesting and that I think are important, even if those topics don’t immediately lead to a commercially viable product within the next 6 months or so. Of course, at a company the stuff you build needs to turn into a product that can be sold in some form or another. On the other hand, the things I’m now working on are topics that are really important for the future of how we build software and how the internet works. But we don’t really understand these topics well enough yet to go and start building commercial products: we are still at the level of trying to figure out, fundamentally, what these technologies need to look like. And since this is fundamental research I realized it’s better to do this at a university than to try to do it at a company, because at a university I’m free to work on things that might not become commercially viable for another ten years, and that is OK. It’s OK to work with a much longer time horizon when you’re in research.</p><h3>“Designing Data-Intensive Applications”</h3><p><strong>Vadim</strong>: We’ll definitely get back to your current research interests. Meanwhile let’s talk about your latest book <a href="https://dataintensive.net/">Designing Data-Intensive Applications</a>. I’m a big fan of your book and I believe it’s one of the best guides for building modern distributed systems. You’ve covered almost all the notable achievements up to date.</p><p><strong>Martin</strong>: Thank you, I’m glad you find it useful.</p><p><strong>Vadim</strong>: Just for those unlucky readers who haven’t read your book yet, could you please name several major achievements in the field of distributed systems nowadays?</p><p><strong>Martin</strong>: Well, the goal of the book is not so much to explain one particular technology; the goal is rather to give you a guide to the entire landscape of different systems that are used for storing and processing data. There are so many different databases, stream processors, batch processing tools, all sorts of replication tools and so on, and it’s really hard to get an overview. If you’re trying to build a particular application it’s really hard to know which database you should use, and which tools are the most appropriate ones for the problem you’re trying to solve. A lot of existing computing books simply didn’t answer that problem in a satisfactory way. I found that if you’re reading a book on Cassandra for example, it would tell you why Cassandra is wonderful, but it generally wouldn’t tell you about things for which it’s not a good fit. So what I really wanted to do in this book was to identify the main questions that you need to ask yourself if you’re trying to build some kind of large-scale system. And through answering those questions you can then help figure out which technologies are appropriate and which are less appropriate for the particular problem you’re trying to solve — because, in general, there’s no one technology that is perfect for everything. And so, the book is trying to help you figure out the pros and cons of different technologies in different settings.</p><h3>Common sense against artificial hype and aggressive marketing</h3><p><strong>Vadim</strong>: Indeed, often — if not always — there are many technologies with overlapping functions, features and data models. And you can’t believe all those marketing buzzwords. You need to read the white papers to learn the internals, and even try to read the source code to understand how it works exactly.</p><p><strong>Martin</strong>: And I found that you often have to read between the lines because often documentation doesn’t really tell you for which things a particular database sucks. The truth is that every database sucks at some kind of workload, the question is just to know which ones they are. So yes, sometimes you have to read the deployment guidelines for ops people and try to reverse-engineer from that what is actually going on in the system.</p><p><strong>Vadim</strong>: Don’t you feel that the industry lacks the common vocabulary or a set of criteria to compare different solutions for the same problem? Similar things are called by different names, some things are omitted which should always be clear and stated explicitly, like transaction guarantees. What do you think?</p><p><strong>Martin</strong>: Yeah, I think a problem that our industry has is that often, when people talk about a particular tool, there’s a lot of hype about everything. Which is understandable, because the tools are made by various companies, and obviously those companies want to promote their products, and so those companies will send people to conferences to speak about how wonderful their product is, essentially. It will be disguised as a tech talk, but essentially it’s still a sales activity. As an industry, we really could do with more honesty about the advantages and disadvantages of some product. And part of that requires a common terminology, because otherwise you simply can’t compare things on an equal footing. But beyond a shared terminology we need ways of reasoning about things that certain technologies are good or bad at.</p><h3>Pitfalls of CAP theorem and other industry mistakes</h3><p><strong>Vadim</strong>: My next question is quite a controversial one. Could you please name any major mistakes in the industry you have stumbled upon during your career? Maybe overvalued technologies or widely-practiced solutions we should have got rid of a long time ago? It might be a bad example, but compare JSON over HTTP/1.1 vs the much more efficient gRPC over HTTP/2. Or is there an alternative point of view?</p><p><strong>Martin</strong>: I think in many cases there are very good reasons for why a technology does one thing and not another. So I’m very hesitant to call things mistakes, because in most cases it’s a question of trade-offs. In your example of JSON over HTTP/1.1 versus Protocol Buffers over HTTP/2, I think there are actually quite reasonable arguments for both sides there. For example, if you want to use Protocol Buffers, you have to define your schema, and a schema can be a wonderful thing because it helps document exactly what communication is going on. But some people find schemas annoying, especially if they’re at early stages of development and they’re changing data formats very frequently. So there you have it, there’s a question of trade-offs; in some situations one is better, in others the other is better.</p><p>In terms of actual mistakes that I feel are simply bad, there’s only a fairly small number of things. One opinion that I have is that the CAP Theorem is fundamentally bad and just not useful. Whenever people use the CAP Theorem to justify design decisions, I think often they are either misinterpreting what CAP is actually saying, or stating the obvious in a way. CAP as a theorem has a problem that it is really just stating the obvious. Moreover, it talks about just one very narrowly defined consistency model, namely linearizability, and one very narrowly defined availability model, which is: you want every replica to be fully available for reads and writes, even if it cannot communicate with any other replicas. These are reasonable definitions, but they are very narrow, and many applications simply do not fall into the case of needing precisely that definition of consistency or precisely that definition of availability. And for all the applications that use a different definition of those words, the CAP Theorem doesn’t tell you anything at all. It’s simply an empty statement. So that, I feel, is a mistake.</p><p>And while we’re ranting, if you’re asking me to name mistakes, another big mistake that I see in the tech industry is the mining of cryptocurrencies, which I think is such an egregious waste of electricity. I just cannot fathom why people think that is a good idea.</p><p><strong>Vadim</strong>: Talking about the CAP Theorem, many storage technologies are actually tunable, in terms of things like AP or CP. You can choose the mode they operate in.</p><p><strong>Martin</strong>: Yes. Moreover, there are many technologies which are neither consistent nor available under the strict definition of the CAP Theorem. They are literally just P! Not CP, not CA, not AP, just P. Nobody says that, because that would look bad, but honestly, this could be a perfectly reasonable design decision to make. There are many systems for which that is actually totally fine. This is actually one of the reasons why I think that CAP is such an unhelpful way of talking about things: because there is a huge part of the design space that it simply does not capture, where there are perfectly reasonable good designs for software that it simply doesn’t allow you to talk about.</p><h3>Benefits of decentralization</h3><p><strong>Vadim</strong>: Talking about data-intensive applications today, what other major challenges, unsolved problems or hot research topics can you name? As far as I know, you’re a major proponent of decentralized computation and storage.</p><p><strong>Martin</strong>: Yes. One of the theses behind my research is that at the moment we rely too much on servers and centralization. If you think about how the Internet was originally designed back in the day when it evolved from ARPANET, it was intended as a very resilient network where packets could be sent via several different routes, and they would still get to the destination. And if a nuclear bomb hit a particular American city, the rest of the network would still work because it would just route around the failed parts of the system. This was a Cold War design.</p><p>And then we decided to put everything in the cloud, and now basically everything has to go via one of AWS’s datacenters, such as us-east-1 somewhere in Virginia. We’ve taken away this ideal of being able to decentrally use various different parts of the network, and we’ve put in these servers that everything relies on, and now it’s extremely centralized. So I’m interested in decentralization, in the sense of moving some of the power and control over data away from those servers and back to the end users.</p><p>One thing I want to add in this context is that a lot of people talking about decentralization are talking about things like cryptocurrencies, because they are also attempting a form of decentralization whereby control is moved away from a central authority like a bank and into a network of cooperating nodes. But that’s not really the sort of decentralization that I’m interested in: I find that these cryptocurrencies are actually still extremely centralized, in the sense that if you want to make a Bitcoin transaction, you have to make it on the Bitcoin network — you have to use the network of Bitcoin, so everything is centralized on that particular network. The way it’s built is decentralized in the sense that it doesn’t have a single controlling node, but the network as a whole is extremely centralized in that any transaction you have to make you have to do through this network. You can’t do it in some other way. I feel that it’s still a form of centralization.</p><p>In the case of a cryptocurrency this centralization might be inevitable, because you need to do stuff like avoid double spending, and doing that is difficult without a network that achieves consensus about exactly which transactions have happened and which have not. And this is exactly what the Bitcoin network does. But there are many applications that do not require something like a blockchain, which can actually cope with a much more flexible model of data flowing around the system. And that’s the type of decentralized system that I’m most interested in.</p><p><strong>Vadim</strong>: Could you please name any promising or undervalued technologies in the field of decentralized systems apart from blockchain? I have been using IPFS for a while.</p><p><strong>Martin</strong>: For IPFS, I have looked into it a bit though I haven’t actually used it myself. We’ve done some work with the <a href="https://dat.foundation/">Dat </a>project, which is somewhat similar to <a href="https://ipfs.io/">IPFS</a> in the sense that it is also a decentralized storage technology. The difference is that IPFS has <a href="https://filecoin.io/">Filecoin</a>, a cryptocurrency, attached to it as a way of paying for storage resources, whereas Dat does not have any blockchain attached to it — it is purely a way of replicating data across multiple machines in a P2P manner.</p><p>For the project that I’ve been working on, Dat has been quite a good fit, because we wanted to build collaboration software in which several different users could each edit some document or database, and any changes to that data would get sent to anyone else who needs to have a copy of this data. We can use Dat to do this replication in a P2P manner, and Dat takes care of all the networking-level stuff, such as NAT traversal and getting through firewalls — it’s quite a tricky problem just to get the packets from one end to the other. And then we built a layer on top of that, using CRDTs, which is a way of allowing several people to edit some document or dataset and to exchange those edits in an efficient way. I think you can probably build this sort of thing on IPFS as well: you can probably ignore the Filecoin aspect and just use the P2P replication aspect, and it will probably do the job just as well.</p><p><strong>Vadim</strong>: Sure, though using IPFS might lead to lower responsiveness, because WebRTC underlying Dat connects P2P nodes directly, and IPFS works like a distributed hash table thing.</p><p><strong>Martin</strong>: Well, WebRTC is at a different level of the stack, since it’s intended mostly for connecting two people together who might be having a video call; in fact, the software we’re using for this interview right now may well be using WebRTC. And WebRTC does give you a data channel that you can use for sending arbitrary binary data over it, but building a full replication system on top of that is still quite a bit of work. And that’s something that Dat or IPFS do already.</p><p>You mentioned responsiveness — that is certainly one thing to think about. Say you wanted to build the next Google Docs in a decentralized way. With Google Docs, the unit of changes that you make is a single keystroke. Every single letter that you type on your keyboard may get sent in real time to your collaborators, which is great from the point of view of fast real-time collaboration. But it also means that over the course of writing a large document you might have hundreds of thousands of these single-character edits that accumulate, and a lot of these technologies right now are not very good at compressing this kind of editing data. You can keep all of the edits that you’ve ever made to your document, but even if you send just a hundred bytes for every single keystroke that you make and you write a slightly larger document with, say, 100,000 keystrokes, you suddenly now have 10 MB of data for a document that would only be a few tens of kilobytes normally. So we have this huge overhead for the amount of data that needs to be sent around, unless we get more clever at compressing and packaging up changes.</p><p>Rather than sending somebody the full list of every character that has ever been typed, we might just send the current state of the document, and after that we send any updates that have happened since. But a lot of these peer-to-peer systems don’t yet have a way of doing those state snapshots in a way that would be efficient enough to use them for something like Google Docs. This is actually an area I’m actively working on, trying to find better algorithms for synchronizing up different users for something like a text document, where we don’t want to keep every single keystroke because that would be too expensive, and we want to make more efficient use of the network bandwidth.</p><h3>New CRDTs. Formal verification with Isabelle</h3><p><strong>Vadim</strong>: Have you managed to compress that keystroke data substantially? Have you invented new CRDTs or anything similar?</p><p><strong>Martin</strong>: Yes. So far we only have prototypes for this, it’s not yet fully implemented, and we still need to do some more experiments to measure how efficient it actually is in practice. But we have developed some compression schemes that look very promising. In my prototype I reduced it from about 100 bytes per edit to something like 1.7 bytes of overhead per edit. And that’s a lot more reasonable of course. But as I say, these experiments are still ongoing, and the number might still change slightly. But I think the bottom line is that there’s a lot of room there for optimization still, so we can still make it a lot better.</p><p><strong>Vadim</strong>: So this is what <a href="https://hydraconf.com/2019/talks/6i4lkw8pwjnadgff5ylr11/">your talk</a> will be about at the Hydra conference, am I right?</p><p><strong>Martin</strong>: Yes, exactly. I’ll give a quick introduction to the area of CRDTs, collaborative software and some of the problems that arise in that context. Then I’ll describe some of the research that we’ve been doing in this area. It’s been quite fun because the research we’ve been doing has been across a whole range of different concerns. On the very applied side, we’ve got a JavaScript implementation of these algorithms, and we’re using that to build real pieces of software, trying to use that software ourselves to see how it behaves. On the other end of the spectrum, we’ve been working with formal methods to prove these algorithms correct, because some of these algorithms are quite subtle and we want to be very sure that the systems we’re making are actually correct, i.e. that they always reach a consistent state. There have been a lot of algorithms in the past that have actually failed to do that, which were simply wrong, that is, in certain edge cases, they would remain permanently inconsistent. And so, in order to avoid these problems that algorithms have had in the past, we’ve been using formal methods to prove our algorithms correct.</p><p><strong>Vadim:</strong> Wow. Do you really use theorem provers, like Coq or Isabelle or anything else?</p><p><strong>Martin</strong>: Exactly, we’ve been using Isabelle for that.</p><blockquote>You can attend <a href="https://thestrangeloop.com/2019/correctness-proofs-of-distributed-systems-with-isabelle.html">Martin’s talk</a> “Correctness proofs of distributed systems with Isabelle” at The Strange Loop conference in September.</blockquote><p><strong>Vadim</strong>: Sounds great! Are those proofs going to be published?</p><p><strong>Martin</strong>: Yes, our first set of proofs is already public. We <a href="https://martin.kleppmann.com/papers/crdt-isabelle-oopsla17.pdf">published</a> that a year and a half ago: it was a framework for verifying CRDTs, and we verified three particular CRDTs within that framework, the main one of which was RGA (<a href="http://csl.skku.edu/papers/jpdc11.pdf">Replicated Growable Array</a>), which is a CRDT for collaborative text editing. While it is not very complicated, it is quite a subtle algorithm, and so it’s a good case where proof is needed, because it’s not obvious just from looking at it that it really is correct. And so the proof gives us the additional certainty that it really is correct. Our previous work there was on verifying a couple of existing CRDTs, and our most recent work in this area is about our own CRDTs for new data models we’ve been developing, and proving our own CRDTs correct as well.</p><p><strong>Vadim</strong>: How much larger is the proof compared to the description of the algorithm? Because it can be a problem sometimes.</p><p><strong>Martin</strong>: Yes, that is a problem — the proofs are often a lot of work. I think in our latest example… Actually, let me have a quick look at the code. The description of the algorithm and the data structures is about 60 lines of code. So it’s quite a small algorithm. The proof is over 800 lines. So we’ve got roughly 12:1 ratio between the proof and the code. And that is unfortunately quite typical. The proof is a large amount of additional work. On the other hand, once we have the proof, we have gained very strong certainty in the correctness of the algorithm. Moreover, we have ourselves, as humans, understood the algorithm much better. Often I find that through trying to formalize it, we end up understanding the thing we’re trying to formalize much better than we did before. And that in itself is actually a useful outcome from this work: besides the proof itself we gain a deeper understanding, and that is often very helpful for creating better implementations.</p><p><strong>Vadim</strong>: Could you please describe the target audience of your talk, how hardcore is it going to be? What is the preliminary knowledge you expect the audience to have?</p><p><strong>Martin</strong>: I like to make my talks accessible with as little previous knowledge requirement as possible, and I try to lift everybody up to the same level. I cover a lot of material, but I start at a low base. I would expect people to have some general distributed systems experience: how do you send some data over a network using TCP, or maybe a rough idea of how Git works, which is quite a good model for these things. But that’s about all you need, really. Then, understanding the work we’ve been doing on top of that is actually not too difficult. I explain everything by example, using pictures to illustrate everything. Hopefully, everybody will be able to follow along.</p><h3>Event sourcing. Low level approach. XA transactions</h3><p><strong>Vadim</strong>: Sounds really great. Actually, we have some time and I would like to discuss one of your <a href="https://queue.acm.org/detail.cfm?id=3321612">recent articles</a> about online event processing. You’re a great supporter of the idea of event sourcing, is that correct?</p><p><strong>Martin</strong>: Yes, sure.</p><p><strong>Vadim</strong>: Nowadays this approach is getting momentum, and in the pursuit of all the advantages of globally ordered log of operations, many engineers try to deploy it everywhere. Could you please describe some cases where event sourcing is not the best option? Just to prevent its misuse and possible disappointment with the approach itself.</p><p><strong>Martin</strong>: There are two different layers of the stack that we need to talk about first. Event sourcing, as proposed by Greg Young and some others, is intended as a mechanism for data modeling, that is: if you have a database schema and you’re starting to lose control of it because there are so many different tables and they’re all getting modified by different transactions — then event sourcing is a way of bringing better clarity to this data model, because the events can express very directly what is happening at a business level. What is the action that the user took? And then, the consequences of that action might be updating various tables and so on.Effectively, what you’re doing with event sourcing is you’re separating out the action (the event) from its effects, which happen somewhere downstream.</p><p>I’ve come to this area from a slightly different angle, which is a lower-level point of view of using systems like Kafka for building highly scalable systems. This view is similar in the sense that if you’re using something like Kafka you are using events, but it doesn’t mean you’re necessarily using event sourcing. And conversely, you don’t need to be using Kafka in order to do event sourcing; you could do event sourcing in a regular database, or you could use a special database that was designed specifically for event sourcing. So these two ideas are similar, but neither requires the other, they just have some overlap.</p><p>The case for wanting to use a system like Kafka is mostly the scalability argument: in that case you’ve simply got so much data coming in that you cannot realistically process it on a single-node database, so you have to partition it in some way, and using an event log like Kafka gives you a good way of spreading that work over multiple machines. It provides a good, principled way for scaling systems. It’s especially useful if you want to integrate several different storage systems. So if, for example, you want to update not just your relational database but also, say, a full-text search index like Elasticsearch, or a caching system like Memcached or Redis or something like that, and you want one event to have an updating effect on all of these different systems, then something like Kafka is very useful.</p><p>In terms of the question you asked (what are the situations in which I would not use this event sourcing or event log approach) — I think it’s difficult to say precisely, but as a rule of thumb I would say: use whatever is the simplest. That is, whatever is closest to the domain that you’re trying to implement. And so, if the thing you’re trying to implement maps very nicely to a relational database, in which you just insert and update and delete some rows, then just use a relational database and insert and update and delete some rows. There’s nothing wrong with relational databases and using them as they are. They have worked fine for us for quite a long time and they continue to do so. But if you’re finding yourself in a situation where you’re really struggling to use that kind of database, for example because the complexity of the data model is getting out of hand, then it makes sense to switch to something like an event sourcing approach.</p><p>And similarly, on the lower level (scalability), if the size of your data is such that you can just put it in PostgreSQL on a single machine — that’s probably fine, just use PostgreSQL on a single machine. But if you’re at the point where there is no way that a single machine can handle your load, you have to scale across a large system, then it starts making sense to look into more distributed systems like Kafka. I think the general principle here is: use whatever is simplest for the particular task you’re trying to solve.</p><p><strong>Vadim</strong>: It’s really good advice. As your system evolves you can’t precisely predict the direction of development, all the queries, patterns and data flows.</p><p><strong>Martin</strong>: Exactly, and for those kinds of situations relational databases are amazing, because they are very flexible, especially if you include the JSON support that they now have. PostgreSQL now has pretty good support for JSON. You can just add a new index if you want to query in a different way. You can just change the schema and keep running with the data in a different structure. And so if the size of the data set is not too big and the complexity is not too great, relational databases work well and provide a great deal of flexibility.</p><p><strong>Vadim</strong>: Let’s talk a little bit more about event sourcing. You mentioned an interesting example with several consumers consuming events from one queue based on Kafka or something similar. Imagine that new documents get published, and several systems are consuming events: a search system based on Elasticsearch, which makes the documents searchable, a caching system which puts them into key-value cache based on Memcached, and a relational database system which updates some tables accordingly. A document might be a car selling offer or a realty advert. All these consuming systems work simultaneously and concurrently.</p><p><strong>Martin</strong>: So your question is how do you deal with the fact that if you have these several consumers, some of them might have been updated, but the others have not yet seen an update and are still lagging behind slightly?</p><p><strong>Vadim</strong>: Yes, exactly. A user comes to your website, enters a search query, gets some search results and clicks a link. But she gets 404 HTTP status code because there is no such entity in the database, which hasn’t been able to consume and persist the document yet.</p><p><strong>Martin</strong>: Yes, this is a bit of a challenge actually. Ideally, what you want is what we would call “causal consistency” across these different storage systems. If one system contains some data that you depend on, then the other systems that you look at will also contain those dependencies. Unfortunately, putting together that kind of causal consistency across different storage technologies is actually very hard, and this is not really the fault of event sourcing, because no matter what approach or what system you use to send the updates to the various different systems, you can always end up with some kind of concurrency issues.</p><p>In your example of writing data to both Memcached and Elasticsearch, even if you try to do the writes to the two systems simultaneously you might have a little bit of network delay, which means that they arrive at slightly different times on those different systems, and get processed with slightly different timing. And so somebody who’s reading across those two systems may see an inconsistent state. Now, there are some research projects that are at least working towards achieving that kind of causal consistency, but it’s still difficult if you just want to use something like Elasticsearch or Memcached or so off the shelf.</p><p>A good solution here would be that you get presented, conceptually, with a consistent point-in-time snapshot across both the search index and the cache and the database. If you’re working just within a relational database, you get something called snapshot isolation, and the point of snapshot isolation is that if you’re reading from the database, it looks as though you’ve got your own private copy of the entire database. Anything you look at in the database, any data you query will be the state as of that point in time, according to the snapshot. So even if the data has afterwards been changed by another transaction, you will actually see the older data, because that older data forms part of a consistent snapshot.</p><p>And so now, in the case where you’ve got Elasticsearch and Memcached, really what you would ideally want is a consistent snapshot across these two systems. But unfortunately, neither Memcached nor Redis nor Elasticsearch have an efficient mechanism for making those kinds of snapshots that can be coordinated with different storage systems. Each storage system just thinks for itself and typically presents you the latest value of every key, and it doesn’t have this facility for looking back and presenting a slightly older version of the data, because the most recent version of the data is not yet consistent.</p><p>I don’t really have a good answer for what the solution would look like. I fear that the solution would require code changes to any of the storage systems that participate in this kind of thing. So it will require changes to Elasticsearch and to Redis and to Memcached and any other systems. And they would have to add some kind of mechanism for point-in-time snapshots that is cheap enough that you can be using it all the time, because you might be wanting the snapshot several times per second — it’s not just a once-a-day snapshot, it’s very fine-grained. And at the moment the underlying systems are not there in terms of being able to do these kinds of snapshots across different storage systems. It’s a really interesting research topic. I’m hoping that somebody will work on it, but I haven’t seen any really convincing answers to that problem yet so far.</p><p><strong>Vadim</strong>: Yeah, we need some kind of shared <a href="https://en.wikipedia.org/wiki/Multiversion_concurrency_control">Multiversion Concurrency Control</a>.</p><p><strong>Martin</strong>: Exactly, like the distributed transaction systems. XA distributed transactions will get you some of the way there, but unfortunately XA, as it stands, is not really very well suited because it only works if you’re using locking-based concurrency control. This means that if you read some data, you have to take a lock on it so that nobody can modify that data while you have that lock. And that kind of locking-based concurrency control has terrible performance, so no system actually uses that in practice nowadays. But if you don’t have that locking then you don’t get the necessary isolation behavior in a system like XA distributed transactions. So maybe what we need is a new protocol for distributed transactions that allows snapshot isolation as the isolation mechanism across different systems. But I don’t think I’ve seen anything that implements that yet.</p><p><strong>Vadim</strong>: Yes, I hope somebody is working on it.</p><p><strong>Martin</strong>: Yes, it would be really important. Also in the context of microservices, for example: the way that people promote that you should build microservices is that each microservice has its own storage, its own database, and you don’t have one service directly accessing the database of another service, because that would break the encapsulation of the service. Therefore, each service just manages its own data.</p><p>For example, you have a service for managing users, and it has a database for the users, and everyone else who wants to find out something about users has to go through the user service. From the point of view of encapsulation that is nice: you’re hiding details of the database schema from the other services for example.</p><p>But from the point of view of consistency across different services — well, you’ve got a huge problem now, because of exactly the thing we were discussing: we might have data in two different services that depends upon each other in some way, and you could easily end up with one service being slightly ahead of or slightly behind the other in terms of timing, and then you could end up with someone who reads across different services, getting inconsistent results. And I don’t think anybody building microservices currently has an answer to that problem.</p><p><strong>Vadim</strong>: It is somewhat similar to workflows in our society and government, which are inherently asynchronous and there are no guarantees of delivery. You can get your passport number, then you can change it, and you need to prove that you changed it, and that you are the same person.</p><p><strong>Martin</strong>: Yes, absolutely. As humans we have ways of dealing with this, for example, we might know that oh, sometimes that database is a bit outdated, I’ll just check back tomorrow. And then tomorrow it’s fine. But if it’s software that we’re building, we have to program all that kind of handling into the software. The software can’t think for itself.</p><p><strong>Vadim</strong>: Definitely, at least not yet. I have another question about the advantages of event sourcing. Event sourcing gives you the ability to stop processing events in case of a bug, and resume consuming events having deployed the fix, so that the system is always consistent. It’s a really strong and useful property, but it might not be acceptable in some cases like banking where you can imagine a system that continues to accept financial transactions, but the balances are stale due to suspended consumers waiting for a bugfix from developers. What might be a workaround in such cases?</p><p><strong>Martin</strong>: I think it’s a bit unlikely to stop the consumer, deploying the fix and then restart it, because, as you say, the system has got to continue running, you can’t just stop it. I think what is more likely to happen is: if you discover a bug, you let the system continue running, but while it continues running with the buggy code, you produce another version of the code that is fixed, you deploy that fixed version separately and run the two in parallel for a while. In the fixed version of the code you might go back in history and reprocess all of the input events that have happened since the buggy code was deployed, and maybe write the results to a different database. Once you’ve caught up again you’ve got two versions of the database, which are both based on the same event inputs, but one of the two processed events with the buggy code and the other processed the events with the correct code. At that point you can do the switchover, and now everyone who reads the data is going to read the correct version instead of the buggy version, and you can shut down the buggy version. That way you never need to stop the system from running, everything keeps working all the time. And you can take the time to fix the bug, and you can recover from the bug because you can reprocess those input events again.</p><p><strong>Vadim</strong>: Indeed, it’s a really good option if the storage systems are under your control, and we are not talking about side effects applied to external systems.</p><p><strong>Martin</strong>: Yes, you’re right, once we send the data to external systems it gets more difficult because you might not be able to easily correct it. But this is again something you find in financial accounting, for example. In a company, you might have quarterly accounts. At the end of the quarter, everything gets frozen, and all of the revenue and profit calculations are based on the numbers for that quarter. But then it can happen that actually, some delayed transaction came in, because somebody forgot to file a receipt in time. The transaction comes in after the calculations for the quarter have been finalized, but it still belongs in that earlier quarter.</p><p>What accountants do in this case is that in the next quarter, they produce corrections to the previous quarter’s accounts. And typically those corrections will be a small number, and that’s no problem because it doesn’t change the big picture. But at the same time, everything is still accounted for correctly. At the human level of these accounting systems that has been the case ever since accounting systems were invented, centuries ago. It’s always been the case that some late transactions would come in and change the result for some number that you thought was final, but actually, it wasn’t because the correction could still come in. And so we just build the system with the mechanism to perform such corrections. I think we can learn from accounting systems and apply similar ideas to many other types of data storage systems, and just accept the fact that sometimes they are mostly correct but not 100% correct and the correction might come in later.</p><p><strong>Vadim</strong>: It’s a different point of view to building systems.</p><p><strong>Martin</strong>: It is a bit of a new way of thinking, yes. It can be disorienting when you come across it at first. But I don’t think there’s really a way round it, because this impreciseness is inherent in the fact that we do not know the entire state of the world — it is fundamental to the way distributed systems work. We can’t just hide it, we can’t pretend that it doesn’t happen, because that imprecision is necessarily exposed in the way we process the data.</p><h3>Professional growth and development</h3><p><strong>Vadim</strong>: Do you think that conferences like Hydra are anticipated? Most distributed systems are quite different, and it is hard to imagine that many attendees will get to work and will start applying what they have learned in day-to-day activities.</p><p><strong>Martin</strong>: It is broad, but I think that a lot of the interesting ideas in distributed systems are conceptual. So the insights are not necessarily like “use this database” or “use this particular technology”. They are more like ways of thinking about systems and about software. And those kinds of ideas can be applied quite widely. My hope is that when attendees go away from this conference, the lessons they take away are not so much what piece of software they should be using or which programming language they should be using — really, I don’t mind about that — but more like how to <em>think</em> about the systems they are building.</p><p><strong>Vadim</strong>: Why do you think it’s important to give conference talks on such complex topics as your talk, compared to publishing papers, covering all their details and intricacies? Or should anyone do both?</p><p><strong>Martin</strong>: I think they serve different purposes. When we write papers, the purpose is to have a very definitive, very precise analysis of a particular problem, and to go really deep in that. On the other hand, the purpose of a talk is more to get people interested in a topic and to start a conversation around it. I love going to conferences partly because of the discussions I then have around the talk, where people come to me and say: “oh, we tried something like this, but we ran into this problem and that problem, what do you think about that?” Then I get to think about other people’s problems, and that’s really interesting because I get to learn a lot from that.</p><p>So, from my point of view, the selfish reason for going to conferences is really to learn from other people, what their experiences have been, and to help share the experiences that we’ve made in the hope that other people will find them useful as well. But fundamentally, a conference talk is often an introduction to a subject, whereas a paper is a deep analysis of a very narrow question. I think those are different genres and I think we need both of them.</p><p><strong>Vadim</strong>: And the last question. How do you personally grow as a professional engineer and a researcher? Could you please recommend any conferences, blogs, books, communities for those who wish to develop themselves in the field of distributed systems?</p><p><strong>Martin</strong>: That’s a good question. Certainly, there are things to listen to and to read. There’s no shortage of conference talks that have been recorded and put online. There are books like my own book for example, which provides a bit of an introduction to the topic, but also lots of references to further reading. So if there are any particular detailed questions that you’re interested in, you can follow those references and find the original papers where these ideas were discussed. They can be a very valuable way of learning about something in greater depth.</p><p>A really important part is also trying to implement things and seeing how they work out in practice, and talking to other people and sharing your experiences. Part of the value of a conference is that you get to talk to other people as well, live. But you can have that through other mechanisms as well; for example, there’s a Slack channel that people have set up for people <a href="https://dist-sys-slack.herokuapp.com/">interested in distributed systems</a>. If that’s your thing you can join that. You can, of course, talk to your colleagues in your company and try to learn from them. I don’t think there’s one right way of doing this — there are many different ways through which you can learn and get a deeper experience, and different paths will work for different people.</p><p><strong>Vadim</strong>: Thank you very much for your advice and interesting discussion! It has been a pleasure talking to you.</p><p><strong>Martin</strong>: No problem, yeah, it’s been nice talking to you.</p><p><strong>Vadim</strong>: Let’s meet on July 11 <a href="https://hydraconf.com/?utm_source=medium&amp;utm_medium=kleppman">at the conference</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=28a680d99ae6" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>