Thursday, October 31, 2019

SOSP'19 Day 0

I attended SOSP this week. SOSP is the premier conference on systems where 500+ researchers follow 30+ paper presentations in a single-track event over three days. SOSP is held every two years --on odd years, alternating with OSDI which is held on the even years.

This was my third SOSP. I had been to SOSP 2009 at Big Sky Montana and SOSP 2013 at Nemacolin Pennsylvania. It is always a treat to attend SOSP. I get to learn new ideas and meet with interesting people. SOSP never fails to impress me with the quality of papers and presentations. I attended almost all of the sessions on Monday and Tuesday and took a lot of notes. I will be releasing these notes over the next 4-5 posts as I find some free time to edit and post them. You can see the entire program here and download the papers freely as open access.

Today, I will just talk about day 0 and the opening of day 1.

Driving to SOSP

Abutalib, a final year PhD student at CMU, had offered to give me a ride to the conference. At Buffalo, I was on his drive to the conference from Pittsburgh, PA to Huntsville, Ontario, Canada. Talib and his labmate/coauthor Michael came to pick me up at 2pm on Sunday. We ate lunch at my house, and left at 3pm. We had 4 hours of driving from Buffalo to Huntsville.  We reached the Canadian border in 30 minutes, there were no lines, and the border check took less than a minute.

After the border, we had 3.5 hours of driving left. Talib had a paper on the conference titled "File Systems Unfit as Distributed Storage Backends: Lessons from 10 Years of Ceph Evolution". (Talib is on the academic job market this year, and he is an excellent candidate for you to hire.) I listened to Talib's presentation, then Talib retired to work more on his presentation. I then moved to the front seat and chatted with Michael for the rest of the drive. It was an interesting chat, and we didn't feel how the time passed.

Michael is a third year PhD student. We talked about CMU PhD course requirements. CMU requires just 6 courses for PhD, as they like the students to focus more on research and not get too distracted with many courses. On the other hand, CMU has a TAship requirement, which is not required in other schools. Regardless of their funding for PhD, the PhD students are required to do a TAship for two semesters. I think this is a good training for becoming faculty.

Michael had taken the distributed systems class, where they had an influential distributed systems paper to read every single day. He had also taken an advanced cloud computing course which covered topics like MapReduce, Spark, Yarn, etc. The course was co-taught by three instructors, who alternated covering certain topics. The course put a big emphasis on "cost", as that is an essential component of the cloud computing model. The students were given limited cloud credits and had to complete the three course projects within this budget. After all, an engineer is one who can do for a dollar what any fool can do for two.

We talked about the big data processing ecosystem. Spark seems to be unrivaled for big data processing. But there is still a gap in distributed machine learning. Tensorflow is not easy to use for distributed machine learning, and Pytorch may be grabbing a good ground there. Michael's PhD research will focus on using efficient compression algorithms for machine learning and DNNs, and briefly chatted about work on those topics.

We talked a lot about blockchains and their value proposition. I think I yakked a lot about Ben-Or, Texel, and decentralized consensus in blockchains.  We talked about TLA+, and its value proposition.

Day 0 evening

We were at the DeerHurst resort, Huntsville Ontario, by 7:30pm. The SOSP registration desk was still open, so we picked our SOSP badges, and walked to the hotel reception to check in. While checking in, I ran into Robbert Van Rennesse, and we talked about his work on Texel consensus for a while.

After I got to my room and drop my bags, I went down to the lobby because there were many SOSP attendees chatting there. It seemed like we had the entire hotel to ourselves, and 500+ geeks would be the main event for the coming three days.

I saw Marcos and Indranil whom I know before, so I joined in their conversation. Mahesh from Facebook was also there. So I had already found  distributed systems folks in the conference. We chatted for more than thirty minutes, standing in the lobby. We talked about Paxos variants. Both Marcos and Mahesh are working with a product group, so we talked about how great engineers enrich projects. We talked about California power outages. We talked about how hard it is to get a paper accepted at SOSP, and how hard it is to receive and process negative reviews, especially bad and unfair ones. We talked about the need for a dedicated distributed *systems* conference.

Day 1 SOSP opening

After breakfast, SOSP'19 kicked off at 8:45am with a short address from the general chairs, Tim Brecht (University of Waterloo) and Carey Williamson (University of Calgary). Then PC Chairs Remzi H. Arpaci-Dusseau (University of Wisconsin) and Yuanyuan Zhou (University of California San Diego) took the stage for brief remarks, thanks, and acknowledgment.

SOSP’19 received a total of 276 paper submissions, reviewed by the program committee (PC) of 55 reviewers. All papers received three reviews in the first round. Based on first round reviews, 154 papers were selected to proceed to the second round, and each then received additional reviews. In total more than 1200 reviews, totaling over 1 million words of feedback. Ultimately the conference accepted papers 38 papers, bringing the acceptance rate to 13%. The best paper awards for the conference were awarded to

This year SOSP organized for the first time artifact evaluation led by Profs. Baris Kasikci and Vijay Chidambaram, and organized by Supreeth Shastri. 23 of the 38 papers were submitted for artifact evaluation. 22 of these earned at least one page, 11 papers earned all badges, and 12 papers had all their results reproduced.

This year there was also a student mentorship program organized by Natacha Crooks and Malte Schwarzkopf. The program matched PhD students to postdoctoral research associates or faculty members and researchers in their research area of interest for meeting at the conference. Of course most PhD students already get mentorship from their advisors, but this program was valuable to show how the community is a welcoming one to the students.

Tuesday, October 22, 2019

Book review. A Mind at Play: How Claude Shannon Invented the Information Age

This book was published by Jimmy Soni and Rob Goodman in 2017. It is 385 pages long and informative.

This is a good book. Shannon is already an extremely interesting researcher, so the book is interesting. The writing is good, gets very good at some places, but it is not top-class writing. A master storyteller like Michael Lewis ( e.g., "Undoing Project"), Walter Isaacson, or Steven Levy would have made this book excellent. I guess the difference would be that these masters would put in an order of magnitude more research in to the subject, do dozens of interviews, and extensive archive search. They would also distill the story and build the book around a single strong theme with some side themes tying to that, and tell a much more engaging story. They would not leave a stone unturned. They would go the extra mile to point us to the insights they gathered, without explicitly showing them, but gently nudging us toward them to make us think we came up with those insights.

Claude Shannon is a giant. It won't be an overstatement to say Shannon is the father or digital era and information age. In his master's thesis at MIT, in 1937 when he was only 21 years old, he came up with the digital circuit design theory, demonstrating the electrical applications of Boolean algebra. In the book review for "Range: Why Generalists Triumph in a Specialized World", I had included this paragraph about Shannon.
[Shannon] launched the Information Age thanks to a philosophy course he took to fulfill a requirement at the University of Michigan. In it, he was exposed to the work of self-taught nineteenth-century English logician George Boole, who assigned a value of 1 to true statements and 0 to false statements and showed that logic problems could be solved like math equations. It resulted in absolutely nothing of practical importance until seventy years after Boole passed away, when Shannon did a summer internship at AT&T’s Bell Labs research facility.

For his PhD in 1940, under supervision of Vannevar Bush, Shannon developed a mathematical formulation for Mendelian genetics, called "An Algebra for Theoretical Genetics".

