Consensus Potpourri: Approximate Majority With Catalytic Inputs
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 30 | |
| Author | ||
| License | CC Attribution 4.0 International: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/52878 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Data modeloutputState of matterProcess modelingBound stateCommunications protocolSample (statistics)Inheritance (object-oriented programming)ApproximationLogical constantComplete metric spacePhase transitionNL-vollständiges ProblemData structurePermianLeakEvent horizonAerodynamicsMathematical analysisApproximationMedical imagingFraction (mathematics)Data structureDynamical systemSequenceMathematicsOrder (biology)Self-organizationSoftwareFunction (mathematics)Type theoryBus (computing)Product (business)Level (video gaming)Random variableDrop (liquid)Phase transitionTask (computing)Flow separationTotal S.A.AnalogyMathematical optimizationEquivalence relationState of matterArithmetic meanBeta functionBitSeries (mathematics)Connected spaceLine (geometry)Green's functionGroup actionRandom walkComplex (psychology)LogarithmMereologyMarginal distributionSlide ruleResultantSampling (statistics)Spontaneous symmetry breakingTerm (mathematics)CountingNumberDataflowNear-ringQuicksortAreaConfiguration spaceRevision controlGoodness of fitLogical constantFamilySimilarity (geometry)MeasurementRegular graphCASE <Informatik>Process (computing)Strategy gameError messageRootInstance (computer science)State observerSquare numberHand fanAdditionPoint (geometry)Inheritance (object-oriented programming)Ocean currentSocial classSet (mathematics)outputArithmetic progressionCommunications protocolWord19 (number)Reading (process)Data conversionInteractive televisionLatent heatCorrespondence (mathematics)Chemical equationDecimalParity (mathematics)Event horizonBit rateView (database)Endliche ModelltheorieNP-hardDifferent (Kate Ryan album)NeuroinformatikCapability Maturity ModelLoginContext awarenessMultiplication sign2 (number)File archiverAssociative propertyMoore's lawValue-added networkMobile WebTwitterInvariant (mathematics)BijectionFunctional (mathematics)LeakPolygonDivisorBound stateSummierbarkeitComputer animation
Transcript: English(auto-generated)
00:01
Hi, my name is John Lazarsfeld and today I'm going to be talking about our paper, Approximate Majority with Catalytic Inputs, which is joint work with Talia Mir and James Osmanis. So our work is about the majority problem in a variant of the original population protocol model.
00:21
So we'll briefly review the original model where we have a population of n-mobile agents where at every step a pair of agents is chosen uniformly at random to interact. And the local state of both agents are updated according to some global transition function. So in the majority problem, we assume that initially every agent is in one of two states,
00:44
either a blue state or a red state. And we also assume that the input margin, which is just the absolute difference in the initial counts of the two states, is non-zero. And the goal then is to converge to a configuration where every agent ends up in the blue state,
01:01
which in this example is the initial majority state. So here are the set of transitions for a simple protocol for this task. And the protocol is referred to often as the third state dynamics, and it was independently discovered by Englund, Eisenstadt, and Osmanis in 2008, and by Perron, Vasudevan, and Vojnavic in 2009.
01:24
And here, whenever a blue and red agent interact, they both cancel each other out and transition into a third green state. Then whenever a green agent interacts with a blue or red agent, the green agent will transition into the state of its interacting partner.
01:44
And so the intuition here is that as long as the input margin is large enough and because the interactions are chosen uniformly at random, then a green agent will always be more likely to interact with a blue agent. And so eventually, we'll end up converging to a configuration
02:02
where every agent is in the blue state. So the complexity measures that we're interested in are one, the number of steps or interactions until we converge successfully. And second, we're interested in the number of states required by protocols. So in this case, the protocol used only three states.
02:26
So in this work, we consider the following variant of the original population model. So we have a population of N catalytic input agents, which are agents that never change state throughout the course of a computation,
02:40
as well as M worker agents that are able to change state. And we let capital N denote the total number of agents in the population. And several recent works by Alistair et al. in 2017 and 2020, as well as by Dudek and Kosowski in 2018, have considered populations that featured a similar distinction
03:02
between the two types of agents. And in particular, Alistair et al. noted that agents that never change state embody chemical catalysts because they may induce a state transition in another agent, while themselves never changing state. And in addition, population protocols have been used recently
03:22
to model both chemical reaction networks, as well as other types of chemical processes. So with this motivation in mind, we call this model in our work the catalytic input model, or the CI model for short. Now, just to visualize this a bit more,
03:40
whenever two catalytic input agents interact, neither will ever change state. But on the other hand, when a catalytic input and a worker agent interact, the worker agent might change state, but the catalytic input never will. And so the majority problem in this model extends naturally, where now we're interested in determining
04:02
which of the two catalytic input states is more prevalent in the population. And now we let the input margin denote just the absolute difference in the count of the two input states. And our goal is to eventually converge to a configuration where every worker reaches some state corresponding to the correct input majority.
04:22
So this might mean that every worker agent enters some blue worker state corresponding to a blue catalytic input majority. So we're interested in the majority problem in the catalytic input model. And so we can first recall
04:41
what we know about the majority problem in the original model. So in the case of general or exact majority, where the input margin could be as small as one, in the recent years, there have been several protocols which can do this quickly or in n-poly log n steps with high probability. Most recently by Ben-Nun et al in 2020.
05:04
But at the same time, early result by Alistair et al in 2017 showed that any protocol for exact majority in the original model requires at least log n states per agent in order to be correct with high probability.
05:21
So a rather large state requirement per agent. Now on the other hand, in a relaxed version of the problem called approximate majority, a correct answer is only expected when the input margin is sufficiently large. And in this case, this can be done using only three states
05:40
in n log n steps with high probability. In particular, using the third state dynamics protocol that we saw in the example on the first slide. And recently Tonden et al in 2019 improved the analysis of this protocol and showed that the protocol converges correctly
06:01
as long as the input margin is square root n log n. So what do we know about the majority problem in the catalytic input model? Well, a recent result by Alistair et al in 2020 gave a protocol for approximate majority in the CI model that converged correctly in n log n steps
06:22
with high probability but requires log n states per worker agent. And in addition, the protocol converged correctly only when the input margin was linear in the number of catalytic input agents. So it's remained open though, first, whether there is a protocol
06:41
for exact majority in this model that converges quickly. And also whether there is a constant state protocol for approximate majority in the CI model. And if so, under what requirements on the input margin. So the main contribution of this work
07:02
is to help partially resolve these two questions. Now, on the one hand, we show that in the case of exact majority, every protocol in the CI model requires at least n squared steps to be correct with high probability when the number of input and worker agents are both a constant fraction of the total population.
07:21
And this implies a strong separation between the CI and original population models. Now, on the other hand, we show that the third state dynamics of the original model can be adapted to give a constant state protocol for approximate majority in the CI model
07:40
that converges in n log n steps with high probability as long as the input margin is square root n log n. So for the remainder of the talk, we'll give a high level overview and intuition for these two results. And then we'll end by mentioning a second set of results that introduces a second variant to the original model.
08:04
So we'll start with the lower bound on protocols for exact majority in the CI model. And the key observation here is that we can never tell whether or not an input agent has previously interacted with a worker agent.
08:20
So whenever we have a interaction between a worker agent and a catalytic input agent, we can view this more as the worker agent taking a random sample with replacement from the input population. Now, for the sake of proving lower bounds in the CI model, we consider the following super CI model.
08:43
So the super CI model features a catalytic input population of n agents, as well as a computationally unbounded super worker w. And here, every time w interacts with the input population, it sees a blue input with probability p
09:03
and a red input with probability one minus p. And so again, we think of this as the super agent taking a random sample with replacement from the catalytic inputs. And so now in the context of majority, the goal of the super worker is to take s samples
09:22
and then use these samples to determine what it thinks the correct input majority is. Now, because the super worker is computationally unbounded, it's capable of simulating any regular CI model protocol. And so this means that if we have a lower bound
09:42
on the number of samples that the super worker needs, in order to produce a correct output with high probability, this implies a lower bound on the total number of interactions that any protocol in the regular CI model needs to be correct with high probability.
10:00
So now, for the exact majority problem, again, the hard case is when the input margin between the two catalytic input states is one. And so this means that the probability that the super worker sees a blue input is very close to the probability that it sees a red input. And moreover, we can show that the optimal strategy
10:24
in terms of minimizing its error of the super worker is just to take s samples and then to output the majority value of these samples. And so then it follows that in this hard instance, in order to overcome the sampling error,
10:42
the super worker needs at least n squared samples in order for half of them to be from the correct majority states. And now when the number of catalytic inputs is a constant fraction of the total population in the regular CI model,
11:01
this then implies the n squared lower bound on the total number of steps needed by any CI model protocol. So we note that this also, the same bound can be applied to determining the parity of the catalytic input states,
11:20
given that there's a one-to-one correspondence between the parity problem and the exact majority problem with input margin one. And again, because we know that exact majority can be done in the original model in n poly log n steps, that this implies a strong separation in the computational power of the two models.
11:47
So while exact majority in the CI model is hard, it turns out that we can successfully adapt the original model third state dynamics to give a constant state protocol for approximate majority in the CI model.
12:02
So specifically the protocol we present uses only five total states. So the two catalytic input states and the only three worker states. And the transitions of the protocol are again adapted from the original third state dynamics, which we saw in the example on the first slide.
12:22
And in particular, the set of interactions between two worker agents are identical to the transitions of the original third state dynamics. And we also add the following two transitions between catalytic input and a blank or green worker, where if a green worker interacts with a blue input,
12:43
the worker will transition to the blue worker state. And if the green worker interacts with the red input, it transitions to the red worker state. So again, the intuition is that if we assume that all the worker agents start in the green state, then as long as the input margin
13:02
between the blue and red input states is large enough, then worker agents in the green state will be more likely to transition into the blue worker state. And although that we will still have a small number of red inputs in the population that remain there over the course of the computation,
13:23
once the number of blue worker agents becomes large enough, then this again means that other worker agents will be more likely to transition into the blue worker state. And eventually this will allow us to converge to the all blue worker configuration corresponding to a blue input majority.
13:42
Now, specifically, we show that as long as the input margin is root n log n, and when the number of workers and inputs are both constant fractions of the total population, then we'll reach this converged configuration within n log n steps with high probability.
14:01
Now, to prove the correctness and the efficiency or the total number of steps needed until convergence, we reduce the problem to looking at a sequence of biased one-dimensional random walks. So in particular, we think about the bias as looking at the fraction of agents
14:22
in each of the five states at any given point of time in the computation. And although these counts and fractions are changing, we use a structure of phases that allows us to abound these counts throughout various points of time in the computation.
14:41
So specifically, we look at the following three progress measures. So I'll first point out that these lowercase letters are random variables denoting the number of agents in the corresponding state at any given point in the computation. And so the first progress measure p represents the total difference between
15:01
the number of agents supporting the blue input state and the number of agents supporting the red input state. And then the progress measures x hat and y hat capture the number of workers in the blue worker state and then the red worker state respectively.
15:21
And we notice the invariance where x hat plus y hat will always be equal to the total number of workers, which is m, throughout the computation. So with these progress measures in mind, we use the following set of three phases
15:40
which was first introduced by Condon et al in 2019 when looking at or when analyzing the original model third state dynamics. So in the first phase, we consider a logarithmic number of stages where at each stage the progress measure p doubles and this continues until p reaches a constant fraction
16:02
of the worker population plus the initial input margin. And then in the second phase, we consider a logarithmic number of stages where the progress measure y hat decreases by a factor of two. And this continues until y hat drops below some value that's logarithmic in the total number of workers.
16:23
And finally, in the third phase, we'd look at the progress measure y hat until it drops to zero. And at this point, when y hat is equal to zero, this corresponds to every worker being in the blue or x worker state. So the strategy of every phase
16:41
is to treat the progress measure we're considering as a biased one-dimensional random walk. And so first we bound the number of productive steps that are needed to complete the phase correctly where the productive steps are just this set of five
17:00
non-null transitions. And from there, we then bound the total number of steps for each phase that are needed to obtain the requisite number of productive steps with high probability and taking a union bound over every phase and stage then gives the final result. So just to visualize this a bit more,
17:21
here's an example execution of the protocol on a population with 5,000 inputs and worker agents where the blue, red, and green lines represent the number of agents in the corresponding states at the various steps of the computation.
17:41
So the first pink vertical line represents the end of the first phase, which we can think of as having a sufficiently large gap between the number of blue and red worker agents. And finally, the second vertical line represents the end of the second phase
18:01
where the progress measure y hat drops below some value that's logarithmic in the total number of workers. So in a sense, the sum of the green and red lines. And finally, in the third phase, the protocol continues until the progress measure y hat drops to zero.
18:21
In other words, meaning that every worker enters the blue worker state. So we now turn to discuss a second set of results, which considers an additional variant to the original population model. And this is called transient leak events. And these are events that were considered as well
18:42
in the work of Alistair et al in 2017 and 2020. And if we recall the connections between population protocols and modeling chemical processes that was mentioned earlier in the talk, we can think of a leak event as simulating the low probability event that a molecule undergoes
19:03
a reaction that would have typically taken place in the presence of a catalyst. So in population protocols, this can be modeled as a spontaneous state transition that occurs at a single agent at every step with some probability beta.
19:20
And in the catalytic input model, only worker agents are susceptible to this type of leak event given that catalytic input agents never change states. Now, similar to the work of Alistair et al, in our work, we consider these leak events to occur adversarially, meaning that they induce
19:41
the worst case state transition with respect to the progress of the protocol that we're interested in. So to visualize this a bit more, if we take our CI model protocol for approximate majority from the previous slide, so at any given step, we might have a regular interaction between two agents,
20:04
but with probability beta at every step, we have one of these transient leak events, which in the case of our protocol would mean that a blue worker agent suddenly flips to the red worker agent state.
20:20
So the protocol of Alistair et al for approximate majority in the CI model was shown to nearly converge within N log N steps with high probability when the leak rate beta was sufficiently small. And here, near convergence just means that the protocol reaches a configuration where all but a fraction of the worker agents
20:44
are in the worker state corresponding to the correct input majority. So our second set of results is to show a similar type of robustness to these leak events of the third state dynamics family of protocols.
21:00
So first, we show that our CI model protocol for approximate majority also nearly converges in N log N steps with high probability when the leak rate beta is sufficiently small. But we also show that the original third state dynamics protocol in the original population model where all agents are susceptible to these leak events,
21:23
that this protocol also nearly converges in N log N steps with high probability for small enough beta. So now I'll just briefly mention some more specifics about the convergence of our protocol in the CI model and the results
21:43
for the original model third state dynamics is follows analogously. So in the CI model, we show that when the input margin is at least root N log N, then the protocol within N log N steps will reach a configuration where at most
22:01
a beta fraction of the worker agents are in the incorrect worker state. So that would mean that a beta fraction of worker agents are in the red worker state even though we have a blue input majority. And the analysis for this near convergence
22:23
uses, it follows similarly from the analysis in the non-leak setting where we use a structure of phases and we consider a biased one-dimensional random walks. And so the strategy here is to first bound the number of these leak events that could occur at any phase of the computation.
22:43
And then from there, we bound the number of non-leak steps that are needed to still make progress throughout the protocol. So to visualize this a bit more, here again is an example execution of the protocol where we track the counts of worker agents
23:03
up to four N log N steps. And in this case, beta is zero, meaning we're in the non-leak setting. And here, just as we saw in the previous slide, we know the protocol will eventually reach a configuration where every worker is in the correct worker majority state.
23:26
But now when we have a leak rate of log N over N, again, we see at the end of the four N log N total steps that a large fraction of worker agents will be in the blue worker state, but that this convergence occurs much slower.
23:42
And finally, if we increase the leak rate to root N log N over N, we can see that after at this cutoff point, the fraction of agents in the blue worker state is still large but is dropped compared to the smaller leak rate. And this is in line with our theoretical results.
24:03
So finally, I'll mention that the third state dynamics protocols, both in the CI model and in the original model, behave similarly in the presence of these transient leak events as they do in the presence of Byzantine agents, which is a type of dishonest agent
24:21
which has been considered in previous work that looks at the original model third state dynamics. And so our final result is to show an equivalence in the behavior of the CI model and original model protocols in the presence of these leak events
24:41
and in the presence of the Byzantine agents. So in conclusion, we've shown that in these catalytic input model, which features the two distinct types of agents, there are some problems like exact majority which can be done quickly in the original model
25:02
but are hard to compute in the CI model. But at the same time, some techniques like the original third state dynamics can be easily adapted into the catalytic input model. So it remains an interesting open question to understand what other types of protocols
25:20
and techniques can be adapted successfully into the CI model. And finally, we showed that the original third state dynamics is robust to the type of transient leak events that we considered in the CI model. And so another interesting question is to better understand what class of protocols
25:41
is similarly robust to the transient leak events in the original population protocol model. So thank you for listening to this talk and we encourage you to read the full version of the paper which is on the archive. So thank you.