Granular Synchrony: A New Network Timing Model for Distributed Computing with Ling Ren

Transcript

Welcome everyone. Summer 2025, a new year, a new summer seminar series. Tons of great speakers lined up. Very happy to introduce our first speaker uh of the summer. Ling Ren, professor at University of Illinois, a well-known leading researcher in consensus, both traditional and blockchain consensus. and today he'll talk us about talk to us about a new fine grained model um of sort of network communication granular synchrony. So Ling >> hey thanks for for the introduction Tim uh and for the invitation to spend the summer here. I visited A6Z crypto research team two or three years ago.

Today is uh I'm happy to tell you a bit about granular synchrony and this is a new timing model for uh distributed computing for blockchains especially for large scale blockchains. I'd like to start with a motivation, right? Why I believe we should study new timing models since there are a few fairly established ones in the literature for decades and then I'll tell you about what a model is and how we can solve consensus in the new model and close with some discussions and future directions. So um timing model this is one of the most important aspect of formal modeling in distributed computing. It basically it describes uh when we have a network of nodes when one

node sends a message to another node how long does it take for that message to arrive. Okay. So um there are a few well- established classic timing models like uh the simplest one is called synchrony right that basically says whenever someone sends a message to another person um there is always a upper bound delta for that message delay and every message respects that delay and everybody knows this upper bound delta okay then there's asynchrony um that just says there's no such bound, right? Any message can take arbitrary amount of time, right? But eventually it will arrive. And uh then

the third one is um kind of a relaxation of um asynchrony, right? It sits in between these two, right? It says the network model alternates between asynchrony and synchrony, right? So sometimes the network is asynchronous but there will be sufficiently many periods of uh synchrony and these periods are sufficiently long. Okay. So these three models are extremely well uh established. Uh we have been doing research in consensus in and many other problems under these models for decades. So why do we need new models? And uh okay before going there let me also clarify that the

timing model um describes not just the message delays if we are uh more serious or um rigorous about it they should also describe clock sk whether my clock increases at the same speed as your clock right or the difference in that clock speed difference whether it's bounded or unbounded but for this talk I will ignore clocks goose right let's just pretend that all of them All of us have perfectly synchronized the clocks. Okay. So why do we need new model? And the reason is that I believe synchrony is too strong. It's the too optimistic as a model. But patchesynchrony and

asynchrony are too weak, too pessimistic. And uh it's um not hard to see why synchrony is too strong. And I think most people in the field would agree with the statements, right? Because if we design a protocol relying on synchrony right then uh we are really making this assumption that every single message respects the delay bound right if just a single message gets delayed right a bit more than delta then we lose all the provable guarantees right in some particles the particle is just straight up broken right in other particles maybe there's not a direct break but um all the proofs we did right no longer apply

Right? And it's not hard in reality for an adversary to delay um message, right? Or delay a few messages between two nodes, right? There are denial service attacks or adversary may control a small part of the network etc. Okay. But on the other hand, partialsynchrony and asynchrony would be too pessimistic because these models they say the adversary controls the entire network. Every single message sent between any pair of nodes can be delayed arbitrarily, right? By the adversary, right, of the adversary's choosing, right? It is unlikely to imagine there's an adversary that really is that

powerful, right? That is able to manipulate all parts of the network at the same time. uh in particular right by now we know that the Bitcoin system and most of the deployed blockchains they do not work in patch synchrony or asynchrony right they would fail miserably in this uh super weak models right but they have been running without interruption for more than a decade now almost two decades now right and they are high value targets right if indeed there's an adversary who can control the entire network we probably would would have seen the attack by now.

Okay. And uh this is uh more fundamental than um this is actually a fundamental limitation right that the bitcoin and most deployed blockchains they do not tolerate asynchrony or pachiosynchrony um because they just fundamentally cannot right because most of these systems they want to target a nice property called dynamic availability right that means not everybody is participating in the protocol all the time at any point maybe there only 20% of the participants that are participating in the protocol and out of those we have honest majority right and the majority of the nodes are actually not paying attention. If you want your particle to be safe and live in such a

