|
Evènement pour le groupe Algorithmique Distribuée
Date | 2011-07-11 14:00-15:00 |
Titre | Dynamic Sharing of a Multiple Access Channel and its Online Analysis |
Résumé | We consider the mutual exclusion problem on a multiple access channel.
Mutual exclusion is one of the fundamental problems in distributed
computing. In the classic version of this problem, n processes perform
a concurrent program which occasionally triggers some of them to use
shared resources, such as memory, communication channel, device, etc.
The goal is to design a distributed algorithm to control entries and
exits to/from the shared resource in such a way that in any time there
is at most one process accessing it. We consider both the classic and
a slightly weaker version of mutual exclusion, called
ε-mutual-exclusion, where for each period of a process staying in the
critical section the probability that there is some other process in
the critical section is at most ε. We show that there are channel
settings, where the classic mutual exclusion is not feasible even for
randomized algorithms, while ε-mutual-exclusion is. In more relaxed
channel settings, we prove an exponential gap between the makespan
complexity of the classic mutual exclusion problem and its weaker
ε-exclusion version. We also show how to guarantee fairness of mutual
exclusion algorithms, i.e., that each process that wants to enter the
critical section will eventually succeed. In the online/competitive
analysis we consider the problem of serving queues of nodes wanting to
send packets over a shared channel so that maximum queue length stays
within constant factors from maximum queue length of an optimal
centralized algorithm.
This is joint work with Marcin Bienkowski, Tomasz Jurdzinski, Marek Klonowski, and
Dariusz Kowalski.
|
Lieu | s. 178 |
Orateur | Miroslaw Korzeniowski |
Email | kosowski@labri.fr |
Url | Wroclaw University of Technology, Poland |
Aucun document lié à cet événement. RetourRetour à l'index
| |