Then in 1948, eleven years later after his MS thesis, he founded information theory with a landmark paper, "A Mathematical Theory of Communication", with applications to digital communication, storage, and cryptography.

He has been very influential in cryptography (with the introduction of one-time pads), artificial intelligence (with his electromechanical mouse Theseus), chess playing computers, and in providing a mathematical theory of juggling, among other things.

The tragic part of this story is how it ends. After suffering progressive decline of Alzheimer's disease over more than 15 years, Shannon died at the age of 84, on February 24, 2001.

As is my custom in book reviews, here are some of my highlights from the book. The book has many more interesting facts and information about Shannon, so I recommend the book strongly if you want to learn more about Shannon.

Shannon's research approach

Of course, information existed before Shannon, just as objects had inertia before Newton. But before Shannon, there was precious little sense of information as an idea, a measurable quantity, an object fitted out for hard science. Before Shannon, information was a telegram, a photograph, a paragraph, a song. After Shannon, information was entirely abstracted into bits.

He was a man immune to scientific fashion and insulated from opinion of all kinds, on all subjects, even himself, especially himself; a man of closed doors and long silences, who thought his best thoughts in spartan bachelor apartments and empty office buildings.
             
It is a puzzle of his life that someone so skilled at abstracting his way past the tangible world was also so gifted at manipulating it. Shannon was a born tinkerer: a telegraph line rigged from a barbed-wire fence, a makeshift barn elevator, and a private backyard trolley tell the story of his small-town Michigan childhood. And it was as an especially advanced sort of tinkerer that he caught the eye of Vannevar Bush—soon to become the most powerful scientist in America and Shannon’s most influential mentor—who brought him to MIT and charged him with the upkeep of the differential analyzer, an analog computer the size of a room, “a fearsome thing of shafts, gears, strings, and wheels rolling on disks” that happened to be the most advanced thinking machine of its day.

Shannon’s study of the electrical switches directing the guts of that mechanical behemoth led him to an insight at the foundation of our digital age: that switches could do far more than control the flow of electricity through circuits—that they could be used to evaluate any logical statement we could think of, could even appear to "decide." A series of binary choices—on/off, true/false, 1/0—could, in principle, perform a passable imitation of a brain. That leap, as Walter Isaacson put it, “became the basic concept underlying all digital computers.” It was Shannon’s first great feat of abstraction. He was only twenty-one.
             
And yet Shannon proved that noise could be defeated, that information sent from Point A could be received with perfection at Point B, not just often, but essentially always. He gave engineers the conceptual tools to digitize information and send it flawlessly (or, to be precise, with an arbitrarily small amount of error), a result considered hopelessly utopian up until the moment Shannon proved it was not.
             
Having completed his pathbreaking work by the age of thirty-two, he might have spent his remaining decades as a scientific celebrity, a public face of innovation: another Bertrand Russell, or Albert Einstein, or Richard Feynman, or Steve Jobs. Instead, he spent them tinkering. An electronic, maze-solving mouse named Theseus. An Erector Set turtle that walked his house. The first plan for a chess-playing computer, a distant ancestor of IBM’s Deep Blue. The first-ever wearable computer. A calculator that operated in Roman numerals, code-named THROBAC (“Thrifty Roman-Numeral Backward-Looking Computer”). A fleet of customized unicycles. Years devoted to the scientific study of juggling.

Claude’s gifts were of the Einsteinian variety: a strong intuitive feel for the dimensions of a problem, with less of a concern for the step-by-step details. As he put it, “I think I’m more visual than symbolic. I try to get a feeling of what’s going on. Equations come later.” Like Einstein, he needed a sounding board, a role that Betty played perfectly. His colleague David Slepian said, “He didn’t know math very deeply. But he could invent whatever he needed.” Robert Gallager, another colleague, went a step further: “He had a weird insight. He could see through things. He would say, ‘Something like this should be true’ . . . and he was usually right. . . . You can’t develop an entire field out of whole cloth if you don’t have superb intuition.”

I had what I thought was a really neat research idea, for a much better communication system than what other people were building, with all sorts of bells and whistles. I went in to talk to him [Shannon] about it and I explained the problems I was having trying to analyze it. And he looked at it, sort of puzzled, and said, “Well, do you really need this assumption?” And I said, well, I suppose we could look at the problem without that assumption. And we went on for a while. And then he said, again, “Do you need this other assumption?” And I saw immediately that that would simplify the problem, although it started looking a little impractical and a little like a toy problem. And he kept doing this, about five or six times. I don’t think he saw immediately that that’s how the problem should be solved; I think he was just groping his way along, except that he just had this instinct of which parts of the problem were fundamental and which were just details. At a certain point, I was getting upset, because I saw this neat research problem of mine had become almost trivial. But at a certain point, with all these pieces stripped out, we both saw how to solve it. And then we gradually put all these little assumptions back in and then, suddenly, we saw the solution to the whole problem. And that was just the way he worked. He would find the simplest example of something and then he would somehow sort out why that worked and why that was the right way of looking at

“What’s your secret in remaining so carefree?” an interviewer asked Shannon toward the end of his life. Shannon answered, “I do what comes naturally, and usefulness is not my main goal. I keep asking myself, How would you do this? Is it possible to make a machine do that? Can you prove this theorem?” For an abstracted man at his most content, the world isn’t there to be used, but to be played with, manipulated by hand and mind. Shannon was an atheist, and seems to have come by it naturally, without any crisis of faith; puzzling over the origins of human intelligence with the same interviewer, he said matter-of-factly, “I don’t happen to be a religious man and I don’t think it would help if I were!” And yet, in his instinct that the world we see merely stands for something else, there is an inkling that his distant Puritan ancestors might have recognized as kin.

University of Michigan

A’s in math and science and Latin, scattered B’s in the rest: the sixteen-year-old high school graduate sent his record off to the University of Michigan, along with an application that was three pages of fill-in-the-blanks, the spelling errors casually crossed out.
             
Engineering’s rising profile began to draw the attention of deans in other quarters of the university, and disciplinary lines began to blur. By the time Shannon began his dual degrees in mathematics and engineering, a generation later, the two curricula had largely merged into one.
             

MIT

The job—master’s student and assistant on the differential analyzer at the Massachusetts Institute of Technology—was tailor-made for a young man who could find equal joy in equations and construction, thinking and building. "I pushed hard for that job and got it."
             
It was Vannevar Bush who brought analog computing to its highest level, a machine for all purposes, a landmark on the way from tool to brain. And it was Claude Shannon who, in a genius accident, helped obsolete it.
             
In Michigan, Shannon had learned (in a philosophy class, no less) that any statement of logic could be captured in symbols and equations—and that these equations could be solved with a series of simple, math-like rules. You might prove a statement true or false without ever understanding what it meant. You would be less distracted, in fact, if you chose not to understand it: deduction could be automated. The pivotal figure in this translation from the vagaries of words to the sharpness of math was a nineteenth-century genius named George Boole, a self-taught English mathematician whose cobbler father couldn’t afford to keep him in school beyond the age of sixteen.

