Friday, August 31, 2012

Stuff I'm reading this weekend

Labor Day weekend, traditionally the last weekend of summer ...

It's a real grab-bag of stuff on my weekend reading list; grab a lawn chair and your favorite beverage and dig in ...

  • My good friend Andrew has a great piece up on a literacy campaign with a public transit theme: Wolves on BART. Beautiful!
  • In The Verge, Sean Hollister spins an insider's tale of the collapse of the gaming startup On Live: OnLive lost: how the paradise of streaming games was undone by one man's ego
    Steve Perlman convinced many players that OnLive was worth investing in, up to and including some employees who gambled their money knowing that the company wasn't making a dime. Everyone we spoke to believed in the power of the cloud. Everyone expected a savior around the corner, but when it came to realizing that vision, only Steve was holding the cards. In hindsight, said one employee, management didn't do such a bad job: "They managed to carry this thing four years longer than anyone thought they would."
  • Mark Bernstein's series of essays on NeoVictorian Computing are completely fascinating. He skewers the software industry for stagnation:
    Today, your software is my software. Some details might change: maybe you use Mellel and I use Word, or you use Excel and I use Numbers. Small differences matter. But it's all pretty much the same. People expect that they won't need to read a manual, that everything is just like it's always been and that nothing ever changes much.

    Bernstein proposes that, to return to a world where software innovated and revolutionized and changed our perspective, we must be willing to experience some discomfort:

    I want this to change. I want a software world where we might again enjoy new software that does things we couldn't do before. I want software that fits specific needs. I'm a software professional; why should I be using the same tools as a sixth grader, or a professional photographer, or an interior decorator?

    Why do we have so little variety in our software? One reason is that we ask it to do what it cannot, and we expect to do too little.

    We should expect to learn. Sophisticated tools require study and effort, and they repay that effort by letting us do things we could not do otherwise. Calculus is a lot of work, but you can't understand physics or the stock market until you understand derivatives. Learning to draw the figure is a lot of work; once you do the work, you can draw.

  • You'll recall that I quite enjoyed Ernest Cline's Ready Player One, so it was fun to see that the Easter Egg Contest hidden in the physical paperback book itself is now complete.

    Congratulations Craig Queen!

  • It's a year old now, but I thoroughly enjoyed Ryan Anderson's trip report from a geologists's field trip to the Kidd Creek mine in Canada: 9800 Feet
    The mine has two shafts because there is a physical limit to how long elevator cables can be. After a certain length, the cable is so heavy that it can barely hold itself up, let alone a car full of passengers or tons of ore. The lifts are designed to be several times stronger than necessary, so that limits the length of the shaft.
    The official site notes quietly that
    The No. 4 shaft extends to 9,889 feet (3,015 metres) below surface and with the completion of the Mine D project, the Kidd mine is the deepest mine below sea level in the world.
  • How do you know when software is worth paying attention to? When its users just flat out love it, which you can sometimes tell by stumbling across paeans like the one written by Calvin French-Owen on MongoDB: What 10gen nailed with MongoDB
    If you’re looking for lessons in building a developer-focused product, you should look no further than 10gen’s decisions with MongoDB. They demonstrate some of the best ways to build a community around a product and make developers love it.
  • Summer is over, the Olympics are done, and the two greatest football teams on the planet have resumed their epic battle: Modric and Song arrivals indicate Barcelona and Real are thinking about each other’s style
    Both sides were playing without their most expensive signing of the summer – Luka Modric for Real, Alex Song for Barcelona. The precise role of each player is uncertain, but both are more naturally suited to the other side – Modric is a short passer that Barca would probably buy if they didn’t already have so many players in that mould, Song is a physical defensive midfielder that more suits a combative Real midfield.
  • I know, I know, I'm just obsessing about this whole Apple-Samsung thing, but really, it's actually pretty important. So here's more to keep you thinking about it, too:
    • Florian Mueller: The biggest issue with the Apple-Samsung jury verdict: are all those patents really valid as granted?
      we must separate the question of what has happened from the one of what will happen next. None of those interviews changes the fact that juries enjoy a whole lot of discretion in terms of how they arrive at their decisions. There are some rules they must respect, but not as many rules as some people may think.
    • Jacques Mattheij: Tim Cook Memo Line by Line
      this is of course all about money, control and market dominance, as well as fighting Android with every tool available. Some time ago it was a Microsoft computer on every desk, now it is an apple phone or tablet in every pocket and on every table. This is all about keeping critical mass because these walled off eco-systems do not thrive in the light of any meaningful competition.
    • Richard Posner: Why There Are Too Many Patents in America
      patent plaintiffs tend to request trial by jury because they believe that jurors tend to favor patentees, believing that they must be worthy inventors defending the fruits of their invention against copycats -- even though, unlike the rule in copyright law, a patentee need not, in order to prevail in an infringement suit, show that the defendant knew he was infringing.
    • Thom Holwerda: A device with a touchscreen and few buttons was obvious
      where does this sudden disregard for history come from? Why are PDAs suddenly that weird uncle you never talk about and only see at birthdays? During the heydays of the PDA, every nerd and geek I knew seemed to have one or more of these things
    • Jeff John Roberts: 3 reasons juries have no place in the patent system
      Patents are not primarily about stopping copycats (that’s why we have trademarks) but are instead a form of industrial policy based on 20-year monopolies. If the policy is effective, it produces more innovation. If the patent policy is not effective, it creates monopolies that harm competitors and consumers.
    • Francisco Ryan Tolmasky: Patents and Juries
      These have the potential to be some of the most important decisions of our lifetime, and they are for the most part completely out of our control. This is why people are so frustrated by these patent trials – it is a feeling of helplessness. The granting of a patent can be as influential on our careers or our lives as the passing of a law, and yet it’s hard to feel like anything other than a mere spectator in the process.
  • The SpiderLabs team have an intriguing article on hashes: Stamping Out Hash Corruption, Like a Boss
    The corruption problem has been around since the late 90’s

    ...

    We discovered the source of this problem to be a logic flaw in how the registry information was being processed.

    It's quite hard to tell whether there is an actual bug in the underlying operating system, or whether the extraction and analysis tools are flawed. Either way, if you think you're trying to extract and process Windows password hashes, pay attention!
  • I don't know quite what to make of this article in Linux Weekly News: OpenIndiana lead Alasdair Lumsden resigns
    Instead we got the Illumian farce from Nexenta, along with their senior staff claiming OI is an existential threat to their continued existence. And when I asked for help back in November, we got Bryan Cantrill telling us all "when you want to do something, just do it" - rich coming from someone paid to work on all this whilst the OI devs volunteer their personal time, often at considerable personal sacrifice, to work on this stuff.
  • Lastly, don't miss this fascinating essay by Johannes Ernst: Why Decentralized Software Is 10x Harder
    If you build a decentralized application, you actually need to ship software. You need to package, test, create installers, test on a variety of platforms, write defensive code to work around misconfigurations your customers are likely to create, etc. For a centralized website, you can often edit files in place on the production server.
    Some call it hacking, others call it keeping the site up.

Well, this should be enough to keep you for an hour or two.

Got more to read? Let me know!

Wednesday, August 29, 2012

No obligations, no gestures, no smiles, and no insults.

I confess to not ever having read an article from the Boston Review before.

But, chasing a pointer from Bruce Schneier's blog, I plowed through Oded Na'aman's fascinating article in the summer issue of Boston Review: The Checkpoint: Terror, Power, and Cruelty.

