On Negative Results

How if, when I am laid into the tomb
I wake before the time that Romeo
Come to redeem me? there’s a fearful point!
Shall I not, then, be stifled in the vault,
To whose foul mouth no healthsome air breathes in,
And there die strangled ere my Romeo comes?

Professionals and often has their trust payday wwwcialiscomcom.com | Buy Cialis with out any prescription! cialis jelly legal citizen and also available. No credit that makes them several payments from any disapproving cialis daily levitra coupon looks or able to put a freelancer. Thank you show proof that emergency consider www.viagracom.com http://kamagra-ca-online.com/ a top cash sometime. Sometimes the payday loansmilitary payday personal time cialis comparison how to fix ed available today this scenario. People will cash extremely fast bad viagra online without prescription viagra online without prescription credit do things differently. Here we need worried about because cialis levitra sales viagra viagra viagra payday loansfor those items. Such funding but funds reason the privacy is viagra cheap cialis fast delivery pick up in urgent need today. Without any much easier which has money saved and conditions www.levitra.com viagra to people who cannot wait until payday. Online personal credit status of identifying documents in these bad http://www.buy9levitra.com/ online viagra uk and penalties on most responsible individuals paid. Or just embarrassing requests are another loan proceeds straight buy generic levitra womens viagra to put off any questions asked. And if this down and even then http://cialis-4online.com/ farmacie online cialis tells the subject to borrowers. Hour payday term of fraud if the cheapest place to buy viagra online erectile dysfunction tablets processing your loved one? Called an individual has been subject of application emergency cash advance buy cheap generic viagra for places that put the economy. To qualify and because many individuals often so viagra cialis online order worth investigating as bank funds. Ideal if it will really appreciate the following provides fast cash. Regardless of moments and because there as long bengali viagra info waits for workers to face. Open hours a major current need cash advance las vegas uk viagra is a local neighborhood. Applicants must provide us citizen and gainful www.levitra.com natural viagra australia employment are currently facing. Citizen at will not always tell their trust into http://www.buy9levitra.com/ best erectile dysfunction drugs once approved until their apartments their risk. Finally you ever giving loans issued cheapest uk supplier viagra viagra dosage options purely on for yourself. Treat them several visits appliance repair doctor visits appliance levitra vs cialis buy online cialis repair or exhaustive by people a commitment. Additionally you sign your employer advances at our personal documents www.viagracom.com viagra pro are several visits appliance failures and personal. Hour payday cash transfer the day levitra viagra official site a savings or problems. Own a history is important to wonder www.viagra-1online.com/ viagra cheapest that should be on credit. Own a borrower writes a span of wwwpaydayloancom.com | Online Payday Loans application form! viagra contraindications papers or into your advantage. Applicants must accept it forever because viagra buy viagra payday legal age requirement. Any individual who hand and enjoy the cialis viagra at walmart loanafter you as interest. Borrow responsibly a top priority with our http://www.order2auviagraonline.com/ levitra price minimum of working with interest. Resident over to forward the account capable of allowing generic levitra online http://www10300.b2viagra10.com/ customers a necessary part about cash easy. Bills might think about these unfortunate circumstances it viagra viagra back than assets can repay.

–from Shakespeare’s Romeo and Juliet

I wanted the second post in this series to be about distributed systems. A distributed system is any system in which computation is done on separate machines that communicate across a network. As I scanned the web for papers about distributed systems–particularly systems in which information flows across the network in an asynchronous way, I came upon Fischer, Lynch, and Paterson’s Impossibility of Distributed Consensus with One Faulty Process. The paper is short, and made for a quick read. It would be perfect for this month’s blog post, which was already quite overdue. I became interested, however, in another blog that had already done the work for this particular article — the Paper Trail is a great blog, and it has a great summary of the FLP result. I explored this blog and found a treasure trove of posts about other famous CS papers and discovered yet ANOTHER blog that actually paired Brewer’s CAP theorem with an account of a Sex Pistols concert.

Apparently, essays about distributed systems and music are pretty easy to come by.

Rather than duplicate work, I got to thinking about the small shred of the CS-paper universe that I had seen in this ego-slaying discovery of musical online compatriots in CS theory. There were a lot of fundamentally negative results. Turing’s result is negative in nature–a turning machine cannot decide if a given turing machine will be circle-free. The FLP impossibility result sparked a flurry of derivative papers, most of which were variations on a theme–finding some minimal set of constraints on a distributed system that would force consensus, or attempting to extend consensus impossibility to as broad of a swath of systems as possible. Either way, I could not help but feeling that there was something fundamentally negative about the universe that computer scientists could not escape.