Finished in the fall of 1937, Shannon’s master’s thesis, “A Symbolic Analysis of Relay and Switching Circuits,” was presented to an audience in Washington, D.C., and published to career-making applause the following year.
             
A leap from logic to symbols to circuits: “I think I had more fun doing that than anything else in my life,” Shannon remembered fondly. An odd and wonkish sense of fun, maybe—but here was a young man, just twenty-one now, full of the thrill of knowing that he had looked into the box of switches and relays and seen something no one else had. All that remained were the details. In the years to come, it would be as if he forgot that publication was something still required of brilliant scientists; he’d pointlessly incubate remarkable work for years, and he’d end up in a house with an attic stuffed with notes, half-finished articles, and “good questions” on ruled paper. But now, ambitious and unproven, he had work pouring out of him.
             
Armed with these insights, Shannon spent the rest of his thesis demonstrating their possibilities. A calculator for adding binary numbers; a five-button combination lock with electronic alarm—as soon as the equations were worked out, they were as good as built. Circuit design was, for the first time, a science. And turning art into science would be the hallmark of Shannon’s career.
                             

Vannevar Bush

More to the point, it was a matter of deep conviction for Bush that specialization was the death of genius. “In these days, when there is a tendency to specialize so closely, it is well for us to be reminded that the possibilities of being at once broad and deep did not pass with Leonardo da Vinci or even Benjamin Franklin,” Bush said in a speech at MIT.
             
Somewhere on the list of Vannevar Bush’s accomplishments, then, should be his role in killing American eugenics. As president of the Carnegie Institution of Washington, which funded the Eugenics Record Office, he forced its sterilization-promoting director into retirement and ordered the office to close for good on December 31, 1939.
             
But the poison tree bore some useful fruit. (Few scientists had compiled better data on heredity and inheritance than eugenicists.) And Shannon was there, in its last months, to collect what he could of it [for his PhD thesis titled "An Algebra for Theoretical Genetics".]
   

Bell Labs

If Google’s “20 percent time”—the practice that frees one-fifth of a Google employee’s schedule to devote to blue-sky projects—seems like a West Coast indulgence, then Bell Labs’ research operation, buoyed by a federally approved monopoly and huge profit margins, would appear gluttonous by comparison.
             
Bell researchers were encouraged to think decades down the road, to imagine how technology could radically alter the character of everyday life, to wonder how Bell might “connect all of us, and all of our new machines, together.” One Bell employee of a later era summarized it like this: “When I first came there was the philosophy: look, what you’re doing might not be important for ten years or twenty years, but that’s fine, we’ll be there then.”
             
Claude Shannon was one of those who thrived. Among the institutions that had dotted the landscape of Shannon’s life, it’s hard to imagine a place better suited to his mix of passions and particular working style than the Bell Laboratories of the 1940s. “I had freedom to do anything I wanted from almost the day I started,” he reflected. “They never told me what to work on.”
   

War time           

Things were moving fast there, and I could smell the war coming along. And it seemed to me I would be safer working full-time for the war effort, safer against the draft, which I didn’t exactly fancy. I was a frail man, as I am now... I was trying to play the game, to the best of my ability. But not only that, I thought I’d probably contribute a hell of a lot more.

“I think he did the work with that fear in him, that he might have to go into the Army, which means being with lots of people around which he couldn’t stand. He was phobic about crowds and people he didn’t know.”
               
If anything, his reaction to the war work was quite the opposite: the whole atmosphere left a bitter taste. The secrecy, the intensity, the drudgery, the obligatory teamwork—all of it seems to have gotten to him in a deeply personal way. Indeed, one of the few accounts available to us, from Claude’s girlfriend, suggests that he found himself largely bored and frustrated by wartime projects, and that the only outlet for his private research came on his own time, late at night. “He said he hated it, and then he felt very guilty about being tired out in the morning and getting there very late. . . . I took him by the hand and sometimes I walked him to work—that made him feel better.” It’s telling that Shannon was reluctant, even decades later, to talk about this period in any kind of depth, even to family and friends. In a later interview, he would simply say, with a touch of disappointment in his words, that “those were busy times during the war and immediately afterwards and [my research] was not considered first priority work.” This was true, it appears, even at Bell Labs, famously open-minded though it may have been.
             
As in other areas of Shannon’s life, his most important work in cryptography yielded a rigorous, theoretical underpinning for many of a field’s key concepts. This paper, “A Mathematical Theory of Cryptography—Case 20878,” contained important antecedents of Shannon’s later work—but it also provided the first-ever proof of a critical concept in cryptology: the “one-time pad.”

According to Turing’s biographer, Andrew Hodges, Shannon and Turing met daily over tea, in public, in the conspicuously modest Bell Labs cafeteria.
             
Shannon, for his part, was amazed by the quality of Turing’s thinking. “I think Turing had a great mind, a very great mind,” Shannon later said.
             

Information theory                

On the evenings he was at home, Shannon was at work on a private project. It had begun to crystallize in his mind in his graduate school days. He would, at various points, suggest different dates of provenance. But whatever the date on which the idea first implanted itself in his mind, pen hadn’t met paper in earnest until New York and 1941. Now this noodling was both a welcome distraction from work at Bell Labs and an outlet to the deep theoretical work he prized so much, and which the war threatened to foreclose.
             
The work wasn’t linear; ideas came when they came. “These things sometimes... one night I remember I woke up in the middle of the night and I had an idea and I stayed up all night working on that.” To picture Shannon during this time is to see a thin man tapping a pencil against his knee at absurd hours. This isn’t a man on a deadline; it’s something more like a man obsessed with a private puzzle, one that is years in the cracking. “He would go quiet, very very quiet. But he didn’t stop working on his napkins,” said Maria. “Two or three days in a row. And then he would look up, and he’d say, ‘Why are you so quiet?’ ”
             
The real measure of information is not in the symbols we send—it’s in the symbols we could have sent, but did not. To send a message is to make a selection from a pool of possible symbols, and “at each selection there are eliminated all of the other symbols which might have been chosen.”
             
The information value of a symbol depends on the number of alternatives that were killed off in its choosing. Symbols from large vocabularies bear more information than symbols from small ones. Information measures freedom of choice.
             
Shannon proposed an unsettling inversion. Ignore the physical channel and accept its limits: we can overcome noise by manipulating our messages. The answer to noise is not in how loudly we speak, but in how we say what we say.
             
Shannon showed that the beleaguered key-tappers in Ireland and Newfoundland had essentially gotten it right, had already solved the problem without knowing it. They might have said, if only they could have read Shannon’s paper, “Please add redundancy.” In a way, that was already evident enough: saying the same thing twice in a noisy room is a way of adding redundancy, on the unstated assumption that the same error is unlikely to attach itself to the same place two times in a row. For Shannon, though, there was much more. Our linguistic predictability, our congenital failure to maximize information, is actually our best protection from error.
                             
The information theorist Sergio VerdĂș offered a similar assessment of Shannon’s paper: “It turned out that everything he claimed essentially was true. The paper was weak in what we now call ‘converses’ . . . but in fact, that adds to his genius rather than detracting from it, because he really knew what he was doing.” In a sense, leaving the dots for others to connect was a calculated gamble on Shannon’s part: had he gone through that painstaking work himself, the paper would have been much longer and appeared much later.
                       