dynamic available model, we have to forgo partsynchrony and asynchrony, right? It's pretty easy to show an impossibility, right? Um because we can just partition the network into multiple small parts, right? And um we rely on we as the adversary rely on asynchrony or partial synchrony to delay all the messages between these uh partitions, right? Then each partition because it is unaware how many what percentage of the network is actually participating for all their know maybe their partition is the only one who's participating right and so all of these part all of these partitions will take steps will make decisions independently and that would lead to

violation in consensus >> I wouldn't really say most deployed blockchains on this slide >> yeah okay uh yeah thanks Thanks for that um for that comment. I think nowadays the more blockchains move towards the more classic static availability setting. All right. And um but if we think about the situation there's actually a large gap between the three established models. On one hand we have synchrony right it's a strong assumption. On the other hand we have partial synchrony and asynchrony that are super weak and pessimistic models. Right? But there is a large gap in between right and uh for the consensus problem at least the most

of the important variants of it right um there also a separation between fault tolerance in synchrony we can we usually require honest majority and in partn asynchrony um the best we can hope for is to tolerate one-third of adversary so now um given my claim or I hopefully I convince that that um synchrony is too strong and partial synchrony and asynchrony are too weak right then it's natural to ask whether we can find something in between right and that is the topic of this talk right then we're going to introduce a new model called granular synchrony that basically covers that entire spectrum uh

in between the basic idea of granular synchrony is that we will not assume every link respects the bound or or no link respects the bound. Right? We will model the graph the network as a graph consisting of a mixture of synchronous links, asynchronous links and partially synchronous links, right? And then depending on how whether uh there are more how many asynchronous links versus how many synchronous links are, right? The model is parameterized and it can degenerate to one of the two extreme or it can sit in between, right?

And in return we will get a fault tolerance that also covers the full spectrum. So this allows us to have a trade-off between network connectivity and um tolerance against adversary. Okay. So I will uh quickly clarify that this is a simplification right in terms when we compare models and their strength there's more than one dimension right. So we cannot just put these models in a in a one-dimensional on a total order right and some of sometimes some of the models are incomparable.

Okay. So um then next I'll briefly mention some of the related or not so related models or works in the literature like so there's there's some work on mobile sluggish faults or sleepy model but these are orthogonal because these are talking about type of node failures right they're not talking about the links all of these works they still have to assume one of the three classic uh timing models and they pick synchron And there are also works of models that consider links that are lossy, right?

That the message may or may not arrive, may get lost, right? But this is also orthogonal, right? Because for the messages that do arrive, we still need a model, right? Whether they arrive on time or can take a while. And the most relevant, right? to and to my knowledge the only relevant work in the space is that their line of works that study the minimum assumption required to circumvent FL and their methodology is to assume a mixture of asynchronous links and partly synchronous links and that is indeed the same methodology um that we take in this work um but as you can see they do not consider any synchronous links right so

their model is uh on my spectrum is also on that um far right. >> Who and when was that last paper? >> So these are actually pretty old. Um I think around 2012 13ish and I don't remember I don't remember the authors of uh all of those papers. Okay. And I will um mention some of these works later in the talk. Okay. So next let me tell you about the granular synchrony model right as I mentioned uh we will model the network as a graph right and each link connects two parties in the graph right and each link may be

synchronous partially synchronous or asynchronous right uh right now our model assumes a undirected graph right meaning that if I have a synchronous connection to you then you have to have a synchronous connection to me right so this is a one limitation that I would like to get rid of but so far we haven't been able to and then as the model is uh is sliding in between some of these extreme classic models our fault tolerance as mentioned also slides in between this right in the case of uh Byzantine faults right it's probably the u case that's more relevant to blockchains right and it's somewhere in between 1/3 and 1/2 the main task

that we have here is to identify the sufficient and necessary graph condition right under which consensus is solvable right for a given pair of N andF and in this talk for simplicity I will focus on the deterministic case right so the protocols are deterministic meaning that the parties or nodes will not toss coins >> does a protocol know which links are which >> no the protocol does not have to know which link is which Right. And when but when we prove the necess necessity of the condition um most of the time it applies to even particles that uh are tailored towards a

