Simple voting protocols?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Simple voting protocols?

Andreas.Raab
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

Reply | Threaded
Open this post in threaded view
|

Re: Simple voting protocols?

Kyle Hamilton
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 ;-)

Reply | Threaded
Open this post in threaded view
|

Re: Simple voting protocols?

Andreas.Raab
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 ;-)
>
>

Reply | Threaded
Open this post in threaded view
|

RE: Simple voting protocols?

Ron Teitelbaum
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 ;-)
> >
> >



Reply | Threaded
Open this post in threaded view
|

Re: Simple voting protocols?

Kyle Hamilton
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 ;-)
> >
> >
>
>

Reply | Threaded
Open this post in threaded view
|

RE: Simple voting protocols?

Ron Teitelbaum
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 ;-)
> > >
> > >
> >
> >
>



Reply | Threaded
Open this post in threaded view
|

Re: Simple voting protocols?

Kyle Hamilton
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 ;-)
> > > >
> > > >
> > >
> > >
> >
>
>
>