Tinkering

Theseus was propelled by a pair of magnets, one embedded in its hollow core, and one moving freely beneath the maze. The mouse would begin its course, bump into a wall, sense that it had hit an obstacle with its “whiskers,” activate the right relay to attempt a new path, and then repeat the process until it hit its goal, a metallic piece of cheese. The relays stored the directions of the right path in “memory”: once the mouse had successfully navigated the maze by trial and error, it could find the cheese a second time with ease. Appearances to the contrary, Theseus the mouse was mainly the passive part of the endeavor: the underlying maze itself held the information and propelled Theseus with its magnet. Technically, as Shannon would point out, the mouse wasn’t solving the maze; the maze was solving the mouse. Yet, one way or another, the system was able to learn.
             
Shannon would later tell a former teacher of his that Theseus had been “a demonstration device to make vivid the ability of a machine to solve, by trial and error, a problem, and remember the solution.” To the question of whether a certain rough kind of intelligence could be “created,” Shannon had offered an answer: yes, it could. Machines could learn. They could, in the circumscribed way Shannon had demonstrated, make mistakes, discover alternatives, and avoid the same missteps again. Learning and memory could be programmed and plotted, the script written into a device that looked, from a certain perspective, like an extremely simple precursor of a brain. The idea that machines could imitate humans was nothing new.
             
In a life of pursuits adopted and discarded with the ebb and flow of Shannon’s promiscuous curiosity, chess remained one of his few lifelong pastimes. One story has it that Shannon played so much chess at Bell Labs that “at least one supervisor became somewhat worried.” He had a gift for the game, and as word of his talent spread throughout the Labs, many would try their hand at beating him. “Most of us didn’t play more than once against him,” recalled Brockway McMillan.
             
He went on: “you can make a thing that is smarter than yourself. Smartness in this game is made partly of time and speed. I can build something which can operate much faster than my neurons.”
             
I think man is a machine. No, I am not joking, I think man is a machine of a very complex sort, different from a computer, i.e., different in organization. But it could be easily reproduced—it has about ten billion nerve cells. And if you model each one of these with electronic equipment it will act like a human brain. If you take [Bobby] Fischer’s head and make a model of that, it would play like Fischer.
             

MIT professorship

MIT made the first move: in 1956, the university invited one of its most famous alumni, Claude Shannon, to spend a semester back in Cambridge as a visiting professor. Returning to his graduate school haunts had something of a revivifying effect on Claude, as well as Betty. For one thing, the city of Cambridge was a bustle of activity compared to the comparatively sleepy New Jersey suburbs. Betty remembered it as an approximation of their Manhattan years, when going out to lunch meant stepping into the urban whirl. Working in academia, too, had its charms. “There is an active structure of university life that tends to overcome monotony and boredom,” wrote Shannon. “The new classes, the vacations, the various academic exercises add considerable variety to the life here.” Reading those impersonal lines, one might miss the implication that Shannon himself had grown bored.

I am having a very enjoyable time here at MIT. The seminar is going very well but involves a good deal of work. I had at first hoped to have a rather cozy little group of about eight or ten advanced students, but the first day forty people showed up, including many faculty members from M.I.T., some from Harvard, a number of doctorate candidates, and quite a few engineers from Lincoln Laboratory. . . . I am giving 2 one and a half hour sessions each week, and the response from the class is exceptionally good. They are almost all following it at 100 percent. I also made a mistake in a fit of generosity when I first came here of agreeing to give quite a number of talks at colloquia, etc., and now that the days are beginning to roll around, I find myself pretty pressed for time.
             
In a lecture titled “Reliable Machines from Unreliable Components,” Shannon presented the following challenge: “In case men’s lives depend upon the successful operation of a machine, it is difficult to decide on a satisfactorily low probability of failure, and in particular, it may not be adequate to have men’s fates depend upon the successful operation of single components as good as they may be.” What followed was an analysis of the error-correcting and fail-safe mechanisms that might resolve such a dilemma.

When an offer came for a full professorship and a permanent move to Massachusetts, it was hard to decline. If he accepted, Shannon would be named a Professor of Communication Sciences, and Professor of Mathematics, with permanent tenure, effective January 1, 1957, with a salary of $17,000 per year (about $143,000 in 2017).
             
After accepting the MIT offer, the Shannons left for Cambridge via California—a year-long detour for a fellowship at Stanford’s Center for Advanced Study in the Behavioral Sciences. Prestigious as the appointment was, the Shannons mainly treated it as an excuse to see the country. They made the leisurely drive through the West’s national parks to California, and back, in a VW bus.
   
Before setting off for the West, though, Claude and Betty purchased a house at 5 Cambridge Street in Winchester, Massachusetts, a bedroom community eight miles north of MIT. Once their California year was complete, they returned to their new home. In Winchester, the Shannons were close enough to campus for a quick commute but far enough away to live an essentially private life. They were also living in a piece of history—an especially appropriate one in light of Shannon’s background and interests.
             
The house would figure prominently in Shannon’s public image. Nearly every story about him, from 1957 on, situated him at the house on the lake—usually in the two-story addition that the Shannons built as an all-purpose room for gadget storage and display, a space media profiles often dubbed the “toy room,” but which his daughter Peggy and her two older brothers simply called “Dad’s room.” The Shannons gave their home a name: Entropy House. Claude’s status as a mathematical luminary would make it a pilgrimage site for students and colleagues, especially as his on-campus responsibilities dwindled toward nothing.
             
Even at MIT, Shannon bent his work around his hobbies and enthusiasms. “Although he continued to supervise students, he was not really a co-worker, in the normal sense of the term, as he always seemed to maintain a degree of distance from his fellow associates,” wrote one fellow faculty member. With no particular academic ambitions, Shannon felt little pressure to publish academic papers. He grew a beard, began running every day, and stepped up his tinkering. What resulted were some of Shannon’s most creative and whimsical endeavors. There was the trumpet that shot fire out of its bell when played. The handmade unicycles, in every permutation: a unicycle with no seat; a unicycle with no pedals; a unicycle built for two. There was the eccentric unicycle: a unicycle with an off-center hub that caused the rider to move up and down while pedaling forward and added an extra degree of difficulty to Shannon’s juggling. (The eccentric unicycle was the first of its kind. Ingenious though it might have been, it caused Shannon’s assistant, Charlie Manning, to fear for his safety—and to applaud when he witnessed the first successful ride.) There was the chairlift that took surprised guests down from the house’s porch to the edge of the lake. A machine that solved Rubik’s cubes. Chess-playing machines. Handmade robots, big and small. Shannon’s mind, it seems, was finally free to bring its most outlandish ideas to mechanical life. Looking back, Shannon summed it all up as happily pointless: “I’ve always pursued my interests without much regard to financial value or value to the world. I’ve spent lots of time on totally useless things.” Tellingly, he made no distinction between his interests in information and his interests in unicycles; they were all moves in the same game.
             
One professor, Hermann Haus, remembered a lecture of his that Shannon attended. “I was just so impressed,” Haus recalled, “he was very kind and asked leading questions. In fact, one of those questions led to an entire new chapter in a book I was writing.”
             
He was not the sort of person who would give a class and say “this was the essence of such and such.” He would say, “Last night, I was looking at this and I came up with this interesting way of looking at it.” He’d say
             
