DISC 2016

Doctoral Dissertation Award

The Principles of Distributed Computing Doctoral Dissertation Award was created in 2012 to acknowledge and promote outstanding research by doctoral (Ph.D.) students on the principles of Distributed Computing.

The award is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). This award is presented annually, with the presentation taking place alternately at PODC and DISC. The 2016 award will be presented at DISC 2016, to be held in Paris, France.

Award-winning dissertations 2016

The Doctoral Dissertation Award Committee has awarded the 2016 Principles of Distributed Computing Doctoral Dissertation Award to Dr. Hsin-Hao Su and to Dr. Shahar Timnat:

Dr. Hsin-Hao Su completed his dissertation “Algorithms for Fundamental Problems in Computer Networks” in July 2015, under the supervision of Professor Seth Pettie, at the University of Michigan, Ann Arbor.

Hsin-Hao’s thesis provides efficient algorithms for fundamental graph problems that arise in networks, in both sequential and distributed settings. Among the latter, the most prominent are his results concerning graph coloring. He showed that numerous existential results in graph theory can be viewed as distributed algorithms with a tiny probability of success (guaranteed by the Lovasz Local Lemma) and that a fast distributed algorithm for the constructive LLL could be used to amplify the success probability to nearly 1. Hsin-Hao presented a O(log n)-time randomized algorithm for the LLL, and illustrated how it could be applied to graph coloring problems where the existence of the coloring is not obvious. Moser and Tardos observed that any LLL algorithm in their “resampling” framework requires Ω(log n) time, so this result is optimal within a natural design space. Hsin-Hao used his LLL algorithm to establish an O(log n)-time algorithm for (4+o(1))Δ/ln Δ−coloring triangle-free graphs. This result more than any other exhibits the technical virtuosity of Hsin-Hao: he discovered not only a great algorithm, but a new bound on the chromatic number of triangle-free graphs.

Before Hsin-Hao’s work many symmetry-breaking problems appeared to have similar complexity: (Δ+1)−coloring seemed similar to the Maximal Independent Set (MIS) problem and (2Δ−1)−edge coloring  seemed similar to Maximal Matching. Hsin-Hao developed new tools for analyzing randomized coloring algorithms in locally sparse graphs, one consequence of which is that (2Δ−1)−edge coloring is provably easier than maximal matching.

Dr. Shahar Timnat completed his dissertation “Practical Parallel Data Structures” in July 2015 under the supervision of Professor Erez Petrank at Technion.

Shahar’s dissertation provides an outstanding advance in our understanding of concurrent algorithms, including novel efficient practical algorithms and a theoretical study of their fundamental properties. The literature on highly-concurrent data structures focuses on lock-freedom, which guarantees that some thread will eventually make progress, and wait-freedom, which guarantees that all threads will eventually make progress in spite of failures and delays of other threads. It was believed that the overhead and complexity required to achieve wait-freedom is too high for practical systems. Shahar’s thesis changes this traditional belief by showing that lock-free algorithms can be made wait-free automatically and with a small performance penalty. His construction is realistic and practical.

Shahar provides a practical wait-free iterator, an original construct that no one knew how to do before. Another contribution is a novel and helpful analysis of the common “helping” pattern that is typically used for constructing wait-free algorithms. This analysis shows that there exist circumstances where some form of helping is required. Like many lower bounds, this has practical impact because it spares data structure designers from wasting their time trying on other approaches. Finally, the thesis proposes a simple transactional interface that is well-adapted both to architectures that provide hardware support for transactions, and to those that do not, yielding a way to design data structures that easily can be ported from one platform to another.

Doctoral Dissertation Award Committee 2016

The 2016 Principles of Distributed Computing Doctoral Dissertation Award Committee:

  • Yoram Moses, Technion
  • Andrzej Pelc (chair), Université du Québec en Outaouais
  • Paul Spirakis, University of Liverpool

Past award-winning dissertations

2015
“Efficient Network Utilization in Locality-Sensitive Distributed Algorithms” by Dr. Leonid Barenboim supervised by Professor Michael Elkin at Ben Gurion University.
2014
“Probabilistic Methods for Distributed Information Dissemination” by Dr. Bernhard Haeupler supervised by Professors Jonathan Kelner, Muriel Médard, and David Karger at MIT.
2013
  • “Fault-tolerant structures in graphs” by Dr. Shiri Chechik supervised by Professor David Peleg at the Weizmann Institute of Science in 2012.
  • “Graphs and geometric algorithms on distributed networks and databases” by Dr. Danupon Nanongkai supervised by Profession Richard J. Lipton at the Georgia Institute of Technology in 2011.