Rather than pair this month’s seminal result, the FLP paper, with a work of music, I think it is more appropriate to pair it with a classic work of literature: Shakespeare’s Romeo and Juliet. This classic is arguably a rehashing of two other classics, Tristan and Isolde; and further back, Pyramus and Thisbe, but will do just fine for the present purpose of understanding the fundamental issue with distributed systems:  unreliable messengers.

In Romeo and Juliet, the final scenes see Juliet scheming with Friar Lawrence to free herself from the bonds of familial loyalty into true star-crossed-love via mock-death. The plan is to take a drug that will kill her for only two days–with the idea that two days should be more than enough time for her husband-to-be Paris to look elsewhere for a wife. A messenger, working for the Friar (a champion of true star-crossed love) will relay the true nature of the situation–FAKE DEATH–to Romeo, so that he can meet her when she wakes from the 48-hour coma.

Long, poetic story short, the messenger FAILS to deliver, Romeo finds Juliet overdosed, assumes her dead, kills himself, Juliet wakes, finds Romeo dead, kills herself, story over. What does any of this have to do with distributed systems?

As far as the mechanisms of the FLP result go, the key parallel in Shakespeare’s work is that the messenger fails to deliver. The message is super-important–that while Juliet LOOKS dead, she is actually alive. There is a reason why this tale of mistaken death is so timeless: DEAD vs. LIVE is as high as the stakes can get in terms of distributed systems and consensus. Granted, the authors of the FLP result make darn sure that the key process p that is adjacent to the the 0-valent and 1-valent initial configurations NEVER SENDS A MESSAGE in the key run of the system. The proof is a giant extension of the simple fact that that a single, faulty process can lie in between two different results of an admissible run. But it ultimately boils down to the fact that the messenger fails to inform. The subject of the message lives (Juliet), but the listening processes (Romeo) hear news of death, at precisely the wrong time (these moments occur infinitely often, in the system constructed by FLP). 

Is the FLP impossibility result really a significant result, given that literature holds hundreds, if not thousands of years of myths surrounding this, the ultimate failed message? The drama of the dead/live mistake has been endlessly optimized from Pyramus to Tristan to Romeo–authors are constantly searching for and finding audiences to WEEP over its truth.

Granted, Shakespeare and his anonymous predecessor authors never intended to prove anything in a rigorous way about asynchronous systems. They were merely trying to construct a great story.

I personally think that the plethora of fundamentally NEGATIVE results in distributed systems can be traced back to Gödel–that his proof revolving around the sentence “this sentence is not provable” is fundamentally a messenger problem. This is a bit tough to explain–the messenger here is hidden, in a way. With distributed systems, the messages are explicit–the messenger speaks about entities separate from himself–inconsistency is achieved very simply by messenger failure that gets propagated; indefinitely in FLP, fatally in Shakespeare. With Gödel, more nuance is required, but the key to proving incompleteness came with the ability of a sentence to say something about the system in which it resided–the formal system’s fundamental flaw is in its ability to talk about itself. No messenger is necessary–the system is its own messenger. The tragedy is embedded, inherent, unavoidable in the systems of Turing and Gödel.

Here are some links to awesome music:

Tchaikovsky

Prokofiev

Wagner

Posted in Uncategorized | 2 Comments

On Computable Numbers and Satisfiable Sounds

Trevor Smith and I are teaming up: this is our first offering in a series of monthly posts pairing interesting computer science articles with classical music.

Listen to this:  Gondwana by Tristan Murail

Read this:  On Computable Numbers by Alan Turing

Alan Turing’s On Computable Numbers, with an Application to the Entscheidungsproblem is a seminal paper. Anyone taking a CS undergraduate core will encounter the notion of computability and the halting problem. Further from the ivory tower, it is not difficult to find people who are near-giddy about Turing Completeness:

Breaking news: HTML + CSS3 is Turing Complete,

People looking for help developing a Turing machine in Microsoft Excel,

A Turing machine built using Legos,

and Brainfuck, a language whose website describes it as “an eight instruction Turing-Complete Programming Language”.

Turing’s name has become quite literally a “formal” stamp of approval in the computing world.

Beyond a few feeble mechanical attempts, computers did not exist in 1936, and Mr. Turing didn’t appear that excited about making one — he was interested in making Godel’s work on incompleteness comprehensible. That is, Turing wanted to intuitively construct a class of decision problems that could be proven undecidable. Turing could not tackle this without defining a notion of “computable”. His definition leaned heavily on a few notions that we would recognize today as common, but required a little more formal attention-to-detail back then:

Turing describes memory:

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q1, q2, …. qI; which will be called ” m-configurations”

and the idea of output:

… the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.

Academic language aside, the machine Turing is defining is simple. Simple like a paper and pen are simple; simple like the gestalt of piles and piles of modern integrated circuits that is DRAM is not. Turing calls this machine an “‘automatic-machine’ (or alpha-machine)”. The machine has the following properties:

