~~NOCACHE~~
/* DO NOT EDIT THIS FILE             */

[[seminaires:distribue:index|Calcul distribué]]\\
Mardi 12 décembre 2017, 14 heures, Salle 3052\\
**Jean Krivine** (IRIF) //Incremental Update for Graph Rewriting//
<button type="link" size="xs" collapse="b19-3515">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b19-3515" collapsed="true">
<well size="sm">
Graph rewriting formalisms are well-established models for the representation of biological systems such as protein-protein interaction networks. The combinatorial complexity of these models usually prevents any explicit representation of the variables of the system, and one has to rely on stochastic simulations in order to sample the possible trajectories of the underlying Markov chain. The bottleneck of stochastic simulation algorithms is the update of the propensity function that describes the probability that a given rule is to be applied next. In this talk we present an algorithm based on a data structure, called extension basis, that can be used to update the counts of predefined graph observables after a rule of the model has been applied. 

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg
</well>
</collapse>


[[seminaires:distribue:index|Calcul distribué]]\\
Mardi 14 novembre 2017, 14 heures, Salle 3052\\
**Laurent Massoulié** (MSR-Inria) //Rapid Mixing of Local Graph Dynamics//
<button type="link" size="xs" collapse="b19-3516">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b19-3516" collapsed="true">
<well size="sm">
Graph dynamics arise naturally in many contexts. For instance in 
peer-to-peer networks, a participating peer may replace an existing 
connection with one neighbour by a new connection with a neighbour's 
neighbour. Several such local rewiring rules have been proposed to ensure 
that peer-to-peer networks achieve good connectivity properties (e.g. high 
expansion) in equilibrium. However it has remained an open question whether 
there existed such rules that also led to fast convergence to equilibrium.
In this work we provide an affirmative answer: We exhibit a local rewiring 
rule that converges to equilibrium after each participating node has 
undergone only a number of rewirings that is poly-logarithmic in the system 
size. The proof involves consideration of the whole isoperimetric profile of 
the graph, and may be of independent interest.

This is joint work with Rémi Varloot.
</well>
</collapse>
Séminaire de Pôle

[[seminaires:distribue:index|Calcul distribué]]\\
Mardi 17 octobre 2017, 14 heures, Salle 3052\\
**Claire Mathieu** (DI - ENS) //Online k-compaction//
<button type="link" size="xs" collapse="b19-3517">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b19-3517" collapsed="true">
<well size="sm">
Given, at each time t = 1, 2, …, n, a new file of length l(t) and a read rate r(t), an
online k-compaction algorithm must maintain a collection of at most k files, choosing (at each time t, without knowing future inputs) some of the files to merge into one, thereby incurring a merge cost equal to the total length of the merged files and a read cost equal to the read rate r(t) times the number of files present at time t. The goal is to minimize the total cost over time. K-compaction algorithms are a key component of log-structured merge trees, the file-based data structure underlying NoSQL databases such as Accumulo, Bigtable, Cassandra, HBase,and others. We initiate the theoretical study of k-compaction algorithms. We formalize the problem, consider worst-case, average-case and competitive analysis (per-instance optimality), and propose new algorithms that are optimal according to these metrics. 

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.
</well>
</collapse>