Going to Toronto

So the number of posts in the next two weeks would be even lower than usual.
Going to present my paper on failure detectors in distributed computing systems, wish me luck.

The McClintock Effect (synchronize your watches!)

In order to not scare the male readers of this post (all two of them!), I chose to name it "The McClintock Effect". A far better name would be, "Does menstrual synchrony really exist". However now that you are reading it, you have no other option but to continue doing so.

The story begins when Martha McClintock published a rather sensational article for Nature in 1971 where she claimed that women who live together tend, for example, in college dorms, tend to synchronize their menstrual cycles. Her research was based on another article that showed that female rats do the same (though their cycle is only few days long), and further work showed that this phenomena exists in other mammals (notably, in chimps).
However, McClintock failed to explain the mechanism behind such synchronism or give any evolutionary explanation for the its existence. Naturally, it faces a lot of criticism, culminating in the 90's (but the debate between pro synchronists and those against it linger on). The critics point to the fact that since different women don't have the same cycle length, synchronism, if any, is just temporary. Moreover, they show errors in the statistical analysis carried by McClintock and others, and even claim there's no evidence for synchronism in rats. See this column on Straight Dope for a short review of McClintock's and her critics' claims.

But I don't care about it. I believe that unless we will lock up female couples in tight cells with no interaction with other females (and probably no interaction with other males), even if there is a mechanism that provides cycle synchronism, we won't notice it working. The signal to noise ratio is too high to see any evidence for such synchronism.
To show my point, I coded a quick simulation of female students. The simulation consisted of
100 students, each having a roommate, a best friend, and a casual friend. If student A is a roommate or best friend of student B, student B is a roommate or best fried of student A. However student A can be a casual friend of B without B being the casual friend A.
Every hour, each student is meeting one other student in random. There's 48% chance she would meet with her roommate, 24% chance she would meet with her best friend, 12% chance she would meet with her casual friend, and 16% she would meet with a random student in the dorm. In real life that would mean, about 12 hours are spent daily with your roommate, 6 with your best friend.
When two students meet up, they compare their cycle. If A is after her menstrual phase in her cycle, while B is before it in her cycle, A prolongs her next cycles by an hour, while B shortens her by an hour. This would ideally make their next cycle more synchronized.
Each student enrolls to the dorms with a cycle of between 27 and 33 days, and a random offset within it (that is, random number of days until her next menstrual phase).

What happens after 365 days? Does a student cycle become more similar to the cycles of her friends (that is, the difference between her offset and the weighted average of her roommate and friends offset)? If not, does her menstrual phase align just with her roommate?
The answer to all those questions (according to my simulation) is a resounding NO. There is no evidence that the students and her friends have more aligned cycle after a year. Here's a representative output of my simulation, displaying the offset in hours between a student's cycle and the weighted average of her friends' cycle, and between her cycle and her roommate's.

Before enrolling to dorms
distance from roommate= 232  distance from friends+roommate= 230

After a year
distance from roommate= 255  distance from friends+roommate= 254

If anything, enrolling to the dorms only makes the student less alike her friends when it comes to her menstrual cycle. I acknowledge I may have some bugs with my simulation and some false assumptions (I have to leave in a couple of hours to take a flight), but I have a feeling the bugs eliminate each other.
Therefore, I think that this simulation shows that even if there is a mechanism that synchronizes females' cycles, we won't notice it. What do you think?

Friday's mutation

The duck with four legs, from Scienceray's list of "The Weirdest and Coolest Deformed Animals on Earth".

Contagious cancer in Harper's magazine

Harper's magazine has a (too) long article on contagious cancer. Although the article focuses on Devil Facial Tumor Disease its main selling point is talking about cancer (any kind of cancer, not just freak contagious ones) in evolutionary terms. Cancer cells are another example that self replication is a driving force in nature. Once an object (in this case insubordinate cell) is able to self replicate, natural selection takes hold, and it's hard to look back.

Maley and Reid have more recently taken such thinking one step beyond evolution—into ecology. Along with Lauren M. F. Merlo (as first author) and John W. Pepper, they published a provocative paper titled “Cancer as an Evolutionary and Ecological Process,” in which they discussed not just tumor evolution but also the ecological factors that form evolution’s context, such as predation, parasitism, competition, dispersal, and colonization. Dispersal is travel by venturesome individuals, which in some cases allows species to colonize new habitats. Merlo, Maley, and their colleagues noted three ways in which the concept of dispersal is applicable to cancer: small-scale cell movement within a tumor (not very important), invasion of neighboring tissues (important), and metastasis (fateful).

