Population protocols with unreliable communication
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 |
| |
| Author | 0000-0002-6660-5673 (ORCID) | |
| License | CC Attribution - ShareAlike 3.0 Germany: 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 and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/54997 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
00:00
Recursive languageServer (computing)System programmingScheduling (computing)Message passingFormal languageInfinityGeneric programmingPredicate (grammar)Read-only memoryLogical constantRule of inferenceTelecommunicationData transmissionCondition numberInteractive televisionSequenceCommunications protocolScheduling (computing)Arithmetic progressionVulnerability (computing)Bound stateDistribution (mathematics)Message passingCategory of beingEndliche ModelltheoriePairwise comparisonState of matterLogical constantInfinityBoolean algebraCombinational logicMathematicsDecision theoryMiniDiscAtomic numberBroadcasting (networking)SubsetMereologySingle-precision floating-point formatPoint (geometry)View (database)Server (computing)Rekursiv aufzählbare MengeSet (mathematics)CASE <Informatik>Theory of relativityRule of inferenceMultisetSemiconductor memorySocial classMicrocontrollerExtension (kinesiology)Metropolitan area networkProcedural programmingClosed setMultiplication signIdentity managementForm (programming)Presentation of a groupCharacteristic polynomialSimilarity (geometry)Power (physics)NeuroinformatikPhase transitionStability theoryRange (statistics)TelecommunicationSynchronizationInterprozesskommunikationDatabase transactionContext awarenessNumberFinite setInversion (music)Direction (geometry)State observerParameter (computer programming)Predicate (grammar)Normal (geometry)ExpressionFormal verificationComplete metric spaceTerm (mathematics)Bounded variationCross-correlationComputer animation
Transcript: English(auto-generated)
00:00
Hello, I am Michael Raskin and I will talk about population protocols, the range of the related similar model and the impact of unreliability of communication on the expressive power. The original formulation of the model of population protocols speaks about small sensors, like I don't know you could try to attach to birds if you want to try
00:22
to track birds individually, and the sensors are so small they have just a fixed amount of memory, in particular not enough memory to identify each other, so they just have a finite internal state and they cannot move of course because it's the birds who actually fly, and then the only thing that sensors can do is that if two sensors by
00:47
chance end up nearby each other, they can do an exchange of information, they can communicate. And to talk about all of these as computation, to allow this computation to return some
01:02
answer, at least yes or no, we say that each internal state of the sensor, of each sensor is either accepting or rejecting, and then we say that the sensors hope to eventually from some point and forever have a consensus, so that either they all
01:22
accept or reject, and this consensus is supposed to accept or reject the initial distribution of internal states, or maybe to accept or reject the initial size if they have identical initial state in the beginning, but they don't need to have
01:43
identical initial state, because for example they might have different initial states based on the properties of the birds they are attached to. The definition of the population protocols, as I tried to summarize, was formally introduced in this specific form in 2004 by Anglian and Naspnes and Diamantia and Fisher and Peralta,
02:05
and you might have also seen this illustration of the birds in some presentations of my colleagues. And of course once a definition becomes popular, there are various restrictions or extensions that are studied. Well, there are of course restrictions on what kind of
02:24
interaction can happen, but there are also extensions, like for example maybe we don't have instantaneous communication, but instead we can send a message and then we can receive a message, and messages can take their sweet time in transit, or maybe there are also
02:42
broadcast interactions when I can tell something to everyone, or maybe there are just multicast, which means that I try to tell something to everyone, but I fail and only tell it to some of my close by neighbors.
03:01
In any case, whatever extension or restriction we want to study, we might also want to revisit whether the original motivation of the definition of population protocols applies in our case. And for example, well, the thing that is preserved, a man called the definition, is that we have just a fixed, constant amount of memory, and so
03:25
our sensors are so small they cannot even remember each other's identifiers. And you know, if you take this motivation at face value, just straight as stated, it feels ancient, or maybe even obsolete, because if you just go to DGP and ask what can I get
03:44
for 10 cents, and you can't really get much cheaper. And then the answer is nothing, because right now we have a shortage. But in normal times, for 10 cents per unit, you can get microcontroller units, which will have, well, they will be small and
04:02
they might have a little memory, for example, 128 bytes. At the same time, is it small or not? Because, you know, if you want to identify uniquely microcontrollers in your flock, it can be whatever, you need some bytes, maybe 4 bytes, maybe 6 bytes.
04:23
Well, we know that 4 bytes we tried to use for IPv4, and for the global deployment, it turned out that 4 billion is not enough. But 6 bytes for many purposes should be fine, and then it means that the small sensors are already large enough that identifying
04:44
each other is not out of reach anymore. But personally, I believe that this is not what we should care about, this is not why we should care about population protocols, or not care about population protocols. Because the nice property of population protocols is that they live on this edge of decidability.
05:06
The reachability and various properties of population protocols are actually equivalent to vast reachability, and so they are accurate and complete. And it's interesting, natural extensions quickly bring you to undecidable problems.
05:23
And so it's interesting what exactly can be expressed while we can still ask questions and have a decidable procedure to get answers about our protocols. You know, even beefy servers like Simplicity, because if you have a large deployment
05:45
and you want it to reach consensus, and it doesn't, you want to have a chance to understand what's going on, you want to have a chance to verify whether your fix actually fixes something. So I think that population protocols, even if the original
06:03
motivation is not very convincing, they are still interesting as a simple model which is nice if we can afford to use it. Of course, if we say that population protocols are nice because it's a restricted model which is nice and cheap, it's a good idea to ask ourselves whether they are actually cheap.
06:25
If we are talking about memory, sure, this finite number of internal states and usually pretty low number of internal states is always nice from the point of view of very low memory use. On the other hand, if you look at our interaction model,
06:40
it's more interesting, because our model of interaction is atomic. When two agents meet and they try to interact, either both say that the interaction has succeeded and so they have their new states, or both say that the interaction has failed and therefore they revert to the original states.
07:00
And this atomicity grantee, this transactional behavior, is pretty expensive. In many cases, in the distributed systems, these synchronization grantees and the atomicity grantees and transaction guarantees are one of the most expensive things possible.
07:23
Sometimes they are even impossible if you have just two agents interact in some contexts. And so I think it's interesting to ask what happens if we forbid requiring atomic interaction. And so the goal is to get a general understanding for what predicates, for what properties
07:49
of the initial distribution of internal states we can reliably get to a stable consensus, well, correct stable consensus, whether these properties were initially satisfied or not.
08:06
And we wanted to be general in the sense that it should apply to a lot of variations, a lot of versions, a lot of extensions of population protocols as studied in the literature, well, at least to some, you know, natural class of the models.
08:24
What we definitely keep as the defining characteristic of the class of population protocols and similar models is that we ask for constant memory per agent and we also say that if we can send some kind of slowly delivered messages,
08:45
then these de-labeled messages should also come from a finite repertoire of messages. Now turning to what we allow as the interactions in the protocol, well, we want to allow broadcast, we want to allow pairwise interactions one-to-one,
09:03
we want to allow sending messages, we want to allow receiving messages, so we want everything in a single model. And these are kind of different and so we just have a very general definition, so you have the multi-set of messages, if you use messages, which are de-labeled
09:22
and then you have the states of each agent and then when you have a situation before interaction, you have a situation after interaction and the interaction rule is just a relation and we don't have too many conditions, we don't care about stuff like decidability of our protocol,
09:43
we can have a protocol with undecidable correctness of traces, but what we do care about is some kind of generalizability. What it means is that if you have some kind of set of agents and they interact and there are of course complicated conditions in their internal state,
10:01
but they do some interaction, then if there are some additional agents, so to say newcomers, then the old-timers will be able to interact even in presence of the newcomers. Newcomers cannot stop the old-timers from doing their thing. Of course, the newcomers can observe the old-timers interacting
10:23
and the newcomers can change their internal state. That's perfectly fine, but they cannot stop the old-timers. And another thing that people care about in the interactions is some global, the sequential behavior of interactions, so the scheduling.
10:41
So for example, if the adversaries say that all this, just the first and the second agent, they always interact and nobody else is ever allowed to interact, this is of course suboptimal and we are not going to reach any interesting situation like that. So people try to invent some kind of fairness condition or use some kind of fairness condition
11:02
which prohibits the scheduler from preventing all the ways of progress of the protocol. And we have very weak requirements for the fairness condition. Whatever people use as fairness, strong fairness, weak fairness, even stronger than strong,
11:21
even weaker than weak, our basic results, our lower bounds and our upper bounds, everything will hold just fine. Where we do put strong requirement on what we study is of course unreliability of communication or lack of atomicity of the interactions.
11:41
So our unreliability is kind of a restriction on how execution happens in the sense that it is always possible that only a subset of agents will update because it's hard to determine whether the interaction has succeeded or has failed and therefore it is possible that some agents will update their internal states
12:03
and some agents will not update their internal state. Of course there are some examples like for example broadcast, where if you know that the broadcast has failed, if you are sending the broadcast and think that it has failed, then nobody can receive it anyway.
12:20
So you can have restrictions that some agents must think that the interaction has succeeded for others to think that the interaction has succeeded, but still there is always a possibility that only a part of the agents will update their internal state. And so the question is, in this pretty general model of protocols
12:45
with single modification of unreliability of communication of course, what properties of the initial distribution of internal states can reliably reach correct consensus whether these properties hold or not.
13:06
And the answer turns out to be very simple, it's just Boolean combinations of comparison of the number of agents with some initial state with constants. So an example is initially there are at least 3 red birds or at most 5 black birds.
13:26
If you prefer servers, then there were at least 3 servers with WD red disks or at most 5 servers with WD black disks. And this actually is the same as the expressive power of Immediate Observation Population Protocols
13:43
also known as One-Way Communication Population Protocol, which are defined as these population protocols such that only one of the agents changes state in the interaction. In other words, an agent can observe another agent and change the internal state,
14:06
but the observer doesn't even notice that it was observed. And of course this model doesn't care whether the communication is reliable or unreliable because unreliability of communication doesn't actually change anything.
14:21
The interaction still either happens or not. And also Immediate Observation Population Protocols actually are simpler than General Population Protocols in the following sense. As I mentioned, the population protocols in general live on this age of decidability almost, they have a k-Rman complete eligibility and stuff like that.
14:40
For Immediate Observation Population Protocol, the situation is actually much better. They have space complete verification and also their eligibility relation is semi-linear and they are just generally simpler and nice. And it turns out that in the unreliable communication setting, they can do everything in terms of computing predicates that any other protocol could do.
15:10
And also let me tell you about a curious power inversion of a sense that consider that the agents never interact directly. We consider the message-based protocol, so every interaction is either one agent,
15:25
just one agent, sending an arbitrarily delayable message or receiving a message sent by this agent or another agent long ago. And so we call these message-based protocols.
15:42
And it turns out that while in the reliable communication settings, they are very powerful, much more powerful than Immediate Observation Population Protocols, in the unreliable setting they become much weaker than Immediate Observation Population Protocols in the sense that they cannot even reliably reach different consensus
16:03
if you initially have two agents or you initially have four agents. Even stuff like that they cannot do anymore. And so this is an inversion of power or you could say that messages that can be delayed arbitrarily long were an asset in the classic reliable setting but become a liability in case of unreliable communication.
16:31
As a very brief overview of the technique, I would say that copy-cut arguments here are finally brought to the full glory they deserve. Instead of the very simple normal copy-cut arguments where you can just reproduce the sequence of state changes
16:46
for some usually very simple reasons, here you cannot do that. But you can build an infinite run where for every agent and for every prefix of the run
17:01
you can add another agent reaching the same target state even though via a slightly different path. And this is sufficient to provide an upper bound on what predicates can be computed. As for the message-based protocols, there something similar happens
17:23
but there the technique is that you have a first iteration, that you want to send so many copies of messages that messages stop being scarce. You don't need to count how many messages there are and that means you don't need to count how many agents are consuming them.
17:43
Of course there can be rare messages but to get rid of them you just try to receive them but fail to update your internal state and you just get rid of the rare messages and you only have abundant messages. So in conclusion, we have looked at correlation protocols and their variations
18:03
and why they are interesting and why this interest suggests one more unexplored direction. And we have seen that unreliability of communication gives the same expressive power from the point of view of computing predicates by consensus to a pretty large range of the models of the population protocol like computations by populations.
18:28
And I will also take liberty to say in the conclusion that we have seen one more way that IO protocols, immediate observation protocols are nice. Thank you all for your attention.
18:40
Are there any questions?