Consensus Protocols: Two-Phase Commit

For the next few articles here, I’m going to write about one of the most fundamental concepts in distributed computing – of equal importance to the theory and practice communities. The consensus problem is the problem of getting a set of nodes in a distributed system to agree on something – it might be a value, a course of action or a decision. Achieving consensus allows a distributed system to act as a single entity, with every individual node aware of and in agreement with the actions of the whole of the network.

 For example, some possible uses of consensus are:

  • deciding whether or not to commit a transaction to a database
  • synchronising clocks by agreeing on the current time
  • agreeing to move to the next stage of a distributed algorithm (this is the famous replicated state machine approach)
  • electing a leader node to coordinate some higher-level protocol

Such a simple-sounding problem has surprisingly been at the core particularly of theoretical distributed systems research for over twenty years. How come? As I see it, the answers are threefold.

Continue reading

The Problem With Mind Readers

This is an essay that I wrote for a competition in College. The competition was for the ‘best explanation of a principle of scientific interest to the general public’. I twisted the definition somewhat and wrote a very light – and rather flawed – introduction to Turing’s Entschiedungsproblem work in the context of explaining what a computer scientist really spends her days thinking about. These are both subjects that are close to my heart: on one hand the tragic life of the brilliant Turing as arguable father of computer science, and on the other the correction of now pervasive assumptions about what computer science is and can be. I don’t think I did either justice, but, happily, the judges seemed to like what I had to say and awarded me first prize.

Despite the prize being a substantial cash sum, it wouldn’t surprise me if there had been only a few entries – but you can only beat what’s in front of you 🙂

In Defense Of Computer Science

Computer science, as an academic discipline, has been the subject of a great deal of scrutiny lately. Of particular interest has been the worth of a CS degree to us, the fee-paying consumers who apparently want nothing more than to transform their college dollars into CV-ready bullet points that will smooth the path to the cubicle job of our dreams.Many of the arguments in these recent exchanges have been predictable. Java is used as a placeholder for all that is wrong with the subject, because teaching it as an introductory language sacrifices pedagogical merit for practical applicability. Proponents of its use retort that they’ll never use type theory anyhow, so what use is it learning it in the first place? The reply is that if they knew about it, they’d get a job where they had to know about it, and so on.

What has surprised me most is that no-one has stood up and defended computer science on its own merits: as an academic subject of some breathtaking beauty and profundity.

Continue reading