Log in

Monday, June 23rd, 2014

Why Mark is a Computer Scientist at Heart

So, I came across a question on Quora about showing that no reversible two-bit gates are universal. (NAND is universal for boolean logic but not reversible!)

My first thought was the CS one: well, how many 3-bit reversible functions are there? We could probably just do exhaustive search on combinations of two-bit gates and exhaust the space, there are far less than 8^8 reversible functions and that's only 16 million. (Hmm... how many are there? Must be something like 8! since each output must appear once and only once, so a reversible function is a permutation of the identity function.)

But the mathematical answer is the one I had to look up. All the 2-bit reversible functions are binary. That is, they are of the form f(x,y)=M(x,y)+(a,b) for some 2x2 matrix M. And the composition of linear transformations is always linear. But you can come up with a nonlinear 3-bit reversible binary function. (The Toffoli gate, which *is* universal, is one of them.)

If given enough time, I could probably come up with the second answer. But the first one is a lot more fun. :)
(Leave a comment)

Saturday, May 31st, 2014

A brick-and-mortar distributed systems problem

On Friday we climbed to the top of the Witch's Hat Water Tower. It's an old water tower (preserved as a area landmark and historic place) whose observation deck is only open once a year.

The top of the tower is reached via an internal spiral staircase which is rather narrow. The tower guides had arranged a system for tracking the number of people in the tower--- they handed blue notecards to those going up and retrieved them from those exiting the tower, thereby limiting the occupancy. But, this still led to congestion on the stairs as groups traveling in opposite directions had to squeeze by each other. Is it possible to come up with a system which also limits the number of people using the staircase in opposite directions? Without cheating by giving the guides mobile phones to communicate. :)

Time-based multiplexing is a common technique. Allow upward traffic for 5 minutes, then downward traffic for the next five minutes.

The token-based approach could also be expanded in a couple ways. For example, use two colors of tokens. Allow a group of people to start upwards but give the last person in the group a special red token. Block all other ascending traffic until the red token returns. When the red token gets to the top, collect it from the carrier and permit a group to begin going downwards, again giving the red token to the last person waiting to go down.

Now, there may be some psychological issues here where people might not appreciate being told to wait to leave the tower! But the guide was already doing a rough-and-ready contention control on the top portion of the stairs.
(1 comment | Leave a comment)

Thursday, May 22nd, 2014

Geeky Linkdump

20 question for Donald Knuth, of which I found Robert Tarjan's the most interesting. Knuth's response (in part):

In general I'm looking for more focus on algorithms that work fast with respect to problems whose size, n, is feasible. Most of today's literature is devoted to algorithms that are asymptotically great, but they are helpful only when n exceeds the size of the universe...

For instance, I've been reading about algorithms that decide whether or not a given graph G belongs to a certain class. Is G, say, chordal? You and others discovered some great algorithms for the chordality and minimum fillin problems, early on, and an enormous number of extremely ingenious procedures have subsequently been developed for characterizing the graphs of other classes. But I've been surprised to discover that very few of these newer algorithms have actually been implemented. They exist only on paper, and often with details only sketched.

I was annoyed at the recent New Scientist article making the rounds about a "proof" of how computers couldn't be conscious under Integrated Information Theory, so I'm glad Scott Aaronson took the time to show why IIT is bunk and saved me some ranting.

My company announced support for storing Hyper-V VMs on the Tintri VMstore bringing our total number of supported hypervisors to three, perilously close to the maximum possible. :) Only Openstack and Xen to go (well, and perhaps a few other KVM variants.) Chris Wahl posted a great review of Tintri at "Tom's IT Pro".

Bruce Schneier points out that the NSA is not magic. We've seen a lot of standard hacks carried out at industrial scale, or from privileged positions within the network, but not an Enigma-scale (or, well, Magic) breakthrough. I'm not sure this is cause for optimism; rather, it speaks poorly about the state of communications security that the NSA doesn't need such breakthroughs to do its job.