2012
“Probabilistic Methods in Distributed Computing” by Dr. Keren Censor-Hillel supervised by Professor Hagit Attiya at the Technion in 2010.

Eligibility

  • To be eligible for the award in year X, a nominated dissertation must have been successfully defended in the period January 1st, X-2 through December 31st, X-1.
  • If the advisor of the dissertation is in the core committee of year X (see below), it cannot be nominated in year X. In this case the eligibility period extends by one year, i.e., a dissertation successfully defended between January 1st, X-3 through December 31st, X-2 is eligible if and only if it was not eligible in either year X-1 or year X-2.
  • The core committee of year X is disjoint from those of years X-1 and X-2. Each dissertation is thus eligible exactly twice.
  • The dissertation must be in English: either originally written in English, or translated.
  • The main topic of the dissertation must be on the principles of Distributed Computing. (For a possible indication of what it is meant by this term, see for example the Call for Papers of DISC and PODC.)

Nomination and Submission

A one-page nomination letter must be submitted by the thesis advisor. The nomination should highlight the dissertation’s contributions and justify why the dissertation is worthy of the award.

Submission Checklist

A nomination must include:

  1. Contact details (affiliation and email addresses) of the advisor and the doctoral student.
  2. A formal document from the student’s department/institution/organization verifying the date that the dissertation was successfully defended (a scanned version is acceptable for the submission, but the original document might be required at a later stage of the evaluation). If not indicated by the document, also state the period of time the student was enrolled in the doctoral program.
  3. A one page justification letter.
  4. The following four lists of work (co)authored by the candidate:
    1. Publications that contain material from the thesis, detailing what material was taken from which part of the thesis and the parts that are not contained in the thesis.
    2. Publications that are cited in the thesis, but do not contain material that also appears in the thesis.
    3. Papers currently under review, including journal submissions of previously published work, that contain material from the thesis, detailing what material was taken from which part of the thesis and the parts that are not contained in the thesis.
    4. Those parts of the thesis which are not included in the other lists.
  5. A list of awards the student received for the thesis and/or publications related to the thesis.
  6. One copy of the dissertation in electronic form (preferably in pdf).
  7. A separate copy of the abstract in electronic form (either as pdf or plain text).

Award Committee and Review Process

The committee will consist of four core members and a number of ad-hoc members, selected as described below. The review process will consist of two stages:

The first selection phase, carried out by the core members, will be based on the nomination letters and publication lists. At the end of this phase, a short list of dissertations to be considered in the second round will be compiled.

Based on the short list, the four core members will identify experts on the topics of the dissertations and invite them to serve as additional (ad hoc) members of the committee. The committee should include sufficiently many members to allow each dissertation to be reviewed by three members without requiring any member to review more than two dissertations.

For an award year X, the four core members will by default be the following:

  • The PC Chair of DISC in year X-9.
  • The PC Chair of PODC in year X-9.
  • The PC Chair of DISC in year X-1.
  • The PC Chair of PODC in year X-1.

The committee chair will alternate between DISC and PODC PC chairs of year X-9. Specifically, when X is even, the chair will be the DISC PC chair of X-9 and when X is odd, the chair will be the PODC PC chair of X-9.

Members of the committees in years X-1 and X-2 are not eligible for participation in the committee for year X. If a core committee cannot be established (for this or any other reason), the corresponding Steering Committee of the award year nominates a person to work on behalf of the missing DISC/PODC PC chair.

Evaluation Criteria

The nominated dissertations will be reviewed for technical depth and significance of the research contributions in the area of Distributed Computing, potential impact on theory and practice, and quality of presentation/writing, including thoroughness of description of related work and understandability of algorithms and proofs.

Award

  • The award presentation will alternate between DISC (even years) and PODC (odd years).
  • The winning dissertation will receive a plaque and a monetary prize.
  • The committee reserves the right to split or decline to give the award.
  • The committee can give Honorable Mentions to up to two non-winning dissertations meriting special recognition (or one Honorable Mention in case the award is split).
Disc 2016 Sponsors