Shannon became a whetstone for others’ ideas and intuitions. Rather than offer answers, he asked probing questions; instead of solutions, he gave approaches. As Larry Roberts, a graduate student of that time, remembered, “Shannon’s favorite thing to do was to listen to what you had to say and then just say, ‘What about...’ and then follow with an approach you hadn’t thought of. That’s how he gave his advice.” This was how Shannon preferred to teach: as a fellow traveler and problem solver, just as eager as his students to find a new route or a fresh approach to a standing puzzle.
             
Even with his aversion to writing things down, the famous attic stuffed with half-finished work, and countless hypotheses circulating in his mind—and even when one paper on the scale of his “Mathematical Theory of Communication” would have counted as a lifetime’s accomplishment—Shannon still managed to publish hundreds of pages’ worth of papers and memoranda, many of which opened new lines of inquiry in information theory. That he had also written seminal works in other fields—switching, cryptography, chess programming—and that he might have been a pathbreaking geneticist, had he cared to be, was extraordinary.
             

Stock market           

By then the family had no need of the additional income from stock picking. Not only was there the combination of the MIT and Bell Labs pay, but Shannon had been on the ground floor of a number of technology companies. One former colleague, Bill Harrison, had encouraged Shannon to invest in his company, Harrison Laboratories, which was later acquired by Hewlett-Packard. A college friend of Shannon, Henry Singleton, put Shannon on the board of the company he created, Teledyne, which grew to become a multibillion-dollar conglomerate. As Shannon retold the story, he made the investment simply because “I had a good opinion of him.”

The club benefited from Shannon as well, in his roles as network node and informal consultant. For instance, when Teledyne received an acquisition offer from a speech recognition company, Shannon advised Singleton to turn it down. From his own experience at the Labs, he doubted that speech recognition would bear fruit anytime soon: the technology was in its early stages, and during his time at the Labs, he’d seen much time and energy fruitlessly sunk into it. The years of counsel paid off, for Singleton and for Shannon himself: his investment in Teledyne achieved an annual compound return of 27 percent over twenty-five years.
             
The stock market was, in some ways, the strangest of Shannon’s late-life enthusiasms. One of the recurrent tropes of recollections from family and friends is Shannon’s seeming indifference to money. By one telling, Shannon moved his life savings out of his checking account only when Betty insisted that he do so. A colleague recalled seeing a large uncashed check on Shannon’s desk at MIT, which in time gave rise to another legend: that his office was overflowing with checks he was too absentminded to cash. In a way, Shannon’s interest in money resembled his other passions. He was not out to accrue wealth for wealth’s sake, nor did he have any burning desire to own the finer things in life. But money created markets and math puzzles, problems that could be analyzed and interpreted and played out.

Tuesday, October 8, 2019

Recent book diet

The last couple of months I have been listening through books using the Libby app. I highly recommend the Libby app: It connects you to your public library, and let's you search, borrow, and download audiobooks from your library easily. I used to listen to a lot of podcasts, but after I downloaded Libby, I have been listening to books mostly. Here are some of those books I listened to.

The Science of Discworld III: Darwin's Watch (2005)

This book is by Terry Pratchett, Ian Stewart and Jack Cohen. It is set on the Discworld world, and it teaches solid science while being entertaining at the same time. The book not only talked about evolution but also a lot about quantum physics, string theory and time travel (yes, the science behind time travel).

The book gives a good account of Darwin's life as well as his contemporaries, like Wallace. I think Darwin's superpower was writing. This was the Victorian era where suddenly the writers started to get and control mindshare of large fraction of population. Darwin seized on this opportunity well, as he was a talented and prolific writer.

In contrast to the myth around him, Darwin was not an atheist. The wikipedia article on the topic tells that he had a Unitarian background, but "from around 1849 Darwin stopped attending church, but Emma (his wife) and the children continued to attend services. On Sundays Darwin sometimes went with them as far as the lych gate to the churchyard, and then he would go for a walk. During the service, Emma continued to face forward when the congregation turned to face the altar for the Creed, sticking to her Unitarian faith." Darwin still believed that "God was the ultimate lawgiver" even after writing the Origin of Species. He wrote "In my most extreme fluctuations I have never been an atheist in the sense of denying the existence of a God.— I think that generally (& more and more so as I grow older) but not always, that an agnostic would be the most correct description of my state of mind."

I recommend this book highly. I think the book could have been shorter and sweeter though. Also the book was not very well organized, but it managed to stay engaging most of the time.

Ready Player One (2011)

This book was written by Ernest Cline. I liked this book, but it had an amateurish feel to it. It turns out this was Cline's first novel.

The book is written in the first person narrative (which is also the case for the Hunger Games book, which I discuss below). Do amateur writers prefer first person narrative because it is harder for them to pull a third person narrative? Is the first person narrative supposed to be more engaging? Maybe the first person narrative acts like a self-hypnosis session for the reader to role-play along.

In the book, the female protagonist, Artemis, is caricaturized to please the male target audience. She came across very submissive in her dialogs with Parzival and this bugged me a lot.

The book plot is significantly different than that of its movie adoptation. The book is all about 80s cultural references, which the author seems to be very comfortable in. I think he set up a nice futuristic world which still enabled him to make the book about 80s nerd-dom.

Overall, this is an OK book. When talking about the haptic VR suit, and the nerd culture of obsessing about stuff, the book gives a realistic but not very desirable view of the future.

Hunger Games (2008)

This book was written by Suzanne Collins. This book also felt rushed and underdeveloped, but it was engaging. The parts where the book talked about hunger and sisterly love tugged hard on the heartstrings. Maybe a bit too strongly.

(SPOILERS!)
There were big gaping plot holes in the book. In the beginning of the games, Peeta was collaborating with Careers. Then he was a ruthless killer, he finished a girl with a knife. He was also portrayed as very good with throwing knives. Later in the game, he comes off as a wimpy pacifist again. He felt very sad when he inadvertently kills Fox-face when she swiped the poisonous wild-berries he collected. What was that all about? Did no one proof-read the book before publishing?

Katniss is comically ignorant of others' feelings towards her. She is smart for other things but very dumb when it comes to reading social cues and especially romantic interests of others. The only plausible alternative to bad writing (which I can't rule out) is that she has Aspergers or Autism. (Google produces many hits for this, but the book did not develop on this line.)

The setting of the book was promising, but I don't think this got developed/analyzed enough either. I realize there are two sequels, so maybe the other books picked up on these. So I recommend to avoid the book or listen/read it with low expectations to pass time. This is easy reading/listening. I listened to this book only because I had a long drive and needed to pass time.

"What Technology Wants" (2010) and "Inevitable" (2016) by Kevin Kelly

I had high expectations going into these books. But I was disappointed by both. And frankly both books are pretty much about the same topics, and they merged in my mind into one (very very long) book.

The first book talks about technium, the ecology/culture around technology, and explores the characteristics of technium and the path of technium. It tries to make a case that technium is an organic/emergent organism, and as a child outgrowing its parents, it will leave home one day. The book already started talking about inevitabilities for technium, leading the way to the second book. The discussion about DNA being a miracle molecule was interesting. The book also mentioned that there are inevitable optimal valleys for evolution to gradient-descent into and these lead to convergent evolution. This was then connected to theories about directed evolution, and whether technium was inevitably somehow coded in our genes. Thought provoking stuff maybe, but it stalls there at the metaphoric level, without any further development, supporting arguments, or critical evaluation.

The inevitable book talks about "12 technological forces that will shape our future". These are outlined as below as quoted from the wikipedia entry:
  1. Becoming: Moving from fixed products to always upgrading services and subscriptions
  2. Cognifying: Making everything much smarter using cheap powerful AI that we get from the cloud
  3. Flowing: Depending on unstoppable streams in real-time for everything
  4. Screening: Turning all surfaces into screens
  5. Accessing: Shifting society from one where we own assets, to one where instead we will have access to services at all times
  6. Sharing: Collaboration at mass-scale 
  7. Filtering: Harnessing intense personalization in order to anticipate our desires
  8. Remixing: Unbundling existing products into their most primitive parts and then recombining in all possible ways
  9. Interacting: Immersing ourselves inside our computers to maximize their engagement
  10. Tracking: Employing total surveillance for the benefit of citizens and consumers
  11. Questioning: Promoting good questions is far more valuable than good answers
  12. Beginning: Constructing a planetary system connecting all humans and machines into a global matrix
The problem with these books are they are very long, with a lot of unnecessary filler text, and they get very boring and dry as the narrative drags on. If I were reading them I could skim and skip ahead, but listening to them I didn't get this opportunity. Another problem with the books is that the topics/ideas concerned are explored in a general and abstract manner.

Kevin Kelly is a very interesting guy. I pay attention to his short writing. But these books were not good. They would be improved a lot by cutting two thirds of them. So my recommendation is to avoid these books and read summaries/highlights from them.

MAD questions

Can we write nonfiction books with story narratives?

You can easily spoil a fictional work/story, but you cannot do that with nonfiction. I was wondering whether we can write nonfiction work with such an engaging story that readers would get angry if you gave spoilers to it.

I think good science/technology journalists already do this. Instead of a generic instance, they focus on one individual and tell the story of a disease or invention in a more personalized way. I liked the "Undoing Project" and "Flash Boys" book by Michael Lewis a lot. I would have complained hard if someone gave me spoilers about those books while I was reading them. Also the Hackers book by Steven Levy was somewhat like that.

Long ago one of my colleagues told me that he is tired of writing papers in the straightforward boring format. He said he tried to write a research paper where he developed gradually to the punchline and gave that at the end and this made the reviewers very unhappy. Today I asked him about the fate of that paper again. He told me that he made "the paper very formal and hideously complicated, so it got published".

There is a benefit to the traditional predictable format, because it makes the readers' and reviewers' job easier. But it also spoils the fun of reading the paper. I sometimes lose interest after an introduction where everything is revealed. Sometimes the only reason I read the rest of the paper is to learn some techniques in detail, or see where the authors cut corners and cheat by sneaking in assumptions/limitations not mentioned in the introduction.

They say the obvious UI is the best, but is our paper writing format where we give the spoilers in the abstract and the introduction the obviously better way to do things?

Sunday, October 6, 2019

Paper review: Comprehensive and efficient runtime checking in system software through watchdogs

This paper by Chang Lou, Peng Huang, and Scott Smith appeared in HotOS 2019. The paper argues that system software needs intrinsic detectors that  monitor internally for subtle issues specific to a process. In particular, the paper advocates employing intrinsic watchdogs as detectors. Watchdogs (also known as grenade timers) have been widely used in embedded devices. Watchdogs use a decrementing timeout counter which resets the processor when it reaches zero. To prevent a reset, the software must keep restarting the watchdog counter after performing/clearing some sanity checks.


Table 1 summarizes the comparison of crash failure detectors, intrinsic watchdogs, and error handlers. Failure detectors are too general, they just make "up-or-down" decisions. They are only good for achieving liveness, as they are too unreliable for making safety decisions.

The disadvantage with error handlers, the paper argues, is  that liveness-related failures often do not have explicit error signals that can trigger a handler: there is no signal for e.g., write being blocked indefinitely or some thread deadlocking or infinitely looping.

The mimicking approach for writing watchdog timers



The paper prescribes the mimicking approach, where the checker selects important operations from the main program, and mimics them for detecting any errors. Since the mimic checker exercises similar code logic in a production environment, it has the potential to catch and locate bugs in the program as well as faults in the environment.

The challenge with this approach is to systematically select important/representative operations from the main program. To solve this problem, the paper proposes a method using static analysis to automatically generate mimic-type watchdogs, which it calls program logic reduction.

We instead propose to derive from P a reduced but representative version W, which nonetheless retains enough code to expose gray failures. Our hypothesis that such reduction is viable stems from two insights. First, most code in P need not be checked at runtime because its correctness is logically deterministic --such code is better suited for unit testing before production and thus should be excluded from W. Second, W’s goal is to catch errors rather than to recreate all the details of P’s business logic. Therefore, W does not need to mimic the full execution of P. For example, if P invoked write() many times in a loop, for checking purposes, W may only need to invoke write() once to detect a fault.

The authors have built a prototype, called AutoWatchdog, and applied it to
ZooKeeper, Cassandra and HDFS, generating tens of checkers for each. Figure 2 shows an example from ZooKeeper.

MAD questions


1. If we detect the problems by mimicking the program, why don't we do the detection as part of the program rather than using a separate watchdog?

The watchdog detectors have a countdown timer for detecting getting stuck at any point due to some operation. This, of course, could have been added to the program as well, but maybe that makes the program look complicated. I guess having this in the watchdog detectors provide modularity, as in aspect-oriented programming.

I guess another benefit of having a separate watchdog detector is that we have a flexibility to locate it more centrally, rather than with the execution in one process. The gray failures paper made a case of asymmetry of information, and that there is a need for more end-to-end detection. Having a separate watchdog detector, we can maybe put parts of it or copies of it in different processes for being able to detect/check faults from different perspectives.

2. How do we make watchdogs compose?
One challenge that will surface when AutoWatchdog creates multiple watchdog detectors for a program is interference among the watchdogs. A reset triggered by a watchdog detector may lead to another reset triggered on another detector. And this may even get continued as the two watchdog detectors trigger resets for each other. Of course, this is more about correction that detection, so this is outside the scope of the paper.

However, even for just detection, care must be taken that the mimicking in the watchdog detectors do not have side effects and mess up the correctness of the program. The paper cautions about this problem: "Executing watchdog checkers should not incur unintended side-effects or add significant cost to the normal execution. For example, in monitoring the indexer of kvs, the checkers may try to retrieve or insert some keys, which should not overwrite data produced from the normal execution or significantly delay normal request handling." I am not sure how it is possible to avoid this problem completely with automatically generated watchdogs. If sandboxes are used, the watchdogs would not be testing/monitoring the real production environment.

Friday, October 4, 2019

Book review: Three body problem

This book, by Cixin Liu, easily secures a place among the top 20 sci-fi books I have read. The book was 400 pages, but was very engaging. I felt sad when I found that I had finished book. I was happy again when I learned the book has two sequels. I am looking forward to reading the sequels.