And, finally, one of my own pieces of writing on Quora: What mathematical functions can convert multiplication to summation? The previous answers were mainly literal-minded "only logarithms work among continuous functions" references rather than coming up with something that might be more interesting to somebody that's curious, like non-logarithmic slide rules.
(Leave a comment)

Wednesday, May 14th, 2014

Unix geekery

I fixed a bug this week which involved a subtle distinction in the behavior of

int f = open( filename, O_RDONLY );
fchmod( f, permissions );


chmod( filename, permission );

Can you guess what situations the latter handles that the open()/fchmod() combination does not?

SpoilersCollapse )
(4 comments | Leave a comment)

Sunday, April 13th, 2014

Minnebar 9

Here's how I spent my time on Saturday at the local 900-person "unconference":

Paul Cantrell, "Scheduling Minnebar with Simulated Annealing" Great talk as is usual from Paul. He intro'd by saying that simulated annealing sounds very fancy but really the algorithm is very dumb. For Minnebar, the key metric is whether people can attend all of the sessions they have expressed interest in through the session web tool. So the function being optimized is the mean, over all attendees, of the percent of their sessions they cannot attend due to scheduling. This may mean it's possible to game the system by registering for fewer sessions. Somebody who registers for 6 will have 0.17/N weight for having two sessions scheduled opposite each other, while somebody who expresses interest in just 2 will have 0.5/N weight on their preference. Certainly you should not register for any you don't much care about.

I asked about whether it was possible to do better on assignment to rooms. Currently Paul just assigns time slots first, then greedily puts the session with the largest number of interested people in the largest room. But I think it may be possible to do better than this--- some recurring sessions are known to be very popular and yet do not get placed in the largest venues.

There were quite a few questions of the form "couldn't you find a better/faster solution with X" to which is response was (correctly) "no, we only run this once a year so we don't care very much."

"Pack Your Own Chute - the Personal Decision to Join a Startup", a panel discussion led by Neal Tovsen, with Paul DeBettignies, Liz Tupper, Matt Hardy, and Todd H Gardner. This one was fairly depressing but a good conversation. They talked about the need to set boundaries and have clear communication with your co-founder when forming a startup. How much money are you willing to lose on this project? Where's your bail-out point? What is the worst-case scenario? (They also talked about some of the fun and freedom too.)

What struck me is that everyone on the panel was talking about creating a startup rather than joining one. Nobody talked about taking a smaller plunge by going to work for somebody else's startup first. (I know I found my time at Kealia very valuable when we started Tintri--- and I wasn't even doing the heavy lifting on the corporate/financial/HR side!) But just like you might save up money to make sure you could survive the 18 months it took to bootstrap your startup, it may make total sense to work for 2-3 years in another startup to build connections and experience for your own.

Another issue that was not confronted directly was moving. Relocating is a big cost and one that I totally understand not wanting to pay--- I didn't. But it should be asked: if the only way to make this startup succeed is to move to San Francisco, would you do so?

I learned about Track:js from one of its founders on the panel (and the other seated next to me in the next session!) A good-looking tool for debugging Javascript problems that happen in production systems, and one Tintri might try out.

Reed Robinson, "Lessons from a Failed Startup". The failed startup was Heroic, a local attempt at a recommendation service for home services. (His dad repairs garage openers.) He had a good list which I'll try to reproduce here, but I wish his slides were available:

  1. Validate your assumptions. (Like, "people care about my product", "the team can build the product", and "people will pay for my product.")
  2. Sell it, then build it. Heroic spent lots of time on UX but decided not to ask people to pay right away. For his next venture he wants to sell the idea and find people willing to fund the development. (I am not a huge fan of this model but VC looks like that if you squint at it correctly.)
  3. Acknowledge holes in your team ASAP. He talked about how Heroic lacked marketing, finance, and sales expertise. It's possible to go overboard as well here--- but you also don't want to dig a hole.
  4. See things to fruition. Reed gave an example of promotions that were tried and quickly discarded after only a week or so. Some strategic moves need time.
  5. Do things that other people don't want to do. His father gets ten emails a week from people wanting to partner with him. Very crowded space, maybe focus on something less "sexy".
  6. Intimately know your cash situation. Ties in with holes in the team.
  7. Have confidence, but don't take yourself too seriously. Celebrate successes.