particular graph. We will study the agreement problem. Right? This is uh perhaps one of the most basic consensus of variance. Okay. Uh in this problem we have n parties and up to f of them can be faulty and every party has an input and in the so there are mainly two requirements that such a um a solution to the agreement problem needs to satisfy the first one is called agreement right that um that correct the parties right non-fy parties output the same value and we need a second requirement um that says if everybody has the same input X then the output of everybody should be that

input right so this is uh the validity requirement is needed to rule out trivial solutions right otherwise um we can just everybody there's a trivial protocol right everybody ignore the input let's just agree on zero okay so let me start with the simplest case um of granular synchrony we'll consider for now crash faults right no malicious nozzing faults yet and we have no asynchronous links. So that means we have a mixture of synchronous links and partially synchronous links. Right? Just to remind everybody again, a synchronous link that says uh is one that says every message that goes on the link always arrives within some bounded time. Right?

And partially synchronous link um says that for for a while the messages on that link may take a very long time but eventually we will get into a synchronous periods right and in the during the synchronous periods um the messages arrive fast okay and uh I should say that we're assuming that the synchronous periods of different links are synchronized, right? Meaning that there is a window of synchrony in which all partially synchronous links behave synchronously.

In a crash fault case, we have these two classic results, right? That says if we're in synchrony, then agreement is always solvable, right? No matter how many nodes can crash. But if we're in a partly synchronous setting, then the best we can hope for is to tolerate minority crashes. So why is that? It's actually a fairly straightforward proof. If that's not the case, right? If f is exactly half of n or n is twice of f, then we can divide these nodes into two groups and then we can rely on partial synchrony to cut off the communication across the groups. Right? So then uh further if half of the if the left group everybody receives input zero there and

everyone in the right group has input one right then this will lead to agreement violation because from the left group's perspective it could be that um all of these folks crashed right and everybody has input zero right so they would have to agree on zero right but for this group it's the exact same same situation, right? They do not hear from that other group due to partial synchrony, but from their perspective, it could have been that all of those crashed, right? And um so they will have to decide on one and that's a violation of agreement.

So now we'll move to granular synchrony. In granular in granular synchrony we have a mixture of synchronous and partially synchronous edges and our fall tolerance will also be in between those two extreme cases and um we the the condition we identified right that's sufficient and necessary to solve agreement in the crash uh no asynchronous link setting right it's this one right it's a condition related to the graphs that says No matter which up to f nodes crash, there cannot be two disjointed groups of n minus f nodes that have no

synchronous paths across them. Right? Pictorially, right? That says if the adversary, right, who is um capable of crashing nodes, right? If there is a way for the adversary to pick a group to crash, right? And then after that there are two big isolated groups left who cannot talk synchronously with each other then consensus is impossible. Otherwise if the adversary cannot find a way to break the network in this fashion then we can solve agreement. So for now let me um okay let me give you an example right uh since we're in the region where n is um

f is in between one and half right so let's suppose n is 1.6 six F right. So this is a dishonest majority and uh if the adversary can corrupt certain nodes can like crash certain nodes and then create two groups that are both pretty large right how large than n minus f then the adversary can successfully cause disagreement among the parties right why um because each of these party is greater than n minus f right it's the same argument as before right from their perspective it could have been that everybody else crashed and they are the only one left. So they need to make progress and make a decision. Right? But then these two groups will make

decisions independently and that leads to a violation of agreement. So the necessity proof is basically the same as before, right? Okay. So um then I'll directly go to like Byzantine false because I guess we or most people are not too interested in crash fault tolerant protocols, right? But uh I'll give you a Byzantine for tolerant protocol in a granular synchrony model later. So now moving on to the Byzantine faults. Uh in Byzantine faults we also have two classic results right that says under synchrony a Byzantine agreement can be solved if and only if there's a honest majority right or the Byzantine faults is strictly less than half.

Right? In partial synchrony agreement is solvable if and only if the number of Byzantine faults is less than one/ird of the total number of parties. Okay. So then we will um consider granular synchrony and we will show that agreement is solvable anywhere within that range. Oops that's a typo that's >> that should be n over three and n over two right. That's uh yeah n over three and n /2 and again under a graph condition right the condition is uh this one is also a little similar to um the the one for crash that consensus is solvable if and only if regardless of which f parties