Na'aman, a graduate student at Harvard, served in the Israeli Defense Force a decade ago, and wrote this article reflecting on his experiences there and how it had changed him.

Now, I don't have any of the appropriate background to comment deeply on the article: I've never traveled to the Middle East; I have no military background; I have little religious background; and I have no experience with living in or near an area of active conflict.

Regardless, this was a fascinating article and I thought he had some very insightful things to say. For example, he discusses the moral and philosophical imperatives of the security checkpoint:

The soldier does not only have authority to make exceptions; the soldier has a responsibility to make exceptions. At the checkpoint, omnipotence is the power to create orders, not merely the power to enforce them. When a soldier’s order is defied, it is he, his judgment, that is defied, not merely a rule that he represents. Disobedience, therefore, is always personal at the checkpoint.

As Na'aman observes, the realities of the checkpoint lead inevitably to a certain outcome:

The circumstances instill in soldiers and Palestinians an intense interest in each other’s minds. This same interest subverts their capacity to recognize each other. There can be neither truth telling nor lying at the checkpoint. No obligations, no gestures, no smiles, and no insults. There can be neither respect nor disrespect, neither shame nor honor. Palestinians will say and do whatever they think is most likely to get them through the checkpoint. Soldiers will say and do whatever keeps the Palestinians scared enough to do nothing but obey.

The result, in the end, says Na'aman, is nothing short of tragic:

Even if the soldier is failing to act on his values, he still has them. He decides not to succumb to indifference, not to let his moral sentiments wear off. He must not grow accustomed to the unnecessary suffering he is bound to inflict with his arbitrary exercise of power. He holds on to guilt as a drowning man holds on to a log of wood.

As Robert Burns put it, 250 years ago:

Many and sharp the num'rous ills
Inwoven with our frame!
More pointed still we make ourselves
Regret, remorse, and shame!
And man, whose heav'n-erected face
The smiles of love adorn, -
Man's inhumanity to man
Makes countless thousands mourn!

Hey Marseilles

We happened to hear Hey Marseilles play last weekend, and we both thought they were superb.

So, if you think you might like that sort of thing, you should wander over to their website and listen to some of their music.

To Travels and Trunks is now on repeat in our car...

2012 World Chess Olympiad is underway

Follow it here!

MongoDB 2.2 released

The NoSQL database MongoDB has released a major new 2.2 release. Interesting new features include tag-aware sharding, read preferences, and removal of the global lock.

For a high-level view of the new release, see this blog entry.

For more details, try the release notes, which have many pointers to additional resources.

There's a wiki page for tag-aware sharding.

There's some documentation for read preferences.

For a completely content-free interview with the CEO, try this Wired article: NoSQL Pioneer MongoDB Doubles Down on the Data Center

Tuesday, August 28, 2012

Post 1000

3.5 years blogging, 1000 posts. Not bad I guess.

Dave Shields wonders: Where have all the bloggers gone?.

I don't know.

For now, I'm just pleased that, as Randall Munroe puts it: "just 24 to go until a big round-number milestone!"

Maybe it's just a macaque

The most delightful article I've read all month appears in this weekend's New York Times magazine: Jon Mooallem's Swing State.

It's so wonderful that I sat down and read it, out loud, to my wife, over dinner.

The article is about macaques, of course, who have been wandering the wilds of Florida for 75 years

The population of wild rhesus macaques in the middle of the state — the tribe from which, the theory goes, the Mystery Monkey strayed — was established in the late 1930s by a New Yorker named Colonel Tooey. (Colonel was his first name.) Tooey ran boat tours on the picturesque Silver River, a premier tourist destination. A brazen showman, he wanted to ratchet the scenery up another notch. So he bought a half-dozen macaques and plopped them on a small island. Macaques are strong swimmers; Tooey had no idea. According to local lore, the animals were off the island within minutes.

But perhaps the macaque is a metaphor:

the public came to see the monkey as an outlaw, a rebel — a nimble mascot for “good, old-fashioned American freedom,” as one local reporter put it. This week, tens of thousands of Republicans will pour into Tampa. There will be lots of national self-scrutiny and hand-wringing at the convention center downtown. But the most fundamental questions — What exactly is government for? Where are the lines between liberty, tyranny and lawlessness? — have been shaking the trees around Tampa for years.

For what is the monkey a metaphor? Moollem suggests that the story of the Tampa Mystery Monkey be read in the context of the increasingly polarized political discussions of the country:

It occurred to me that the two mind-sets — apathy and paranoia — probably yield the same result. You wind up off to the side of real democracy, disengaged from the strenuous project of brokering a better society.

I love that phrasing: "the strenuous project of brokering a better society." Yes, indeed.

But don't get all caught up in what the article is, or isn't about.

Just go read it: read about Vernon Yates, and Captain Tom O'Lenick, and Mr. and Mrs. Clas, and all the other wild characters that populate this marvelous fable about who and why we are.

A steady murmur about HFT

Weeks after the Knight Capital mini-crisis (for which, I think, the best current explanation is the Nanex theory), the ongoing discussion about High Frequency Trading continues, at some sort of background-noise level.

A few postcards from the din:

  • Shortly before Reuters shut his blog down, Felix Salmon posted this blog article, pointing to Larry Tabb's article at the Wall Street and Technology blog site: Fragmentation Is Redlining the Markets:
    Given the events of the past six months, the SEC should think hard about the market structure it has created, and do its utmost to rein it in. While the SEC can't stop computers from getting faster, there is no reason it can't reduce price and venue fragmentation, which should slow the market down, reduce message traffic and lower technology burdens.
  • A nice piece by Renee DiResta on the O'Reilly site: Wall Street’s robots are not out to get you
    But it’s nonsense to make the leap from one brokerage experiencing severe technical difficulties to claiming that automated market-making creates some sort of systemic risk. The way the market handled the Knight fiasco is how markets are supposed to function — stupidly priced orders came in, the market absorbed them, the U.S. Securities and Exchange Commission (SEC) and the exchanges adhered to their rules regarding which trades could be busted (ultimately letting most of the trades stand and resulting in a $440 million loss for Knight).
  • The DiResta article points to a recent New York Times article by Nathaniel Popper: On Wall Street, the Rising Cost of Faster Trades.
    “They’ve reached the point where the competition is measured in microseconds and there are essentially no benefits to the public at that level,” said Lawrence E. Harris, the former chief economist at the Securities and Exchange Commission, and now a professor at the University of Southern California.
  • And, at NPR's Planet Money, an article about Thomas Peterffy of Interactive Brokers: A Father Of High-Speed Trading Thinks We Should Slow Down
    Peterffy says automation has done some very good things for the world. It's made buying and selling stocks much much cheaper for everyone.

    But Peterffy thinks the race for speed is doing more harm than good now. "We are competing at milliseconds," he says. "And whether you can shave three milliseconds of an order, has absolutely no social value."

  • Lastly, on the Marginal Revolution site, an interesting article by Alex Tabarrok: HFT versus the sub-optimal Tick
    there is good evidence for Salmon’s hypothesis that firms care about nominal share price; In Tick Size, Share Prices, and Stock Splits (JSTOR, H/T OneEyedMan) James Angel makes the interesting point that even as the S&P and CPI soared between 1924 and 1994 the average nominal price of a stock was very flat near $32. Angel’s explanation is that firms use the IPO price and splits to keep a consistent relationship between tick size and share price because: "A large relative tick size also encourages dealers to make a market in a stock….a larger tick provides a higher minimum round-trip profit to a dealer who can buy at the bid and sell at the offer."
Lots of discussion, no easy solution, no obvious consensus: the debate continues.