Bridget Kromhout, Monitoring at a SaaS Startup. Talked about her work in ops at 8thBridge, and a wide variety of tools. One thing the Tintri support lead emphasizes is that alerts need to be actionable--- don't wake somebody up in the night for something they can't fix. Bridget reinforced this message strongly. Nagios is old but still a good tool for ensuring alerts are what you want. Some of the newer tools like Sensu are so complicated that ops people fear they need monitoring on their monitoring tool.

She shared a couple stories in which 8thBridged goofed some by not using some of the information they had available. MongoDB's MMS was telling them about a global write lock problem but they weren't monitoring or alerting on it. Etsy has a very good monitoring team and tries to monitor even those things that don't seem to be moving, "just in case they make a run for it."

Tools: Graphite and StatsD for collecting and showing stats (they feed info into nagios from them for actual alerting), Whisper for storing time-seris data, Carbon for buffering and storing stats. Slides with more references here: http://www.slideshare.net/bridgetkromhout/monitoring-at-a-saas-startup

Maybe Tintri should look at providing stats directly into some of these tools. She talked about Logstache (?), Kibana, and ElasticSearch as some next-generation tools it might be worth looking into.)

Jeff Lin of BustOut Solutions, "Chasing Ninja Rockstars: Searching for Top Talent and Why We're Doing it All Wrong". I should have given one this a miss. The key problem, as Jeff admitted, is that he doesn't do much hiring. His 13-person team is 5x smaller than the number of hires Tintri made last quarter. So when we asked questions like how to source more diverse candidates, or how to get team buy-in to change hiring practices, he didn't have any suggestions.

He had some good points about team culture mattering, and creativity requiring diversity, but it was not very practical advice on how to get there.

Jeff told an anecdote that pissed me off. At a previous company (not BustOut) his boss took the resumes and filtered out all those with Master's or PhD degrees and said he basically didn't want to hire anybody who had spent too much time in the "ivory tower" because they were out of touch with technology trends.

I'm not sure what Jeff thought the point of this story was (I think it was in support of skills over credentialism) but it directly contradicted much of the rest of what he said about looking for good problem-solvers and people who were enthusiastic learners. Nobody goes for their PhD to get a better salary. (The same may not necessarily be true of MSCS.) I suspect a not-so-subtle side effect is that Jeff's old boss didn't want to pay more for developers.

James Renkin, "Building A Global, Privacy-Conscious CDN On $20 A Day". This talk was pure geeky joy. James located 11 sites throughout the globe that were willing to let his virtual server peer with their BGP (the Internet's routing protocol.) He was thus able to create a content distribution network on his own using BGP anycast to direct users to the "closest" (sort of) server. This is what the big guys do (some root DNS servers use it, Akamai might but usually just uses DNS redirection.) But he did it for an outlay of about $7000/year. About $500 of that is the IP address range (which you have to jump through multiple hoops to get--- he's got an ISP side business which he was able to leverage.) The remainder is running the servers and additional charges for injecting his route into BGP. I learned a lot of this stuff during my PhD work, so this talk made me really happy. I have no intention of duplicating his work, though.

The conference had a couple innovations that didn't work so well. Best Buy let us use their employee parking garage this year instead of visitor parking, but frankly it's a maze (not very well marked, poor traffic flow.) They only had one exit gate opening to leave and more than one person got into the wrong lane.