The book started in a very engaging way with the discussion of cultural revolution. This was engaging for me because 1) I didn't know much about this period in Chinese history, and 2) I am an academic and I was aghast by what has been done to the academics and intellectuals at that period. I couldn't fathom such an ignorance was possible. But given the path Turkey has been going down during the past 10+ years, and given the descent of US politics to such a path, I  followed these descriptions in horror. I couldn't imagine things could get that bad and stay that bad that long.

The importance of basic science was very well emphasized in this book. The book had a meta message. It starts with cultural revolution where science was shunned/repressed, and after the events escalate in present day earth, the world is also in a place where science is repressed/undervalued. I did enjoy those parallels.

The book included cutbacks and forth to a VR game the protagonist played, called "Three body" game. This reminded me of the back-and-forth cuts in "Ender's Game" with the game Ender was playing on his device, and in Diamond Age with the stories the girl's book told, and the prelude sections in Godel-Escher-Bach book. The cut-back techniques used here was excellent. The fictional characters in the game referred to prominent scientist, and the game showed some parallels to the progression of science on Earth as well.

Cultural revolution 

Since I didn't know much about China's history, I first thought the cultural revolution descriptions in the book were fictional. It has got to be because it is so surreal how people bought into this stuff and how the entire country chose illiteracy over literacy and ceased to function for 10 years. Secondly, I thought, how come Cixin Liu, a Chinese author, write freely about this period and criticize it sharply. It turns out it is OK to criticize cultural revolution and Red Guards provided that you do not blame Chairman Mao for it. Even though he started the cultural revolution to purge intellectuals (who must be corrupted by Western influence), apparently he was innocent and unaware of the extent of the purge. (Four ministers in the party got blamed for the events afterwards.) This is of course absolutely ridiculous. What is sad is that crimes and madness of this magnitude goes unpunished and everyone was (or had to be) OK with it. But such is life. Unfortunately, as I get older, I shed my unfounded faith about the good in humanity----which is also a theme explored in this book.

But for this mass struggle session, the victims were the reactionary bourgeois academic authorities. These were the enemies of every faction, and they had no choice but to endure cruel attacks from every side. Compared to other “Monsters and Demons,” reactionary academic authorities were special: During the earliest struggle sessions, they had been both arrogant and stubborn. That was also the stage in which they had died in the largest numbers. Over a period of forty days, in Beijing alone, more than seventeen hundred victims of struggle sessions were beaten to death. Many others picked an easier path to avoid the madness: Lao She, Wu Han, Jian Bozan, Fu Lei, Zhao Jiuzhang, Yi Qun, Wen Jie, Hai Mo, and other once-respected intellectuals had all chosen to end their lives.
“Relativity is part of the fundamental theories of physics,” Ye answered. “How can a basic survey course not teach it?” “You lie!” a female Red Guard by his side shouted. “Einstein is a reactionary academic authority. He would serve any master who dangled money in front of him. He even went to the American Imperialists and helped them build the atom bomb! To develop a revolutionary science, we must overthrow the black banner of capitalism represented by the theory of relativity!” 
- “Should philosophy guide experiments, or should experiments guide philosophy?” Ye’s sudden counterattack shocked those leading the struggle session.   
- “Of course it should be the correct philosophy of Marxism that guides scientific experiments!” one of the male Red Guards finally said. “Then that’s equivalent to saying that the correct philosophy falls out of the sky. This is against the idea that the truth emerges from experience. It’s counter to the principles of how Marxism seeks to understand nature.”                

The revolution eats its children first. The Red Guards didn't get punished, but they didn't prosper either.
“Of the four of us, three had signed the big-character poster at the high school attached to Tsinghua. Revolutionary tours, the great rallies in Tiananmen, the Red Guard Civil Wars, First Red Headquarters, Second Red Headquarters, Third Red Headquarters, Joint Action Committee, Western Pickets, Eastern Pickets, New Peking University Commune, Red Flag Combat Team, The East is Red—we went through every single milestone in the history of the Red Guards from birth to death.” 
“Then, we were sent to the wilderness!” The thickset woman raised her arms. “Two of us were sent to Shaanxi, the other two to Henan, all to the most remote and poorest corners. When we first went, we were still idealistic, but that didn’t last. After a day of laboring in the fields, we were so tired that we couldn’t even wash our clothes. We lay in leaky straw huts and listened to wolves cry in the night, and gradually we woke from our dreams. We were stuck in those forgotten villages and no one cared about us at all.” The one-armed woman stared at the ground numbly. “While we were down in the countryside, sometimes, on a trail across the barren hill, I’d bump into another Red Guard comrade or an enemy. We’d look at each other: the same ragged clothes, the same dirt and cow shit covering us. We had nothing to say to each other.”  
“Tang Hongjing was the girl who gave your father the fatal strike with her belt. She drowned in the Yellow River. There was a flood that carried off a few of the sheep kept by the production team. So the Party secretary called to the sent-down students, ‘Revolutionary youths! It’s time to test your mettle!’ And so, Hongjing and three other students jumped into the river to save the sheep.
The cold winter of the Cultural Revolution really was over, and everything was springing back to life. Even though the calamity had just ended, everything was in ruins, and countless men and women were licking their wounds. The dawn of a new life was already evident.  
Science and technology were the only keys to opening the door to the future, and people approached science with the faith and sincerity of elementary school students.



BIG SPOILERS FROM NOW ON!!

From here on there are big spoilers. Read on the rest, only if you have read the book. It is a great book, and you shouldn't spoil your enjoyment by reading my discussion of the plot.

The cultural revolution days set the background for Ye Wenjie, one of the key figures in the story, and her choice which affects the fate of humanity. From Ye Wenjie's days working on the radio observatory at Red Coast, the book skips to the present day, to another protagonist Wang Miao, a nanotechnology professor who was contacted by a secretive "Frontiers of Science" group. After that Wang starts seeing a countdown in his camera and then in his eyes/retinas. At this point things escalated quickly. The pace of the book went from slow to uncomfortably fast. At this point, I was convinced  the only explanation for this "miracle" is the simulation hypothesis (that we are living in a simulation), because no natural force can pull of this miracle.

Later I learned that Ye Wenjie did invite Trisolarians (an alien race living on a planet 4 light years away) to invade the Earth. Then I started to wonder how the book will be able to explain this countdown timer miracle as a technology of the alien race. But the book delivered on this at the end. The answer was the sophon project, a 2-D supercomputer folded into a 11-d proton! This was simply awesome!

I really liked the reveal of three suns as the cause of chaotic and stable eras in the Trisolarian planetary system in the Three Body VR game. The game also revealed details about the Trisolarian society. Their society was interesting. It is an autocratic and very socialist society (maybe sort of hinting back to the Chinese government again).

Shi Qiang, or detective Da Shi, was a very interesting character. The ship slicing scene with nano-wires was unreal. It was very gory, and I don't think it was warranted. (After I read this, I had a nightmare about it.) But how could the people on the ship not detect the problem earlier. If they see other people getting sliced 10 meters ahead, they can easily run back, sound an alarm and warn others. Also why didn't the sophons warn the ship about the trap? Given that they are super-AI and omnipresent and omniseeing, they had a good chance to detect this, no?

