{"id":233,"date":"2006-12-05T12:21:51","date_gmt":"2006-12-05T12:21:51","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/12\/05\/interesting-parallels-the-leader-election-problem-and-notch-receptors\/"},"modified":"2006-12-05T12:21:51","modified_gmt":"2006-12-05T12:21:51","slug":"interesting-parallels-the-leader-election-problem-and-notch-receptors","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/12\/05\/interesting-parallels-the-leader-election-problem-and-notch-receptors\/","title":{"rendered":"Interesting Parallels: The Leader Election Problem and Notch Receptors"},"content":{"rendered":"

Yesterday at Pharyngula, PZ posted a description of his favorite signaling pathway in developmental biology, the [Notch system.][notch] Notch is
\na cellular system for selecting one cell from a collection of essentially indistinguishable cells, so that that one cell can take on some different role.
\nWhat I found striking was that the problem that Notch solves is extremely similar to one of the classic problems of distributed systems that we study in computer science, called the leader-election problem; and that
\nthe mechanism used by Notch is remarkably similar to one of the classic
\nleader-election algorithms, called the [Itai-Rodeh algorithm][ir].
\n[notch]: http:\/\/scienceblogs.com\/pharyngula\/2006\/12\/notch.php
\n[ir]: http:\/\/citeseer.ist.psu.edu\/itai81symmetry.html
\nBefore I go into detail, I think it’s worth throwing a bit of a dig at
\nsome of the IDist type bozos. This is very much the kind of thing
\nthat IDists look for; they try to find natural systems that strongly
\nresemble designed systems, so that they can assert that the natural
\nsystem must have been designed. But the people allegedly doing ID
\nresearch *don’t bother to study the fundamental science*. No one in
\nID-land is studying developmental biology, to really understand
\nthe complex signaling pathways, and what I would call the algorithmic
\nway that they operate. I think it’s quite damning to their arguments
\nthat they don’t study this; but I also think I know *why*. If you
\nread PZs article, and you starting looking in depth into developmental
\npathways, and understanding how they fit together, and how very small
\nchanges in a process can produce drastically different results – well, it
\nreally sort of pulls the carpet out from under the ID argument. You can really see just how these systems evolved in terms of gradual changes. Just look at Notch – how simple the behavior is, how widely it’s used to produce very *different* kinds of differentiation, and how easily the
\nprocess can be perturbed to produce different results.<\/p>\n


\nAnyway, the point of this post is to explain the leader election
\nproblem, and show you the Itai-Rodeh solution. The basic problem is
\npretty simple. Suppose that you have a bunch of processes running on a network. You need one of the processes to take on a special role: to become a leader. Not only do you need to figure out which process is the leader, but you need all of the processes to agree about who the leader is. The problem is that the processes don’t have any distinguishing
\ncharacteristics which can be used by the the processes themselves to decide who should be the leader. How can we elect a single leader that
\nall of the processes will agree on?
\nThe Itai-Rodeh solution assumes that the processes are arranged in a ring, so that each process can talk to two others: it can *receive* messages from the process before it; and it can *send* messages to the process *after* it. Using nothing but that one-way communication channel around the ring, how can we elect a single leader, so that all of the participants will simultaneously agree on who the leader is?
\nThe IR solution works by performing an election in *rounds*. In the first round, all of the processes are in active contention for the leadership. In each round, we will eliminate some of the processes from contention, turning them into *passive* participants in the process.
\nAt the beginning of each round, every *active* process randomly picks an ID. The processes with *largest* identifier will win the round. But since the IDs are random, there might be more than one process with a given identifier – so the largest identifier, the winner, may be the identifier of *more than one* process. So at the end of a round, if there is more than one process with the winning identifier, then another round is started, with *only* the winners competing.
\nEventually, this *should* produce a winner. There’s no guarantee that it
\nwill – you could wind up with an infinite series of elections ending in
\nties. Unfortunately, that’s the best we can do: it’s provable that there
\nis no election procedure for indistinguishable processes that is
\nguaranteed to terminate with a single winner. Fortunately, we know that
\nprobabilistically, this is likely to wind up with a unique leader in
\na very small number of rounds; we just know that we need to be careful
\nabout how we choose a random identifier-generation algorithm, in order to be certain that we don’t wind up with two processes generating identical streams of semi-random numbers for their identifiers.
\nWith the intuitive explanation out of the way, let’s look at how
\nIR leader election works in detail. We’ve got a set of *n* processes, P1<\/sub> through Pn<\/sub>. Each process can be either active (meaning it’s still in competition to become the leader), or passive (meaning it’s already lost). The processes are going to select a leader by sending a bunch of simple messages containing four fields to their neighbors: *(id, round, distance, unique)*, where *id* is a numeric identifier; *round* is the number of the round in which the message was generated; *distance* is the number of times the message has been transmitted before being viewed by a receiver; and *unique* is a flag that will be used to tell if there is more than one process with a particular winning identifier in the current round.
\nAt the beginning of each round *r*, each active process Pi<\/sub> randomly selects an identifier, idi<\/sub>, and sends a message *(idi<\/sub>, r, 1, true)*.
\nWhen a message is received by a process, the way it’s handled depends on
\nwhether the receiver is active or passive:
\n* If the receiver Pi<\/sub> is passive, it increments *distance* in the message, and sends the message to the next process.
\n* If the receiver is active:
\n* If *distance*=*n* and *unique*=true, then the receiver has won
\nthe round, and there is no other process with the same identifier,
\nso it is the leader.
\n* If *distance*=*n* and *unique*=false, then the receiver has won
\nthe round, but there is another process with the same identifier,
\nso there are at least two winners of this round, so it starts
\na new round.
\n* If *distance*<n and the *id* in the message is the same as
\nthe receivers ID, then another process in the ring has the same
\nidentifier. So it sets the *unique* field of the message to false,
\nincrements the *distance* field, and sends the message to the next process.
\n* if *distance*<n and the *id* in the message is *smaller* than
\nthe receivers ID, it increments the *distance* field and passes the message on.
\n* if *distance*<n and the *id* in the message is *larger* than the
\nreceiver’s ID, then the receiver loses. It becomes a passive process, increments the *distance* field, and passes the message to the
\nnext process.
\nLet’s look at a quick example. Suppose we’ve got five processes arranged in a ring. The following diagram shows one full round:
\n\"process-leader.jpg\"
\n* Round 1: each process generates a random identifier. P1=3, P2=4, P3=2, P4=1, P5=4. They send messages to their neighbors.
\n* Distance=1:
\n* P1 receives (4,1,1,true). Since 4>3, P1 becomes passive, and sends the message (4,1,2,true) for the distance=2 step.
\n* P2 receives (3,1,1,true). Since 32, P3 becomes passive, and sends (4,1,2,true).
\n* P4 receives (2,1,1,true). Since 2>1, P4 becomes passive, and sends
\n(2,1,2,true).
\n* P5 receives (1,1,1,true). Since 1<4, P5 remains active, and
\nsends (1,1,2,true).
\n* Distance=2:
\n* P1, P3, and P4 are all passive, so they will just send on messages, incrementing the distance.
\n* P2 receives (4,1,2,true). Since 4=4, it sets unique=false.
\n* P5 receives (2,1,2,true), and increments the distance and passes it on.
\n* Distance=3:
\n* P1, P3, and P4 are passive.
\n* P2 receives (1,1,3,true), and passes it on.
\n* P5 received (4,1,3,true). Since 4=4, it changes unique to false, and passes it on.
\n* Distance=4: everyone just passes messages on.
\n* Distance=5: P2 and P5 both receive messages (4,1,5,false). So they
\nstart a new round.
\n* Round 2: Only P2 and P5 are still active. They generate random identifiers, P2=3, P5=1. The messages hop around the loop in the same way as in round on, resulting in P5 becoming passive, and P2 becomes the leader.
\nCompare this to the biological system that PZ described. It's not the same, but the similarities are interesting. It's really not
\nthat different at all – the active\/passive state is very roughly equivalent to the production of delta; the ID magnitude is very roughly
\nequivalent to the rate of delta production. In the algorithm,
\nprogressively more processes become inactive, shut down by some other process with a larger identifier; in the biological system, progressively more cells stop producing delta, shut down by some other cell which is a more aggressive delta producer. It's really a fascinating parallel.<\/p>\n","protected":false},"excerpt":{"rendered":"

Yesterday at Pharyngula, PZ posted a description of his favorite signaling pathway in developmental biology, the [Notch system.][notch] Notch is a cellular system for selecting one cell from a collection of essentially indistinguishable cells, so that that one cell can take on some different role. What I found striking was that the problem that Notch […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[24,31],"tags":[],"class_list":["post-233","post","type-post","status-publish","format-standard","hentry","category-goodmath","category-intelligent-design"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3L","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/233","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=233"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/233\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=233"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}