Graph algorithms and population protocols: Uniform Bipartition in Population Protocol Model with Arbitrary Communication Graphs
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 30 | |
| Autor | ||
| Lizenz | CC-Namensnennung 4.0 International: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/52871 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
00:00
SystemprogrammierungMini-DiscProtokoll <Datenverarbeitungssystem>Gleichmäßige KonvergenzBipartiter GraphEnergiedichteOrdnungsreduktionGruppentheorieGruppenoperationDivisionGraphLokales MinimumAggregatzustandSymmetrieWorkstation <Musikinstrument>Ganze ZahlDatenmodellSymmetrische MatrixNichtunterscheidbarkeitKonfigurationsraumGruppenoperationSchlussregelKontextbezogenes SystemPhysikalischer EffektProtokoll <Datenverarbeitungssystem>GraphProgrammierungSchätzungProzess <Informatik>GRASS <Programm>MultiplikationsoperatorZahlenbereichGreen-FunktionResultanteEinfache GenauigkeitMereologieRichtungQuadratzahlTypentheorieGruppentheorieArithmetische FolgeEnergiedichteGüte der AnpassungDatensatzFamilie <Mathematik>TelekommunikationAggregatzustandNichtlinearer OperatorInteraktives FernsehenMAPRationale ZahlDiskrete GruppeQuantenzustandRoutingBus <Informatik>DruckverlaufSpieltheorieVirtuelle MaschineTouchscreenDifferenteWorkstation <Musikinstrument>Konfiguration <Informatik>TaskAutomatische HandlungsplanungKonfigurationsraumStatistische SchlussweiseOrdnungsreduktionMusterspracheSchaltnetzMinkowski-MetrikSoftwareschwachstelleLokales MinimumPrimidealUniformer RaumSymmetrieTabelleVollständigkeitKonditionszahlBildgebendes VerfahrenGebundener ZustandExistenzsatzModelltheorieSchnittmengeVollständiger GraphZustandsmaschineSoftwareKartesische KoordinatenRobotikFigurierte ZahlComputeranimation
07:32
GraphKonfigurationsraumSymmetrieSymmetrische MatrixProtokoll <Datenverarbeitungssystem>SystemprogrammierungAggregatzustandLokales MinimumWorkstation <Musikinstrument>Ganze ZahlDatenmodellFontGleichmäßige KonvergenzBipartiter GraphVariableTopologieSymmetrieProtokoll <Datenverarbeitungssystem>SoftwareschwachstelleKonfigurationsraumSchnittmengeModelltheorieUniformer RaumGebundener ZustandKonditionszahlZweiGraphVollständigkeitResultanteAggregatzustandPrimidealDickeTelekommunikationDelisches ProblemZahlenbereichInteraktives FernsehenDreiecksfreier GraphAsymmetrieGruppenoperationLokales MinimumCASE <Informatik>GraphfärbungWorkstation <Musikinstrument>MinimumTopologieNatürliche ZahlStrategisches SpielBipartiter GraphAuflösbare GruppeTypentheorieRichtungMultiplikationPartitionsfunktionVariableTabelleWasserdampftafelGRASS <Programm>ProgrammierungEreignishorizontKontextbezogenes SystemPortal <Internet>ÄhnlichkeitsgeometrieSchätzfunktionArithmetische FolgeMixed RealityNormalvektorPhysikalische TheorieBefehl <Informatik>VererbungshierarchieGruppentheorieInternetworkingSchlussregelKonfiguration <Informatik>p-BlockDatenstrukturQuantenzustandMultiplikationsoperatorStrömungsrichtungSchnitt <Mathematik>MAPProzess <Informatik>SpieltheorieGoogolAbstandPhysikalischer EffektComputeranimation
15:04
Workstation <Musikinstrument>TopologieSystemprogrammierungAggregatzustandLokales MinimumSymmetrieGanze ZahlDatenmodellGraphSymmetrische MatrixProtokoll <Datenverarbeitungssystem>RestklasseZeitbereichGruppentheorieNichtunterscheidbarkeitProtokoll <Datenverarbeitungssystem>GraphfärbungUniformer RaumMultiplikationMinimumPartitionsfunktionTelekommunikationAbstandGruppenoperationBitAdditionGraphAggregatzustandFigurierte ZahlInteraktives FernsehenMinkowski-MetrikAuswahlregelDomain <Netzwerk>DifferenteRichtungGruppentheorieIdentitätsverwaltungExistenzsatzDickeProgrammierungDreiecksfreier GraphStrategisches SpielKomplex <Algebra>SoftwareschwachstelleVerkehrsinformationBitratePunktEndlich erzeugte GruppeFehlermeldungResultanteeCosSpeicherabzugGRASS <Programm>Vorzeichen <Mathematik>MultiplikationsoperatorMagnetbandlaufwerkSchlussregelÜberlagerung <Mathematik>Physikalischer EffektWorkstation <Musikinstrument>p-BlockKettenkomplexVerband <Mathematik>Prozess <Informatik>ZahlenbereichMinimalgradOrbit <Mathematik>HalbleiterspeicherPlastikkarteFacebookWellenpaketLesen <Datenverarbeitung>DezimalzahlStrömungsrichtungMathematikSchlüsselverwaltungInterrupt <Informatik>MereologieTotal <Mathematik>Computeranimation
22:35
Workstation <Musikinstrument>GraphBeschreibungskomplexitätFeasibility-StudieAggregatzustandSymmetrische MatrixOffene MengeDatenmodellUniformer RaumProtokoll <Datenverarbeitungssystem>Komplex <Algebra>GraphMultiplikationsoperatorAggregatzustandDemo <Programm>TelekommunikationPartitionsfunktionProgrammierungGRASS <Programm>Arithmetische FolgeStellenringCoxeter-Gruppe
Transkript: Englisch(automatisch erzeugt)
00:00
Hello everyone, I am Hiroto Asumi at Nain Institute of Science and Technology. Today, I'd like to talk about our research, uniform by passion in the population proton model with arbitrary communication graphs. First, let me introduce the population proton model. This is a model of multiple passively moving agents.
00:23
In this model, agents are uniform state machines. When two agents approach, they update their state by interaction. We'd look at this figure. Initially, there are many agents with state i. If two agents approach, interaction occurs between them.
00:41
And then, these agents update their states. In this case, they update their states from i to x. The population proton model has many application examples such as sensor networks to monitor wild birds and molecular robot networks. In the population proton model, there are many existing researches.
01:04
For example, they include reaction, counting, majority, and uniform by passion. In this research, we focus on the uniform by passion problem. From now, I explain uniform by passion problem.
01:20
All of the uniform by passion problem is to divide the population into two groups of the same size. And maintain the group after that. Please note that the difference is at most one between groups. Because if the number of agents is odd, it cannot be divided into two. Please look at this figure.
01:42
This is an example of the uniform by passion. Initially, all agents have state i. By executing the protocol for uniform by passion, eventually, agents are divided into two groups of the same size. Here, states r and b mean these agents belong to group red and these agents belong to group blue.
02:04
So three agents belong to group red and three agents belong to group blue. That is, each group contains the same number of agents. After that, these agents maintain this configuration.
02:21
The uniform by passion problem has some application. For example, we can assign a different task to each group and reduce energy consumption by switching only one group. Most existing works consider complete communication graphs. That is, all agents can interact with each other.
02:42
This is the image. In our research, we consider the uniform by passion problem in the condition where communication is restricted. That is, the communication graph is arbitrary. In arbitrary communication graphs, some pair of agents may not interact.
03:02
If there exists an edge between agents, they can interact. However, if there is no edge, agents cannot interact. From now, I will explain our results. We consider various assumptions such as space station, fairness, and symmetry.
03:20
I will explain these assumptions later. This table shows the minimum number of states to solve the uniform by passion. In previous results, the upper and lower bounds with complete graphs were clarified in many settings. In our results, we clarified the upper and lower bounds with arbitrary communication graphs in many settings.
03:45
I will explain the details of this table later. Now, I will explain our model. A protocol consists of a state set and a set of transients. A state set is a set of possible states for agents.
04:02
Transients are denoted by these. Which means that when an interaction occurs between an agent with state p and an agent with state q, they update their state to p' and q' respectively. This set of transients includes transients for each combination of states.
04:25
And we consider a protocol with arbitrarily connected graphs. That is, some pair of agents may not interact. In addition, we assume that every agent has the designated initial state.
04:42
From now, I explain other four assumptions. Each of the assumptions has two settings. We consider the problem for each setting. First, I explain the base station. We consider a protocol with a base station or without a base station. When we consider a protocol with a base station, we assume that a single base station exists in the population.
05:06
The base station is a special agent which is distinguishable from other agents and has a powerful capability. We do not care the number of states of the base station. So, the existence of the base station simplifies the design of protocols.
05:24
We assume that other agents are identical. When we consider a protocol without a base station, all agents are identical. Next, I will explain fairness. This is the assumption of induction patterns of agents.
05:41
We assume two types of fairness. One is global fairness. Another is weak fairness. In order to explain this fairness, first I will explain a configuration. A configuration is a global state of a population. In other words, it is a combination of states of all agents.
06:03
When an interaction happens between two agents, states of the agents transition. At that time, a configuration also transition. Now, I explain fairness. First, I explain global fairness. The global fairness guarantees that if a configuration C occurs infinitely often, every configuration disabled from C occurs infinitely often.
06:28
We wrote this figure. When A and B interact in this configuration, this configuration occurs. Similarly, when B and C interact in this configuration,
06:41
this configuration occurs. And when C and A interact in this configuration, then this configuration occurs. Now, under global fairness, if this configuration occurs infinitely often, all of them occurs infinitely often.
07:01
Next, I explain weak fairness. The weak fairness guarantees that interaction occurs infinitely often between each pair of agents if an edge exists between them. If this graph is given, then they interact infinitely often like this.
07:20
From now, I explain the difference between global fairness and weak fairness. We will cut this figure. If A and B interact at configuration C, the configuration transitions to C prime. If B and C interact at C prime, the configuration transitions to C double prime. And if C and A interact at C double prime, the configuration transitions to C again.
07:46
The weak fairness guarantees that interaction occurs infinitely often between each pair of agents if an edge exists between them. So, under weak fairness, agents may repeat these transitions forever and just C, C prime, and C double prime occur.
08:05
Thus, although this C-S is reachable from C, C-S may not occur under weak fairness. On the other hand, under global fairness, eventually C-S occurs. This is because if this C occurs infinitely often, every configuration reachable from C occurs infinitely often.
08:28
Next, I explain symmetry. We consider two types of protocols. One is a symmetric protocol. The other is a symmetric protocol. In symmetry protocols, if this transition exists, then this transition also exists.
08:47
In particular, if this transition exists, P prime equals Q prime holds. That is, if two agents in the same state interact, then they have to transition to the same state.
09:02
On the other hand, if a protocol is not symmetric, the protocol is asymmetric. So, in asymmetric protocols, if two agents in the same state interact, they can transition to the different states. Please look at the results again.
09:21
Please recall that this table shows a minimum number of states to solve the uniform by partition. In a model with no base station under global fairness, we show that with arbitrary communication graphs, four states are optimal for asymmetric protocols and five states are optimal for symmetric protocols.
09:45
With complete communication graphs, three states are optimal for asymmetric protocols and four states are optimal for symmetric protocols. So, one additional state enables problem solvability in arbitrary communication graphs in this setting.
10:01
Moreover, we show that under weak fairness, there is no asymmetric protocol that solves the problem with arbitrary communication graphs. Although just three states are sufficient in the same setting with complete communication graphs, in a model with a base station, we propose three protocols.
10:21
First one is three-state protocol under global fairness. Second one is 3p plus 1 state protocol under weak fairness, where p is the upper bound of the number of agents. These results yield identical upper bounds for both asymmetric and symmetric protocols.
10:44
Additionally, we also show a condition of communication graphs in which the number of states in the protocol can be reduced from 3p plus 1 to constant. This is it. If we assume communication graphs such that the length of every cycle in the graph is not a multiple of l,
11:04
we show that the number of states in the protocol can be reduced to 3l plus 1, where l is a positive integer at least 3. Next, I explain some proposed protocols.
11:21
First, I explain a three-state protocol with a base station under global fairness. The states are described like this. So, there exists three states, black, blue, and red. Initially, each agent has this black state. The idea is simple.
11:41
The base station just assigns red and blue alternatively to black agents like this. Since the graph is arbitrary, some agents cannot interact with the base station. If the base station cannot interact with black agents, the black state moves by interacting with red or blue agents like this.
12:07
So, since we assume global fairness, eventually all black agents are assigned red or blue by the base station. Moreover, after assignment, since there is no black agent, agents never change their color.
12:23
Therefore, these protocols solve the uniform bipartition under global fairness. Next, consider the case of weak fairness. This protocol does not work under weak fairness. This is because under weak fairness, black agents may not come next to the base station.
12:43
For example, black states go back and forth between two agents like this. In this case, this black state is not assigned a color. From now, I explain a 3p plus 1 state protocol under weak fairness with a base station.
13:05
This is the basic strategy of the protocol. Initially, all agents are black. Then, to assign red or blue by the base station, create a Spine3 rooted at the base station. After that, the base station assigns red and blue alternatively to agents.
13:26
Since the base station can assign a color only to neighbor agents, black states are carried in the direction of the base station. Eventually, all black states are assigned red or blue. In this way, the protocol works even under weak fairness.
13:42
This is because since there is a direction of the base station, all black states can be carried in the direction of the base station. And then, all agents can get red or blue. From now, I explain the details. First, I show preliminaries.
14:01
Agents have state variable, color, and depth. Variable color represents the color of agents. The color of Ini is black, R is red, and B is blue. Variable color is attached to Ini. Variable depth means how far the agent is from the base station.
14:24
Depth is attached to bottom. The states are described like this. If depth equals X and color equals Ini, the nodal color is black and X is described in this node. Similarly, if the color equals R, the nodal color is red, and if the color equals B, the nodal color is blue.
14:49
The base station is described like this. Now, I explain how to create a spanning tree. Initially, the depth of each agent is bottom. When agent A with bottom interacts with B, S depth becomes 1 if B is the base station.
15:06
This means the distance between the agent and the base station is 1. This is an example. When the base station and an agent with bottom interact, the bottom becomes 1.
15:22
When A and B interact, S depth becomes B's depth plus 1 if B's depth is not equal to bottom. This is an example. When an agent with 1 interacts with an agent with bottom, this agent transitions to 2.
15:42
Similarly, when an agent with 2 interacts with an agent with bottom, this agent transitions to 3. Then, eventually, the depth of each agent becomes a distance from the base station on 3. After creating a spanning tree, the base station assigns red and blue alternatively to black agents.
16:05
Concretely, when the base station interacts with an agent with depth equal to 1, the base station assigns a color to the agent. Please look at this execution example. They interact like this and this agent with depth equal to 1 gets a color.
16:25
After that, black states are carried in the direction of the base station. Concretely, when a black agent interacts with a red or blue agent with smaller depth, they exchange their color. For example, when a black agent with depth equal to 2 interacts with a red agent with depth equal to 1, they exchange their color.
16:48
Then, the base station can interact with the black agent. Since the black agent never changes its color, eventually the base station interacts with the agent. At that time, the base station assigns a color to the agent.
17:04
By repeating these behaviors, finally all agents are assigned colors red or blue and the uniform by-partition is completed. This is a long program of the protocol. This one is the base station.
17:22
First, distances from the base station are assigned. And then, the base station assigns red and blue to agents.
17:47
Now, the population is divided uniformly. Next, I show a protocol that works if we assume communication graphs such that the length of every cycle is not a multiple of L, where L is at least 3.
18:04
The protocol is 3L plus 1 state under weak fairness with the base station. Please recall that although the space complexity of the previous protocol depends on the number of agents, this protocol is constant space.
18:21
The strategy of the protocol is the same as the previous protocol. The difference is the domain of depth. In this protocol, the domain of depth is L. This is an example of L equals 3. In the protocol, depth is assigned 1, 2, 3, 1, 2, 3 like this.
18:41
And then, black states are carried in the direction of the base station 1, 2, 3, 3, 2, 2, 1, 2, 2, 1. And the base station assigns a color to the agent. However, if there is a cycle such that its length is a multiple of L, the protocol does not work.
19:02
This is the example. Since black states can be carried from 1, 2, 3, some black states may be repeating moving like this. And the base station cannot aware the black state. Finally, I explain a four-state protocol.
19:21
This protocol is asymmetric and works under global fairness with no base station. The difference between this protocol and the previous protocols is the existence of the base station. First, I show preliminaries. These are a set of agents.
19:42
All omega and all are red color and thus they belong to a red group. And b omega and b are blue color and thus they belong to a blue group. Moreover, these states are described like this. And let R omega be an initial state of agents.
20:04
Additionally, since there is no base station, all agents are identical. From now, I explain the details of the protocol. The key idea is to make blue agents by using two omegas. For example, if two agents with R omega interact, then one of them changes its color from red to blue and two omegas are deleted.
20:31
Similarly, if an agent with R omega interacts with an agent with b omega, red agents change its color to blue and two omegas are deleted.
20:42
Note that if two agents with b omega interact, they do not change their color because they are already blue. Since initially all agents have omega and their color is red, after all omegas are deleted by these transitions,
21:00
half of all agents become blue and other half of all agents keep red. Thus, the uniform by partition is completed. Please look at this figure. This is an execution example of the protocol. When these agents interact, they transition like this.
21:21
In a similar way, they interact and transition like this. Now, if they interact, one of them transitions to blue and the uniform by partition is completed. However, between them there is no edge, so they cannot interact. This means that we need additional transition rules that make omega moves on graphs.
21:45
More concretely, omega moves by an interaction if an agent has omega. For example, if an agent with omega interacts with an agent without omega, then omega moves like this. By these transition rules, omega can move freely on graphs and thus eventually two omegas meet.
22:06
Please look at this execution example. In this configuration, they cannot interact. However, they interact and omega moves like this.
22:21
Then finally two omegas interact and are deleted. By repeating such behavior, in any graphs, eventually all omegas are deleted and the uniform by partition is completed. This is a demo program of the protocol. Initially, all agents are red and have omega.
22:46
As agents interact repeatedly, omegas disappear and blue increases.
23:04
Eventually, all omegas are deleted and the population is divided uniformly like this. Finally, let me conclude. We consider the solubility for the uniform by partition with arbitrary communication graphs.
23:22
There are some open problems. One is the time complexity of the problem. Another is solubility with arbitrary initial states. This is all for my presentation. Thank you very much for watching.