By the way, Felix Salmon has resumed writing, at his personal website. I still wonder why Reuters shut their blogs down...

Monday, August 27, 2012

Trying to digest the Apple/Samsung verdict

Are you, like me, trying to understand the Apple/Samsung verdict? Here's some of the reporting I've found most helpful:

  • On Slate, Matthew Yglesias looks at Who Really Lost the Apple vs. Samsung Case? You Did.
    Dealing a billion-dollar hit to its only real rival in the smartphone profit game is a big win for Apple, and the fact that the trade-dress infringements will disrupt Samsung’s manufacturing and supply chain makes it a particularly solid blow.
  • The Atlantic's web site is carrying a survey-style article by Alexis Madrigal: What Apple's Legal Win Over Samsung Means for You, Technology, Design, and the World. Madrigal leads with the Wall Street Journal's assessment that, while Apple wins, consumers lose:
    Get ready for the Apple tax, at least in the short term. After its stunning victory against rival device-maker Samsung Electronics Co., experts say consumers should expect smartphones, tablets and other mobile devices that license various Apple Inc. design and software innovations to be more expensive to produce.
    Madrigal also links to Robert Scoble's amusing against-the-common-wisdom reaction:
    I think this is actually a sizable win for Samsung. Why? It only cost $1 billion to become the #2 most profitable mobile company. Remember how much Microsoft paid for Skype? $8 billion. So, for 1/8th of a Skype Samsung took RIM's place and kicked HTC's behind. Not too bad.
  • I thought that Joshua Gans had a fairly well-considered analysis on his Digitopoly web site: Five shades of grey on Apple-Samsung, noting that competition works best when the competitors actually compete by offering better products, not just cheaper ones:
    If Samsung can just copy an iPhone, then Samsung can have an incentive to position itself close to the iPhone in ‘product space’ and rely on price competition to ensure market share. Apple has to reduce price or cede share. But if Samsung cannot just copy an iPhone, then Samsung has to position itself differently. So when copying is possible, those consumers who most like the iPhone design and gestures get benefits while when copying is not possible, consumers who don’t like the iPhone design and gestures get benefits because Samsung will try and think of things that will attract them.
  • Florian Mueller breaks down the verdict on his blog and offers his opinion that Apple's legal victory is thorough, complete, and devastating.
    A California jury just handed Apple a near-complete victory on its own claims and awarded it more than $1 billion in damages, and rejected all of Samsung's claims. With most of the infringement having been established to have been willful, the jury essentially concluded that Samsung is a reckless copycat and, since some of the infringement is Google's responsibility, basically agreed with Steve Jobs's claim that Android is a stolen product.

    Apple CEO Tim Cook was absolutely right not to settle prior to this verdict.

    After the scandal that emerged when it turned out that Mueller was paid by Oracle while covering the Oracle v Google case (as Mueller points out, he did disclose this at the time), it's unclear how to evaluate his coverage of these cases. Another view on the legal aspects of the case can be found at the Groklaw case discussion, which, as usual with the Groklaw site, is also thorough and detailed.
    This story is far from over, in other words, and while Apple's CEO, Tim Cook, waxed philosophical about the trial, and saying that it was about values, not money, one important US value is that the jury fulfill its responsibilities, one of which is to read and make sure they understand and follow the jury instructions they are given. I believe Cook would agree that trials are supposed to be fair, with everyone doing their part. If this jury thought they knew the right result without instructions, and if they hurried so much they made glaring mistakes, and they did, and all in Apple's favor, something isn't right in this picture.
    TechDirt's Mike Masnick is also following the jury aspects of the case on the TechDirt blog and suggests there are serious concerns:
    The jury instructions are again clear that the jury needs to consider the prior art, but according to this juror, Manuel Ilagan, after foreman Hogan talked about his own experience with patents, they decided that prior art was "bogging us down" and they might as well "skip" it.
After watching this trainwreck, so soon after the Oracle v Google trainwreck, it seems to me incontrovertible that, as Judge Posner observed a month ago:
As in any jungle, the animals will use all the means at their disposal, all their teeth and claws that are permitted by the ecosystem.

Sigh. Surely the world can use its resources more effectively than this?

Fun photos of the GitHub office space

What do you do if you land the biggest software-only investment round ever? You build some nice office space for your team, that's for sure!

Business Insider has a nice photo-essay of the GitHub office space here

It looks like a fun place to work, although I sure don't understand this new-fangled passion for everybody hanging out in one big room together.

I worked in an environment like that once. It was noisy, distracting, and unproductive, and after a few months many of the individual engineers had worked around the problems either by changing their office hours so they weren't in the shared space when others were, or by stacking books and papers on their desks to build miniature walls for privacy and less distraction from co-workers.

Oh, well, I guess I'm a dinosaur :)

Saturday, August 25, 2012

America's Cup mishap pictures

I love these pictures of some of the action at the America's Cup races on the bay this week.

Friday, August 24, 2012

A nice short explanation of how a copy-on-write BTree works

