Tag Archives: consensus

[2024 dev2next] distributed consensus algorithms

Posted on by
Reply

Speakers: Mykyta Protsenko, Alex Borysov

For more see the table of contents

Scenario: need 5 people to meet: two in Ukraine, one east coast US and two West coast US. Need to meet weekly

Consensus properties

  • Fault tolerance – not reliant on one person to see result
  • Safety – only one value chosen
  • Liveness – get to consensus in finite about of time, can take multiple iterations

2 phase commit

  • One person asks and someone says can attend if everyone can. everyone says yes.
  • Commit and now official.
  • Simple but downsides. When group big, a lot of acks. If one no, transaction aborted and start over. Also, waiting for slowest node to reply.
  • If coordinator loses internet, everything blocked
  • Fails on fault tolerance and liveness

Paxos Protocol

  • Everyone has a ballot with unique ballot number
  • Propose a time with next ballot
  • Submit last vote null message to promise that will vote. Can be for or against.
  • Once majority promise to vote, sends actual begin ballot message
  • Then people actually vote
  • Consensus is majority. Sends message that reached consensus
  • Each participant must track last ballot tried, promise to vote and actual vote.
  • Choosing proposer and ballot don’t have to same person
  • Can only vote if confirmed a promise to vote in cluster
  • Learners can observe to be notified when consensus is reached
  • Fault tolerant because majority is enough
  • Safety because majority based
  • Doesn’t ensure liveness.
  • Can elect member as leader who can be the only one to propose
  • 2 round trips for consensus

Cassandra

  • Uses Paxos
  • Need to know order of data – linearizable consistency
  • Don’t mix transaction types. ex: use if exists/if not exists consistently.
  • Lightweight transactions are faster than two phase commit
  • Incurs performance penalty by design because more Paxos interactions.

Raft

  • Two message types
  • Leader based. All other nodes are followers
  • No reelections. Leader stays as leader until disappears
  • Like Paxos, use increasing numbers
  • Every node starts as a follower. on term 1 Followers notice no leader. One or more volunteers and increases term number. Others vote on leader. Only one vote for that term so can’t vote twice.
  • Once leader elected, followers send requests to leader who propagates
  • Log replication – can be applied (not final) or committed
  • Use commit index as tracker of what data was committed. Allows to see state
  • All followers have a heartbeat tracker. If leader disappears, the one who hasn’t heard from the leader in the longest time becomes a candidate to be new leader. If away and request leader, gets rejected because have one
  • If outside cluster and want to know status, asks leader
  • Fault tolerance – yes leader or follower can droo
  • Safety – guarantees one choice. Also only commit data from term
  • Liveness – in practice yes, but in theory no

Mongo DB

  • Uses Raft
  • If slow member is leader, there is a write bottleneck.
  • Can horizontally scale by replica set. Can hash keys so majority of requests aren’t all on one replica

Accord

  • New algorithm; not widely available
  • Leader based protocols create bottleneck
  • Fast and slow paths
  • If can get majority with fast path, can tell slower nodes later; even async
  • A node must be part of all fast paths majority so can share with others when back online
  • Fast path should be 3/4 of nodes to guarantee someone has latest state
  • Slow path remains as simple majority
  • ACID
  • Reorder buffer to reset transactions to be in order based on time differenitials

My take

I knew what two phase commit was. Everything else was new to me. Excellent start to the morning! The five people voting made it easier to follow. The reasons for them disappearing (Ukrainian soldier, Californian losing power) also helped pay attention. (Left a few minutes early to answer a phone call)

finger voting – teamwork and voting

Posted on by
Reply

In the past month, I’ve used “finger voting” in three contexts.

What is finger voting?

Voting with your fingers of course. Seriously thought, finger voting is a bit like rock, paper scissors. First the choices are presented. Then everyone sticks out their fist when ready to vote. The person who called the finger vote says 1, 2, 3, reveal and everyone votes at the same time. This could be thumbs up/thumbs down/thumbs side to indicate agreement/disagreement/neutrality. Or it can be a series of options. One finger means we should have pizza, two fingers means we should have sandwiches. Finger voting can be used for binding votes or polls.

Why is finger voting beneficial?

Decisions by consensus often take a long time. Sometimes the decision is such that any of the outcomes are acceptable. Sometimes at topic has been discussed at length and more discussion isn’t going to change anything. Sometimes you just want to take the pulse of the room to see if there is a consensus before spending a long time discussing. Finger voting lets you see where everyone stand.

Another benefit of finger voting is that the quieter people in the group get an equal say. It avoids the scenario where you have one vocal person in favor, one vocal person opposed and it appears the room is split down the middle. A finger vote/poll lets you see if it is split down the middle or just that one vocal person.

Context 1 – Work

We use finger voting for a variety of things. Some examples:

  • Process changes at the retrospective
  • Design decisions after discussing the options
  • To see how people feel about the sprint at the end of sprint planning

Context 2 – FRC (FIRST Robotics Challenge) Brainstorming

This year there were a number of strategies you could use for the robot. This decision is important because you get locked into it pretty quickly. There were a few conversations we got mired in. I suggested a finger vote to see what the majority of the room was thinking. While this worked, I learned that not being able to “demand” a finger vote makes it take much longer. At work, when anyone on the team suggests a finger vote, we have one. It may be a finger vote poll or a “binding” decision (well until the next retrospective). But a call for a finger vote at work isn’t distanced from said vote by a period of half an hour.

Context 3 – FLL (FIRST Lego League) judging

Today, I judged technical/robot design. The way judging works, there are four pairs (or triples) of judges who all see different teams and created an ordered list. Then the four groups get together to form a combined ordered list of X teams. To do this each group talks about their strongest team and all four groups concur on who was strongest overall. Then the next highest from that group replaces it and all four groups concur and…  Historically, the step of figuring out which of four teams should be ranked highest is a difficult step because you need at least eight people to agree. And typically that means the vocal people have a disproportionate impact on the decision.

Today, there 9 judges (three pairs and one triple) for technical/robot design. Two of us have been doing it for many years. I asked Dave (the other veteran judge) if I could moderate. He graciously agreed and I gave finger voting a shot.

Each group presented their strongest team and why. Then we used our fingers to show which of the four teams was strongest. Majority rules. And we proceeded. There were two votes that were really close and we discussed more there. There was even one where we had a three way tie. We discussed and revoted and there was no tie. (If there was another tie, I was going to propose we vote for which of the three was the weakest and see if we could get it down to two.)

Anyway, finger voting rocks. Consider it on your teams!