Mercredi 25 mars (Chairman : Achour Mostefaoui)

x 12:30 - 14:00 Déjeuner

x 14:00 - 14:45 Cyril Gavoille : Calculer les distances dans un graphe en

                               temps constant avec des étiquettes de 0.793n bits

x 14:45 - 15:30 Reut Levi : Constructing Near Spanning Trees with Few Local

                            Inspections

x 15:30 - 16:00 Pause café

x 16:00 - 16:45 Alessia Milani : An introduction to Software Transactional

                                 Memory

x 16:45 - 17:30 Matthieu Perrin : Update Consistency for Wait-free Concurrent

                                  Objects

x 19:00 - 20:00 Apéritif

x 20:00 - 22:00 Diner

Jeudi 26 mars (Chairman : David Ilcinkas)

x  9:00 -  9:45 Yves Métivier : A Distributed Enumeration Algorithm and

                           Applications to All Pairs Shortest Paths, Diameter...

x  9:45 - 10:30 Moti Medina : Best of Two Local Models: Local Centralized

                              and Local Distributed Algorithms

x 10:30 - 11:15 Paolo Penna : Logit Dynamics with Concurrent Updates

x 11:15 - 17:00 Ski / réunion de travail

x 19:00 - 20:00 Apéritif

x 20:00 - 22:00 Diner

Vendredi 27 mars (Chairman : Pierre Fraigniaud)

x  9:00 -  9:45 George Giakkoupis : Randomized mutual exclusion with constant

                                    amortized RMR complexity

x  9:45 - 10:30 Nicolas Hanusse: Peut-on router dans Internet avec des tables

                                  de routage d'au plus 5 entrées ?

x 10:30 - 11:00 Pause Café

x 11:00 - 11:45 Adrian Kosowski : Discrete Lotka-Volterra Population Protocols:

                                  Convergence, Majority Amplification, and

                                  Equity for Under-Represented Minorities

x 11:45 - 13:15 Déjeuner

------

Résumés:

Cyril Gavoille

Calculer les distances dans un graphe en temps constant avec des étiquettes de

0.793n bits.

Dans cet exposé je présenterai une structure de données compacte permettant de

calculer en temps constant la distance entre n'importe quelle paire de sommets

d'un graphe arbitraire à n sommets. Cette structure de données se présente sous

forme d'étiquette associée à chacun des sommets, la distance entre les u et v

étant décodée à partir d'un calcul impliquant seulement les étiquettes de u et

de v. La solution triviale, à l'aide d'un vecteur de distances de taille n,

produit des étiquettes de nlogn bits. En fait, aucune technique utilisant

o(nlogn) bits et décodant en temps constant n'est connue. Cependant, si on

relâche la contrainte du décodage en temps constant, des solutions avec O(n)

bits existent. Une des meilleures d'entres elles utilisent 11n bits pour un

décodage O(logn). Notre solution réduit la taille des étiquettes à 0.793n bits

avec un décodage constant et s'étend naturellement aux graphes valués.

Reut Levi

Constructing Near Spanning Trees with Few Local Inspections

Constructing a spanning tree of a graph is probably the most basic task in graph

theory.  Motivated by several recent studies of local graph algorithms, we

consider the following problem: given a connected bounded-degree graph $G$, can

one construct a connected subgraph $G'$ consisting of $n+o(n)$ edges, where

given an edge $e$, the algorithm should decide whether $e \in G'$ by inspecting

only a {\em constant} number of edges of $G$? Our main results are:

- We show that if every $t$-vertex subgraph of $G$ has expansion $1/(\log

t)^{1+o(1)}$ then one can (deterministically) construct a sparse spanning

subgraph $G'$ of $G$ using few inspections. To this end we analyze a ``local''

version of a famous minimum-weight spanning tree algorithm.

- We show that the above expansion requirement is sharp even when allowing

randomization.  To this end we construct a family of $3$-regular graphs of high

girth, in which every $t$-vertex subgraph has expansion $1/(\log t)^{1-o(1)}$.

Alessia Milani

An introduction to Software Transactional Memory

