On “Humming Consensus”, an allegory
"We reject kings, presidents, and voting. We believe in rough consensus and running code." -- David Clark, about the IETF
And to quote a paragraph from the introduction of https://tools.ietf.org/html/rfc7282:
To reinforce that we do not vote, we have also adopted the tradition of "humming": When, for example, we have face-to-face meetings and the chair of the working group wants to get a "sense of the room", instead of a show of hands, sometimes the chair will ask for each side to hum on a particular question, either "for" or "against".
In my imagination, I see a kind of humming consensus, somewhat in the sprit of the IETF’s humming consensus. A network partition means that not all participants can hear the pitch/notes of the hummers on the other side of the partition. Yet despite partitions where not everyone can hear everyone else, we can determine a rough consensus that is good enough to solve some distributed systems problems.
In a Musical Galaxy, Far, Far Away…
We wish to compose a piece of music called the One True Song Manuscript of the Universe. The OTSMotU will be composed concurrently by multiple composers. This is a recipe for musical chaos, unless we add some additional limits. The limits will, very roughly, be like choosing a musical genre that all of our distributed composers must use.
(Aside: I’m trying to avoid using the word “score” in this document because it could mean a piece of written music or a numeric ranking of some kind. this analogy uses both meanings.)
The genre of music places restrictions on choices of instruments, key signature, chords & chord progressions (if multi-voicing is allowed at all!), acceptable rhythms, etc. What if we choose to compose plainchant? Let’s make things even easier than plainchant! Let’s adopt Gregorian monophonic plainchant rules but also disallow words entirely and we only accept whole note (single note per measure) rhythm.
In short, we’re only allow composition of very limited melodies. Hummed melodies, to be precise. {grin}
That sounds easy, right? Well, perhaps. But our composers are also professional hummers, and they’re going to perform the One True Song Manuscript of the Universe while it’s being composed. Concurrently! This sounds like improvisational jazz, perhaps?
Many copies of the music manuscript
No musician can ever see the entire One True Song Manuscript of the Universe (OTSMotU) at all times. A composer is never separated from her/his manuscript, so a composer can always read her/his manuscript. However, reading a copy of another composers’ manuscript is different matter.
Many rooms for the composers to work in
All composers prefer to work in the same concert hall where everyone else composes and hums, but that isn’t always possible. Sometimes a composer calls for a “sectional rehearsal” and moves to a rehearsal room in the basement. These extra rehearsals are usually unplanned and unpredictable. The sectional rehearsals may be a single composer or really any sub-group of the composers. The rehearsal rooms are both soundproof and have doors without windows; from the outside, nobody can see copies of the OTSMotU sheet music inside a rehearsal room or hear what is being hummed inside the room. Any writing or humming work can be done in the big concert hall or any rehearsal room at any time.
Composers can also what other composers are proposing by reading from other manuscript copies. Unfortunately, a composer can only read (or write) a copy that’s in the same room as the composer. In general, however, if a copy is in another room, that’s OK, we will continue based on the copies that are available in the room at that instant of time. Also, we don’t worry about the time spent walking between rehearsal rooms and the main concert hall: we assume that the composers can walk infinitely quickly between all of the rooms.
Writing music into other copies of the One True Song Manuscript of the Universe
The crazy & beautiful thing is that each composer may write to any other composer’s copy of the manuscript! Each measure of the OTSMotU’s music is identified by a measure number; we’ll call it “M” as short-hand notation. Each composer can propose a single value for measure M: pitch, rhythm, etc. If some manuscript copy already has music written at measure M, then any attempt to write to measure M will fail because of the ink that each composer uses. Why? Read the next section, on indelible ink!
Each composer writes to her/his manuscript copy first, and then if successful, to all other copies that are in the same room at that time. If some copies are in another room, that’s OK, we’ll continue with our work anyway. The details will be clear, soon. Please be patient with this storyteller.
Indelible and atomic ink
All measures are written in indelible ink that can never be altered. If a composer has written music to a copy of measure M of OTSMotU, nobody can alter or erase that copy’s measure M. The indelible ink has another special property that we rely upon.
The ink is both indelible and “atomic”: a composer can write an entire measure of music atomically, meaning that the writing appears to be infinitely fast and results in either a perfect measure of music or a perfect empty measure. No single copy of any given measure of music can ever be partially written.
Composers work at different speeds
Each composer operates at his/her own speed and own working rhythm: some are fast, others slow. Some are morning birds and others are night owls. All composers in a given room can see & read from everyone else’s manuscript copy in that room; all manuscripts in other rooms are inaccessible. Composer Z might take a nap, no matter the time of day or what room Z is working in, but any other composer in Z’s room can read or write Z’s manuscript.
In any race between multiple composers who attempt to write to the same manuscript copy of measure M, there is always exactly one winning composer. The indelible nature of each manuscript copy gives us a lot of safety and peace-of-mind. Any slow or sleeping composer can try to write music without damaging any music written by composers who are awake or who are simply quicker.
For example, what if Composer A is just too slow and wakes up very late one morning. Composer A discovers that composer B has already chosen music for measure M and written it to A’s copy of measure M. (Composer B also wrote measure M in her manuscript and all other manuscripts in the room while A was sleeping.) Measure M cannot be erased or changed. Composer A has two choices: accept what B wrote or else try to write some new music at some measure M+1 (or later).
Let’s Review!
In the rules as we agreed previously, we have quite a limited amount of information in a single measure of music:
* a single whole note (the only rhythm we’re allowed to use)
* the single whole note’s pitch
If we used modern notation, it might look something like this: 
It would be helpful to add an annotation that separates composers who are humming from those who are not. We could add dynamic markings (e.g., loudness or softness of volume), except that such marks didn’t exist in the 14th century.
To be pragmatic, let’s make a small break with 14th century conventions and add some new music markings.
* Break the each measure of the manuscript into per-composer lines.
* Add the “rest”: the composer is not humming at all, i.e., the
composer is silent. * Add a simple one-measure crescendo: a voice goes from silent to full volume. * Add a simple one-measure decrescendo (also called a “diminuendo”): a voice goes from full volume to silent.
3 part unison musicNeato! Now we have information about which composers are asleep or believed to be in another room, using a rest marking. When we believe that a composer has awakened or returned from another room, we can add a crescendo. When we believe that a composer will go to sleep or leave for another room, we can add a diminuendo/decrescendo.
3 part unison music, with restsPlease note that whenever a composer writes a copy of measure M, the indelible & atomic ink will write to all parts/voices. For examples, this includes any single measure of all three parts (A’s, B’s, and C’s) in the previous two examples of 3-part unison.
Did You Just Tell Me to Go {CENSORED!} myself?
Hey, storyteller! Cool story, bro. This doesn’t give us a path to consensus! You are a liar! It wouldn’t be as bad as mixing Mozart, Ingve Malmsteen, and Woodie Guthrie together, but it would be musical chaos nonetheless. It could generate polyphony (e.g., multiple notes played simultaneously), which is definitely against the rules that we agreed upon. It could also create unsafe voice leading, e.g., tritone intervals, diabolus in musica or “the Devil in music” that is also a big no-no.
Yes, of course. You are correct. Let’s add a few more pieces of musical notation and a few more rules. Then we’ll see that rough consensus is possible.
Dividing the Musical Manuscript Into “Public” and “Private” Halves
Let’s divide each manuscript copy into “public” and “private” halves. Each manuscript half has two copies for any measure M: the public version of M and the private version of M. Both halves of the manuscript are written in the same indelible ink that was described above: each measure in either half can be written exactly once and never altered afterward.
The word “private” has a special meaning for writing any measure M.
* The private half of the manuscript is **only writable by the manuscript’s owner.**
* The private half of the manuscript is readable by anyone in the same room.
The rules for the “public” half are different.
* The public half of the manuscript is **writable by anyone in the same room.**
* The public half of the manuscript is readable by anyone in the same room.
For any composer X, X will only write measure M of proposed music P in her/his private manuscript copy if:
1. Unison with everyone else in the room: The proposed measure of
music P is equal to the music written on everyone’s public manuscript copies for measure M, including X’s own copy. 2. The genre rules are unbroken: The music of all of X’s private manuscript’s written measures, from the beginning through measure M, do not violate any genre restrictions (i.e., our plainchant + humming + rhythm restrictions).
If both of these conditions are true, then composer X will write the proposed music P to X’s manuscript’s private half at measure M.
Aside: a comparison with CORFU
We interrupt this allegory to bring you an important news bulletin.
This allegory about music composition is quite close to the CORFU protocol’s method for creating consensus. The main differences are:
1. Actors in CORFU do not hum or make other noise, really.
2. The atomic unit of writing/reading data in CORFU is a single page.
In this allegory, we talk about a single measure of music. 3. CORFU has only a single storage area type, equivalent to this allegory’s “public” manuscript. 4. CORFU includes a special “sequencer” actor who tells each composer what measure number to write his/her proposed music at. 5. If you cannot talk to the CORFU “sequencer” because the sequencer isn’t in the same room/network partition that you’re in, then you can try to guess an unwritten page number and write to it. If the server at the head of the chain tells you that the page is already written, then you’ve guessed incorrectly and you should try to guess a larger page number. 6. CORFU specifies exactly one order in which any writer may write a page to a replica server: the order of the CORFU chain is the one and only order, and all writers must obey that order. In this allegory, order doesn’t matter, so the suggested order is: a). try to write to your personal copy first, then b). try to write to all other copies in your room, in any order. 7. CORFU supports only strong consistency and therefore cares more about failed writes to replica servers. Humming consensus is more lakadaisical: write or read errors (or timeouts) don’t always cause a failure of the write/read operation.
Time for a break
My apologies, but I’m quite tired by all of this storytelling. I need a bit of a break. I need some time to edit and refine and condense my allegory about the One True Song Manuscript of the Universe. I am honored that you’ve spent so much time reading my story. I hope that it makes you want to compose some music of your own.
I also hope that you find that allegory isn’t a very satisfactory way to describe algorithms. Running code and formal specifications are two examples of much more precise descriptions. Perhaps this storyteller can return with a bit more precision, sometime soon?
Credits, etc.
* Using allegory to describe distributed systems is an old idea, going back at
least as far as Lamport’s “The Part-Time Parliament” and probably much further back than this poor storyteller knows. * Music notation by http://www.noteflight.com. I took screenshots of the browser window, then reduced the resolution to try to fit comfortably into a Web browser window.