Dynamic & Radio Networks: Broadcasting with mobile agents in dynamic networks
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/52892 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
00:00
TabelleInhalt <Mathematik>GraphentheorieSchwach besetzte MatrixSymbolische DynamikDatennetzRechnernetzGraphTeilmengeUnendlichkeitFolge <Mathematik>CASE <Informatik>TeilgraphZusammenhängender GraphKonstanteGraphUntergruppeGruppenoperationDifferenteCASE <Informatik>Inverser LimesTeilgraphCoxeter-GruppeOffene MengeSoftwareSchwach besetzte MatrixSymbolische DynamikResultanteEndliche ModelltheorieUnrundheit
01:53
Auflösbare GruppeNetzwerktopologieEinfacher RingKnotenmengeTheoremGraphHypercubeHausdorff-DimensionKonfigurationsraumGerichteter GraphZahlenbereichCASE <Informatik>InformationKreisflächeGraphArithmetisches MittelSystemaufrufUnrundheitBildverstehenKlasse <Mathematik>MereologieDateiformatQuick-SortGruppenoperationMultiplikationsoperatorLeistung <Physik>Vollständiger VerbandMessage-PassingNeuroinformatikSoftwareBeobachtungsstudieSpielkonsoleDimensionsanalyseVirtuelle MaschineNummernsystemBildgebendes VerfahrenWorkstation <Musikinstrument>Analytische FortsetzungVererbungshierarchieOrtsoperatorComputersicherheitHypermediaKonforme AbbildungZusammenhängender GraphDemoszene <Programmierung>Serviceorientierte ArchitekturBenutzerschnittstellenverwaltungssystemKonfigurationsraumGemeinsamer SpeicherNichtlinearer OperatorDifferenteSpannweite <Stochastik>Algorithmische ProgrammierspracheÄhnlichkeitsgeometrieThumbnailDistributionenraumTeilmengeVarietät <Mathematik>DatensatzKonstanteTheoremMobiles InternetHypercubeSymbolische DynamikBroadcastingverfahrenEndliche ModelltheorieEinfacher RingGebundener ZustandAlgorithmusAuflösung <Mathematik>SchnittmengeFigurierte ZahlAbstandDatennetzResultanteAggregatzustandZweiKnotenmengeDynamisches SystemSchwach besetzte MatrixKugelkappeBitGraphentheorieDreiecksfreier GraphSummierbarkeitZahlensystemEinfach zusammenhängender RaumThetafunktionComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:01
Hi everyone, my name is Nikos Jauhoudis and I'm going to present to you a joint work with Santano Das, Laminea Lucio and Evripidis Markov. Our presentation consists of five main points, introduction, where we establish the problem and the model for our problem,
00:21
sparse graphs, grids, and tense graphs, where we discuss the results on those kinds of graphs, and finally, conclusion, where we sum everything up and give some open problems for further investigation. Introduction. Let's firstly talk about dynamic networks.
00:44
Dynamic networks are modeled by a graph G, which is called an underlined graph, and consists of all the available vertices and edges. In each round, some of the edges may be missing.
01:08
And with that way, we have each round a different spanning graph of the original graph G. In the worst case, each round, the adversary chooses which edges are missing,
01:27
but he must choose those edges in such a way that the available subgraph must be connected. That means that there is a limit to the edges that can be removed,
01:46
and that limit is at most M minus N minus one edges. Now that we have established what a dynamic network is, we can see the problem definition.
02:05
Essentially, there is a group of agents, and one of those agents has a specific message. And the goal is to broadcast that message to all agents. This can happen only when the agent, initially called the source, meets with another agent at a specific node.
02:29
Then and only then, they can exchange information, and actually the source can give the message to the other agent. From there, there are two agents with the message,
02:44
and in the same way, they can give that message to other agents by meeting them at specific nodes. Why is this an important problem to solve?
03:01
Well, first of all, because of the need to share information between many agents in various situations, and second of all, we can achieve collective computation with such a procedure, as well as reconstruct available data remotely. There is a wide range of studies related to this work.
03:22
Firstly, the broadcast problem has been studied in static networks. Secondly, in dynamic networks, similar problems have been studied in the message passing model. And thirdly, in dynamic networks with mobile agents, only a few problems have been studied,
03:43
namely exploration, gathering or patrolling, caps and rubber, and other problems with various restrictions on the dynamicity. Our contributions, in short, are the following. First of all, it is easy to see that in trees, the problem is solvable for any number of agents.
04:06
In rings, with five or more nodes, we need at least two agents that do not know the message in order to distribute successfully the information from the original source.
04:20
In cactus graphs, the number of agents needed is not a constant. In ladder graphs, if you imagine a ladder, we need at least as many agents as the number of steps on the ladder. In grids, we have the impossibility result of L-1 times W-1 ignored agents.
04:45
In complete graphs, the order of agents needed to solve the problem is big theta of N. And last but not least, in hypercubes, we need at least N over 2 minus 1 agents in order to solve the problem.
05:03
Let us define our model in which the broadcast problem is studied. We have a network modeled by a graph, there is a local orientation, which means that each port label is consistent and the graph is changing over time by having a subset of the initial set of edges,
05:25
but it must remain constantly connected, and we study the problem in a wide variety of different graphs, as you can see in the figure. On the one hand, the agents can see the whole graph as well as the positions of all other agents,
05:44
and they can distinguish which agents have the message or not. The position of each agent is initially distinct. On the other hand, the adversary can choose the initial configuration,
06:02
and he can choose how the graph evolves over time, respecting always the constantly connected restriction, and has full knowledge of the algorithm the agents are executing. Now that we have established our model under which the agents and the adversary are operating, let us discuss our results.
06:26
First things first, on the ring we have the following theorem, which states that if we have a large enough ring, we can solve broadcast with at least 2 ignorant agents,
06:41
but when the ring is smaller, we can solve it with just 1 ignorant agent. As you can see in figure 2, we have 3 different cases for the ring, from left to right. The first case is when we have a large enough ring and there is only 1 ignorant agent. In this particular situation, there is no way that the agents can move without the adversary,
07:08
preventing them from exchanging the message. At first, the path of distance 2 will be disconnected, and if the agents try to move from the other path, then the adversary can remove one edge from that path, leaving the other path connected.
07:26
In the middle case, with 2 ignorant agents, there is no way the adversary can prevent the distribution of the message. The agents will approach from different sides, and one of them will meet the source.
07:44
Now the roles have changed, and the 2 agents that have the message will surround the remaining ignorant agent, effectively solving the problem. For the last case, we can easily see that there is always a path of distance at most 2,
08:01
and therefore the adversary is not able to prevent the agents from distributing the message. For the cactus graphs, we have the following definition. A cactus graph is a connected graph in which any 2 simple cycles have at most 1 node in common.
08:24
And the main theorem states that the number of agents needed is dependent on the number of big and small circles. Specifically, if there are no big circles, then we need at least as much ignorant agents as the number of circles.
08:43
If there are big circles, then we need at least the sum of circles plus 1 ignorant agents in order to solve the problem. Let us divide this problem into 2 smaller ones. We first consider a case of a cactus with only small circles. As you can see in this figure, there are just enough agents in order to solve the problem.
09:06
The reason is that with 3 ignorant agents, there will always be 1 agent that can move from ring to ring, distributing information where is needed. However, if there are only 2 ignorant agents, then every agent can be trapped in a circle and no one will ever meet any other agent.
09:28
For the case of big circles, as you can see, 3 ignorant agents are not enough, because the source can never meet with any ignorant agent. We need at least one more in order to get 2 ignorant agents in the same circle as the source.
09:46
That way we can follow the same principle as in rings to distribute the message. Let's now talk about grids. For the case of the ladder, that is a grid with 2 rows and l columns, we have 2 main theorems.
10:05
It is evident that there is a gap between the lower and the upper bound of the problem. There is no algorithm that solves the problem with less than l-1 ignorant agents, and we give an algorithm with at least l agents.
10:21
Let us discuss the results with some examples. On the left, the problem is not solvable. The idea is that there is always a column on the ladder which is unoccupied. The adversary will keep that vertical edge active and remove the other ones, preventing the agents from distributing the message.
10:43
On the right, we have the solvable case, and the idea of the algorithm is that there is always a set of moves that can move the ignorant agents closer to the source, maintaining their original formation and their general formation.
11:02
For example, it is easy to see that in this particular case, the best the adversary can do is to have an active path of distance at least 3. However, after the agents move, there will be no such path and they will solve the problem gradually by one agent
11:30
meeting on the next round of the source, and from there they can distribute the message to the other agents collaboratively.
11:42
In a general grid, we have the impossibility result that the broadcast problem is not solvable with less than l-1 times w-1 ignorant agents, where l and w is the number of columns and rows respectively. The result can be extended in a d-plus-one-dimensional grid, and there is no algorithm yet that solves the problem in a general grid cage.
12:11
Let us now move to dense graphs. For the case of a complete graph, we need at least n-2 agents in order to solve the problem.
12:24
As you can see in the figure, we do not have enough agents, and the adversary can always pick as an active path a path of distance at least 3. If we had two more agents, then there will be no such path, and we can solve the problem by gradually distributing the message from agent to agent.
12:47
For the hypercube, we can imagine in three dimensions a cube, with each vertex labeled as a binary number, consisting of three bits. Then we can expand this into higher dimensions. We need at least n-2-1 ignorant agents in order to solve the problem.
13:11
Let us observe what happens for the case of a three-dimensional hypercube. For the possibility result, there is actually a set of configurations where the problem is not solvable.
13:25
In fact, the adversary can choose the active edges in such a way that the agents can only change their configuration to another configuration inside that set. Thus, there is no available moves in order to solve the problem.
13:42
On the other side, we have an algorithm that can solve the problem using four ignorant agents and a source. Here we need a different notation for each configuration. u0 is the node where the source resides, and then the superscript tells us how many steps away from u0 its particular node is.
14:07
As you can see, there are a number of configurations from which the broadcast problem is solvable after a constant number of rounds. shown in the possible configurations.
14:22
The agents from such configurations can form such configurations from any initial configuration, effectively solving the problem no matter which edges the adversary choose to be active or not. Conclusion To sum up, we studied the problem of broadcast on constantly connected dynamic graphs.
14:48
We focused on finding the number of agents which is necessary and sufficient in order to solve the problem on a wide variety of graphs. We have shown that in sparse graphs the number of agents is independent of the network size,
15:06
and in denser graphs the number of agents needed is of the order of big data when. For some open problems, we have the gap for the grids and hypercubes on the lower and upper bound.
15:22
We could use these techniques to solve other problems in dynamic graphs, we could classify other problems based on their resources needed, and we could change the assumption of global visibility for the agents partially or totally.
15:41
Thank you for your time.