@INPROCEEDINGS{LeFessant2009f,
author = {Stevens {Le Blond} and Fabrice {Le Fessant} and Erwan {Le Merrer}},
title = {Finding Good Partners in Availability-aware P2P Networks},
booktitle = {International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'09)},
year = {2009},
month = {Nov},
url = {http://fabrice.lefessant.net/papers/sss2009.pdf},
abstract = {We study the problem of finding peers matching a given availability pattern
in a peer-to-peer (P2P) system.
Motivated by practical examples, we specify two formal problems of
availability matching that arise in real applications: disconnection
matching, where peers look for partners expected to disconnect at the
same time, and presence matching, where peers look for partners
expected to be online simultaneously in the future.
As a scalable and inexpensive solution, we propose to use epidemic protocols
for topology management; we provide corresponding metrics for
both matching problems.
We evaluated this solution by simulating two P2P applications, task
scheduling and file storage, over a new trace of the eDonkey network,
the largest available with availability information.
We first proved the existence of regularity patterns in the sessions of
14M peers over 27 days.
We also showed that, using only 7 days of history, a simple predictor could
select predictable peers and successfully predicted their online periods for
the next week.
Finally, simulations showed that our simple solution provided good
partners fast enough to match the needs of both applications, and that
consequently, these applications performed as efficiently at a much lower
cost.
We believe that this work will be useful for many P2P applications for
which it has been shown that choosing good partners, based on their
availability, drastically improves their performance and stability.
}
}
@INPROCEEDINGS{LeFessant2009e,
author = {Anthonis Papadimitriou and Fabrice {Le Fessant} and Aline {Carneiro Viana} and Cigdem Sengul},
title = {Cryptographic Protocols to Fight Sinkhole Attacks on Tree-based Routing in Wireless Sensor Networks},
booktitle = {Workshop on Secure Network Protocols (NPSec'09)},
year = {2009},
month = {Oct},
url = {http://fabrice.lefessant.net/papers/npsec2009.pdf},
abstract = {This work focuses on: (1) understanding the impact of sinkhole
attacks on tree-based routing topologies in Wireless Sensor Networks
(WSNs), and (2) investigating cryptography-based strategies to
limit network degradation caused by these attacks. This work is
particularly important as WSN protocols that construct a fixed
routing topology may be significantly affected by malicious
attacks. Furthermore, considering networks deployed in a difficult
to access geographical region, building up resilience against such
attacks rather than detection is expected to be more beneficial. We
thus first provide a simulation study on the impact of malicious
attacks based on a diverse set of parameters, such as the network
scale and the position and number of malicious nodes. Based on this
study, we propose a single but very representative metric for
describing this impact. Second, we present the novel design and
evaluation of two simple and resilient topology-based
reconfiguration protocols that broadcasts cryptographic values. The
results of our simulation study show that our reconfiguration
protocols are practical and effective in improving resilience
against sinkhole attacks, even in the presence of some collusion.
}
}
@INPROCEEDINGS{LeFessant2009d,
author = {Stevens {Le Blond} and Fabrice {Le Fessant} and Erwan {Le Merrer}},
title = {Choix de partenaires en P2P suivant des critères de disponibilité},
booktitle = {Conférence Française sur les Systèmes d'Exploitation (CFSE'09)},
year = {2009},
month = {Sep},
url = {http://fabrice.lefessant.net/papers/cfse2009.pdf},
abstract = {Nous étudions la problématique de recherche distribuée de pairs correspondant
à un motif de disponibilité donné, dans un système pair-à-pair (P2P).
Motivés par des exemples concrets, nous spécifions deux problèmes formels
de correspondance de disponibilité qui apparaissent dans des
applications réelles: la {\em correspondance de déconnexion}, où les
pairs cherchent des partenaires dont la déconnexion coïncide avec la leur,
et la {\em correspondance de présence}, où les pairs cherchent
des partenaires connectés en même temps qu'eux dans le futur.
Nous proposons, comme solution peu coûteuse et passant à l'échelle,
l'utilisation de protocoles épidémiques pour la gestion
de la topologie du réseau logique (comme le protocole T-Man); des
métriques adéquates sont
fournies pour les deux problèmes de correspondance.
Notre solution a été évaluée en simulant deux applications P2P, l'{\em
ordonnancement de tâches} et le {\em stockage de fichiers}, sur une
trace inédite d'eDonkey, la plus grande fournissant
les informations de disponibilité des pairs. Nous prouvons tout d'abord
l'existence de motifs réguliers dans les sessions de 14M de pairs sur
27 jours. Nous montrons également, en utilisant 7 jours d'historique,
qu'un prédicteur simple peut sélectionner des pairs prédictibles, pour
prédire avec succès leur période de présence en ligne pour la
semaine suivante. Enfin, les simulations ont montré que notre solution
simple a fourni rapidement de bons partenaires afin de répondre au
besoin des deux applications, et ainsi de leur permettre de s'exécuter
aussi efficacement à un coût bien inférieur.
Nous pensons que ce travail sera utile pour beaucoup d'applications
P2P, pour lesquelles il a été montré que choisir ses partenaires, en se basant
sur leur disponibilité, améliore de façon conséquente les performances
du système.
}
}
@INPROCEEDINGS{LeFessant2009c,
author = {Samuel Bernard and Fabrice {Le Fessant}},
title = {Optimizing Peer-to-Peer Backup using Lifetime Estimations},
booktitle = {International Workshop on Data Management in Peer-to-Peer Systems (Damap'09)},
year = {2009},
month = {Mar},
url = {http://fabrice.lefessant.net/papers/damap2009.pdf},
abstract = {In this paper, we study the viability of a peer-to-peer backup
system on nowadays internet connections. In particular, we
show that peer lifetime estimation can be used to reduce the
maintenance cost of peer-to-peer backup. Previous studies
have shown that lifetimes in a peer-to-peer system follow
a Pareto distribution. Consequently, peers can be sorted
on their expected lifetimes, depending only on the length
of their history in the system. By carefully selecting the
peers on which backup data is stored, repairing cost can be
highly reduced for long-term backup users, while it is still
acceptable for new users. The efficiency of this technique is
evaluated through simulations of a state-of-the-art peer-to-
peer backup system.}
}
@TECHREPORT{LeFessant2009b,
title = {{F}ighting {S}inkhole {A}ttacks in {T}ree-based {R}outing {T}opologies},
author = {{P}apadimitriou, {A}nthonis and {L}e {F}essant, {F}abrice and {C}arneiro {V}iana, {A}line and {S}engul, {C}igdem},
abstract = {{T}his work focuses on: (1) understanding the impact of sinkhole attacks on tree-based routing topologies in {W}ireless {S}ensor {N}etworks ({WSN}s), and (2) investigating cryptography-based strategies to limit network degradation caused by these attacks. {T}his work is particularly important as {WSN} protocols that construct a fixed routing topology may be significantly affected by malicious attacks. {F}urthermore, considering networks deployed in a difficult to access geographical region, building up resilience against such attacks rather than detection is expected to be more beneficial. {W}e thus first provide a simulation study on the impact of malicious attacks based on a diverse set of parameters, such as the network scale and the position and number of malicious nodes. {B}ased on this study, we propose a single but very representative metric for describing this impact. {S}econd, we present the novel design and evaluation of two \emph{simple and resilient} topology-based reconfiguration protocols that broadcasts cryptographic values. {T}he results of our simulation study show that our reconfiguration protocols are practical and effective in improving resilience against sinkhole attacks, even in the presence of some collusion.},
keywords = {wireless sensor network, sinkhole attacks, resilience, tree-based routing protocols},
language = {{A}nglais},
affiliation = {{ASAP} - {INRIA} {S}aclay - {I}le de {F}rance - {INRIA} - {CNRS} : {UMR} - {INSA} - {I}nstitut {N}ational des {S}ciences {A}ppliqu{\'e}es - {U}niversit{\'e} de {R}ennes 1 },
pages = {24 },
type = {Research Report},
institution = {INRIA},
number = {{RR}-6811},
year = {2009},
url = {http://hal.inria.fr/inria-00355873/en/}
}
@TECHREPORT{LeFessant2009a,
title = {{F}inding {G}ood {P}artners in {A}vailability-aware {P}2{P} {N}etworks},
author = {{L}e {B}lond, {S}tevens and {L}e {F}essant, {F}abrice and {L}e {M}errer, {E}rwan},
abstract = {{I}n this paper, we study the problem of finding peers matching a given availability pattern in a peer-to-peer ({P}2{P}) system. {W}e first prove the existence of such patterns in a new trace of the e{D}onkey network, containing the sessions of 14{M} peers over 27 days. {W}e also show that, using only 7 days of history, a simple predictor can select predictable peers and successfully predict their online periods for the next week. {T}hen, motivated by practical examples, we specify two formal problems of availability matching that arise in real applications: disconnection matching, where peers look for partners expected to disconnect at the same time, and presence matching, where peers look for partners expected to be online simultaneously in the future. {A}s a scalable and inexpensive solution, we propose to use epidemic protocols for topology management, such as {T}-{M}an; we provide corresponding metrics for both matching problems. {F}inally, we evaluated this solution by simulating two {P}2{P} applications over our real trace: task scheduling and file storage. {S}imulations showed that our simple solution provided good partners fast enough to match the needs of both applications, and that consequently, these applications performed as efficiently at a much lower cost. {W}e believe that this work will be useful for many {P}2{P} applications for which it has been shown that choosing good partners, based on their availability, drastically improves their efficiency.},
language = {{A}nglais},
affiliation = {{PLANETE} - {INRIA} {S}ophia {A}ntipolis / {INRIA} {R}h{\^o}ne-{A}lpes - {INRIA} - {ASAP} - {INRIA} {S}aclay - {I}le de {F}rance - {INRIA} - {CNRS} : {UMR} - {INSA} - {I}nstitut {N}ational des {S}ciences {A}ppliqu{\'e}es - {U}niversit{\'e} de {R}ennes 1 - {ASAP} - {INRIA} - {IRISA} - {CNRS} : {UMR}6074 - {INRIA} - {I}nstitut {N}ational des {S}ciences {A}ppliqu{\'e}es de {R}ennes - {U}niversit{\'e} de {R}ennes 1 },
pages = {17 },
type = {Research Report},
institution = {INRIA},
number = {{RR}-6795},
year = {2009},
url = {http://hal.inria.fr/inria-00352529/en/}
}
@TECHREPORT{LeFessant2008b,
title = {{P}ace-{M}aker: {T}racking peer availability in large networks},
author = {{L}e {F}essant, {F}abrice and {S}engul, {C}igdem and {K}ermarrec, {A}nne-{M}arie},
keywords = {peer-to-peer, cryptography, availability, monitoring},
language = {{A}nglais},
affiliation = {{ASAP} - {INRIA} {S}aclay - {I}le de {F}rance - {INRIA} - {CNRS} : {UMR} - {U}niversit{\'e} {R}ennes {I} - {INSA} - {I}nstitut {N}ational des {S}ciences {A}ppliqu{\'e}es - {ASAP} - {IRISA} - {CNRS} : {UMR}6074 - {INRIA} - {U}niversit{\'e} {R}ennes {I} - {I}nstitut {N}ational des {S}ciences {A}ppliqu{\'e}es de {R}ennes },
pages = {33 },
type = {Research Report},
institution = {INRIA},
number = {{RR}-6594},
year = {2008},
abstract = {In this paper, we introduce Pacemaker, a scalable and lightweight protocol to measure reliably the availability of peers. To the best of our knowledge, Pacemaker is the only protocol resilient to the presence of selfish peers, i.e. peers lying about their availability and minimizing their contribution to the system. Pacemaker relies on a novel {\em pulse-based} architecture, where a small set of trusted peers regularly flood the network with pulses containing cryptographic values. Collecting these pulses enables peers to later prove their presence in the system at any time, using cryptographic signatures. This new architecture overcomes many limitations of ping-based systems, and can be easily deployed on ad-hoc networks and social-based topologies. Simulation results show that our protocol provides accurate availability measurements even in the presence of selfish peers. Furthermore, our results are verified by experiments in Planetlab, which also illustrate the deployability of Pacemaker in real networks.},
url = {http://hal.inria.fr/inria-00305620/en/}
}
@INPROCEEDINGS{LeFessant2008a,
author = {D. Frey and J. Royan and R. Piegay and A.M. Kermarrec and E. Anceaume and Fabrice {Le Fessant}},
title = {Solipsis: A Decentralized Architecture for Virtual Environments},
booktitle = {International Workshop on Massively Multiuser Virtual Environments (MMVE'08)},
year = {2008},
month = {Mar},
publisher = {IEEE},
url = {http://fabrice.lefessant.net/papers/mmve2008.pdf},
abstract = {Lack of scalability is a key issue for virtual-environment technology,
and more generally for any large-scale online experience because
it prevents the emergence of a truly massive virtual-world
infrastructure (Metaverse). The Solipsis project tackles this issue
through the use of peer-to-peer technology, and makes it possible
to build and manage a world-scale Metaverse in a truly distributed
manner. Following a peer-to-peer scheme, entities collaborate to
build up a common set of virtual worlds. In this paper, we present
a first draft of the Solipsis architecture as well as the communication
protocol used to share data between peers. The protocol
is based on Raynet, an n-dimensional Voronoi-based overlay network.
Its data-dissemination policy takes advantage of the viewdepedent
representation of 3D contents. Moreover, the protocol effectively
distributes the execution of computationally intesive tasks
that are usually executed on the server-side, such as collision detection
and physics computation. Finally, we also present our web
component, a 3D navigator that can easily run on terminals with
scarce resources, and that provides solutions for smooth transitions
between 3D Web and Web 2.0.}
}
@ARTICLE{LeFessant2007b,
author = {Patrick Eugster and Pascal Felber and Fabrice {Le Fessant}},
title = {The "Art" of Programming Gossip-based Systems},
journal = {Operating Systems Review - Special topic: Gossip-Based Networking},
publisher = {ACM SIGOPS},
volume = {41},
number = {5},
year = {2007},
month = {oct},
url = {http://fabrice.lefessant.net/papers/osr2007.pdf},
abstract = {How does one best go about building actual gossip-based
protocols? Trying to answer this question has brought us to
address two preliminary questions, namely (1) what the in-
trinsics of such systems or protocols are, and (2) what kind
of applications would in the end be built on top of such
protocols. We address the first question by arguing that
gossip-based protocols are all built following one and the
same pattern, and describing three building blocks which
we claim are used to support this recurrent pattern--most
notably a source of randomness. We validate these claims
by devising simplified versions of well-known protocols, in a
layered fashion, on top of a conceptual interface describing
these basic services. The second question is addressed by ar-
guing that gossip-based protocols exhibit some probabilistic
or imperfect flavor (e.g., probabilistic or partial completion),
and by proposing to take such probabilistic behavior into ac-
count when devising interfaces for applications building on
top of gossip-based protocols. We argue for inherent support
for these probabilities in the programming model.}
}
@INPROCEEDINGS{LeFessant2007a,
author = {Fabrice {Le Fessant}},
title = {{Gestion de versions de formats avec Camlp4}},
booktitle = {Dix-huiti\`emes Journ\'ees Francophones des Langages Applicatifs (JFLA'07)},
year = 2007,
address = {Aix-les-bains, France},
publisher = {INRIA},
abstract = { La gestion des changements de formats est un problème crucial de l'informatique : encore
aujourd'hui, peu d'applications sont capables de lire des données sauvées dans un format d'une
version antérieure ; en distribué, les versions de programmes devant communiquer entre eux sont
de plus en plus hétérogènes, en particuliers dans les systèmes pair-à-pair.
Dans ce papier, nous présentons une extension de syntaxe d'Objective-Caml en Camlp4
permettant de gérer plus ecacement les évolutions de formats, aussi bien dans les chiers
sauvegardés que dans les messages échangés dans un système distribué.},
url = {http://fabrice.lefessant.net/papers/jfla2007.pdf}
}
@INPROCEEDINGS{LeFessant2006b,
author = {Rachid Guerraoui and
Sidath B. Handurukande and
Kevin Huguenin and
Anne-Marie Kermarrec and
Fabrice {Le Fessant} and
Etienne Riviere},
title = {GosSkip, an Efficient, Fault-Tolerant and Self Organizing
Overlay Using Gossip-based Construction and Skip-Lists Principles},
booktitle = {International Conference on Peer-to-Peer Computing (P2P'06)},
year = {2006},
abstract = {This paper presents GosSkip, a self organizing and fully distributed
overlay that provides a scalable support to data storage and retrieval
in dynamic environments. The structure of GosSkip, while initially
possibly chaotic, eventually matches a perfect set of Skip-list-like
structures, where no hash is used on data attributes, thus preserving
semantic locality and permitting range queries. The use of
epidemic-based protocols is the key to scalability, fairness and good
behavior of the protocol under churn, while preserving the simplicity
of the approach and maintaining O(log(N)) state per peer and O(log(N))
routing costs. In addition, we propose a simple and efficient
mechanism to exploit the presence of multiple data items on a single
physical node. GosSkip\u2019s behavior in both a static and a dynamic
scenario is further conveyed by experiments with an actual
implementation and real traces of a peer to peer workload.
},
url = {http://fabrice.lefessant.net/papers/p2p2006.pdf}
}
@INPROCEEDINGS{LeFessant2006a,
author = {Sidath B. Handurukande and
Anne-Marie Kermarrec and
Fabrice {Le Fessant} and
Laurent Massouli{\'e} and
Simon Patarin},
title = {Peer sharing behaviour in the eDonkey network, and implications
for the design of server-less file sharing systems},
booktitle = {EuroSys Conference (EuroSys'06)},
year = {2006},
abstract = {In this paper we present an empirical study of a workload gathered by
crawling the eDonkey network - a dominant peer-to-peer file sharing
system - for over 50 days. We first confirm the presence of some known
features, in particular the prevalence of free-riding and the Zipflike
distribution of file popularity. We also analyze the evolution of
document popularity. We then provide an in-depth analysis of several
clustering properties of such workloads. We measure the geographical
clustering of peers offering a given file. We find that most files are
offered mostly by peers of a single country, although popular files
don't have such a clear home country. We then analyze the overlap
between contents offered by different peers. We find that peer
contents are highly clustered according to several metrics of
interest. We propose to leverage this property by allowing peers to
search for content without server support, by querying suitably
identified semantic neighbours. We find via trace-driven simulations
that this approach is generally effective, and is even more effective
for rare files. If we further allow peers to query both their semantic
neighbours, and in turn their neighbours' neighbours, we attain hit
rates as high as over 55% for neighbour lists of size 20.},
url = {http://fabrice.lefessant.net/papers/eurosys2006.pdf}
}
@TECHREPORT{LeFessant2005b,
title = {{P}eer {S}haring {B}ehaviour in the e{D}onkey {N}etwork, and {I}mplications for the {D}esign of {S}erver-less {F}ile {S}haring {S}ystems},
author = {{H}andurukande, {S}. and {K}ermarrec, {A}nne-{M}arie and {L}e {F}essant, {F}. and {M}assouli{\'e}, {L}aurent and {P}atarin, {S}.},
abstract = {{P}eer-to-peer file sharing systems have grown to the extent that they now generate most of the {I}nternet traffic, way ahead of {W}eb traffic. {U}nderstanding workload properties of peer-to-peer systems is necessary to optimize their performance. {I}n this paper we present an empirical study of a workload gathered by crawling the e{D}onkey network a dominant file sharing system for over 50 days. {B}esides confirming the presence of some well-known features, such as the prevalence of free-riding and the {Z}ipf-like distribution of file popularity, we also analyze several previously ignored aspects of such workloads. {M}ore specifically, we measure the geographical clustering of peers offering a given file. {W}e find that most files are offered mostly by peers of a single country, although popular files don't have such a clear home country. {W}e also analyze the overlap between contents offered by different peers. {W}e find that peer contents tend to be clustered, which may be taken as evidence that peers possess specific interests. {W}e leverage this and allow peers to search for content without any server support, by maintaining a list of semantic neighbours, i.e. peers with similar interests. {S}imulation results confirm the clustering property of the trace and show that a high hit ratio is achieved by querying the most recently discovered peers even after removing the top 15% most generous peers. {R}esults also indicate that the clustering is much higher for rare files.},
keywords = {{PEER}-{TO}-{PEER} {OVERLAY} {NETWORKS} / {FILE} {SHARING} {APPLICATION} / {CLUSTERING} {PATTERNS} / {TRACE} {ANALYSIS} / {SEMANTIC} {PROXIMITY}},
language = {{A}nglais},
affiliation = {{PARIS} - {INRIA} - {IRISA} - {CNRS} : {UMR}6074 - {INRIA} - {E}cole {N}ormale {S}up{\'e}rieure de {C}achan - {I}nstitut {N}ational des {S}ciences {A}ppliqu{\'e}es de {R}ennes - {U}niversit{\'e} de {R}ennes 1 - {D}istributed {P}rogramming {L}aboratory - {\'E}cole {P}olytechnique {F}{\'e}d{\'e}rale de {L}ausanne - {M}icrosoft {R}esearch {C}ambridge - {M}icrosoft - {M}icrosoft {R}esearch - {U}niversity of {B}ologna - {U}niversit{\`a} degli studi di {B}ologna - {L}aboratoire d'informatique de l'{\'e}cole polytechnique - {LIX} - {CNRS} : {UMR}7161 - {P}olytechnique - {X} - {INRIA} {F}uturs - {INRIA} },
pages = {38 },
type = {Research Report},
institution = {INRIA},
number = {{RR}-5506},
year = {2005},
url = {http://hal.archives-ouvertes.fr/inria-00070501/en/}
}
@INPROCEEDINGS{LeFessant2005a,
author = {Behshad Behzadi and
Fabrice {Le Fessant}},
title = {DNA Compression Challenge Revisited: A Dynamic Programming
Approach},
year = {2005},
booktitle = {Combinatorial Pattern Matching, 16th Annual Symposium (CPM'05), Jeju Island, Korea, June 19-22, 2005, Proceedings},
abstract = { Standard compression algorithms are not able to compress
DNA sequences. Recently, new algorithms have been introduced specifically for
this purpose, often using detection of long approximate repeats. In this
paper, we present another algorithm, DNAPack, based on dynamic
programming. In comparison with former existing programs, it compresses DNA
slighly better, while the cost of dynamic programming is almost neglectible.
},
url = {http://fabrice.lefessant.net/papers/cpm2005.pdf}
}
@INPROCEEDINGS{LeFessant2004c,
author = {Sidath B. Handurukande and
Anne-Marie Kermarrec and
Fabrice {Le Fessant} and
Laurent Massouli{\'e}},
title = {Exploiting semantic clustering in the eDonkey P2P network},
booktitle = {ACM SIGOPS European Workshop, Leuven,
Belgium, September 19-22, 2004},
year = {2004},
month = {Sep},
abstract = { Peer-to-peer file sharing now represents a significant portion of the
Internet traffic and has generated a lot of interest from the
research community. Some recent measurements studies of peer-to-peer
workloads have demonstrated the presence of semantic proximity
between peers. One way to improve performance of peer-to-peer file
sharing systems is to exploit this locality of interest in order to
connect semantically related peers so as to improve the search both in
flooding- and server-based systems. Creating these additional connections
raises
interesting challenges and in particular (i) how to capture
the semantic relationship between peers (ii) how to exploit
these relationships and (iii) how to evaluate these
improvements. In this paper, we evaluate several strategies to
exploit the semantic proximity between peers against a real trace collected in
November 2003 in the
eDonkey 2000 peer-to-peer network. We present the results of this
evaluation which confirm the presence of clustering in such networks
and the interest to exploit it.},
url = {http://fabrice.lefessant.net/papers/sigops2004.pdf}
}
@INPROCEEDINGS{LeFessant2004b,
author = {Fabrice {Le Fessant} and
Sidath B. Handurukande and
Anne-Marie Kermarrec and
Laurent Massouli{\'e}},
title = {Clustering in Peer-to-Peer File Sharing Workloads},
booktitle = {Peer-to-Peer Systems III, Third International Workshop
(IPTPS'04), La Jolla, CA, USA, February 26-27, 2004, Revised
Selected Papers},
year = {2004},
month = {Feb},
abstract = {Peer-to-peer file sharing systems now generate a significant portion of
Internet traffic.
A good understanding of their workloads is crucial in
order to improve their scalability, robustness and performance.
Previous measurement studies on Kazaa and Gnutella were based on monitoring peer requests, and mostly concerned with peer and file availability and network traffic.
In this paper, we take different measurements: instead of passively
recording requests, we actively probe peers to get their cache
contents information.
This provides us with a map of contents, that we use to evaluate the degree of
clustering in the system, and that could be exploited to
improve significantly the search process.},
url = {http://fabrice.lefessant.net/papers/iptps2004.ps.gz}
}
@INPROCEEDINGS{LeFessant2004a,
author = {Bernadette Charron-Bost and
Fabrice {Le Fessant}},
title = {Validity Conditions in Agreement Problems and Time Complexity},
booktitle = {SOFSEM'04: Theory and Practice of Computer Science, 30th
Conference on Current Trends in Theory and Practice of Computer
Science, Merin, Czech Republic, January 24-30, 2004},
year = {2004},
month = {Jan},
abstract = {We first introduce a new class of distributed agreement problems,
ranging from Uniform Consensus to Non-Blocking Atomic Commitment,
by varying the validity condition in the specification.
We then provide an early deciding algorithm to solve each problem of
this class in the synchronous model with crash failures.
Our algorithm achieves the previously established lower bounds for time
complexity showing that these lower bounds are tight.},
url = {http://fabrice.lefessant.net/papers/sofsem2004.ps.gz}
}
@INPROCEEDINGS{LeFessant2003b,
author = {Fabrice {Le Fessant} and
Philippe Raipin Parv{\'e}dy and
Michel Raynal},
title = {Brief announcement: early decision despite general process
omission failures},
booktitle = {Conference on Principles of Distributed Computing (PODC'03)},
year = {2003},
url = {},
abstract = {}
}
@TECHREPORT{LeFessant2003a,
title = {{ML}donkey, a {M}ulti-{N}etwork {P}eer-to-{P}eer {F}ile-{S}haring {P}rogram},
author = {{L}e {F}essant, {F}abrice and {P}atarin, {S}imon},
abstract = {{A} lot of designers of functional languages have one dream: finding a killer application, outside of the world of symbolic programming (compilers, theorem provers, {DSL}s), that would make their language spread in the open-source community. {O}ne year ago, we tackled this problem, and decided to use to program a network application in the emerging world of peer-to-peer systems. {T}he result of our work, , has superseded our hopes: it is currently the most popular peer-to-peer file-sharing client on the well-known freshmeat.net site, with about 10,000 daily users. {M}oreover, is the only client able to connect to several peer-to-peer networks, to download and share files. {I}t works as a daemon, running unattended on the computer, and can be controlled remotely using three different kind of interfaces. {I}n this paper, we present the lessons we learnt from its design and implementation.},
keywords = {{PEER}-{TO}-{PEER} / {FILE} {SHARING} / {FUNCTIONAL} {PROGRAMMING}},
language = {{E}nglish},
affiliation = {{REGAL} - {INRIA} {R}ocquencourt - {INRIA} - {CNRS} : {UMR}7606 - {U}niversit{\'e} {P}ierre et {M}arie {C}urie - {P}aris {VI} },
type = {{R}esearch {R}eport},
institution = {INRIA},
number = {{RR}-4797},
year = {2003},
url = {http://hal.archives-ouvertes.fr/inria-00071789/en/}
}
@TECHREPORT{LeFessant2002b,
title = {{V}alidity {C}onditions in {A}greement {P}roblemsand {T}ime {C}omplexity},
author = {{C}harron-{B}ost, {B}ernadette and {L}e {F}essant, {F}abrice},
abstract = {{W}e study the time complexity of different agreement problems in the synchrono- us model with crash failures, by varying their validity condition. {W}e first introduce a continuous class of agreement problems, the k-{TA}g problems, which includes both the {U}niform {C}onsensus and {N}on-{B}locking {A}tomic {C}ommitment. {W}e then exhibit a general early-deciding algorithm, that we instanciate to solve every problem of this class. {T}he algorithm always achieves the previously established lower-bounds for early-deciding, showing that these lower-bounds are tight.},
keywords = {{DISTRIBUTED} {CONSENSUS} / {SYNCHRONOUS} {MODEL} / {NON}-{BLOCKING} {ATOMIC} {COMMITMENT} / {ERALY}-{DECIDING} {ALGORITHM} / {K}-{TAG} / {LOWER}-{BOUNDS} / {VALIDITY} {CONDITIONS} / {TIME} {COMPLEXITY}},
language = {{E}nglish},
affiliation = {{SOR} - {INRIA} {R}ocquencourt - {INRIA} },
type = {{R}esearch {R}eport},
institution = {INRIA},
number = {{RR}-4526},
note = {{P}rojet {SOR}},
year = {2002},
url = {http://hal.archives-ouvertes.fr/inria-00072062/en/}
}
@INPROCEEDINGS{LeFessant2002a,
author = {C{\'e}dric Fournet and
Fabrice {Le Fessant} and
Luc Maranget and
Alan Schmitt},
title = {JoCaml: A Language for Concurrent Distributed and Mobile
Programming},
year = {2002},
booktitle = {Advanced Functional Programming, 4th International School,
AFP 2002, Oxford, UK, August 19-24, 2002, Revised Lectures},
url = {http://fabrice.lefessant.net/papers/jocaml-afp4.pdf}
}
@INPROCEEDINGS{LeFessant2001b,
author = {Fabrice {Le Fessant}},
title = {Detecting distributed cycles of garbage in large-scale systems},
booktitle = {Conference on Principles of Distributed Computing (PODC'01)},
year = {2001},
abstract = {Distributed scalable garbage collectors, mostly based on some
kind of reference counting, fail to detect distributed cycles of garbage.
This problem may lead to important memory leaks in distributed storage
systems. In this paper, we present a new algorithm which detects and collects
such distributed cycles of garbage.
Our algorithm is based on the propagation of marks along chains of remote
pointers. It uses two new mechanisms: min-max marking , to propagate two
different marks to each stub, and sub-generation , to build an acyclic
graph on a cycle using back-tracking information. A new technique, called
optimistic back-tracking , is also used to speed-up sub-generation.
The resulting algorithm is completely distributed, asynchronous,
fault-tolerant and inexpensive. Moreover, it collects incrementally all
distributed cycles of garbage, without partitioning the system. Thus, it is
particularly well adapted to large-scale networks. Finally, it can be easily
implemented with minor modifications of a local tracing garbage
collector.},
url = {http://fabrice.lefessant.net/papers/podc2001.ps.gz}
}
@INPROCEEDINGS{LeFessant2001a,
author = {Fabrice {Le Fessant} and
Luc Maranget},
title = {Optimizing Pattern Matching},
booktitle = {Internationnal Conference on Functional Programming (ICFP'01)},
year = {2001},
abstract = {We present improvements to the
backtracking technique of pattern-matching compilation.
Several optimizations are introduced,
such as commutation of patterns, use of exhaustiveness information, and control
flow optimization through the use of labeled static exceptions and context
information.
These optimizations have been
integrated in the Objective-Caml compiler.
They have shown good results in increasing the speed of
pattern-matching intensive programs, without increasing
final code size.},
url = {http://fabrice.lefessant.net/papers/icfp2001.ps.gz}
}
@INPROCEEDINGS{LeFessant1999b,
author = {Sylvain Conchon and
Fabrice {Le Fessant}},
title = {Jocaml: Mobile Agents for Objective-Caml},
booktitle = {1st International Symposium on Agent Systems and Applications
/ 3rd International Symposium on Mobile Agents (ASA/MA'99),
3-6 October 1999, Palm Springs, CA, USA},
year = {1999},
pages = {22-29},
abstract = {Jocaml is a system for mobile agents built inside the
Objective-Caml language. Jocaml eases the development of concurrent,
distributed and mobile agent based applications, by expressing useful
distribution abstractions using a small set of simple but powerful primitives
taken from the Join-Calculus.
The system provides total transparency for migration, application states
(after migration, all threads resume their execution in the state before
migration), communications (communication channels with other agents are kept
during migration) and composition (sub-agents migrate with their parent
agent). Other features of the Jocaml system are mobile objects with
transparent remote method invocation, distributed garbage collection,
failure detection and execution efficiency. Jocaml has already been used in
several applications, such as a mobile editor, some distributed games and a
distributed implementation of Ambients.
This paper describes the Jocaml programming model and language, its current
implementation and some interesting applications. },
url = {http://fabrice.lefessant.net/papers/asama99.ps.gz}
}
@INPROCEEDINGS{LeFessant1999a,
author = {Marc Shapiro and
Fabrice {Le Fessant} and
Paulo Ferreira},
title = {Recent Advances in Distributed Garbage Collection},
booktitle = {Advances in Distributed Systems, Advanced Distributed Computing:
From Algorithms to Systems},
year = {1999},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {1752},
abstract = {Dynamically-allocated memory must eventually be reclaimed. But manual reclamation is error-prone, and if an object is de-allocated prematurely, a program that later follows a pointer to it might behave incorrectly. In contrast, garbage collection (GC) automatically reclaims objects that can no longer be reached by any path of pointers.
In a distributed system, an object might not only be referenced from one program, but also from other programs and other computers. This makes manual reclamation quite intractable. We consider here the problem of distributed garbage collection (DGC). DGC is particularly important in a large-scale distributed system, since a de-allocation error might cause a completely unrelated program to fail, possibly far away and an arbitrarily long time later.
DGC has been a subject of academic research since at least 1977. With the growth of the Internet, DGC is now receiving its share of commercial attention. For instance, both Java RMI and DCOM come with some form of DGC.
The next section contains a quick review of DGC techniques; for a more in-depth treatment, we refer to published surveys. Then we detail two recent advances in DGC, both developed in the context of the Broadcast project. One is an algorithm for collecting distributed cycles of garbage in a message-passing system; the other is an algorithm for DGC in a system with caching and/or replication. Both have been implemented in real systems and are in actual use. This article assumes some familiarity with centralised GC, now a mature area. We use the following vocabulary. Objects connected by references form a graph; a remote reference may point into another process. An application or {mutator} enters the graph via {roots}, allocates objects, and performs assignment of reference variables. The system or {collector} reclaims garbage, i.e., objects that are reachable by no path from any root. },
url = {http://fabrice.lefessant.net/papers/raid99.pdf}
}
@ARTICLE{LeFessant1998b,
author = {Fabrice {Le Fessant} and
Luc Maranget},
title = {Compiling Join-Patterns},
journal = {Electr. Notes Theor. Comput. Sci.},
volume = {16},
number = {3},
year = {1998},
booktitle = {international workshop on High-Level Concurrent Languages (HLCL'98)},
month = {Sep},
abstract = {The join-calculus is both a name passing calculus and a core
language for concurrent and distributed programming. An essential
part of its implementation is the compilation of
join-patterns. Join-patterns define new channels and all the
synchronizations they take part to at the same time. Relying on the
experience based on our two implementations, we study the
translation of join-patterns into deterministic finite-state
automata as well as some related optimizations.},
url = {http://fabrice.lefessant.net/papers/hlcl98.ps.gz}
}
@INPROCEEDINGS{LeFessant1998a,
author = {Fabrice {Le Fessant} and
Ian Piumarta and
Marc Shapiro},
title = {An Implementation for Complete, Asynchronous, Distributed
Garbage Collection},
booktitle = {Conference on Programming Languages Design and Implementation (PLDI'98)},
year = {1998},
month = {Jun},
abstract = {Most existing reference-based distributed object systems
include some kind of acyclic garbage collection, but fail to provide
acceptable collection of cyclic garbage. Those that do provide such
GC currently suffer from one or more problems: synchronous operation,
the need for expensive global consensus or termination algorithms,
susceptibility to communication problems, or an algorithm that does
not scale. We present a simple, complete, fault-tolerant,
asynchronous extension to the (acyclic) cleanup protocol of the SSP
Chains system. This extension is scalable, consumes few resources,
and could easily be adapted to work in other reference-based
distributed object systems---rendering them usable for very
large-scale applications.},
url = {http://fabrice.lefessant.net/papers/pldi98.ps.gz}
}
@INPROCEEDINGS{LeFessant1997a,
author = {Fabrice {Le Fessant} and Ian Piumarta and Marc Shapiro},
title = {A detection algorithm for distributed cycles of garbage },
booktitle = {OOPSLA'97 W.\ on Garbage Collection and Memory
Management},
year = 1997,
address = {Atlanta GA (USA)},
month = OCT,
abstract = { We present an algorithm that detects cycles of garbage in
reference-based distributed systems. It is derived from Hughes'
algorithm, in a simplified form that makes far fewer assumptions about
the system. A local garbage collector marks incoming and outgoing
references with timestamps that are propagated asynchronously between
spaces. A central site computes the minimum reachable timestamp,
allowing stale references to be identified and deleted. The
coexistence of non-participating spaces, and spaces participating in
collections controlled by more than one central site, is allowed.},
url = {http://fabrice.lefessant.net/papers/oopsla97-gc.ps.gz}
}
This file has been generated by bibtex2html 1.88.