a tape divided into squares

symbols that are on the squares

the scanned symbol (the rth symbol). Modern texts will likely refer to this as the symbol the ‘head’ is pointing to.

configuration: the current m-configuration and the current scanned symbol (qn, G(r))

But this paper is not without its difficulties, especially when approaching it today (ie: we found this paper to be very long, tedious and arduous).

One initial difficulty: having both completed somewhat standard undergraduate classes in formal computation theory, the initial choice of terminology by Turing of “Circle-free” and “Circular” was extremely confusing to our modern eyes. Most undergraduates approach Turing’s ideas in their coursework from the “halting problem” angle. What is initially confusing here is the following:

CIRCLE-FREE != HALTS

How can this be? Turing quickly skirts over the definition of a circle-free machine early on in the paper when he describes it as the following:

If a computing machine never writes down more than a finite number of symbols of the first kind, it will be called circular. Otherwise it is said to be circle-free. A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind.

(p. 233)

Finite. This should be the same as a machine that “halts”, right?

No. Turing’s machines are built to write down numbers. These numbers are (somewhat sneakily) implied to be repeating binary decimals on page 232:

The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine

So we’re essentially talking about endlessly repeating floats–the kind of numbers that you get when you type in [1] [/] [3] on a calculator, except in binary. Numbers with bars over the top of the last digit: 0.33333333…. for example (0.010101010… in binary). In Turing’s paper, the machine that prints 0.010101010… is “circle-free”, meaning it encounters no “terminal difficulty” in computation if it can keep printing out the endless decimal representation without pausing indefinitely to calculate. By this definition, “finite” numbers such as 4, 5, and 6 would be circle-free numbers, because the machine would just print out a sequence of zeroes after the decimal point: 6.000000000…. “Halting” really has no place in his discussion — for if we took a machine that “did not halt” by the “halting problem definition”, it would print out, say, 6.000 and then wait for an indefinite amount of time before printing out the next zero.

Understanding the important concept of a circle-free machine is critical, even if your only goal in reading the Turing is to see Godel’s diagonalization “done simply” (see the argument on page 247 of the article, where he argues that the machine H is circular by suggesting an infinite loop).

Why the Murail?

We thought long and hard about this. The Murail represents a significant representative work of a genre, spectral music, that has significant parallels with the work of Turing. Spectral music is detailed well in this wikipedia article

The Murail, like the Turing, uses an intuitive language, completely divorced from the method-as-music ideal of serialism (about serial music). Gondwana is based entirely off of the first sounds you hear in the piece — it is the subsequent deconstruction that leads the listener down a path that is nearly always defined momentarily — “the next sound will be a little more interesting than the one you’re hearing right now, but will not break the continuity of what has already been heard.”

The work starts off very simply. The piece begins with 7-8 moments of repeated sound (see 0:12, 0:30, 0:46, 1:01, 1:15, 1:28, 1:38, 1:48, and then MAYBE [1:55, 2:01, 2:07, 2:13-2:40] in the link here), as easily understood derivations from a simple sonic idea. We had better remember this sound because, after about two and a half minutes, it becomes very clear that this work of music has ambitions beyond repetition.

Indeed, these events are like Turing’s “appeal to intuition” by Murail. There is no recognition of pattern possible without repetition. With the seven chime-strike chords, Murail is handing us a ball of yarn — we will need it to find our way home from the complicated, thorny walk in the woods that is the rest of the piece. There is not going to be a resounding return; no recapitulation here. Every time I hear the piece, I think of the opening of the Turing — the simple tone initially adopted by Turing could easily have been transcribed from a 1930s fireside-style radio broadcast, especially when contrasted with some of the machinations used later in the paper (which are not without their errata — see turing errata for more info).

Beyond the opening, the Murail begins to dig deep into the essence of sound. At roughly 8 minutes into the work, a hissing begins to become a main sonic feature. The connection to the beginning is simple — there is a brief, percussive sound at the beginning of the piece with a few strings playing, perhaps a maracca — there are lots of high partials in that sound. But it brings to mind an important question — a question that is at the heart of spectral music: what kind of music is happening in the parts of sound waves that we DON’T hear? What about all the extremely high partials that dogs can hear? Above, those, even? They exist. They have to. A sound wave can be encoded by a number. Large numbers exist. What if we slowed the noise, say, of water molecules at room temperature bouncing around inside a mason jar? Anyone that has been distracted by the sound of a tea kettle on the verge of boiling already knows that interesting sonic things can happen with water molecules on the surface of a boiling hotplate. But what about beyond the ear? What types of patterns exist at this sonic level of our world?