Reading that, I remembered Devil Facial Tumor Disease and wondered whether there might not be a fourth way: transmissibility. An infectious cancer is a successful disperser. It colonizes new habitat. DFTD seems to be dispersing and colonizing, much as pigeons disperse across oceans, colonizing new islands. This wasn’t just evolution; it was evolutionary ecology.

I called one of the paper’s coauthors, John W. Pepper, an evolutionary biologist at the University of Arizona, and asked whether I was stretching the notion too far. No, he said, you’re not. If he could revise that paper again, Pepper told me, he would insert the idea that tumors evolve toward transmissibility.

Short update - another (short) article on looking at cancer as an evolutionary process can be found at "Survival Of The Fittest: Even Cancer Cells Follow The Laws Of Evolution", a summary of a recent article by Yeang et al.

Spore's .png format (illustrated)

Well, the obvious just happened, and I found that my work on decoding Spore's image files was in vain. A couple of clever guys from Something Awful have reversed engineered Spore Creature Creator to gain insight on the way it encodes the creature models in .png files, and then published a Python script to decode them. Looking at the encoding algorithm (which includes encryption and permutation), I'm quite sure that I couldn't find it by just examining the image files, and reverse engineering was the right path.

Following is a brief description on the steps taken by spore to encode a creature. Some of the details were omitted, just to make the big picture a bit clearer. If you know your way around Python, you may want to fill those missing details later.

So, lets start with the basics. We are given a creature model, in text format (xml) and a image of the creature. The model file is about 30k in size, and the image's width and height are 128 pixels, making it 16384 pixels long. Each pixel is composed of 4 bytes (for red, green, blue and transparency channels), which makes the image 65536 bytes long. Each byte is composed of 8 bits, where the least significant bit, the one that changes the value of the byte the least, is called the LSB.

Now, that we have our definitions straight, we can turn to the encoding process itself.
First, take the creature model, and compress it (using the deflate algorithm, nothing novel here). This usually shrinks the model size to less than 8192 bits (I'm really sorry for the Powerpoint graphics).




Add to the compressed model a header, footer containing a strong CRC (to make sure you would not open an erroneous model) and pad it with zeros to make it exactly 8192 bits long.

Now, take the image and produce an encryption key using the value of its bytes. This is done by first applying a permutation on the image bytes, and then scrambling them. The final encryption key is 8192 bits long.


Xor the compressed model bits with the key bits to produce an encrypted model. The thing to remember here is that given the key, you can simply Xor the encrypted bits again to gain the decrypted model.

Replace the the LSBs of the bytes in the image with the encrypted model bits. Since there are 65536 bytes in the image, there are 65536/8=8192 LSBs, so we have enough room for the whole creature. One last twist, you don't just replace the n'th LSB with the n'th encrypted model bit. You actually have a premutation function, p, and change the p(n)'th image LSB with the n'th model bit. Since we are changing only the least significant bits, we may not notice any change change in the output picture at all.



One thing to note - when we are creating the encryption key from the image, we don't use the image LSBs (as a matter of fact, we don't use the 3 least significant bits of each byte). This enables us to get the same encryption key from the encoded key as the one we got from the original image, even though we changed the LSBs.

Using the image as the encryption key was a smart move from Maxis, since it disable the evil user from simply taking the LSBs in one image and replacing them with LSBs from another image, to create a creature that looks one way in Sporepedia, and another within Spore. A more sinister user might have encoded a model that would crash your computer within an innocent looking image (for example, he could create a model, that when compressed weighs less than 8192 bits, but when expanded, weighs hundreds of megabytes).

So, is that all? Can we now encode the NSFW creature DonkeyPunch (by Tastyhumanburgers)


in the cute and lovely Crowned Laggie (by vib rib)?



The guys in SomethingAwful also published an encoding procedure, but it usually doesn't work. You can encode your creature in its own image, in a slightly changed version of its own image (you can move a pixel here, delete one there) and even encode the creature in a blank image. But you can't encode one creature in another's image.

We are surely missing something, but I can't tell what, two possible guesses:
1. Spore checks that the creature model resembles the creature in the image file. I doubt it, since you can encode a creature in a blank image.
2. Spore doesn't use the 3 least significant bits in each byte when creating an encryption key for a reason. We know that one of the bits is used to encode the creature, could the other two be used to encode some kind of an additional checksum? I doubt that too, but this post is long enough without going into my reasons.

Ideas?