The organizers brought in food trucks to serve lunch but the lines were long and it was not all that warm a day to be standing outside. I think three trucks was insufficient; it didn't help that it was not clear there were three separate lines, and that one of the trucks opened late.

There was also a keynote from an agile coach that I didn't get much out of. I was amused that he emphasized subtracting things to get more productivity but he's usually called in as an "add" to the team.
(2 comments | Leave a comment)

Tuesday, January 28th, 2014

100 answers on Quora

I reached this dubious milestone this week.

Here are the five answers I've written with the most upvotes:

Given that the digits of pi never end and never repeat, does a running average of those digits tend toward any limit?

Was Facebook or Twitter involved at all in the January 2014 [sic] wage fixing scandal?

What have you learned as an early employee at a startup?

Is suicide a problem in Sillicon [sic] Valley?

How good is ten jack offsuit against two random cards?

Answer I feel is most under-rated:

What is the #1 staffing problem that startups face?
(1 comment | Leave a comment)

Thursday, September 12th, 2013

I can't find the earlier version of this rant, though I'm sure I made it

Nearly every kid (and, heck, probably adults learning mathematics for the first time) who is introduced to the concept of infinity asks questions like "what's zero times infinity" or "what's the square root of infinity" or "can you divide one by infinity?"

Which is most helpful response?

1. Snotty lectures about how infinity isn't really a number, so you can't even ask that sort of question.

2. Reasonable explanations about how these terms aren't always well-defined, and the problems you run into trying to give them a definition.

3. Here are some ways in which mathematicians have tried to answer those questions in ways that still make sense!

Unfortunately, as the links above show, #1 is by far the most popular approach. #2 is not bad, but if you actually want somebody to stay interested in math, I think #3 is far superior.

Mathematics is a game. It's not a set of rules, it's about making up rules and seeing where they lead. And concepts like surreal numbers, projective geometry, and Hilbert spaces all use infinities in ways that are mathematically consistent but "bizarre". Surreal numbers in particular are a great example of taking seriously such ideas as infinitesimals and "infinity plus one" and giving them a concrete meaning instead of blowing such obvious ideas off as stupid. For that matter, the whole field of complex analysis results from taking seriously something that was previously just a "hack" to make the cubic function come out right: "what is the square root of -1?"

Some games don't work out, but that's probably just because nobody's been clever enough yet. Or in some cases, the game is provably not very interesting (which is sort of meta-interesting). But the next time somebody tries to get pseudo-sophisticated with you by explaining how your math question can't even be asked, treat them as you would any other bully.
(7 comments | Leave a comment)

Thursday, September 5th, 2013

Transpositions are Easy

Building on the toy games introduced here.

I figured the easiest tile-game move to analyze is transpositions. Only two tiles are affected by any move, and they have to be opposite colors in any minimal solution. My earlier code showed, for example, that it takes 8 tile swaps (orthogonal moves only) to convert:

and it's pretty easy to find such a sequence of moves. To do so you sort of eyeball where the "gaps" are and which other pieces are closest to those gaps. Can this idea be formalized into a (non-brute-force) algorithm for finding minimal move counts? I think so.

Let's start with the algorithm, then argue that its results make sense. Transform the problem into a minimum-cost bipartite matching problem. The two sets are the goal positions and the pieces, and the edge costs are the distance (in moves) between each pair. So the matrix representation of the transformed problem looks like this:
         pieces -->
goals  0 1 3 2 3 3 3 5   
  |    1 0 2 1 2 2 4 4
  V    2 1 1 2 1 3 5 3
       3 2 0 3 2 4 6 4
       1 2 4 1 2 2 2 4
       2 1 3 0 1 1 3 3
       3 2 2 1 0 2 4 2
       4 3 1 2 1 3 5 3

The minimum selection of 8 elements from this matrix, which share no row or column in common, gives the number of moves in the solution. It's obvious that no fewer number of moves will work. But can we show that this number is achievable?