One interesting technique for providing snapshot isolation (readers don't block writers) concurrency in a BTree is known as "copy on write".

Here's a nice short web page that shows a copy-on-write BTree in action: http://www.bzero.se/ldapd/btree.html

With pictures, it's clear and easy to follow.

Wednesday, August 22, 2012

A compendium of database-y stuff

I found myself wandering through some rather random database-y stuff recently; here's some of the fun stuff I've been reading this week:

  • Cassandra query performance. Aaron Morton, a Cassandra committer, posted a slide deck entitled: Cassandra SF 2012 - Technical Deep Dive: query performance. It's a very interesting presentation, although by the time you're a few dozen slides into the presentation, and he's described 8 or 10 different ways to try to tweak the Cassandra commit and cache algorithms, will you be as freaked out as I was?
  • OpenLDAP MDB. I think they're positioning this as an embedded data store:
    MDB is an ultra-fast, ultra-compact key-value data store. It uses memory-mapped files, so it has the read performance of a pure in-memory database while still offering the persistence of standard disk-based databases, and is only limited to the size of the virtual address space.
    Read more at: The MDB site.

    It's cool to look at what people do to make an embedded data store as absolutely blindingly fast as possible.

  • Distributed transactions for Google App Engine. If I'm understanding this correctly, these guys built a consistent distributed data store on top of a collection of independent local data stores.

    It's an extremely interesting paper, and a 1-hour video presentation by the author is also available from that page.

    Our contribution is that we provide transactional semantics without restriction (1): we create a kind of transaction that works across objects not in the same Entity Group. We call these transactions "Distributed Transactions" (DTs) in order to distinguish them from the original GAE "Local (to one Entity Group) Transactions".

    When using our Distributed Transactions the set of objects operated upon must be specified directly by their Keys, as one does with an object store, not by predicates on their properties, as does with a general relational query.

  • HBase Replication: Operational Overview. Available here.

    HBase's replication support continues to evolve. It still looks like a very complex system that is quite hard to monitor and diagnose. The basic tool appears to be to do some sort of massive data diff on your running system(s):

    A standard way to verify is to run the verifyrep mapreduce job, that comes with HBase. It should be run at the master cluster and require slave clusterId and the target table name. One can also provide additional arguments such as start/stop timestamp and column families. It prints out two counters namely, GOODROWS and BADROWS, signifying the number of replicated and unreplicated rows, respectively.
  • MemSQL Architecture. Yet another in-memory database that claims to be the fastest one of all. In a recent blog entry describing their benchmarking, the developers say:
    MemSQL is an in-memory database that stores all the contents of the database in RAM but backs up to disk. MongoDB and MySQL store their data on disk, though can be configured to cache the contents of the disk in RAM and asynchronously write changes back to disk. This fundamental difference influences exactly how MemSQL, MongoDB and MySQL store their data-structures: MemSQL uses lock-free skip lists and hash tables to store its data, whereas MongoDB and MySQL use disk-optimized B-trees.

    Todd Hoff reports his notes from interviewing the MemSQL team here, saying:

    On the first hearing of this strange brew of technologies you would not be odd in experiencing a little buzzword fatigue. But it all ends up working together. The mix of lock-free data structures, code generation, skip lists, and MVCC makes sense when you consider the driving forces of data living in memory and the requirement for blindingly fast execution of SQL queries.
  • PVLAN, VXLAN and cloud application architectures. I don't know very much about modern networking technologies, so most of this page went way over my head, but it sounds like the evolution in the networking world is as fast as it is in the data world.
    In short – you need multiple isolated virtual network segments with firewalls and load balancers sitting between the segments and between the web server(s) and the outside world.

    VXLAN, NVGRE or NVP, combined with virtual appliances, are an ideal solution for this type of application architectures. Trying to implement these architectures with PVLANs would result in a total spaghetti mess of isolated and community VLANs with multiple secondary VLANs per tenant.

  • Why BTrees beat Hashing for sharding. I've written about the Galaxy project before; it's new but quite intriguing. In this post, they try to do some benchmarking as well as some analytical reasoning.
    not only have we got O(1) (amortized) worst-case performance in terms of network roundtrips, but the actual constant is much less than 1 (because C>>2b), which is what we'd get when using a distributed hash-table. This is perfect scalability, and it is a direct result of the properties of the B+-tree (and other similar tree data structures), and is not true for all data structures.

Tuesday, August 21, 2012

Ready Player One: a very short review

One of my summer relaxations this year was Ernest Cline's Ready Player One.

Ready Player One is somewhere at the intersection of science fantasy, nerd humor, and romance. It's full of jokes and puzzles and references to classic elements of the 80's.

It's kinda weird and hard to describe, but it was a lot of fun and I flew through it, which is just want you want from your summer reading, right? A sample:

"It's not really up for debate, Homer," I said. "Ladyhawke is an eighties classic."

"It's fucking lame, is what it is! The swords look like they were made out of tinfoil. And that soundtrack is epically lame. Full of synthesizers and shit. By the motherfucking Alan Parsons Project! Lame-o-rama! Beyond lame. Highlander II lame."

"Hey!" I feigned hurling my Intellivision controller at him. "Now you're just being insulting! Ladyhawke's cast alone makes the film canon! Roy Batty! Ferris Bueller! And the dude who played Professor Falken in WarGames!" I searched my memory for the actor's name. "John Wood! Reunited with Matthew Broderick!"

By the way, this was a book I wanted to read on the Kindle, and it was available on the Kindle. But, at least at the time I bought it, the paperback edition was $8.99 and the Kindle edition was $9.99 (it's now changed so that the paperback edition is $0.50 more than the Kindle edition). So I bought the paperback. Now I will give it to somebody else to read. It's completely unclear to me why the prices are set in this fashion.

Monday, August 20, 2012

Reuters blogs outage continues

From what I can tell, the Reuters blogs are now entering their fifth consecutive day of outage, apparently due to the second major security problem of this month.

Reuters had no immediate information on who was behind the hacking, the second time this month that the blogging platform of Reuters.com has been compromised.

It's of course extremely important that they close their security holes, but I hope they are able to put the blogs site back online soon, for I'm missing my Felix Salmon fix!

Apparently, Felix isn't sure what to do, either, and for the time being has decided to go fishing.

This whole thing isn't getting much press, as far as I can tell.

Do people even notice when major media websites go offline for extended periods?

Saturday, August 18, 2012

Hard problems, studied over many years

It's not that the easy problems have all been solved; it's just that I'm pleased when there is continued efforts on hard problems sustained over many years.

Herewith, some examples:

  • Slate reprints an interview with JPL astrophysicist Slava Turyshev regarding the Pioneer Anomaly.
    we saw a very unusual tiny force that fell right in between Newton's gravity and Einstein's general relativity. That prompted people to think that maybe the spacecraft was sensing the presence of a new type of physics. It was either a major discovery or a puzzle that, in the solving, would help us build better craft to study gravity.
    Part of the problem is that the data from the satellites was almost all lost:
    In the 1970s and 1980s, mission data was recorded on magnetic tapes, and to study the Pioneer anomaly we needed the probe's navigational data. But mission tapes were normally saved for only a few months and then thrown away, so you're lucky if you can find what you need. The only data available from Pioneer 10 was from planetary flybys, which were kept to study gravity around planets. Then we had to figure out how to read it. You need a proper machine with the right software, and you need to "upconvert" the data to modern formats so it can be used in today's computer modeling systems. That took years.
  • In the world of database concurrency control, for many years you could choose between serializability, which gave you correct results, but poor concurrency, or snapshot isolation, which gave you high concurrency, but inaccurate results. Of course, nowadays, the NoSQL gang are jettisoning correctness and consistency entirely, but I'm pleased to observe that some hard workers are still trying to build systems that do the right thing, including these three:
  • The interaction between TCP Congestion Control and Application Protocols has been a problem for more than three decades, and continues to be actively studied. Patrick McManus gives us a great update on the ongoing work on the HTTP application protocol to improve its performance and its interaction with TCP's congestion control:
    HTTP has been a longtime abuser of TCP and the Internet. It uses mountains of different TCP sessions that are often only a few packets long. This triggers lots of overhead and results in common stalling due to bad interaction with the way TCP was envisioned to be deployed. The classic TCP model pits very large FTP flows against keystrokes of a telnet session - HTTP doesn't map to either of those very well. The situation is so bad that over 2/3rds of all TCP packet losses are repaired via the slowest possible mechanism (timer expiration), and more than 1 in 20 transactions experience a loss event. That's a sign that TCP interactions are the bottleneck in web scalability.
    Mark Nottingham explains that while SPDY is the start, it's not necessarily the complete answer:
    It’s important to understand that SPDY isn’t being adopted as HTTP/2.0; rather, that it’s the starting point of our discussion, to avoid a laborious start from scratch. Likewise, we’re not replacing all of HTTP — the methods, status codes, and most of the headers you use today will be the same. Instead, we’re re-defining how it gets used “on the wire” so it’s more efficient, and so that it is more gentle to the Internet itself (see Jim Gettys — one of the original authors of HTTP/1.1 — discussing buffer bloat for more on this).
  • And lastly, but perhaps most importantly, Wired Magazine gives us a status report on the wonderful work being sponsored by the Gates Foundation to try to build a better toilet.
    The challenge: Create a toilet that doesn’t rely on piped water, sewer, or electrical connections. And while you’re at it, fashion something useful from the waste that goes in. Energy and water might be nice. Do it all for $0.05 per user per day, and you might win a $100,000 prize. Attacking the problem with the world’s most advanced science is one thing, but doing it within strict X-Prize-like parameters is entirely another. This week they announced the winners.
    An interesting side-light is the focus on the user interface (yes!) of the toilet:
    Apart from making the new toilets as inexpensive as possible, said Fisher, the key is making them a social norm and object of aspiration, and making pit latrines and in-the-open defecation an object of community opprobrium.

    “With a lot of these social enterprises and designs, the problem isn’t that we should have designed it better. It’s that we haven’t designed around the problems of convincing people to change their behavior,” Fisher said. “That’s where we need the innovation.”

Friday, August 17, 2012

Backpacking 2012: Rancheria Creek, Hetch Hetchy Reservoir, Yosemite National Park

The most important thing a backpacker must do is to pay attention to the weather.

When you are out in the wilderness, with only what you can carry, it is essential that you understand what weather you will be facing, and plan accordingly.

On this trip, I didn't do that, and I paid the price. Luckily, the people I was with were more aware than me, and it all turned out well. Learn from my mistakes, so you don't make your own!

This year, we repeated a trip that we had done nearly a decade ago. The trip begins from the O'Shaughnessy Dam at the foot of Hetch Hetchy Reservoir in Yosemite National Park. The trail winds around the far side of the reservoir, staying fairly close to the reservoir's edge, until you reach Rancheria Creek, at which point the trail breaks away from the lake and heads up higher into the park.

Due to time constraints, we were packing the trip in tightly.

We left the Bay Area as early as we could on Friday morning, but after stops for gas and coffee, a trip to the Oakdale SaveMart to pick up fresh-made sandwiches from the deli, and then the long drive up the hill, it was mid-morning by the time we reached the Hetch Hetchy ranger station. We filled out our paperwork, picked up bear cannisters, and drove down the seven mile single lane road to the dam.

By the time we had parked the cars, readied our packs, and were stepping out onto the trail, it was noon.

And it was 98 degrees. And getting hotter by the minute.

Even though the trail stays close to the lake surface, this has been an unusually hot and dry year, and this weekend was the middle of the mid-August heat. We walked on, trying to conserve our energy and water, but by the time we reached Wapama Falls, it was dry, dry, dry.

For comparison, Wapama Falls often looks like this.

And, only last summer, there was so much water at Wapama Falls at the end of June that it was the site of a backpacking tragedy.

But there was no water for us at Wapama Falls, so we re-shouldered our packs and began the ascent up over the large granite dome between us and Tiltill Creek.

By this time, it was mid-afternoon, and probably 103 degrees. After a long sunny stretch, the trail plunged into a small oak grove. Suddenly, I realized that I was exhausted, and my pulse was racing through the roof. I sat down to rest, and Roger caught up with me after a few minutes.

Thinking I was recovered, I strapped my pack back on, but I made it only 50 feet farther up the trail before I had to stop again, dizzy and faint.

It soon became clear that I was overcome by the heat. Worse, we were all out of water. Worse still, I think something was wrong with the sandwich.

After 20 minutes of resting, Roger and Rich determined to press on, bound for the next water, which we estimated we'd find at Tiltill Creek.

A full 45 minutes later, I was able to resume hiking, but by this point I'd made a rather dramatic decision: I shed about 15 pounds of weight, composed of my (full) bear canister and some excess gear. I packed it all in my day pack and left it by the side of the trail, thinking that, once I got my main gear up to camp, I could trot back and get the remaining gear, or (at worst) I could return at the crack of dawn Saturday morning to fetch it.

With a significantly lighter pack, and having completely emptied my stomach (yes, I think that sandwich wasn't quite right...), I was hiking strong again. By the time I reached Tiltill Creek, Roger and Rich had just finished filtering and filling the group's 3 gallons of water bottles, so I was able to have a long, full drink.

When I told Roger what had happened, he instantly volunteered to race back and get my gear. Roger is a year-round triathlete, and in superb shape, so he thought he'd be back within 40 minutes. I finished taking my main pack up to the Rancheria Creek camp, and settled down to wait for Roger.

And waited. And waited.

It turned out that, just a few minutes after starting back, Roger had encountered a full-grown California Black Bear on the trail. In that section of trail, hugging the granite cliff face some 400 feet above lake level, there was no other way forward or back. So the bear stood his ground.

Eventually, Roger was able to retreat far enough that he found a spot where he could climb above the trail, and the bear made its way on.

By the time we all connected back up, and got our gear to camp, it was 8:00, and rapidly getting dark. Happily, though, we were all safe, and ready to spend the weekend relaxing by the river.

What did I learn?

  • Understand the weather!. For the last few years, I'd been taking trips at much higher altitudes, even camping near the snow several times, so I'd been in the habit of bringing long pants, coats, hat and gloves, etc. Here, at low elevation, in a very warm and dry year, I was horribly mis-packed.
  • Understand your situation: I was hiking too hard, in extremely hot weather, with little shade and water. I needed to take it easier, and not push myself to the point of exhaustion.
  • Never go alone. Happily, I was with a highly-experienced group, strong and capable, and they kept me from doing anything stupid. Had I been by myself, things might have turned out very differently

A few more pictures here:

Bryan Backpacking 2012

Yosemite National Park is a beautiful, special place. It is certainly the most beautiful place in the country, possibly the most beautiful place on the planet.

But it is the real world, not an amusement park. Just this week, two young boys drowned in the Merced River. Meanwhile, one man is dead and another woman seriously ill from Hantavirus in Curry Village. And right on the trail we hiked, it's been barely 13 months since two experienced hikers drowned trying to cross the footbridges at Wapama Falls (don't miss this video!).

Go to Yosemite. Walk the trails, see the sights, enjoy this special place. But be careful, be thoughtful, go with a friend (or two or three!) and come back alive.

Wednesday, August 8, 2012

Some boats in a race

It keeps getting shifted around by takedown notices, so it may not be HERE or HERE for much longer, but if you haven't already seen Irish comedian Francis Higgins deliver his commentary on the women's Laser Radial Olympics competition, you must!

Tuesday, August 7, 2012

Mumbling

We went to see The Dark Knight Rises.

It's an extremely enjoyable film, very well executed, and everything is top-notch: acting, writing, music, visuals, costumes, you name it. Fun from start to end.

But I had a problem:

Two of the major characters have (intentionally) altered speech; it's an important and necessary part of their characters (think Darth Vader, but in a slightly different genre).

But I often couldn't understand what they were saying!

I got most of it, but there were definitely several sequences where I was left rather baffled, trying to figure out what the most important characters were saying.

And I couldn't understand Liam Neeson all that well either, but that happens in every movie he's in. And he wasn't wearing a mask.

It's a fun movie; if you haven't seen it, and you like that sort of thing, don't miss a chance to see it on the big screen with the great music.

And the famous "bridges scene" is indeed superb.

But let me ask you something: when did Summer 2012 become known as "The Movie Season Where All The Leading Ladies Have To Wear Black Leather Jumpsuits"?

MVCC theory

If you're one of those people who is fascinated by the internals of concurrency control algorithms, here's some fun new references that you might enjoy.

  • I recently came across a great new paper from a team lead by Per-Ake Larson of Microsoft: High-Performance Concurrency Control Mechanisms for Main-Memory Databases

    These guys are really pushing the edge, trying for both the highest-concurrency AND the highest raw performance, because they're looking at fully memory-resident databases. The paper is quite clear and easy to read, and I really enjoyed the way that they dug into some of the intricacies and edge cases. Plus, it has a great set of references to chase.

    Decades of research has shown that multiversion concurrency control (MVCC) methods are more robust and perform well for a broad range of workloads. This led us to investigate how to construct MVCC mechanisms optimized for main memory settings. We designed two MVCC mechanisms: the first is optimistic and relies on validation, while the second one is pessimistic and relies on locking. The two schemes are mutually compatible in the sense that optimistic and pessimistic transactions can be mixed and access the same database concurrently. We systematically explored and evaluated these methods, providing an extensive experimental evaluation of the pros and cons of each approach.
  • Following some of the references from the above paper, I came across an older paper by Alexander Thomasian; it came out about a decade ago, but it was new to me: Concurrency Control: Methods, Performance, and Analysis.. The paper is behind the ACM paywall, but you might be able to find it online elsewhere.

    This paper spends a lot of time trying to derive analytical formulae for evaluating the performance impacts of concurrency control, which I think is rather a waste of time, in general, since the assumptions turn out to be rather ridiculous. I also hate the way the paper uses its own jargon, like saying "txn" instead of "transaction".

    But there are some nice sections, for example Section 2.6 which surveys a collection of "Methods to Improve Locking Performance".

    The concurrent processing of long read-only queries for decision support applications and short update txns introduces conflicts between the two workloads, especially when the former follows a strict 2PL paradigm.
  • A much more interesting paper is Michael Cahill's PhD thesis from 2009: Serializable Isolation for Snapshot Databases

    The point of his thesis is this: Snapshot Isolation, by itself, does not provide Serializable transactions. However, it is possible to augment Snapshot Isolation with additional locks, in a manner which provides serializability.

    Despite the attractive properties of SI, it has been known since SI was formalized in (Berenson et al., 1995) that SI permits non-serializable executions. In particular, it is possible for an SI-based concurrency control to interleave some transactions, where each transaction preserves an integrity constraint when run alone, but where the final state after the interleaved execution does not satisfy the constraint. This occurs when concurrent transactions modify different items that are related by a constraint, and it is called the “Write Skew” anomaly.

    ...

    In this thesis, we instead focus [on] changing the DBMS internals to guarantee that every execution is serializable regardless of the semantics of the transactions, while still having the attractive properties of SI, in particular much better performance than is allowed by strict two-phase locking.

    Note that, while working for SleepyCat/Oracle about 8 years ago, Cahill wrote a Snapshot Isolation implementation for BerkeleyDB, which I believe is the implementation that is now shipped as the "transactional" BDB edition, so he certainly knows what he's talking about here. Cahill's thesis ended up winning an award for the Australian dissertation of the year. Cahill also discusses an alternate implementation, for the InnoDB engine (again, an Oracle product) of MySQL.

Pretty geeky stuff, I know; my wife will certainly give me a hard time for this post. But if this is your cup of tea, drink deeply!

Monday, August 6, 2012

Kaspersky profile

Two weeks ago, Wired Magazine ran an article by Noah Shachtman: Russia’s Top Cyber Sleuth Foils US Spies, Helps Kremlin Pals.

The long and detailed article sparked a response from Kaspersky on his blog: What Wired Is Not Telling You – a Response to Noah Shachtman’s Article in Wired Magazine.

And then Shachtman responded to Kaspersky's response: Kaspersky Denies Kremlin Ties, Compares Himself to Indiana Jones.

It's all powerfully-worded stuff, and very interesting to read.

The Wired article draws attention to the increasingly-powerful role that security-related software companies play in modern life:

What is mentioned is Kaspersky’s vision for the future of Internet security—which by Western standards can seem extreme. It includes requiring strictly monitored digital passports for some online activities and enabling government regulation of social networks to thwart protest movements. “It’s too much freedom there,” Kaspersky says, referring to sites like Facebook. “Freedom is good. But the bad guys—they can abuse this freedom to manipulate public opinion.”

These are not exactly comforting words from a man who is responsible for the security of so many of our PCs, tablets, and smartphones. But that is the paradox of Eugene Kaspersky: a close associate of the autocratic Putin regime who is charged with safeguarding the data of millions of Americans; a supposedly-retired intelligence officer who is busy today revealing the covert activities of other nations; a vital presence in the open and free Internet who doesn’t want us to be too free. It’s an enigmatic profile that’s on the rise as Kaspersky’s influence grows.

As Kaspersky himself points out, his company is not the only one with such ties:
All three of the world’s leading security companies – Symantec, McAfee/Intel, and Kaspersky Lab – work with law enforcement bodies worldwide to help fight cyber-crime. The ITU, CET, FBI, FSB, U.S. Secret Service… we all have a duty to help them solve criminal cases.

As a number of commenters have observed, it's certainly not necessarily a bad thing that Kaspersky's company is headquartered outside the U.S.A., and has at least some independence from the ever-increasing invasive measures that the U.S. government has been imposing.

We should give Kaspersky Labs credit for their ongoing work to educate the world about the complexities of software security, and for revealing and sharing information about complex malware like Stuxnet and Flame.

But we should also pay attention to the concerns that Shachtman and Wired raise, about the increasing power of companies like Kaspersky, Symantec, RSA, etc., and about the close relationship that people at these companies have with the so-called "military-industrial complex".

Hard issues, hard discussion; to my mind, that's how it should be.

Turtles all the way down

The Mars Reconnaissance Orbiter apparently was able to capture a picture of Curiosity descending to the Mars surface.

That means, if I understand it correctly, that this is a picture taken by a satellite, of a satellite, about to land on a satellite.

Sunday, August 5, 2012

Knight Capital Group, continued

The ongoing saga of Knight Capital Group continues to unfold.

Four full days have passed since whatever-it-was happened on Wednesday morning, and plunged Knight Capital into this severe crisis.

But there is still precious little information available about what actually happened, in detail.

Several articles that I've read attempt to shed some light:

  • In the New York Times, we read that many are still confused about why it apparently took Knight nearly 45 minutes to resolve the problem, once they learned of it: Trading Program Ran Amok, With No ‘Off’ Switch:
    Several market insiders said that they were bewildered, because in a market where trading losses can pile up in seconds, executives typically have a simple command that can immediately halt trading.

    “Even just a minute or two would have been surprising to me. On these time scales, that is an eternity,” said David Lauer, a trader at a high-speed firm until a year ago. “To have something going on for 30 minutes is shocking.”

  • An article from Reuters notes the dramatic shift of order processing away from Knight's sytems: Knight Capital heads into make-or-break weekend
    through Tuesday of this year, Knight accounted for 20 percent of the market making activity in shares of Apple, one of the most actively traded stocks on a daily basis. By midday Friday, Knight was the market maker for just 2 percent of the share volume
  • And multiple other articles are speculating that Knight Capital is on a very short lifeline, and might not even exist as a corporation by the end of the next 24 hours.

Of course, Knight themselves aren't saying much. I suspect we will have to wait until the SEC or some other organization performs a more detailed investigation to really learn the details.

In the meantime, though, what do we know about what actually happened?

We have a little bit of information from Knight's official press release, which you can find on the SEC web site KNIGHT CAPITAL GROUP PROVIDES UPDATE REGARDING AUGUST 1ST DISRUPTION TO ROUTING IN NYSE-LISTED SECURITIES. It's so short, it deserves listing in its entirety:

As previously disclosed, Knight experienced a technology issue at the open of trading at the NYSE yesterday, August 1st. This issue was related to Knight’s installation of trading software and resulted in Knight sending numerous erroneous orders in NYSE-listed securities into the market. This software has been removed from the company’s systems.

Clients were not negatively affected by the erroneous orders, and the software issue was limited to the routing of certain listed stocks to NYSE.

Knight has traded out of its entire erroneous trade position, which has resulted in a realized pre-tax loss of approximately $440 million. Although the company’s capital base has been severely impacted, the company’s broker/dealer subsidiaries are in full compliance with their net capital requirements. Knight will continue its trading and market making activities at the commencement of trading today. The company is actively pursuing its strategic and financing alternatives to strengthen its capital base.

CNBC reported some more details about what happened when Knight "traded out of its entire erroneous trade position": Goldman Sachs Priced Knight Unwind at $440 Million.

It was Goldman Sachs that helped Knight Trading Group to unwind its inadvertent purchase of 148 stocks on Wednesday

...

Goldman Sachs agreed to purchase Knight’s unwanted positions as part of one huge basket sale, the people familiar with the matter said, late on Wednesday. But the illiquid nature of some of the stocks and the urgency with which Knight wanted to sell the positions left the bank with plenty of negotiating power, added these people.

It's interesting that the press release terms this an "erroneous trade position", and the CNBC story calls it "Knight's unwanted positions". These terms make it look like the basic bug was that the software was buying stock that Knight didn't intend it to be buying, leaving Knight with a whole pile of unwanted stock.

If the error was entirely on the buy side, though, why were prices so volatile on Wednesday morning, and why was the volume so heavy?

Meanwhile, many have observed that it's highly significant that this event occurred on August 1st, which was apparently the date on which the NYSE's Retail Liquidity Program went into affect. On the Fortune web site, Stephen Gandel speculates about whether this was actually a coincidence or not Why Knight lost $440 million in 45 minutes:

Some say that market makers provide a service. Others say Knight and others seek out the orders of individual investors because they view those orders as so-called dumb flow and easier to trade against. What is clear is that Knight and others have figured out how to make money off the stock trades of you and me in ways that we can't detect but we probably pay for somehow. Eric Scott Hunsader, who runs trading research firm Nanex, estimates market makers have been able to generate $5 billion in profits rapidly trading the orders of individual investors and others in the past seven years.

On Wednesday, the same day that Knight lost $440 million, the NYSE launched its own computer driven trading system, called the Retail Liquidity Program, that the exchange hopes will reclaim some of the trading volume it has lost to market makers. NYSE hopes RLP will create more competition among traders and brokers and market makers so that more of those orders get filled at better prices on the exchange.

What is the Retail Liquidity Program? Well, here's what the NYSE themselves have to say about it in their press release:

"The Retail Liquidity Program is an attractive trade execution alternative for individual investors," said Joseph Mecane, Executive Vice President, NYSE Euronext. "Providing price improvement for retail orders within an exchange environment affords individual investors new economic incentives and ensures greater transparency, liquidity and competition throughout the U.S. cash equities marketplace."
I have no idea what that means.

The Wall Street Journal offers some more digestible information: What Exactly Is NYSE’s Retail Liquidity Program?

The NYSE proposal—called the “Retail Liquidity Program”—works along the same lines as the dark pools that trade large blocks of shares for institutions. Dark pools are private platforms set up for anonymous stock trading.

For example, if a doctor trading stocks from his home office wanted to sell 100 shares of Sirius XM Radio Inc. at the bid price of $1.85 a share, a tenth-of-a-cent improvement on the NYSE would see his order filled for $185.10, instead of $185.00.

Most of the Wall Street Journal information, however, is deep behind WSJ's paywalls, so I may never know what information they had to share.

After all this, I'm still left puzzled by what the software error was. Was it a poor user interface, that allowed some poor trader to make an enormous (but human) mistake, as in the famous "fat finger" explanation for the May, 2010 flash crash? Was it an error in the time execution of position-changing orders, or an error in the overall size of otherwise-valid orders, as various others have speculated?

I'd love to know, mostly because each time I learn about a software error, and how it was made, and how the testers didn't uncover it, I think some more about the errors that I make, and how to avoid them, and how to catch them, and how to ensure that they have, at worst, obvious, easily-diagnosable, and straightforwardly-repairable effects.

Saturday, August 4, 2012

It's not just a game ...

... it's a new type of management structure.

Your weekend long form reading is this article by Yanis Varoufakis of Valve, examining Valve's corporate culture from the economist's perspective: Why Valve? Or, what do we need corporations for and how does Valve’s management structure fit into today’s corporate world?:

I attempted to place Valve’s quirky management structure in the context of time-honoured debates and perspectives. Central to my narrative of ‘Valve’s way’ was the notion of an ‘alternative spontaneous order’: one that emerges within a corporation (as opposed to within a market-society) on the basis of individual time allocations (as opposed to price signals). The tantalising thought arose, during my musings, that this organisational structure may be as scalable as a market mechanism

How much of this transformation is due to the enabling powers of the computer? The author suggests, quite a lot:

The eradication of distribution and marginal costs, the capacity of producers to have direct access to billions of customers instantaneously, the advances of open source communities and mentalities, all these fascinating developments are bound to turn the autocratic Soviet-like megaliths of today into curiosities that students of political economy, business studies et al will marvel at in the future, just like school children marvel at dinosaur skeletons at the Natural History museum.

Many fascinating side discussions in the comments as well.

But, uhm, nothing new about The Next Game...

Friday, August 3, 2012

Notstop looking

We found a few hours the other night to watch Extremely Loud and Incredibly Close.

Have you seen it? You should.

The movie, like the book before it, is extremely divisive: you may despise it. As Jon Foer said when Mother Jones asked him:

MJ: Do you think readers will hold you to a higher standard because of the subject?

JSF: If they do, that’s good, because books are held to too low a standard. People don’t care enough. They don’t get worked up enough. They don’t get angry enough. They don’t get passionate enough. I’d rather somebody hate what I do than be indifferent to it.

But I didn't hate it; I loved it.

"It's that movie about 9/11," everyone will tell you. Which it is.

But it's really a story about parents and children, about the living and the dead, and about how we each have to discover who we are and where we came from.

It's about tall things and airplanes, yes, but it's also about the search for the legendary sixth borough, about maps and clues and the voyage of discovery, about 472 people named Black, about facing your fears and riding on the swings, and about the key that unlocks it all.

Are you there? Find the stairwell. Come home.

Thursday, August 2, 2012

Knight trading debacle, redux

Everybody seems to have an idea about how to fix whatever it is that went wrong with Knight Capital's new software this week.

Says the New York Times: Errant Trades Reveal a Risk Few Expected:

The fiasco, the third stock trading debacle in the last five months, revived calls for bolder changes to a computer-driven market that has been hobbled by its own complexity and speed. Among the proposals that gained momentum were stringent testing of computer trading programs and a transaction tax that could reduce trading.

Really, though, I have no idea how the NYT could claim that these were risks that "few expected". Anybody who thought about this for even a few seconds would understand that these risks were present.

And, I really don't understand how they expect to accomplish this:

Some S.E.C. officials are pushing new measures that would force firms to fully test coding changes before their public debut, according to a government official who spoke on the condition of anonymity.

What does that even mean, "fully test coding changes". It just exhibits a complete absence of any familiarity with the world of complex system software.

To its credit, the article does offer a bit of a constructive suggestion later:

“When they put these things out in the world they are really being tried for the first time in a real-life test,” said David Leinweber, the head of the Center for Innovative Financial Technology at the Lawrence Berkeley National Laboratory. “For other complex systems we do offline simulation testing.”

I wonder what these "other complex systems" are. For example, is this the sort of complex systems testing that would help figure out why half of India lost electrical power this week? If ever there was a need for simulation testing to assess the robustness of a complex system, power transfer infrastructure certainly jumps to mind...

This is actually the first time I've ever heard of "the Center for Innovative Financial Technology at the Lawrence Berkeley National Laboratory". So I went to look it up, and it appears that here is the home page.

Frankly, it looks like one guy, who's written a book, and writes a blog called Nerds on Wall Street (which I'm now subscribed to), and has access to some government-funded supercomputer resources. Here's a paper he's written describing how he thinks supercomputer simulations can help stabilize the financial markets: Federal Market Information Technology in the Post Flash Crash Era: Roles for Supercomputing.

It's all interesting stuff, but it's hard to buy the argument that requiring algorithmic trading software to be certified by a government agency using supercomputer simulations is really the right answer.

But, what is the right answer?

HFT again

Guess, what, it's algo day again!

The New York Times headline shrieks: Flood of Errant Trades Is a Black Eye for Wall Street

Traders on Wednesday said that a rogue algorithm repeatedly bought and sold millions of shares of companies like RadioShack, Best Buy, Bank of America and American Airlines, sending trading volume surging. While the trading firm involved blamed a “technology issue,” the company and regulators were still trying to understand what went wrong.

Nanex has charts and graphs: What Really Happened, or How to Test Your New Market Making Software and Avoid Detection

the same firm may have been on both sides of each trade and were simply testing out new market making software. After all, the NYSE started their new Retail Liquidity Price Improvement Program the very same day. And many of the trade executions are inside the bid/ask; something very unusual for trades and quotes from NYSE. Also, virtually all these trades are for 100 shares - the minimum number required to be reported in the system. And the timing of the trades is very evenly spaced, too evenly spaced. And many examples show a buy and sell appearing at virtually the same time, so close that the second trade has the very next exchange sequence number.

The New York Times says that Knight Capital have confirmed that they were indeed implementing new trading software, and that for a period of about 45 minutes, they were losing 10 million dollars a minute: Knight Capital Says Trading Mishap Cost It $440 Million

The problem on Wednesday led the firm’s computers to rapidly buy and sell millions of shares in over a hundred stocks for about 45 minutes after the markets opened. Those trades pushed the value of many stocks up, and the company’s losses appear to have occurred when it had to sell the overvalued shares back into the market at a lower price.

The New York Stock Exchange apparently cancelled a number of invalid trades. It's still not clear to me what makes a trade invalid, and how the exchange decides to uphold or cancel a particular trade.

Felix Salmon says that part of the problem is that the traders don't understand the behavior of the code they write: When large-scale complex IT systems break.

The fact is that a lot of the stock-trading world, at this point, especially when it comes to high-frequency algobots, operates on a level which is simply beyond intuition. Pattern-detecting algos detect patterns that the human mind can’t see, and they learn from them, and they trade on them, and some of them work, and some of them don’t, and no one really has a clue why. What’s more, as we saw today, the degree of control that humans have over these algos is much more tenuous than the HFT shops would have you believe. Knight is as good as it gets, in the HFT space: if they can blow up this badly, anybody can.

Salmon points to an earlier article on Barry Ritholtz's blog: Wait: The Art and Science of Delay, in which Ritholtz quotes from Frank Portnoy's recent book Wait: The Art and Science of Delay

This is where the story gets, as Harrison put it, weird. He explains: “When we got everything set up in New York, the trades were faster, just as we expected. We saved thirty-five milliseconds by moving everything east. All of that went exactly as we planned.”

“But all of a sudden, our trading costs were higher. We were paying more to buy shares, and we were receiving less when we sold. The trading speeds were faster, but the execution was inferior.

I sympathise with all of this. Every day, I work with complex, intricate, sophisticated algorithms whose precise behavior I don't understand. I don't know any short-cuts: you have to be the sort of person who enjoys working with systems like these; you have to be disciplined, patient, thorough, and meticulous; you have to use every tool available to you (design and code reviews, test harnesses, monitoring tools, diagnostic logs, simulators, assertions in the code); and, most importantly, you have to develop and sustain a team of people who all can work together, who all are interested in building software that works, and who all bring different talents and skills to the problem.

And even then, it takes time, money, sustained effort, and a fair bit of luck.

Wednesday, August 1, 2012

Massachusetts WinFall lottery gambling associations

This month, the Massachusetts Office of the Inspector General has published its report on its investigation into the Massachusetts State Lottery's Cash WinFall game.

I know this sounds like an extremely dry subject.

Trust me, it's not.

You really should go click on the above link right now and read the report. It's not that long; it reads very quickly.

Cash WinFall, modeled on an earlier Michigan State Lottery game, has a very special feature, called the "roll-down":

Cash WinFall had a feature that distinguished it from other on-line games: the jackpot was capped at $2 million. If the jackpot reached $2 million and no one matched all six numbers, the money in the jackpot was distributed among the lower tier prizes for that drawing. The Lottery referred to this as a “roll-down” and it dramatically boosted payouts for lower tier prizes.

It turns out that, statistically, the roll-down feature introduced a certain unusual behavior in the probabilities of the game:

In every roll-down drawing in the game’s history, for every $1 wagered, there was $1.15 (or usually more) sitting in the Cash WinFall prize pool to be shared among that drawing’s ticket holders. In that sense, every ticket was worth more than it cost. A person could make $1.15 for every $1 he bet – a 15 percent profit – simply by getting what the statistical probabilities say should be the average share. The most practical way to do that is to buy a large number of tickets.

It turns out that a "large number of tickets" means a really large number of tickets: successful betting groups, or "high-volume bettors", found that they needed to buy approximately 300,000 tickets in a 72 hour period in order to make the numbers work.

Yes, you read that right: 300,000 tickets for a single lottery drawing!

It turns out that there are a number of challenges in purchasing 300,000 lottery tickets for a single lottery game:

One constraint was simply getting enough ticket slips filled out. ... Under Lottery rules, betting slips can’t be computer generated so the group had to fill out betting slips by hand – oval by oval – to match each set of numbers generated by Mr. Harvey’s computer program. Simply filling out the betting slips was time-consuming. However, the betting slips could be reused...

But the complications don't end there:

Another constraint was locating stores that would handle large volume purchases. Many retail outlets balked at processing tickets on the scale that the MIT group and other high-volume bettors were seeking. Handling 10,000 tickets, including scanning in the slip with the requested numbers, could easily take several hours.

It gets worse:

If the weather was humid, the ticket machines were more likely to jam. If a terminal was running low on ink, it could take several tries to redeem a winning ticket.

And, since it was all strictly legal, don't forget the tax paperwork:

Like Mr. Harvey and Mr. Selbee, Dr. Zhang said he has held onto his losing tickets, which number in the millions. He had first stored them in boxes in his attic. But when his ceiling started to crack under the weight of his growing ticket collection, he promptly moved the ticket boxes to the garage.

But the groups persevered, continuing their purchases, and making substantial profits, for six years. By this point, they were constituting almost all of the action in the game:

Just three gambling companies collected 1,105 of the 1,605 Cash WinFall prizes statewide after a May drawing, each following a strategy that involved buying hundreds of thousands of dollars worth of the $2 tickets at selected stores over a few days.

Finally, in the summer of 2011, an series of articles in the Boston Globe resulted in substantial changes to lottery policy that eventually shut the entire thing down.

Anyway, the report is wonderful, filled with many, many more examples of the crazy, wacky world we live in, and the strange things that people do to pass their time in it.

Go. Read. Enjoy!

Olympian drama

One of my favorite parts of the Olympics is paying attention to all sorts of sports that I never am able to follow. Here in America, you can watch basketball, football, baseball, and other major sports all the time. But rarely will you see televised archery, or water polo, or badminton.

So, somewhere in between blogging and photo-journalism, check out this wonderfully well-presented story about the drama that unfolded during the women's epee semifinals at the Olympics: An Olympic Fencer Refuses To Leave The Floor After Getting Screwed.

In fencing, leaving the piste means that you have officially accepted the judges' ruling. And seeing as the clock didn't start, and she should still have a shot at gold, she sat down. It's the filibuster of fencing.