Software Transactional memory (or STM for short) is a promising programming

paradigm that aims at simplifying concurrent programming by using the notion of

a transaction.  A transaction executes a piece of code containing accesses to

data items which are shared by several processes in a concurrent setting.  By

using transactions, the programmer needs only enhance its sequential code with

invocations of special operations to read or write data items.  It is guaranteed

that if any operation of a transaction takes place, they all do, and that if

they do, they appear to other threads to do so atomically, as one indivisible

operation.

In this talk, I will present the STM paradigm and the main algorithmic

techniques to implement it.

Matthieu Perrin

Update Consistency for Wait-free Concurrent Objects

In large scale systems such as the Internet, replicating data is an essential

feature in order to provide availability and fault-tolerance. Attiya and Welch

proved that using strong consistency criteria such as atomicity is costly as

each operation may need an execution time linear with the latency of the

communication network. Weaker consistency criteria like causal consistency and

PRAM consistency do not ensure convergence. The different replicas are not

guaranteed to converge towards a unique state. Eventual consistency guarantees

that all replicas eventually converge when the participants stop

updating. However, it fails to fully specify the semantics of the operations on

shared objects and requires additional non-intuitive and error-prone distributed

specification techniques.

This talk will introduce and formalize a new consistency criterion, called

"update consistency", that requires the state of a replicated object to be

consistent with a linearization of all the updates. In other words, whereas

atomicity imposes a linearization of all of the operations, this criterion

imposes this only on updates. Consequently some read operations may return

out-dated values. Update consistency is stronger than eventual consistency, so

we can replace eventually consistent objects with update consistent ones in any

program. Finally, update consistency is universal, in the sense that any object

can be implemented under this criterion in a distributed system where any number

of nodes may crash.

Yves Métivier

A Distributed Enumeration Algorithm and Applications to All Pairs

Shortest Paths, Diameter...

We consider the standard message passing model; we assume the system is fully

synchronous: all processes start at the same time and time proceeds in

synchronised rounds. In each round each vertex can transmit a different message

of size $O(1)$ to each of its neighbours.  This paper proposes and analyses a

distributed enumeration algorithm of vertices of a graph having a distinguished

vertex which satisfies that two vertices with consecutive numbers are at

distance at most $3$.  We prove that its time complexity is $O(n)$ where $n$ is

the number of vertices of the graph.  Furthermore, the size of each message is

$O(1)$ thus its bit complexity is also $O(n).$ We provide some links between

this enumeration and Hamiltonian graphs from which we deduce that this

enumeration is optimal in the sense that there does not exist an enumeration

which satisfies that two vertices with consecutive numbers are at distance at

most $2$.

We deduce from this enumeration, algorithms which compute all pairs shortest

paths and the diameter with a time complexity and a bit complexity equal to

$O(n)$.  This improves the best known distributed algorithms (under the same

hypotheses) for computing all pairs shortest paths or the diameter presented by

Peleg, Roditty and Tal and and by Holzer and Wattenhofer having a time

complexity equal to $O(n)$ and which use messages of size $O(\log n)$ bits.

Moti Medina

Best of Two Local Models: Local Centralized and Local Distributed Algorithms

We consider two models of computation: centralized local algorithms and local

distributed algorithms. Algorithms in one model are adapted to the other model

to obtain improved algorithms.  Distributed vertex coloring is employed to

design improved centralized local algorithms for: maximal independent set,

maximal matching, and an approximation scheme for maximum (weighted) matching

over bounded degree graphs. The improvement is threefold: the algorithms are

deterministic, stateless, and the number of probes grows polynomially in log^∗n,

where n is the number of vertices of the input graph.  The recursive centralized

local improvement technique by Nguyen and Onak~\cite{onak2008} is employed to

obtain an improved distributed approximation scheme for maximum (weighted)

matching. The improvement is twofold: we reduce the number of rounds from O(log

n) to O(log^∗n) for a wide range of instances and, our algorithms are

deterministic rather than randomized.

Paolo Penna

Logit Dynamics with Concurrent Updates

In this talk I will discuss results on a family of noisy best-response dynamics