Now, alas, you can't just read off the matching to get the sequence of moves. For example, in the case
moving "piece 8 to position 3" has cost 2, as does "piece 6 to position 3 and piece 8 to position 6", so both are solutions to the matching, but only the latter is feasible. If we tried to move piece 8 twice we'd need an additional move to put 6 back into place. We need to show that any infeasible plan can be transformed into one which is feasible with the same number of moves.

Fortunately, this is pretty easy. Suppose the plan calls for moving piece A onto the square currently occupied by piece B. This move is a no-op since the pieces are identical in this puzzle. We can remove that transposition from the move sequence by "swapping the identities" of A and B instead of making the no-op move. That is, whenever we would move A to a non-empty space occupied by B, instead swap the labels and continue moving the new "A-prime" (previously "B"). This will leave "B-prime" one space away from its initial starting point, so after A-prime has moved on, use one move to put B-prime back into its starting point (or its goal point). This exactly balances out the move we removed because it was a no-op.
Puzzle:                        *     *
             A     0     0     B     0

Plan:        A -->   -->   -->   -->    (4 transpositions)
                               B        (0 transpositions)

Execution:   A -->   --> rename
                               A'-->    (3 transpositions)
                         B'-->          (1 transposition)

The transformation can be applied multiple times to move through multiple pieces as well, just move the renamed pieces back in reverse order (first-in-last-out). As a check, I ran the minimum-matching algorithm across all 4x4 positions and it agreed with the previously computed values.

Using this algorithm, we can both solve individual large instances as well as perform parallel counts of move distances without using a large amount of memory. The best minimal matching algorithms are O(N^3), though, so this is a significantly more compute-intensive method of finding all minimal word distances than the brute force approach.

This example of a random 12x12 matrix

requires 267 moves to restore to the sorted state, according to this algorithm, with one possible plan (goal, piece) = (0, 0), (1, 5), (2, 62), (3, 1), (4, 2), (5, 67), (6, 60), (7, 3), (8, 4), (9, 56), (10, 8), (11, 9), (12, 70), (13, 71), (14, 6), (15, 7), (16, 65), (17, 12), (18, 49), (19, 13), (20, 14), (21, 15), (22, 50), (23, 51), (24, 10), (25, 63), (26, 11), (27, 64), (28, 20), (29, 66), (30, 21), (31, 69), (32, 28), (33, 61), (34, 16), (35, 17), (36, 18), (37, 58), (38, 19), (39, 48), (40, 59), (41, 54), (42, 55), (43, 22), (44, 23), (45, 24), (46, 25), (47, 26), (48, 57), (49, 46), (50, 52), (51, 31), (52, 32), (53, 27), (54, 42), (55, 68), (56, 37), (57, 29), (58, 30), (59, 44), (60, 45), (61, 40), (62, 47), (63, 35), (64, 53), (65, 41), (66, 36), (67, 43), (68, 33), (69, 38), (70, 34), (71, 39). That is, piece 0 moves left twice into position 0, piece 5 moves left seven times into position 1, position 2 is filled from below, position 3 is filled with the piece "1" already in it. But following the procedure above we can see that piece "5" and "1" will be renamed if we carry out this sequence. (I haven't written the code to actually simulate playing all 267 moves to verify, so there may be an error lurking here but I'm pretty confident in the proof above.)

There might be some way to tighten up the matching to prefer non-crossing moves, for example by increasing "1" to "1.001", "2" to "2.003", "3" to "3.006", etc., to introduce a bias for plans which perform two "real" moves instead of a longer one which will get broken up.

Unfortunately this practical algorithm doesn't seem to provide any hints toward enumerating the distribution of minimal distances for various sizes of board.
(1 comment | Leave a comment)

Sunday, August 18th, 2013


The size of the search space in the toy problem I described in the last post is basically (n^2) choose (n^2)/2 for an n x n board. My initial implementation is in-memory only which only works for 3x3 and 4x4. It ought to work for 5x5 too but for some reason Python (on Windows) just stopped computation rather than giving me an out-of-memory error or finishing.

