 |
Information dynamics of cooperative stochastic networks - design and analysis
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
121107 |
| Type |
PD |
| Principal investigator |
Gerencsér, Balázs |
| Title in Hungarian |
Információterjedés együttműködő sztochasztikus hálózatokon - tervezés és vizsgálat |
| Title in English |
Information dynamics of cooperative stochastic networks - design and analysis |
| Keywords in Hungarian |
sztochasztikus hálózatok, információgyűjtés, csatorna korlátozások |
| Keywords in English |
stochastic networks, information aggregation, channel constraints |
| Discipline |
| Mathematics (Council of Physical Sciences) | 100 % | | Ortelius classification: Probability theory |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Alfréd Rényi Institute of Mathematics |
| Starting date |
2016-10-01 |
| Closing date |
2019-09-30 |
| Funding (in million HUF) |
15.090 |
| FTE (full time equivalent) |
2.10 |
| state |
closed project |
Summary in Hungarian A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A kutatás középpontjában olyan algoritmusok állnak, amelyek egy gráf csúcsain megjelenő kezdeti értékek átlagának számítását végzik. Ezt a világos matematikai problémát számos alkalmazási terület motiválja, pl. szenzor hálózatok, telekommunikáció, pénzügyi hálózatok illetve konszenzus kialakítás.
A kiindulási alap ezeknek az az algoritmusoknak a Markov-láncos interpretációja, ahol az utóbbi keverési ideje az átlagolás sebességének felel meg. Több korábbi meglepő eredmény alapján indokoltnak tűnik, hogy kilépjünk a kényelmesen kezelhető, erős szimmetriával rendelkező reverzibilis Markov-láncok világából. Vannak olyan konkrét hálózatok, ahol a keverési idő gyorsulására vonatkozó, empirikusan tesztelt sejtést kell bizonyítani. Másrészt keresünk olyan új konstrukciókat, amelyek kivezetnek a reverzibilis lehetőségek világából, ugyanakkor keverés szempontjából jobban teljesítenek.
További cél kommunikációs csatornákat jellemző egyéb feltételek kezelésére új algoritmusok kidolgozása és vizsgálata. Speciálisan aszinkron csatornák esetén az ún. push-sum algoritmus megoldást nyújt, amelynek konvergenciája bizonyított. Új kihívás az algoritmus konvergenciájának a vizsgálata akkor, amikor csomagvesztés is várható. Amennyiben a kommunikációt zaj terheli, hibatűrő megoldásokat kell kidolgozni.
Az átlagoló struktúrák explicit konstruálása mellett önszerveződő hálózatok kezelése is a kutatási céljaink közé tartozik. Átlagoló eljárások online/adaptív kialakítása önmagában is izgalmas kihívás. Jelen projektben azt vizsgáljuk, hogy kommunikációs korlátok mellett ezt hogyan lehet hatékonyan megvalósítani.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A kutatás fő témája különböző forrásokból származó információk összegzése, átlagolása, aggregálása esetleg extrapolálása. A tudomány világában általánosan elterjedt és letisztult vélemény, hogy erre elosztott megoldást kell találni, ahol nem egyetlen központ irányításán és számítási kapacitásán múlik a működés, hanem az lokális kommunikáció és együttműködés segítségével zajlik.
A kutatás alapvető célja ennek a koncepciónak a hatékony megvalósítása úgy, hogy a kommunikációs csatornák korlátait (csomagvesztés, zajos adatok, aszinkron csomagkezelés) is figyelembe vesszük.
Ez a cél a követező alapkérdésekben fogható meg:
Egy standard átlagoló algoritmus megfeleltethető egy Markov láncnak. Mit nyerhetünk hatékonyságban, ha elengedjük a szimmetria standard, technikai elemzés szempontjából kényelmes feltevését?
Egy aszinkron kommunikációs hálózatban az ún. push-sum algoritmus megvalósítja az átlagolást. Milyen hiba várható, ha csomagvesztések is történhetnek? Mit tudunk módosítani az algoritmuson, hogy a csomagvesztés jelenségét jobban kezelje?
Mit tegyünk, ha a kommunikációt zaj terheli, de hibatűrő megoldást szeretnénk?
Hogyan tudjuk előzetes, külsőleg meghatározott paraméterek használata helyett a hálózatban önszerveződő módon kialakítani az átlagolás folyamatát?
A kutatás során ezen kérdések matematikai vetületével foglalkozunk. Pontosan megfogalmazott tételek segítségével olyan eredményekre jutunk, amik biztos alapként szolgálhatnak későbbi algoritmusok kidolgozásához. Ezt kiegészítik experimentális/szimulációs vizsgálatok, amelyekkel megbízható sejtéseket tudunk megfogalmazni, illetve amelyek segítik a későbbi kutatások irányvonalát kijelölni.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
Az alapkutatások tekintetében az egyik lényeges szempont a nem-reverzibilis Markov-láncok kezelhetőségében tervezett előrelépés. A keverési hatékonyság szempontjából ez egy ígéretes folyamatosztály, ahol még további elméleti eszközök kiépítésére van szükség. Az elméleti és kísérleti eredményektől azt is várjuk, hogy figyelemfelkeltő hatása lesz, és ezek a lehetőségek beépülnek új algoritmusok/folyamatok osztályába. A kutatás várható eredménye lesz továbbá számos algoritmus új variánsának megalkotása, amik bővítik a kutatók eszközkészletét, így az újonnan vizsgált hálózati problémákra precízebben illesztett megoldásokat tudnak választani.
A kutatási tervben kifejtett módon a vizsgált témák részét képezik több, jelenleg is aktív hálózat kialakításának (szenzorhálózatok, okosvárosok). Mindezek működésének egy fontos eleme a hálózat pontjain elérhető adatok összesítése az éppen adott kommunikációs lehetőségek szerint. A kutatás során hatékonyabb és pontosabb algoritmusokat keresünk erre az elosztott átlagolási feladatra. Az itt elért felfedezések visszacsatolva a kérdéseket motiváló rendszerekbe jelentős előrelépést jelenthetnek azok megbízható és hatékony működésében.
A projekt egyediségét az adja, hogy hidat teremt itthon már futó kutatási tevékenységek között. Számos mérnöki csoport foglalkozik kommunikációs hálózatokkal, ezekhez jól illeszkedik egy kapcsolódó, precízen véghezvitt matematikai kutatás. Másfelől, erős valószínűségszámítással foglalkozó csoportok számára értékes lehet, ha az alkalmazásokból közvetlenül adódó kérdések kerülnek fel a kutatási palettára.
A pályázat erőssége abban áll, hogy a kutató matematikai képzettségét és számítógépes jártasságát hatékonyan tudja ötvözni a felvetett témák kutatására, ügyelve arra is, hogy szem elől ne tévessze az eredetileg kitűzött kérdést. Az erős nemzetközi kapcsolatok (UCL, MIT) lehetővé teszik, hogy a kutató folyamatosan tájékozott legyen a tematikával kapcsolatban történő fejleményekkel.
A kutatási kérdések aktualitását és relevanciáját már az is igazolja, hogy egy részüket olyan fajsúlyú kutatók, mint Asuman Ozdaglar (MIT) illetve Itai Benjamini (Weizmann Institute) javasolták.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A kutatás központjában olyan témával foglalkozunk, ami mind gyakrabban előbukkan például szenzorhálózatok, pénzügyi rendszerek, "okos városok" témakörében. Az ismétlődő feladat a következő: sok, különböző helyről származó adatot kell a hálózatnak összesítenie. Ennek a feladatnak a kezelésénél kritikust szempont a hatékony és a kommunikációs problémákra nézve hibatűrő megoldás meghatározása.
A hatékonyság céljából továbblépünk az elterjedt, szimmetrikus sémákhoz képest, amelyek viselkedését és korlátait már jól ismerjük. Az aszimmetrikus megoldásokat ugyan kevésbé értjük, szimulációk már sejtetik, hogy lényegesen gyorsabb módszerek várhatóak, és érdemes ezeket jobban megvizsgálni.
A hibatűrés céljából kezelni fogjuk a pontatlan mérések, rosszul időzített vagy elveszett üzenetek lehetőségét. Számos, már létező algoritmusnál nem ismert annak hatása, ha ilyen hibák bekövetkeznek. Ezek megértésén túl szeretnénk az ismert módszereket továbbfejleszteni, hogy pontosságban és hatékonyságban előnyösebbek legyenek ilyen valós helyzetekben való alkalmazásra.
Elképzelhető egy hálózatban, hogy nem tudjuk előre meghatározni ennek az információkat összesítő folyamatnak a paramétereit. Erre az esetre foglalkozunk olyan megoldásokkal, ahol a szereplők maguk tudják beállítani ezeket a változókat. Megvizsgáljuk, hogy ezek a lehetőségek hatékonyságban és hibatűrésben hogyan teljesítenek, és hogyan viszonyulnak az előző esetekhez, ahol a folyamat explicit volt meghatározva.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The central theme of the research is about algorithms which compute the average of initial values appearing on the nodes of a graph. This is a well defined mathematical problem, which in turn is motivated by several applications, including sensor networks, telecommunication, financial networks, or consensus seeking.
The starting point is interpreting Markov-chains, where the mixing time quantifies the efficiency of this averaging. We plan to leave the comfortable domain of reversible Markov-chains with strongly symmetric structure, to design promising and more effective variants. There are specific cases where the conjecture of speedup is already tested, and the analytic proof is to be found. In other cases, starting from a reversible Markov-chain, we want to find modified versions which might not be reversible any more, but in terms of the initial goal, mixing efficiency, perform better.
A further goal is the treatment of communication constraints. The so-called push-sum algorithm is designed to tackle the issue of asynchronous communications. We analyze this algorithm when packet drops are also expected to happen. Afterwards, we plan to improve the algorithm to handle this constraint by itself.
If communication noise is present, it is necessary to find robust solutions. Our aim is to prove stability for this case and to construct more general algorithms based on the available ones.
Not only we want to treat the cases where an explicit construction is possible, but also to include the option of self-organizing networks. Setting up the averaging process online is challenging by itself, we now want to incorporate the communication constraints mentioned above.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
The main theme of the research is the integration of information from several sources. It is already standard in research communities to handle such situations using distributed methods, where the solution does not depend on a single central entity, but is solved using local communication and cooperation.
The principal goal of the research is to realize this in an efficient way, also in the presence of communication constraints (packet drops, noise, asynchronous communication).
This goal can be phrased by the following questions:
A standard averaging algorithm can be interpreted as a Markov-chain. What can we gain in terms of efficiency if we allow to drop the symmetry restriction of reversibility?
In an asynchronous communication network the push-sum algorithm performs the averaging. What error do we expect when packet drops are also possible? How can we modify the algorithm to handle this restriction by itself?
What can we do in the presence of communication noise but when we need a robust algorithm?
Instead of externally setting the parameters of the averaging algorithm, how can we ensure this calibration to happen in a distributed manner?
In the research we focus on the mathematical aspects of the questions mentioned. We hope that the precisely stated theorems and analytic proofs provide results that can serve as a starting point for further research. This is complemented by experimental and simulation work which help to phrase reasonable conjectures and serve as a lead for future research directions.
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
In the view of fundamental research one of the key aspects is the development of tools to handle non-reversible Markov-chains. For mixing efficiency, this is a promising class, where it is still important to improve the theoretical tools. We also expect to raise awareness, both by the proofs and also by the convincing simulations, so that this class becomes the part of the routinely used tool-set. The research also produces several variants of existing algorithms, to extend the possibilities of fellow researchers when tailoring them for other problems related to network studies.
As detailed in the research plan, the problems studies are present in multiple networks active today (sensor networks, smart cities, etc.) An important step during their operation is the aggregation of data present at different nodes of the network, using the communication channel available. In the research project we seek for more efficient and more precise algorithms for the task of distributed averaging. After all, the results obtained can be implemented in the motivating applications to let them advance in terms of reliability and usability.
The special feature of the project is the connection it induces between research activities already present in Hungary. Multiple engineering groups put considerable effort on network research, where fundamental mathematical research activity can be an important supplement. On the other hand, strong probability theory groups might benefit if problems directly motivated by applications are included in their research activity.
The strength of the research project is due to the researcher being able to use both his mathematical qualifications and computer skills to tackle the problems proposed, while making sure not to lose track of the original topics. Strong international connections (UCL, MIT) make it possible to be up-to-date on the advances happening for the research topics.
The actuality and relevance of the research questions is justified knowing that some of them have been proposed by top researchers like Asuman Ozdaglar (MIT) and Itai Benjamini (Weizmann Institute).
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
During this research we work on a topic that we face over and over again when treating sensor networks, financial networks, smart cities. The task is the following: given a collection of data from various points, it needs to be aggregated by the network. The critical aspect is to solve this in an efficient but also robust manner.
To improve efficiency, we need to step further from the usual symmetric schemes, which are already well understood. It is harder to deal with the asymmetric variants, but simulations already suggest that considerably faster methods are to be expected, and it is important to have a closer look.
For robustness, we plan to handle the possibilities of measurement noise, asynchronous communication or lost messages. For a number of existing algorithms, the effect of such constraints are not yet known. In addition to understanding these cases, we plan to improve these methods to make them more efficient and precise in these realistic situations.
It might be the case in a network that we cannot set up all the parameters externally and in advance. For this setting, we work on solutions where the nodes of the network can set these variables by themselves. We investigate the performance of such algorithms in terms of efficiency and robustness, and compare with the other methods treated before.
|
|
|
|
|
|
|
|
|
|
