Seminar by Robert E. Tarjan: Zip Trees

Robert E. Tarjan

  • Speaker: Robert E. Tarjan, Department of Computer Science, Princeton University and Intertrust Technologies
  • Title: Zip Trees
  • When: June 29, 2018 — 14:00
  • Where: I3S, Salle de conférence 007

  • Abstract: This talk will present the zip tree, a simple and efficient type of binary search tree. Zip trees use randomization to achieve balance. A zip tree can be viewed as a binary-tree representation of a skip list or as a variant of a treap. Insertion and deletion avoid the multiplicity of cases that arise in standard balanced trees. Zip trees can be adapted to exploit biased access distributions. Their simplicity makes them promising for concurrent use.

  • Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.

  • See the thread on Twitter

Cérémonie des Lauréats de prix d’excellence d’Université Côte d’Azur

Members of COATI participates to the 2017 edition of Cérémonie des Lauréats de prix d’excellence d’Université Côte d’Azur.

More pictures here.

PhD defense of Nicolas Huin

PhD Nicolas Huin

    • Title: “Energy Efficient Software Defined Networks”
    • When: September 28, 2017 — 14:30
    • Where: Inria Sophia Antipolis, amphi Kahn
    • Committee:

    • Abstract: In the recent years, the growth of the architecture of telecommunication networks has been quickly increasing to keep up with a booming traffic. Moreover, the energy consumption of these infrastructures is becoming a growing issue, both for its economic and ecological impact. Multiple approaches were proposed to reduce the networks’ power consumption such as decreasing the number of active elements. Indeed, networks are designed to handle high traffic, e.g., during the day, but are over-provisioned during the night. In this thesis, we focus on disabling links and routers inside the network while keeping a valid routing. This approach is known as Energy Aware Routing (EAR).

      However current networks are not adapted to support the deployment of network-wide green policies due to their distributed management and the black-box nature of current network devices.The SDN and NFV paradigms bear the promise of bringing green policies to reality.The first one decouples the control and data plane and thus enable a centralized control of the network.The second one proposes to decouple the software and hardware of network functions and allows more flexibility in the creation and management of network services.

      In this thesis, we focus on the challenges brought by these two paradigms for the deployment of EAR policies. We dedicated the first two parts to the SDN paradigm. We first study the forwarding table size constraints due to an increased complexity of rules. We then study the progressive deployment of SDN devices alongside legacy ones. We focus our attention on the NFV paradigm in the last part, and more particularly, we study the Service Function Chaining problem.

      All the publications at the core of this thesis are available online here


PhD Nicolas Huin

Wilkes Award 2017

, ,

The paper Energy Efficient Content Distribution [1] won the Wilkes Award 2017 (The Wilkes Award is given once a year to the authors of the best paper published in the volume of The Computer Journal from the previous year)

Congratulation to the authors!

  • J. Araujo, F. Giroire, J. Moulierac, Y. Liu, and R. Modrzejewski, “Energy Efficient Content Distribution,” The Computer Journal, vol. 59, iss. 2, pp. 192-207, 2016. doi:10.1093/comjnl/bxv095
    [BibTeX] [Download PDF] 
    @article{araujo:hal-01238051,
TITLE = {{Energy Efficient Content Distribution}},
AUTHOR = {Araujo, J and Giroire, Fr{\'e}d{\'e}ric and Moulierac, J and Liu, Yi and Modrzejewski, R},
URL = {https://hal.inria.fr/hal-01238051},
JOURNAL = {{The Computer Journal}},
PUBLISHER = {{Oxford University Press (UK)}},
VOLUME = {59},
NUMBER = {2},
PAGES = {192-207},
YEAR = {2016},
MONTH = Feb,
DOI = {10.1093/comjnl/bxv095},
KEYWORDS = {Energy Efficiency ; Integer Linear Programming ; Content Deliv-ery Network ; In-network Caching ; Future Internet},
PDF = {https://hal.inria.fr/hal-01238051/file/compj.pdf},
HAL_ID = {hal-01238051},
HAL_VERSION = {v1},
}