are byzantine among the remaining parties there cannot be two disjointed groups each of size n minus 2f F right and um they have no synchronous paths across them right so again let me give you an example right if the adversary can corrupt certain nodes certain f nodes right and then to disconnect to such large groups right for example let's say n is 2.6 6 F right and then after corrupting F two groups of 0.9 F and 7F right that are disconnected or cannot talk to each other synchronously right both of these are larger than N minus 2F which is 6 right so then

there's no chance of solving agreement okay so why is that right this time it's because on the middle group are malicious right or Byzantine Right? So they can play double agents, right? So they will behave towards the left group, right? As if um they were the only one participating, right? And right they will tell the left group, right? The right group never responded, right? Most likely they have crashed or they are malicious. And they will say the opposite to the right group, right? That they uh they have never heard about they have never heard from the left group. Okay. Right. And

again uh because there are no synchronous path across the left group and the right group then we can rely on pio synchrony to partition right those two honest groups right so uh if you're familiar with the pio synchrony classic proof right this is the same thing right why do we need f less than n over3 in the pio synchrony model right it's because if that's not the case And n suppose n is strictly equal to 3f then we can divide the groups into three right each of size f and then the adversary corrupts the middle one right and uh the left one and the right one those two groups will make

progress independently with the help of the f malicious parties in in the middle. Okay. So once again this condition is clearly necessary because of the split brain attack and in a minute I'll uh tell you how we can solve consensus in this model to right to to to prove this condition is sufficient. Okay but before that uh let me also draw your attention to the unifying power of the granular synchrony model. we can make the granular synchrony model degenerate to right both sides right but there is a footnote I put there um so let's look at the partially synchronous

side right suppose we do have n equals 3f + one right what happens then there are two f plus one honest in total right and this condition says consensus is solvable if we cannot find two disjoint groups of n minus 2f on its nodes and that condition always holds right because there just aren't that many on it nodes. Okay. Right. So once we go to n equals 3f plus one con agreement is always solvable even if all of the edges are partially synchronous. On the other hand if our n is 2f plus one right so this is uh just barely on its majority.

So then this condition says uh we cannot find two groups of one honest node right. So every pair of onest nodes need to be connected by a synchronous path. Okay but uh um maybe you have realized right that doesn't quite degenerate to the synchrony model. Okay. Right. Because it just says that every two honest nodes need to be connected by a synchronous path, not a direct link between them.

Right? So this actually leads me to realize this is a misconception that even I and I believe my co-authors had right. We thought granular synchrony degenerates to partial synchrony on one end and to standard synchrony to the other end, right? But that's actually not the case, right? It's only through discussion with you all that I realized right that's not the case right we actually have a somewhat new result here right that uh even right suppose we want to target n= 2f+1 right the strict honest majority does that require um fully synchronous work right for consensus to be solvable most of the existing particles do

require that but turns out That's not necessary right? Let's I consider a graph like this, right? We where we have f nodes, right? And then the remaining f plus one nodes form a line, right? But all of them, right? There's a like dense pair wise connection across the two groups, right? this on this graph um agreement is solvable right even though we do not have full synchrony here right in particular we have no synchronous edges um in the bottom graph other than the line

okay I think this is a somewhat interesting observation that if you are super familiar with literature you can probably piece together some hints from uh some prior works right to realize um this fact right but uh at least I personally didn't know this um before doing this work there's also a partially synchronous analog of this observation or not >> no in on the other end it does properly degenerate to partial synchrony >> why are they why are they different >> yeah perhaps you can argue that standard synchrony maybe should just be defined this way, right? Um that the extra right

that that it doesn't require pair-wise synchronous edges, right? This many synchronous edges is sufficient that having even more synchronous edges beyond this minimum condition may make it more convenient to design protocols, may make your protocols more efficient. Um but in terms of feasibility right it's uh not the fundamental condition. >> So to what extent I mean can I just if you tell me that does you like synchronous spanning tree can I just think of that as like synchronous all to all except with delta replaced by n times delta something like that just by flooding basically.