9C5 = 126
16C8 = 12,870
25C13 = 5,200,300
36C18 = 9,075,135,300
49C25 =~ 6.3 * 10^13
64C32 =~ 1.8 * 10^18

What you need for the brute-force algorithm is basically a bit per tile arrangement (permutation) to tell whether you've visited it already, plus a list of the "frontier" of newly-generated arrangements:

next = []
for X in frontier:
  for P in permutations:
    if P.X not already visited:
       mark P.X visited
       next.add( P.X )
frontier = next

So you only need sequential access to the queue of positions at distance D, in order to calculate D+1; that queue can safely be placed in a file.

9 billion bits is just over a gigabyte, thus a "streaming" algorithm where frontier/next are files will scale at least that far. And could even be written in pure Python! The files for each distance can be stored as a list of numbers representing the positions (no more than 64 GB for this size problem) or we can include some additional metadata if we want to remember the actual word.

How much further could we go using the same basic algorithm? Well, 49C25 bits is about 7.2 terabytes, so in-memory on a single computer is out. But, we could certainly use an array of flash drives to store the visited set. (A Tintri T540 has 2.4TGB of raw flash, but you could get 1 TB SSDs if you really want them.) Assuming sufficient parallelism to keep the drives busy, >=100000 IOPS is feasible, but even if each position required even a single I/O we're talking 20 years. (We might be somewhat smarter about I/Os but on the other hand the brute-force approach will visit the same position many times. Even a million IOPS is still 2 years.)

On the other hand, 7.2TB of memory is only about 31 Amazon EC2 cr1.8xlarge instances, so storing a distributed hash table would be feasible and solve the problem in a much shorter period of time. You would do this in a sort of map/reduce style, distributing the multi-TB list of positions in generation D to each node and have each independently produce its slice of generation D+1. Each node would categorize each P.X as "visited", "not visited", or "some other node's problem", and then merge all the "not visited" to form the list for the next iteration. Of course, you'd need at least at least half a petabyte to store the results, which doesn't come cheaply either. But you could throw money at the problem and it would still be doable within a reasonable amount of time. We're talking about 4 days to stream all the data at 10Gbps, though, so "reasonable" is probably at least a couple weeks.

So what about 8x8? Well, now the hash table itself is 200 petabytes. Even SETI-at-home style resources aren't adequate for this, as you'd need almost 900,000 computers with 244GB of memory to implement the straightforward approach. 200 petabytes is about as large as a storage cluster gets today, or larger, I think--- most examples I can find are no more than half that. (Internet Archive is at about 10 petabytes, Megaupload held about 30 petabytes, Facebooks's Hadoop cluster is 100PB physical.) Instead--- assuming you can build out a multimillion dollar exabyte storage solution for the intermediate steps of the solution--- you'd need to find ways to make CPU-vs-space tradeoffs. The algorithm would have to change at this point, given today's technology, and would probably consume a nontrivial portion of the Internet's communication capability. (Partitioning a second time by giving each computer only part of D and part of the visited set doesn't scale because you require N^2 passes to make sure you found all the previously visited positions in D+1.)

I asked earlier this year whether it's still true that computers can get just one "size" larger than humans--- in this example, I think computers can get 3 sizes larger, assuming the 4x4 grid is human-tractable and the 5x5 is not.
(Leave a comment)

Saturday, August 17th, 2013

Some preliminary goofing around on tile games

My vacation project has been putting together some Python code to systematically study various tile-permuting operations found in match-3 or sliding puzzle games. What I'm interested in is: given a particular goal on a square grid (like making a group of N tiles, or arriving at some other in a set of arrangements), how many moves does it take to reach the goal? Are certain types of moves better suited to particular types of goals?

Read more...Collapse )
(1 comment | Leave a comment)
Previous 10 | Next 10