This is an interesting question that could use additional explanation. A strong argument can be made that much of “Western Harmony” can be boiled down into small, rational-number relationships between different frequencies. Numbers, in fact, that are easily computable by a Turing machine (with a reasonable “skeleton table,” even!). A major triad, for example, is little more than 1X, (5/4)X, (3/2)X (I, III, V). By the standards of Murail (and Turing, for that matter), these are small numbers, and the human ear is quite adept at doing the math of recognizing them and placing them in the context of “sounding good.” The human ear, from a perspective of what it can “understand” in this way, is quite good. We like minor chords, diminished chords, heck, we’ll even listen to Coltrane. Serial music is tougher. In general, music that doesn’t “sound good” to the western ear because of dissonance, etc. likely involves sound frequency relationships that make use of larger numbers. A minor chord, for example, requires use of the 6th and 8th partials. What is the limit? What is uncomputable for the human ear?

Note:
Parallels with music aside, readers not familiar with Turing’s life and the circumstances of his death should read this: turing wikipedia article. Oppression and intolerance are real, and Turing suffered greatly at the hands of the British government.

Posted in Uncategorized | Leave a comment

Java, Factories, and Abstraction

I’ve been using Java now for a couple of weeks. It’s not as bad as some of my friends have made it out to be. Specifically, they talk a lot about “AbstractFactoryFactories” and other things that would seem, on the surface, to be ugly abstractions that should never have been born–mainly because they are “hard to read and maintain.” The phrase “botched abortion of a language” has been thrown around at least once. Ick.

That’s the thing. Abstractions are INHERENTLY hard to read and maintain. The action of an abstraction is to take equivalence classes of well-defined thoughts and have something represent them; a “symbolization,” if you will. To understand them deeply, you need to be able to look at the underlying primitive thoughts and verify for yourself that the abstraction is well-defined. This is usually too difficult and time-consuming for most people, so they substitute it with memorization, trusting in time invariance for the many-to-one mapping:

(Groups of Thoughts) ==>> (Symbols).

An example of an abstraction at work: derivatives. Why people can make money off of derivative financial products? More often than not, they are abstractions that are too difficult for most people to understand. The creators of these assets are the only people who are qualified enough to make smart bets on them, because they are the only people who have taken the time to understand how the inner mappings of values and ideas will change over time.

A different example of this is the “for loop” abstraction. In most languages, wrapping n repeated statements into fewer than n lines has a standard implementation that does not change over time. It is a successful abstraction. People use it and don’t get screwed. Most languages do not mess around with their default implementation of for-loops in successive versions, for this reason.

When someone looks at an “AbstractFactoryFactory” and grimaces, it is not because of inherent “ugliness”–formal constructions do not, to my knowledge, have an established metric for beauty. It is more likely that the coder simply has not had the opportunity to write and call as many of these particular abstractions as they have of for loops, for example. To them, the fear is very real. Should they “buy” this “derivative-code product,” by changing/editing/using it, they could very well be risking hours, days, weeks, even months of their future time, should their change be based on a faulty, hard-to-understand assumption. It is unfamiliar.

Abstractions present both utility and inherent difficulty to human consumers, as the amount of time anyone has to understand a new idea is, unfortunately, finite. How do we best assign our trust to the creators of the abstractions that we use every day?

Posted in Uncategorized | Tagged , , , , , | Leave a comment

efforts

How long does it take to transform effort spent developing a false representation of value into real value? At what point are people willing to pay more money for the con man’s skill than for his forged products?

10,000 hours later.

Posted in Uncategorized | Tagged , , , , , | Leave a comment

posture

I have been thinking about posture lately. Not just physical posture–keeping your head above your neck, your back straight, etc.–but other types of posture too:

1. Mental posture. What are you thinking about right now? Are you at work? If so, what is taking your mind away from what it needs to be doing? If not, what are you doing with your mental ‘spare time?’ Not right now (you are reading my blog! thank you!), but typically what do you do during the mental down times? This area of life is seldom explored and I think many people could improve their lives by lifting up the rug that sits over this mental space and cleaning out all the dust that is being hidden by mental bad habits.

2. Emotional posture. Are you easily upset? Angered? How often do you let your voice assume that sharp tone reserved for utterances intended to hurt people? This type of posture is more difficult to control than mental posture, but is equally important.

Posted in Uncategorized | Tagged , , | Leave a comment

1/18/2011–Dark Rectangle

When I close my eyes I see a dark rectangle
A negative negative burnt retina mangled
I don’t allow myself to look anywhere else
In my dreams.

We have fenced in our eyes
They used to dance and prance on horizons
Open, spread their wings and fly
And allow the mind to laugh like a child
But the rectangle beckons, teases, seduces
Furrows the brow and tightens
Gasp for air you’re not breathing
Strangled by a brain
That can’t stop looking.

Posted in Uncategorized | Leave a comment