Smalltalk
› Squeak
› Croquet
›
Croquet - Dev
Simple voting protocols?
Locked
 
|
Hi Folks -
Just had a nice chat with Brad about replicated routers (e.g., to make it so that Croquet has no single point of failure) and it seems that a nice and easy way to do that would be to simply add "backup" (downstream) routers to the "master" router, and, if the master router goes down, have the downstream routers decide which one is the new master and simply take it from there (other details deliberately omitted ;-) But herein lies a problem: We currently don't have an implementation of a voting protocol (byzantine or not) by which the backups could decide whether the master is considered down or not and which of the backups becomes the new master. My question is: Does somebody have an implementation (or a decription of) a *simple* voting protocol that would serve these purposes? I'd really like the idea of truthfully claiming that Croquet doesn't have any single point of failure (but I don't have infinite time to go and implement Paxos ;-) Cheers, - Andreas |
|
|
Just some thoughts for a quick and dirty:
1) The latest version of the software becomes the master. (This probably doesn't apply to Croquet, but an alternate might be 'capabilities of the machine it's running on' -- how much RAM, how fast the network connection is, mean and max distribution latency to other routers, etc -- the remaining one with the most desirable characteristics becomes the master.) 2) Of the ones that have the most desirable characteristics, they participate in a lottery -- they generate a random number, and the highest one becomes the master. In the event of multiple 'highest', only those participate in another round of the lottery. Continue until there's only one, or for 3 rounds total. 3) If you get this far, apply some function (maybe an SHA) to the router's ID, and the highest integral value of those results becomes the master. Determining if the master is down could be done via a 'heartbeat' of the router's IDs being sent around, with a maximum timeout before a new election is forced. The NETBIOS protocol (yay, something forged over 20 years ago by IBM and Microsoft) forces a new election every 11 minutes, and whenever a new master-candidate browser joins the network. It might be worthwhile to, in those heartbeat messages, collect statistics such as those listed in step 1, and then every 100 or so heartbeats send those statistics around. If a better set of statistics is seen by anyone, it could/should initiate an election. -Kyle H On 5/2/06, Andreas Raab <[hidden email]> wrote: > My question is: Does somebody have an implementation (or a decription > of) a *simple* voting protocol that would serve these purposes? I'd > really like the idea of truthfully claiming that Croquet doesn't have > any single point of failure (but I don't have infinite time to go and > implement Paxos ;-) |
|
|
In reply to this post by Andreas.Raab
Hi Kyle -
Good thoughts. The main issue that I still see is to decide whether a machine is really down or not. If we can reliably decide whether a router is down or not we could just use a priority list that each router uses to decide who is the new master. But unless you can decide whether the master is down or not you end up in this ugly situation that if #2 on the list ever thinks #1 is down it has no way to decide whether it should switch to #3 ('cause the link to #1 is down) or whether it should assume command instead. That's where I think we need the "group decision" for; e.g., #2 should really propose a vote on who is the master and if it gets the majority, it will be the new master, if not, it will merely switch its upstream link to any of the other backup routers. Cheers, - Andreas Kyle Hamilton wrote: > Just some thoughts for a quick and dirty: > > 1) The latest version of the software becomes the master. (This > probably doesn't apply to Croquet, but an alternate might be > 'capabilities of the machine it's running on' -- how much RAM, how > fast the network connection is, mean and max distribution latency to > other routers, etc -- the remaining one with the most desirable > characteristics becomes the master.) > > 2) Of the ones that have the most desirable characteristics, they > participate in a lottery -- they generate a random number, and the > highest one becomes the master. In the event of multiple 'highest', > only those participate in another round of the lottery. Continue > until there's only one, or for 3 rounds total. > > 3) If you get this far, apply some function (maybe an SHA) to the > router's ID, and the highest integral value of those results becomes > the master. > > Determining if the master is down could be done via a 'heartbeat' of > the router's IDs being sent around, with a maximum timeout before a > new election is forced. > > The NETBIOS protocol (yay, something forged over 20 years ago by IBM > and Microsoft) forces a new election every 11 minutes, and whenever a > new master-candidate browser joins the network. It might be > worthwhile to, in those heartbeat messages, collect statistics such as > those listed in step 1, and then every 100 or so heartbeats send those > statistics around. If a better set of statistics is seen by anyone, > it could/should initiate an election. > > -Kyle H > > On 5/2/06, Andreas Raab <[hidden email]> wrote: >> My question is: Does somebody have an implementation (or a decription >> of) a *simple* voting protocol that would serve these purposes? I'd >> really like the idea of truthfully claiming that Croquet doesn't have >> any single point of failure (but I don't have infinite time to go and >> implement Paxos ;-) > > |
|
|
In reply to this post by Andreas.Raab
If you are looking to save on network traffic you could do a little hop skip. Node A sends a ping to Router that should be alive at some time T. The router sends a message to each node (you could attach it to a router sync message) each node that receives it sets their next ping time to (Delay + random time interval). As an example, as a node when I receive a message ping response from the router I set my next ping time to say 30 seconds delay (no pings for 30 seconds) and a random interval between 1 and 30 seconds. Then I will either receive a ping response after 30 seconds or I will be the first to initiate a ping in which case we cut down on the number of ping requests and distribute the ping responsibilities. (Although in practice faster machines will be preferred for initiating pings since a delay in resetting the ping time will create real time offsets.) The benefit here is that when the ping fails from anyone one node all of them will know about it within the random interval. You could also stop the flood of pings to the router after a failure by sending out an election message to your priority list. Ron Teitelbaum President / Principal Software Engineer US Medical Record Specialists [hidden email] > -----Original Message----- > From: Andreas Raab > Sent: Tuesday, May 02, 2006 11:09 PM > > Hi Kyle - > > Good thoughts. The main issue that I still see is to decide whether a > machine is really down or not. [snip] > > Cheers, > - Andreas > > > Kyle Hamilton wrote: > > Just some thoughts for a quick and dirty: > > > > 1) The latest version of the software becomes the master. [snip] > > > > 2) Of the ones that have the most desirable characteristics, they > > participate in a lottery [snip] > > > > 3) If you get this far, apply some function (maybe an SHA) to the > > router's ID, and the highest integral value of those results becomes > > the master. > > > > Determining if the master is down could be done via a 'heartbeat' of > > the router's IDs being sent around, with a maximum timeout before a > > new election is forced. > > > > [snip] > > > > -Kyle H > > > > On 5/2/06, Andreas Raab <[hidden email]> wrote: > >> My question is: Does somebody have an implementation (or a decription > >> of) a *simple* voting protocol that would serve these purposes? I'd > >> really like the idea of truthfully claiming that Croquet doesn't have > >> any single point of failure (but I don't have infinite time to go and > >> implement Paxos ;-) > > > > |
|
|
In reply to this post by Andreas.Raab
One of the requirements for a voting protocol is that the node that
believes it has been chosen to be the master by the voting announces it (acceptance speech). If another machine believes it is, it sends out an acceptance speech, and then everyone uses the lowest-hashed ID of the two until a new full election can take place. There are several types of "down" that need to be examined: 1) master machine dies and is truly down 2) sole network link from master machine to rest of network dies, but master machine stays up 3) OSPF/BGP multihomed routing in effect, one of the links goes down but the other(s) stay(s) up; a slave is using the downed link (thus loses connectivity with the current master while BGP deals with the routing update) while at least one other slave is using the link that's up. Are there any other cases that I'm missing? The third seems to be the most problematic, but there are issues with the second as well. This is a situation where an IRC topology is not useful (i.e., only a single path from any one node to any other node). I would think that routers maintaining connections to at least two peers (in the event of 3 or more on the network) would be very helpful; however, this requires serialized-but-possibly-unsequenced messages. (Perhaps a serial number of the last message received from any identity could be kept, and if for some reason an older message comes in from that identity it could be ignored?) Just some thoughts. -Kyle H On 5/2/06, Andreas Raab <[hidden email]> wrote: > Hi Kyle - > > Good thoughts. The main issue that I still see is to decide whether a > machine is really down or not. If we can reliably decide whether a > router is down or not we could just use a priority list that each router > uses to decide who is the new master. But unless you can decide whether > the master is down or not you end up in this ugly situation that if #2 > on the list ever thinks #1 is down it has no way to decide whether it > should switch to #3 ('cause the link to #1 is down) or whether it should > assume command instead. That's where I think we need the "group > decision" for; e.g., #2 should really propose a vote on who is the > master and if it gets the majority, it will be the new master, if not, > it will merely switch its upstream link to any of the other backup routers. > > Cheers, > - Andreas > > > Kyle Hamilton wrote: > > Just some thoughts for a quick and dirty: > > > > 1) The latest version of the software becomes the master. (This > > probably doesn't apply to Croquet, but an alternate might be > > 'capabilities of the machine it's running on' -- how much RAM, how > > fast the network connection is, mean and max distribution latency to > > other routers, etc -- the remaining one with the most desirable > > characteristics becomes the master.) > > > > 2) Of the ones that have the most desirable characteristics, they > > participate in a lottery -- they generate a random number, and the > > highest one becomes the master. In the event of multiple 'highest', > > only those participate in another round of the lottery. Continue > > until there's only one, or for 3 rounds total. > > > > 3) If you get this far, apply some function (maybe an SHA) to the > > router's ID, and the highest integral value of those results becomes > > the master. > > > > Determining if the master is down could be done via a 'heartbeat' of > > the router's IDs being sent around, with a maximum timeout before a > > new election is forced. > > > > The NETBIOS protocol (yay, something forged over 20 years ago by IBM > > and Microsoft) forces a new election every 11 minutes, and whenever a > > new master-candidate browser joins the network. It might be > > worthwhile to, in those heartbeat messages, collect statistics such as > > those listed in step 1, and then every 100 or so heartbeats send those > > statistics around. If a better set of statistics is seen by anyone, > > it could/should initiate an election. > > > > -Kyle H > > > > On 5/2/06, Andreas Raab <[hidden email]> wrote: > >> My question is: Does somebody have an implementation (or a decription > >> of) a *simple* voting protocol that would serve these purposes? I'd > >> really like the idea of truthfully claiming that Croquet doesn't have > >> any single point of failure (but I don't have infinite time to go and > >> implement Paxos ;-) > > > > > > |
|
|
In reply to this post by Andreas.Raab
This is where the concept of an alternate universe comes in. If nodes
connected to a router split in some way but each group is still able to communicate (say a main internet line goes down), then the nodes that can communicate with the router are happy, but the others elect their own new router. When the connection is restored what happens to that world, are there two universes and no way to reconcile them. You can't solve this problem by saying that more then half of the nodes are required to win an election and the other worlds shut down because what if some delay experienced by the users causes multiple nodes to disconnect? Does this matter or is it ok that some of the people disappear into their own universe? Worm hole anyone? Ron Teitelbaum President / Principal Software Engineer US Medical Record Specialists > -----Original Message----- > From: Kyle Hamilton > Sent: Wednesday, May 03, 2006 10:25 AM > > One of the requirements for a voting protocol is that the node that > believes it has been chosen to be the master by the voting announces > it (acceptance speech). If another machine believes it is, it sends > out an acceptance speech, and then everyone uses the lowest-hashed ID > of the two until a new full election can take place. > [SNIP] > 3) OSPF/BGP multihomed routing in effect, one of the links goes down > but the other(s) stay(s) up; a slave is using the downed link (thus > loses connectivity with the current master while BGP deals with the > routing update) while at least one other slave is using the link > that's up. > > [SNIP] > > Just some thoughts. > > -Kyle H > > On 5/2/06, Andreas Raab <[hidden email]> wrote: > > Hi Kyle - > > > > Good thoughts. The main issue that I still see is to decide whether a > > machine is really down or not. If we can reliably decide whether a > > router is down or not we could just use a priority list that each router > > uses to decide who is the new master. But unless you can decide whether > > the master is down or not you end up in this ugly situation that if #2 > > on the list ever thinks #1 is down it has no way to decide whether it > > should switch to #3 ('cause the link to #1 is down) or whether it should > > assume command instead. That's where I think we need the "group > > decision" for; e.g., #2 should really propose a vote on who is the > > master and if it gets the majority, it will be the new master, if not, > > it will merely switch its upstream link to any of the other backup > routers. > > > > Cheers, > > - Andreas > > > > > > > > > > > On 5/2/06, Andreas Raab <[hidden email]> wrote: > > >> My question is: Does somebody have an implementation (or a decription > > >> of) a *simple* voting protocol that would serve these purposes? I'd > > >> really like the idea of truthfully claiming that Croquet doesn't have > > >> any single point of failure (but I don't have infinite time to go and > > >> implement Paxos ;-) > > > > > > > > > > > |
|
|
In reply to this post by Andreas.Raab
In the event of an MMOG system, if a Router can't be reached, or calls
to back-end processing systems fail, then the people who can't be serviced by the back end are forcibly disconnected. There cannot be an "alternate universe" when the data that backs the universe isn't available. In the event of a standard Squeak system, I'd say "once the routers can talk to each other again open portals to the alternates." Though that would probably not work well either... I just don't know. -Kyle H On 5/3/06, Ron Teitelbaum <[hidden email]> wrote: > This is where the concept of an alternate universe comes in. If nodes > connected to a router split in some way but each group is still able to > communicate (say a main internet line goes down), then the nodes that can > communicate with the router are happy, but the others elect their own new > router. When the connection is restored what happens to that world, are > there two universes and no way to reconcile them. You can't solve this > problem by saying that more then half of the nodes are required to win an > election and the other worlds shut down because what if some delay > experienced by the users causes multiple nodes to disconnect? Does this > matter or is it ok that some of the people disappear into their own > universe? Worm hole anyone? > > Ron Teitelbaum > President / Principal Software Engineer > US Medical Record Specialists > > > -----Original Message----- > > From: Kyle Hamilton > > Sent: Wednesday, May 03, 2006 10:25 AM > > > > One of the requirements for a voting protocol is that the node that > > believes it has been chosen to be the master by the voting announces > > it (acceptance speech). If another machine believes it is, it sends > > out an acceptance speech, and then everyone uses the lowest-hashed ID > > of the two until a new full election can take place. > > [SNIP] > > 3) OSPF/BGP multihomed routing in effect, one of the links goes down > > but the other(s) stay(s) up; a slave is using the downed link (thus > > loses connectivity with the current master while BGP deals with the > > routing update) while at least one other slave is using the link > > that's up. > > > > [SNIP] > > > > Just some thoughts. > > > > -Kyle H > > > > On 5/2/06, Andreas Raab <[hidden email]> wrote: > > > Hi Kyle - > > > > > > Good thoughts. The main issue that I still see is to decide whether a > > > machine is really down or not. If we can reliably decide whether a > > > router is down or not we could just use a priority list that each router > > > uses to decide who is the new master. But unless you can decide whether > > > the master is down or not you end up in this ugly situation that if #2 > > > on the list ever thinks #1 is down it has no way to decide whether it > > > should switch to #3 ('cause the link to #1 is down) or whether it should > > > assume command instead. That's where I think we need the "group > > > decision" for; e.g., #2 should really propose a vote on who is the > > > master and if it gets the majority, it will be the new master, if not, > > > it will merely switch its upstream link to any of the other backup > > routers. > > > > > > Cheers, > > > - Andreas > > > > > > > > > > > > > > > On 5/2/06, Andreas Raab <[hidden email]> wrote: > > > >> My question is: Does somebody have an implementation (or a decription > > > >> of) a *simple* voting protocol that would serve these purposes? I'd > > > >> really like the idea of truthfully claiming that Croquet doesn't have > > > >> any single point of failure (but I don't have infinite time to go and > > > >> implement Paxos ;-) > > > > > > > > > > > > > > > > > > > |
«
Return to Croquet - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |