Seminár z teoretickej informatiky - Rastislav Královič (14.10.2016)

v piatok 14.10.2016 o 11:00 hod. v miestnosti M/213

12. 10. 2016 12.37 hod.
Od: Rastislav Královič

Prednášajúci: Rasťo Královič

Názov: Zložitosť distribuovaného Wake-Up problému v hyperkockách a úplných grafoch

Termín: 14.10.2016, 11:00 hod., M/213

Abstrakt:
Often, in a distributed system, a task must be performed in which all entities must be involved; however only some of them are active, while the others are inactive, unaware of the new computation that has to take place.
In these situations, all entities must become active, a task known as WAKE-UP. Another typical occurrence of this problem, known also as RESET, is when some entities, upon detecting the occurrence of an anomalous condition, decide that the ongoing computation must be restarted. It is not difficult to see that BROADCAST is just the special case of the WAKE-UP problem, when there is only one initially active entity. In this paper we study the message complexity of performing a wake-up in hypercubes and in complete networks.

podľa článku: On the Complexity of Distributed Wake-Up, Stefan Dobrev, Rastislav Kralovic and Nicola Santoro, CANDAR 2016

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php