Consensus & Organising Coffee - Computerphile
ฝัง
- เผยแพร่เมื่อ 14 ม.ค. 2025
- Just like humans organising to meet for coffee, computers need ways of organising themselves. Heidi Howard, of the System Research Group at University of Cambridge explains the basics.
Could We Ban Encryption?: • Could We Ban Encryptio...
How Blurs & Filters work: • How Blurs & Filters Wo...
PAXOS: • Paxos Agreement - Comp...
Geometric Face Recognition: • Geometric Face Recogni...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
This is great for a fixed number of trusted nodes, but if you want an arbitrary unknown number of nodes or if you cannot trust all nodes, you can't form consensus this way. Bitcoin introduced a method to form consistent and available consensus over arbitrary decentralised networks using Proof-of-Work. In simple language, Bitcoin allows any number of computers from around the world to talk together and come to a consensus with minimal trust, and anyone can be running these computers.
+zaco21 With Bitcoin you do have to wait before transactions have a strong enough consensus yes. In many cases this is not an issue, especially where it is reasonable to wait before shipping goods. For low-value items it can be reasonable to except unconfirmed transactions.
It is possible to monitor the network over a short space of time to look for double spends, though this cannot work against Finney attacks and may not always catch double spends quickly enough. But for low-value items this can be sufficient.
The block interval can be reduced from 10 minutes, though this has side effects (orphaning, bloat). One solution for fast blockchain confirmations is called Delegated Proof-of-Stake which is used by BitShares. This involves electing people to provide consensus updating over a short fixed amount of time.
Another solution is to use 2-of-2 addresses with a trustworthy party that specifically prevents double spending. The third party cannot steal funds. Using a timelock would allow one party to redeem funds after a particular amount of time, avoiding total reliance on the third party.
Therefore blockchain consensus can be made to work close to instantaneously with various methods and solutions that have their pros and cons.
That intro screen.. "ATM machine"
+Ludvig Nygaard because further in we talk about ATMS
Austin Pinheiro But then it's still an ATM, or AT Machine.
+Ludvig Nygaard Yeah, busted! - In the UK we don't usually call them ATMs - we call them a 'cash machine' - so I messed it up, as well as the spelling on the thumbnail! >Sean
***** I.. No.. Why.. Stop that!
+Ludvig Nygaard It's what I type my PIN number into
2 months later, where's that video about paxos?
You misspelled the thumbnail...
+Caleb Limb And it hurts so bad >.< ^^
They did not, however you don't either.
Jackson Steal
...what? First, they did. Second... "you don't either" what? O.o
+Benjamin Philipp Jackson meant it can be spelt two ways. One British and one US English. So....
They didn't spell it wrong and you don't either.
Colour v Color or Tyre v Tire
Perhaps he was succinct to a fault.
:-)
Peter Walker
Neither US nor British spelling calls for a c in that place.
Wouldn't make any "Cense", would it?
7:43
what if the overlap node failed?
+Austin Pinheiro I gather in reality it's not just one node, so the likelihood of enough failing seems fairly unlikely.
+Austin Pinheiro Consensus would not be achieved if the algorithm required 51 or higher majority and the required overlap wasn't achieved. This is why Proof of Work consensus systems incentivize peers as they understand the limitations of the network with nodes coming online and dropping off, network latency issues, and insecure or compromised nodes. This anticipates attacks and malicious actors and insures there are enough distributed and decentralized nodes that cannot be faked or manipulated (Sybil attack) without heavy costs involved
+Austin Pinheiro A failed node wouldn't be used in the transaction.
+Austin Pinheiro If the overlap node failed then another node will be used, unless no more than 2 nodes can be used. In the case that no more than 2 nodes are available, the transaction will fail because the transaction requires a majority. this is also called a quorum.
+Austin Pinheiro There isn't just ONE overlap node. Slightly re-iterating some of the things mentioned here. Since a majority is required between A,B,C,D,E. If (Transaction 1 : A,B,C) reach an agreement, and then C fails, (Transaction : D, E and (A or B)) would need to reach agreement with a different transaction for the system to become inconsistent. As you might have noticed, A & B both know the new state of the system and will refuse to acknowledge this new transaction. Notice that there isn't one overlap node but any of the remaining can be that overlap node, so both A&B can be that overlap node. To answer your question, nothing would really happen since distributed systems are designed with failure in mind(en.wikipedia.org/wiki/CAP_theorem) :)
Awesome. A video about consensus algorithms. I did an internship last Summer for a company developing a consensus based database.
Only they used RAFT protocol instead of PAXOS.
Database consistency, redundancy, distributed processing...the subject(s) could easily cover weeks of a college computer science course. As has been expressed in this video, it's a simple idea with complex real-world problems which conspire against getting it exactly right.
Two books on tcp/ip and one on Visual C++
4:56 That "prepare phase" is simply a "distributed BEGIN TRANSACTION".
is the count in phase 2 a semaphore?
+Realraven2000 Looks like it :-) exactly my thoughts.
I totally need to get more organised!
Heidi is so pretty.
Can you make a video series about algorithm design?
Maybe discuss typical algorithms which are cool, such as min-cut via contraction.
Nakamoto Consensus is one of the better solutions in a network of peers that cannot be trusted or may not be reliable with Byzantine fault tolerance consensus problems. Having a majority of servers or nodes make a decision alone only is sufficient if all nodes can be trusted which is dangerous principle to rely upon even for in house "trusted" nodes as they can be compromised. The genius of Nakamoto Consensus rules is that they rely on proof of work where there are real tangible costs in processing transactions that get exponentially more difficult to override with time. There are many working blockchains that already implement these strategies for decisions, arbitration, notary services, authentication, ect..
+sanisidrocr It works in theory but in practice it's extremely slow and resource intensive.
+Soundwave Please elaborate what you mean by slow by suggesting what task you consider slow within these systems. BFT protocols are inefficient compared to simple databases, but much more efficient compared to replicating the security done through regulation and human oversight. Those that complain about inefficiencies aren't usually considering all the externalities with traditional consensus mechanisms.
***** Please clarify how it fails to work. I use it daily for a wide range of activities.
***** Too slow? Bitcoins speed is tied for sending a transaction with all debit /cc's (less than a second)and for confirmations bitcoin averages about 10 minutes to 30 minutes while credit card transactions confirm within 60-120 days. Is there something specific you are referring to or are you just unfamiliar with merchant processing and/or bitcoin?
P.S.... you don't need to wait for a bitcoin "confirmation" to approve of a transaction as merchant processors can query the mempool and use other indicators before the next block is confirmed. Have you ever used bitcoin before?
Additionally, do you understand that all major banks are now heavily invested in bitcoin because they understand the value and usefulness of not only blockchain tech but bitcoin directly?
***** Banks and investors are principally investing in Bitcoin companies and employees and not simply speculating on the currency so you are misleading others.
The lightning network caching layer being developed for bitcoin will insure that confirmations are both instant, secure, and without the need to use centralized merchant processors. for the time being using a merchant processor is fine for instant confirmations.
If a cc chargeback can occur within 60-120 days the money isn't exactly confirmed now is it?
I accept btc, pay employees in btc, use it for arbitration and escrow, and buy with it daily. It is more convenient and more secure than credit cards in my experience.
I recommend people use it for utility and not speculate however as it is still young and volatile. It may be tempting to speculate because of this bullish rise in value this last month, but to others you should research into the matter a bit and recognize that stable forms of Fiat still have some utility as they are currently less volatile. One doesn't have to choose between either and can leverage them both right now to save money and reduce costs.
Classic resource contention issues in parallelism. Explains why multi core systems have yet to reach full potential and highlights some techniques contemplated in load balancing systems.
It all looks easy, until to start nasty use case testing. Then, the more you bolt on to get around it the nastier it gets, like needing spanning tree.
I can't help but admire people who solve this stuff.
Thanks for the lecture.
Gahh!! No mention of PAXOS or RAFT. Gotta wait for the next video. :)
automated teller machine machine? So, something used to help the service personnel extract or load money?
Why are the transactions happening with many servers? Why is this model more efficient than each server serving a different fraction of the accounts?
+retepaskab One big reason is to have replicas of the data. This allows some of the servers to fail, without having downtime in the whole system. If a single server served a given account and failed, the system would be down for the user of that account.
+retepaskab replicate data for redundancy, for error checking , if nodes come on and offline, for decentralized trust models like those found with bitcoin where you do not trust the nodes individually but collectively you can.
1:30 DRACS? IS THAT YOU?
Very nice. Thank you!
What happens in this scenario?
Bob: 100
John: 100
2 servers with this data
Bob -> Server 1 -> [-50, Bob]
Server 1 -> Server 2
( Server 2 -> -100
Server 2 -> Server 1 -> [-100, Bob]
>>) -> [-50, Bob]
Bob would end up taking out 150, assuming he could reach both machines in time. Data wouldn't be replicated, and in a larger setup (with, let's say, 5 machines), it could break.
Eventually the data will all be synced but the whole point of this setup is that no transaction will take place unless at least one of the machines involved in previous transactions was also involved in this one. I suppose if you could somehow setup multiple bots at different machines and have them all take money out at the same time it could work but the moment the data was resynchronized the error would become obvious. Running to another machine is not practical as even with the slowest internet the transaction is going to occur in a fraction of a second, he'd also have to run to the other machine before the one he was at had actually dispensed money since that step doesn't happen until after the transaction is finalized.
Proof of Work consensus uses game theory to create a Nash equilibrium where you are rewarded for cooperating and increasing security instead of attacking the network of consensus forming nodes. Additionally, any perceived "trusted" nodes are incentivized to be carefully checked and tested as there are real world costs with mistakes in addition to the intrinsic costs of making a sub-optimal or incorrect decision when attempting consensus. These principles are akin to achieving better accuracy within prediction markets when real assets and stake are on the line.
who texts by putting the phone to their ear!!
+TheSoradam Maybe the same people I see walking around the street talking into their phone while holding it horizontally out from their mouth?
+trejkaz lol
+trejkaz I also see people talking with their phone horizontal next to their mouth on speakerphone whilst walking. Why do they even do that?
+Callum Aitchison Well, the sensible reason is because there's other people with them and they want them to also hear the conversation / join in with it.
For example, on "the Apprentice" TV show, the contestants often do this - hold their phones in front of them on speakerphone - but that's because they're being filmed for a TV show and doing so allows the camera to also pick up what's being said on both sides of the conversation.
I don't doubt, though, that there are idiots who've failed to work out that this is only due to it being broadcast on TV, not because it's some kind of trendy new way of holding your phone, and just blindly imitate it, thinking it makes them look "dynamic" and "entrepreneurial" or something.
KlaxonCow That's a good point. Thing is, they're often alone.
You either misspelled the thumbnail or the title :)
0:26 "with an ATM machine"
I guess I'll be using my PIN number with that ATM machine, eh?
I get lost at 1:25 ....
what if the failing server is the one that knows she withdrawn the money, the one in the intersection?
The ATM won't withdraw money if it can't contact its friend. So "this is the only ATM that know about withdrawal" won't happen..
I would still say that the blockchain is the most superior method of accomplishing computer consensus.
+zaco21 I'm talking about something else here, I'm implying that the blockchain does exceedingly well in a trustless environment. The blockchain offers a use case for a ledger that sacrifices efficiency to avoid censorship. Giant corporations are hacked, important evidence is faked, the blockchain has the ability to prevent this. The blockchain is for large scale public services that everybody may check for legitimacy, not something that your personal server room would use locally.
***** Please elaborate how. In fact, if I, for some reason, cannot trust any api service with their data, I download the blockchain for myself and verify every hash of each block. Since each block is tied to the last with this hash, changing ONE BIT of ANY part of the blockchain invalidates all of the blocks because the hash will be different.
So let's say the blockchain has 5 blocks, I decide to "fake" a transaction in block 3. I use block 2's hash, my fake transaction, and the other transactions to make a hash of block 3. Since block 3's hash has been changed, block 4 is invalidated because the "block 3" hash does not match up. Block 5 is invalidated because block 4 is invalidated.
So what ends up happening is my fake blockchain is rejected and bitcoin goes on strong. *There has been not one successful attempt at hacking bitcoin.*
***** >Doesn't mean it can't be altered
If the data is altered, it becomes invalid. When you download the blockchain, you check every blocks's hash and transaction data to be valid. Yes, all 20+GB of it. Re-read my earlier comment about how this checking mechanism works.
And I said *successful* attempt. The bug has been patched, a fork was created and everyone jumped onto that fork. Those illegitimate coins no longer on the main chain.
What if Charlie invites Diane, who Alice dislikes...
The books are bordering me.
+Bill Kang You're surrounded by books?
Since it's your second language, I am sorry :-) I see what you mean. But the book which is 'bothering' me more, is the ASP one on the left :-D
There was something weird about this episode.
She's cute! Interesting video as ever
+tbird81 why exactly am I a creep? Is it illegal to say somebody's cute or something? Go pick on someone else they might actually care.
+Roland Gharfine I agree, she looks cute indeed :) Nice to see more women in working at computer sciences.
Wicked Mouse Exactly
I didn't know Alice was a guy's name :P
+Sina Madani Never heard of Alice Cooper?
+KlaxonCow And Marilyn Manson.
She's a cutie
She's quite pretty
This is just how the bitcoin chain works.
atm machine...
I usually enjoy these videos, but this one seems jumbled and confusing. I didn't initially understand the problem at hand and what you were trying to solve. Bad introduction, bad segues and weird analogies.
+Omicron Vega This was the first video where I wasn't familiar with the problem already and while in previous videos I was often left with a feeling of "this could have been explained better" or "this must have been confusing for someone not already familiar with the topic," _now_ I can say with confidence that it _was_ confusing to someone unfamiliar with the topic.
+zaco21 I don't think anybody here was asking to just dumb it down. It's almost the contrary actually. IMHO, this channel has the general tendency to "explain" things in such a vague and nondescript way that you basically have no chance of understanding neither the problem nor the possible solutions without already having been familiar with the topic.
If you can't see the didactic problems this video has, I actually don't want to take the time and work necessary to point it all out. Because it's a lot. If Sean were to ask himself, that'd be different. But you don't have the power to influence future videos anyway and you don't need to try and explain to us here what the video failed to explain. If I want to read up on consensus algorithms, I know how to do that with less work involved on your _and_ my part.
2:30 That works fine in a *tiny*l network, but is *completely impractical* in anything larger than trivial. (Can you imagine an ATM asking 30,000 other ATMs if there's enough money in Alice's account? It's just silly.)
How can you talk about consensus algorithms and not mention Nakamoto consensus used in Bitcoin.
what r u waiting to do a bitcoin/blockchain video? dude!
This is so creepy lol