>> Yes I think that's a simple transformation. >> Okay. >> Yes. >> So that would say this distinction. So that's a way of formalizing what you just said that the distinction is really just about kind of efficiency considerations, not about possibility considerations. Yes. >> Okay. >> Yeah. Yeah. That Yeah, that's a good point. Yeah. That you can you can um add a wrapper on top of this network to make it a fully synchronous network with a worse delay bound. Good. >> And then different questions. So like these conditions like if you gave me a graph it would be hard to check if these conditions were true. I will talk about that in uh

>> it's like a balance it's like a minimum balance cut type problem right to even check the condition right >> yeah um yeah let me talk about that in a let me answer that in a bit >> okay >> okay so next I'd like to tell you how how to build a consensus protocol in the granular synchrony model right I will not give you all the details right but uh I think I will be able to convey the crux of the matter All right. So, let me start with a classic partially synchronous BFT particle, right? Like PBFT, tenderint, they all uh roughly work like this. It's organized in the sequence of views,

right? Each view has a unique leader, right? They uh these particles may do round robbing leaders or randomized leaders. And within the view, right, let's say this is a view number K, right? The leader will send a proposal. Okay, it will pick a value and I send it to everybody and then other nodes will vote in two rounds, right? So they will first do a one round of voting, right? And uh if they collect n minus f first the round of votes, then they will lock on that value. Okay, we'll talk about what lock means uh in a very soon. And then uh they will also send a round two vote. Okay. Then upon receiving n minus f round two votes they will decide on

that value. Okay. So then there is uh after that there is a non-trivial procedure called view change. I go to a next leader. Um right but this is the basic idea. Right. So um how many of you are familiar with this type of particles? Okay. Yeah most most people here. All right. So why is this uh why is this a secure particle? Right. um we we mostly need to worry about safety within a view and safety across views right within a view this is sufficient right because in order for one node to decide a value there are n minus f who need to vote for that value right and if you want a conflicting

value to be decided then there are n minus f who need to vote for that conflicting value right so then there's a standard corum intersection arguments right if you have n minus f voting for x n minus f voting for x prime right And the intersection between these two groups is uh their sum minus n which is n minus 2f right and in the classic partially synchronous particles n is at least 3 f plus one right so that intersection is at least f plus one which means there is one honest in intersection right which means that honest node double voted right and which would not happen right honest node would not double vote right so we cannot have two

large quorums voting for conflicting values. Now uh safety across views is slightly trickier right that if one node decides on a value right and this is where we need this notion of lock right n minus f must have voted for it and must have locked on it right and then in a new view a new leader when the new new leader wants to propose a value right it needs to respect the locks right it needs to go and ask people uh what values are you currently locked on it needs to collect these locks and uh show these locks to justify its proposal. Right? If somebody is uh and the leader is required to repropose the

highest lock, right? If there is any lock, this is also quum intersection argument, right? So there are n minus f who locked on a decided value, right? And the new leader must show n minus f locks, right? So that intersection is again f+ one which is uh which contains at least one honest nodes and so that honest node is guaranteed to inform the new leader of the potentially decided value. Right? So the new leader will have to repropose it. Okay. So this is uh uh the like basic idea behind PBFT tenderint hot stuff like pretty much all the partially synchronous particles.

Okay. Right. So now we will try to adapt this protocol in to the granular synchrony model. Right. Um but the main difficulty is that now we're in a regime where n is at most 3f. Right? Smaller than 3f plus one. Right? So then our inter quum intersection argument breaks down. The intersection is at most F. It could be that all of them are Byzantine, right? And the Byzantine can indeed double vote. The Byzantine can indeed um pretend to lock something and then later say they never locked, right? So we need to rely on the granular synchrony graph condition to fix this problem. Let's take a another

look at this train of thoughts. Right? If one person decides then n minus f have voted for it and n minus 2f on it nodes are among the people who voted right. So n minus 2f is a special value for our granular synchrony model right because our model says regardless of which nodes are bizantine there cannot be two disjoint groups of n minus 2f right what that means is that if one group is at least n minus 2f then the other group is smaller than n minus 2f right so they're f corrupted right and this um this right group is less than