Selected notes from the book

“In China, any idea that dared to take flight would only crash back to the ground. The gravity of reality is too strong.” 
“Theory is the foundation of application. Isn’t discovering fundamental laws the biggest contribution to our time?” 
“At the same time, they want to ruin science’s reputation in society. Of course some people have always engaged in anti-science activities, but now it’s coordinated.” 
“Everyone is afraid of something. The enemy must be, too. The more powerful they are, the more they have to lose to their fears.”
After calming himself and walking to the other end of the long table, Wang said, “It’s actually pretty simple. The reason why the sun’s motion seems patternless is because our world has three suns. Under the influence of their mutually perturbing gravitational attraction, their movements are unpredictable—the three-body problem. When our planet revolves around one of the suns in a stable orbit, that’s a Stable Era. When one or more of the other suns move within a certain distance, their gravitational pull will snatch the planet away from the sun it’s orbiting, causing it to wander unstably through the gravitational fields of the three suns. That’s a Chaotic Era. After an uncertain amount of time, our planet is once again pulled into a temporary orbit and another Stable Era begins. This is a football game at the scale of the universe. The players are the three suns, and our planet is the football.”
Pan studied everyone meaningfully, and then added in a soft voice, “How would you feel if Trisolaran civilization were to enter our world?” “I would be happy.” The young reporter was the first to break the silence. “I’ve lost hope in the human race after what I’ve seen in recent years. Human society is incapable of self-improvement, and we need the intervention of an outside force.” 
“And it is this: The human race is an evil species. Human civilization has committed unforgivable crimes against the Earth and must be punished. The ultimate goal of the Adventists is to ask our Lord to carry out this divine punishment: the destruction of all humankind.” 
“Pan-Species Communism. It’s an ideology I invented. Or maybe you can call it a faith. Its core belief is that all species on Earth are created equal.”
They are sealing off the progress of human science. Because of the existence of these two protons, humanity will not be able to make any important scientific developments during the four and a half centuries until the arrival of the Trisolaran Fleet. Evans once said that the day of arrival of the two protons was also the day that human science died. 
Charcoal inside a filter is three-dimensional. Their adsorbent surfaces, however, are two-dimensional. Thus, you can see how a tiny high-dimensional structure can contain a huge low-dimensional structure. 
You will never be as good at it as criminals, masters of out-of-the-box thinking.                
“That flower may be delicate, but it possesses peerless splendor. She enjoys freedom and beauty in the ease of paradise.” 
The science consul said, “Project Sophon, to put it simply, aims to transform a proton into a superintelligent computer.” 
“This is a science fantasy that most of us have heard about,” the agricultural consul said. “But can it be realized? I know that physicists can already manipulate nine of the eleven dimensions of the micro-scale world, but we still can’t imagine how they could stick a pair of tiny tweezers into a proton to build large-scale integrated circuits.
A particle seen from a seven-dimensional perspective has a complexity comparable to our Trisolaran stellar system in three dimensions. From an eight-dimensional perspective, a particle is a vast presence like the Milky Way. When the perspective has been raised to nine dimensions, a fundamental particle’s internal structures and complexity are equal to the whole universe. As for even higher dimensions, our physicists haven’t been able to explore them, so we cannot yet imagine the degree of complexity.” 
The science consul said, “A sophon has been born. We have endowed a proton with wisdom. This is the smallest artificial intelligence that we can make.”
             
“As soon as we increase the dimensionality of this proton, it will become very small.       
“Princeps, the sphere we see now is not the complete sophon. It’s only the projection of the sophon’s body into three-dimensional space. It is, in fact, a giant in four-space, and our world is like a thin, three-dimensional sheet of paper.
             
Yes. I can see the control center, everyone inside, and the organs inside everyone, even the organs inside your organs.
             
“A sophon observing three-space from six-space is akin to us looking at a picture on a two-dimensional plane. Of course it can see inside us.”      
“It’s not exactly going ‘through.’ Rather, it’s entering from a higher dimension. It can enter any enclosed space within our world. This is again similar to the relationship between us, existing in three-space, and a two-dimensional plane. We can easily enter any circle drawn on the plane by coming in from above. But no two-dimensional creature on the plane can do such a thing without breaking the circle.” 
“After the two sophons arrive on Earth, their first mission is to locate the high-energy particle accelerators used by humans for physics research and hide within them.
             
The study of the deep structure of matter is the foundation of the foundations of all other sciences. If there’s no progress here, everything else—I’ll put it your way—is bullshit.”

Wednesday, October 2, 2019

Frugal computing

Companies care about cheap computing.

Well, the first thing they care about is usability: Is it easy for average programmers to develop solutions using the framework?

And the second thing they care about is cheap computing: Does this break the bank? Can I do this cheaper?

Speed, efficiency, elegance, technical strength... These are often not of interest. People are OK with their analytic jobs return results hours later. We watched aghast, at the beginning of Hadoop epidemic, people use MapReduce for doing analytics in a wasteful and slow manner.

I was recently thinking about this question: How can we trade-off speed with monetary cost of computing? If the constraints are that the user will not need the results before a couple hours but it would be nice to get the results in a day, what is the cheapest way to get this analytics job done in the cloud?

While distributed systems may be the answer for a lot of questions (such as providing fault-tolerance, low-latency access for geo-distributed deployment, scalability, etc.), it is not very advantageous for cheap computing. This is because distributed processing often comes with a large overhead for state synchronization, which takes a long time to get compensated, as the "Scalability at what COST paper" showed. With frugal computing, we should try to avoid the cost of state synchronization as much as possible. So work should be done on one machine if it is cheaper to do so and the generous time budget is not exceeded. Other machines should be involved when it is cheaper to involve them, and when there is not a lot of state to synchronize.

Primitives for frugal computing

Memory is expensive but storage via local disk is not. And time is not pressing. So we can consider out-of-core execution, juggling between memory and disk.

Communication costs money. So batching communication and trading off computation with communication (when possible) would be useful for frugal computing. If something is computationally heavy, we can have lookup tables stored in disk or S3 (if still feasible monetarily).

We may then need schemes for data-naming (which may be more sophisticated then simple key), so that a node can locate the result it needs in S3 instead of computing itself. This can allow nodes to collaborate with other nodes in an asynchronous, offline, or delay-tolerant way. For this, maybe the Linda tuplespaces idea could be a good fit. We can have an await based synchronization. This may even allow a node or process to collaborate with itself. The node may might switch to other threads when it is stuck waiting for a data item, and then come pick up that thread when the awaited thing becomes ready through work of the other threads and continue execution from there.

In frugal computing, we cannot afford to allocate extra resources for fault-tolerance, and we need to do in a way commensurate with the risk of fault and the cost of restarting computation from scratch. Snapshots that are saved for offline collaboration may be useful for building frugal fault-tolerance. Also self-stabilizing approach can also be useful, because it can provide forward error correction instead of a costly roll-back error correction.

This is all raw stuff, and in the abstract. I wonder if it would be possible to start with an opensource data processing framework (such as Spark), and customize it to prioritize frugality over speed. How much work would that entail?

Two-phase commit and beyond

In this post, we model and explore the two-phase commit protocol using TLA+. The two-phase commit protocol is practical and is used in man...