used to model players bounded rationality. In these dynamics, the higher the

payoff derived from a strategy the higher the probability that the player will

actually choose that strategy. For the class of potential games, the stationary

distribution has a simple closed formula (Blume '93,'97), which describes the

long term behavior of the system. This type of results is based on a particular

"schedule" of the player, that is, the process consists of selecting *one*

player uniformly at random for updating his/her strategy.

It is therefore natural to ask if the system behavior changes significantly when

a different "schedule" is adopted (still selected players update their

strategies according to the same noisy best response). In particular, in this

talk I will present an extreme case in which *all* players update their

strategies simultaneously (i.e. in parallel).

We shall see two results that relate this dynamics to the one introduced by

Blume:

(1) A certain reversibility condition of the process is equivalent to a class of

local interaction games, in which players are nodes of a "social" graph and they

play some potential game with each of the neighbors.

(2) Though the stationary distribution changes when considering parallel

updates, what we "observe" in the two dynamics is essentially the same if the

social graph is "close" to bipartite.

This is a joint work with Vincenzo Auletta, Diodato Ferraioli, Francesco

Pasquale, and Giuseppe Persiano.

George Giakkoupis

Randomized mutual exclusion with constant amortized RMR complexity

In this paper we settle an open question by determining the remote memory

reference (RMR) complexity of randomized mutual exclusion, on the distributed

shared memory model (DSM) with atomic registers, in a weak but natural (and

stronger than oblivious) adversary model. In particular, we present a mutual

exclusion algorithm that has constant expected amortized RMR complexity and is

deterministically deadlock free. Prior to this work, no randomized algorithm

with o(log n/ log log n) RMR complexity was known for the DSM model. Our

algorithm is fairly simple, and compares favorably with one by Bender and

Gilbert (FOCS 2011) for the CC model, which has expected amortized RMR

complexity O(log^2 log n) and provides only probabilistic deadlock freedom.

Nicolas Hanusse

Peut-on router dans Internet avec des tables de routage d'au plus 5 entrées ?

Les schémas de routage compact ont pour objectif de proposer des solutions de

routage avec des tables de routage de taille sous-linéaire par rapport au nombre

de routeurs N et garantissant des chemins de longueurs proches des plus courts

chemins. Le meilleur schéma de routage compact générique existant utilisent des

tables N^1/2 et garanti 3 fois les plus courts chemins. Nous proposons un schéma

de routage spécialisé pour les graphes sans-échelle qui sont représentatifs des

réseaux réels ainsi que sa construction distribuée. Pour une famille de graphes

aléatoires en loi de puissance, nous pouvons garantir des tables beaucoup plus

petites que le schéma générique sans détériorer significativement l'étirement

des routage. L'exposé indiquera la pertinence de notre schéma sur plusieurs

topologies.

Adrian Kosowski

Discrete Lotka-Volterra Population Protocols: Convergence, Majority Amplification, and Equity for Under-Represented Minorities

In this talk we consider a natural class of population protocols whose dynamics

are modelled by the discrete version of Lotka-Volterra equations. In such

protocols, when an agent $a$ of type (species) $i$ interacts with an agent $b$

of type (species) $j$ with $a$ as the initiator, then $b$'s type becomes $i$

with probability $P_{ij}$. In such an interaction, we think of $a$ as the

predator, $b$ as the prey, and the type of the prey is either converted to that

of the predator or stays as is. Such protocols capture the dynamics of some

opinion spreading models and generalize the well-known Rock-Paper-Scissors

discrete dynamics.

We start by considering the convergence time and show that any

Lotka-Volterra-type protocol on an $n$-agent population converges to some

absorbing state in time polynomial in $n$, w.h.p., when any pair of agents is

allowed to interact. By contrast, when the interaction graph is a star, even the

Rock-Paper-Scissors protocol requires exponential time to converge. We then

study threshold effects exhibited by Lotka-Volterra-type protocols with 3 and

more species under interactions between any pair of agents, giving examples of

protocols which achieve ``majority amplification'' and ``coin-flip consensus''

effects in a distributed system. Some of our techniques may be of independent

value.