mus 2f if we add them up that's less than m minus f right what that means is that this left group actually has to be larger right so there this is this does this this doesn't add up to everybody yet right so there's additional nodes who have to be connected to the left group right and this connected component in total is at least at least f plus one right because uh these two add up to less than musf so what that means for us is that right now when we let's just um as a example

I'll just do safety across views right um within a view is about the same right when one node decides n minus f lock n minus 2f honest lock right they are connected to F+1 honest nodes due to the granular synchrony condition right they're connected via synchronous paths right so if we just give them a little time right they will be able to transfer their lock to this larger group right this uh n minus 2f who initially locked they will send their locks to other people right and in a little bit time it will these logs will propagate to a bigger group of

size f plus one and then a new leader comes in the new leader needs to collect the n minus f logs right and now we again have a intersection right this n minus f and that f n uh that f plus one they intersect at at least one on its node right so that on it node will transfer the lock to the new leader force is the new leader to repropose the potentially decided value and we get back safety across views.

>> So right so the the F+1 that comprises both the N minus 2F people who >> yes >> who honest voters plus the people they can reach by synchronous paths. Yes. >> Okay. So that f plus one refers to those two white circles combined. >> This combined is f plus one. Yes. Okay. So yeah, so this is um um basic intuition, right? We pretty much whenever we need a quorum intersection argument, right, we will invoke this argument to uh essentially upgrade our M minus 2F cororum to a F+1 cororum, right? And that F+1 cororum will intersect with the other N minus F

cororum. So you have like two new rounds per view or something like that or >> Yes, we need um yeah with the protocol in what I'm presenting the protocol is not very efficient right we actually need a lot more rounds right because um okay because this is may not be a direct connection right this is just a path maybe a long path so we actually may need to make that an N rounds Right. Waiting time. Okay. Yeah. So now I'll get back to uh Tim's two questions. Right. First, the algorithm is graph agnostic, right?

I it never examines which link is synchronous versus partially synchronous, right? But the conditions are necessary even if you want to tailor an algorithm for a particular graph. The other question from Tim is a great one, right? Is that how do we know that granular synchrony condition holds, right? So I also uh struggled quite a bit when working on this right that um it seems unrealistic to go out to the field and measure every link right to I to then to to figure to label each edge whether it's a synchronous and partly synchronous and then check the graph condition right um but eventually I convinced myself this is not a problem right because uh we just don't have to

check right and I compare Compare this to what we currently do, right? We currently assume that the adversary cannot corrupt F nodes, right? Why do we believe that? Right? We never went to these nodes to investigate um their security practices, right? Whether they I followed whether they regularly update their software, right? Whether they uh like to accept bribes, right? whether they have financial ties with other different other nodes, right? We just assumed that no more than f can be corrupted, right?

If no more than f is corrupted, our protocol works. If the adversary manages to corrupt f plus one, then the protocol fails, right? And uh there's nothing we could have done, right? Um if indeed the adversary corrupts more than f where f is the 1/2 or 1/3, whatever the limit is, right? So I would argue that the situation here is the same, right? I just assume that the attacker cannot corrupt the network right so badly to create these large groups right if it cannot do that then our protocol works in if it manages to do that then our protocol fails right so I think the situation is not too different from what we currently do

>> I'd say I only half agree with you in the sense that one question is just what are you in a position to monitor so this is the point you're making right so maybe you can't monitor if a note is faulty and you can't monitor if a link is synchronous or not right but the point is it's like if you but then like suppose you could monitor right so if you could monitor who was faulty or not it would be trivial to check whether the bound of f held >> suppose I just gave you >> suppose I just told you the synchronous links and the non-synchronous links >> then there's the computational problem yes >> of given that information does the bound hold and the point is like if the graph is big that is also going to be quite >> nrivial that may even be an nplete

problem problem. Yeah. So, >> so I think there's a second issue here that's not there with just the fault bound. So, >> yeah, I I would agree with you if uh you take that view, right? Um I think I just don't feel whether we even go there, right? Because I don't think any protocol did any checking of uh who's malicious, who's uh not malicious, right? is even then um >> well like let's I mean like crash faults you could certainly do this for example right I mean like the idea of like monitoring is not crazy right like it's going to be only >> partially successful but >> okay y uh it's empty but you can

approximate it which means that you could probably still get some guarantees if someone if someone were to give you like all of the information about these guys are >> okay >> synchronous these guys are asynchronous you'd still be able to get something better than just knowing how many people are. >> Have you looked into the approximation factor? >> I think the approximation factor is like log n for balance vertex font with a non-trivial leaning constant. Exactly. >> Yeah, I think if we really have to check perhaps there's there we have we will have better luck with like huristics and set solvers.

>> I mean it's possible that the mathematical program relaxations would do well in practice and you'd do well. I'm not sure. But I'm just saying like there is this >> like so like what would be like like one thing I don't know if this is true but like imagine you could have a protocol that worked even if a certain like semi-definite programming relaxation of the network was sufficiently you know large or something like that right then you'd have a efficiently checkable condition that would be sufficient for consensus >> so that would be like a stronger result for example >> a stronger okay yeah >> right so with that I think there's a alternative interpretation ation of the granular synchrony model, right? That is protocol designer picks a pair of n minus n and f and wants to deploy a

protocol with these two parameters, right? And the adversary can corrupt nodes and it it can corrupt links, right? Corrupt links meaning slow down links to make it partially synchronous or asynchronous, right? Um but the adversary is assumed to not be able to create these two large disconnected groups, right? Hope it's not too hard to see that uh these are essentially saying the same thing. So lastly, very quickly um I just give you some food for thought, right, for the summer, right?

There's future directions that I'm interested in. Okay, this part is perhaps a little interesting. So let me spend a little more time on it, right? And so far we have not add asynchronous links, right? So now let's uh let me add back asynchronous links. Now we have three types of links. synchronous, partially synchronous and all things and asynchronous, right? And in this case, agreement for crash faults is solvable deterministically if and only if first the previous no split brain condition holds. And um not a complicated graph condition that I I won't go into the details but the interesting thing is right what I want to highlight here is that now if we consider f is strictly less than half

right so we're not trying to go to the intermediate um corruption then we know this first condition becomes vacuous right it always holds right and then agreement is solvable deterministically if and only if this other condition holds right So this could be interesting and significant to um some people if you care about the fundamental results of consensus right because this is the minimum condition to circumvent FLP right FLP says if all links are asynchronous then consensus is not solvable deterministically right what uh this result is saying is that if there are sufficient partially synchronous

links to satisfy this graph condition um then consensus can be solved deterministically right and in fact this disproves a prior conjectured minimum condition uh which is uh I said something else it's another graph condition that's strictly stronger than the one we found >> so this is a new result >> this is a new result >> okay >> okay and then there's a counterpart in the Byzantine case but in the Byzantine case we were only able to prove a negative result for graph agnostic algorithms for graph tailored algorithms with it is still open what the necessary condition is right so there's some open problems here okay so to summarize a

granular synchrony model has some nice properties it's weaker than synchrony allows some messages to take more than delta it tolerate more faults than pio synchrony and asynchrony right it naturally unifies the two models on the extremes and we have identified the necessary and sufficient condition for solving consensus there but uh there's still quite a few open problems here, right? Uh the first one is that we can study other problems in this model, right? Consensus is not the only problem that involves parties talking to each other, sending messages to each other, right? There are a bunch of problems in as well. Um even in in consensus, there's still like um uh reliable broadcast and in crypto the verifiable

secret sharing, multi-body computation, etc., right? Can be revisited in the new model. Um secondly, the protocols I presented are fairly inefficient because it requires a lot of forwarding and uh uh evolve is making um some exciting progress like that shows we can actually get pretty efficient protocols that asympto are as efficient as the ones in pure synchrony and pure parts synchrony. Okay. And uh uh right now we I'm assuming undirected graphs, right? So it's interesting to see what happens what changes in the directed graph and um you can combine it with other models right but um bigger open problem right

is that may have underd delivered a bit I hopefully you didn't notice so far right uh that when I set out to discover uh to to define a new timing model my primary motivation is to try to capture dynamic availability so right now Bitcoin and all of the dynamic available protocols have to be analyzed in the synchrony model. Not because it fundamentally requires synchrony, it's just that we don't have any other model uh that we can use to analyze them. Right? So um I was hoping that we would find some intermediate model between synchrony and asynchrony that still supports dynamic availability. Right?

But granular synchrony um at least the condition with the condition we identified was not that right because it's um pretty much tied to full availability it says as long as there are no two large components consensus should be solvable but in a dynamic availability problem even small isolated group I will make a conflicting decision right so I would say this problem is still open right I'm still searching for um like the right model for large scale distributed consensus that hopefully supports dynamic availability.

>> So if you relax the um condition that either like all the links are synchronous or partial synchron at the same time um do you you have like thoughts on what happens >> if all the links are >> like if you allow the timings of when things are synchronous to be interled somehow >> if the partial partially synchronous links are not synchronous at the same time. Um, no, we haven't thought about it. >> Okay. Okay. I guess maybe relatedly, if you have something like an adversary that's allowed to like have some fraction of the links, they switch from time to time. Um, so like either things are synchronized or they're they're not, but like adversary chooses which ones to corrupt. Is that connected or known at all?

>> Like can can you say that part again? >> So like um >> so is in between between things being arbitrarily interled or like perfectly synchronized. Say an adversary is like allowed to um have some fraction be not synchronized and some fraction be like introduced. >> Um are are you mainly interested in that the adversary moves around? >> Yeah. Yeah. So like they can't have all the links at the same time but the network maybe >> you haven't considered um any notion of uncorrupted link or uncrupter node.

That usually makes stuff very hard, very quick right? >> Yes. For I think it it might be slightly easier for link, right? For for node, yes, there's some keys involved. Once you corrupt a node, it learns the key and it's unclear how to uncrupt it. But for a link, uh at least the notion of uncorrupt is clear, right? Um yeah, I but I think the challenge there is that you cannot let the adversary jump back and forth too quickly, right? And so there needs to be some cool off in the model. So on the SL side, so did you say that the condition you do know that the condition that you identified for strict majority with full availability is not sufficient for dynamic availability. Did you say

>> it was not sufficient because it's in particular it allows small uh isolated groups, right? The only thing it doesn't allow is two big isolated groups, right? But with dynamic availability, even a small isolated group will cause trouble. And so do you even do you have like a conjectured necessary condition or >> yeah not uh okay >> yeah nothing comes to mind. >> I like your comment Tim about like uh coming up with an STP or an LP that will like be maybe like a relaxation of that condition to a more continuous model and then prove that that's tight. I don't know how you would model a link though

in that case like I don't know maybe all links are synchronous but just like with very large bounds or some >> I I thought Tim's point was mainly that find the maybe slightly stronger condition that's easy to check >> that >> um yeah that that's one that's one version of it definitely yeah >> basically insist on easy to check and get whatever you can get >> was sort of the thing what I was thinking Yeah, >> and if you can get the if you can get everything you have now and it's easy to check, then all the better, right? But maybe you need some tradeoff. So, >> sorry, coming back to Prenab's question about the adversary moving. If the

protocol is network agnostic, I shouldn't be making decisions based on whether this link is synchronous or not, right? >> We are not, >> right? >> So, what what what goes wrong when the adversary moves around on the links? Um, let's see. Because these protocols they they have a unit usually called a view. You want to argue that a view succeeds, right? So if you let the adversary corrupt part of the network in the beginning of the view, right? And then move to a different segment of the different different part of network in the middle of the view, right? So then it can

>> I see. >> Right. Yeah. So that's why I feel intuitively if you built in some um right some cool down period right when you uncorrupt the edge you cannot immediately corrupt another edge things might work >> so there's no explicit attack as such >> it's just that we don't have the proof techniques or >> I can probably come up with a explicit attack if there's no such cool down right or ah right okay very uh very easy attack is that I always corrupt all the edges of the leader, right? That actually doesn't violate um the condition.

>> All right, Mr. Franklin again.