DISC 2013

Category Archives: Uncategorized

LNCS 8205 is now available online

Access link.

Please follow these instructions how to activate the Association Code on SpringerLink.

The Multiple Association Code for DISC 2013  was send by e-mail to registered  participants.

TADDS 2013 Program is now available

Preliminary Program of DISC event on Networking

Thursday, October 17

17:30-17:40: Welcome Remarks

17:40-18:10: Resource Placement Under Stochastic Demands in Networked Topologies

Hanoch Levy, Tel Aviv University

We consider the problem of how to place and efficiently utilize resources in network environments. The setting consists of a regionally organized system which must satisfy regionally varying demands for various resources. The operator aims at placing resources in the regions as to minimize the cost of providing the demands. Examples of applications include peer supported video on demand services and cloud-based systems consisting of regional server-farms. The challenge posed by the system is the need to deal with an arbitrary multi-dimensional (high-dimensionality) stochastic demand. We show that, despite this complexity, one can optimize the system operation while accounting for the full demand distribution. We analyze this problem and provide a solution framework and algorithmic solutions for a wide variety of model variations.

      • Joint work with Yuval Rochman and Eli Brosh

18:10-18:40: Efficient multi-pattern matching on Compressed HTTP traffic.

Yaron Koral, Tel Aviv University and the Hebrew University

‘Signature-based’ detection is one of the fundamental technique to detect malicious activities in a network environment. Today, the performance of the security tools is dominated by the speed of the string-matching algorithms that detect these signatures.

A significant part of the traffic over the Internet is compressed HTTP. However, current security tools do not deal with such a traffic and require some kind of decompression phase before performing the multi-patterns matching task. Thus, there is a high performance penalty in pattern matching on compressed data.

In this talk, we present efficient algorithms for ’on-the-fly’ multi-pattern matching algorithms for common HTTP compression algorithms, such as GZIP and SDCH (Google’s compression algorithm). Our results show that surprisingly it is usually faster to do pattern matching on the compressed data, with the penalty of decompression, than to do pattern matching on regular traffic.

The talk is based on three papers: one with A. Bremler-Barr (INFOCOM 2009, later in Transactions on Networking 2012), one with Y. Afek and A. Bremler-Barr (Networking 2011,  later in Computer Communication 2012) and one with S. Tzur-David, D. Hay and A. Bremler-Barr (INFOCOM 2012).

18:40-19:10: Some Open Questions on the Borderline of Networking and Distributed Computing.

Michael Schapira, the Hebrew University

We will illustrate via Internet routing several promising research directions at the interface of distributed computing and networking including mechanisms for establishing connectivity (and other desiderata) in the data plane, self-stabilizing Internet protocols, and incentive-compatible protocols.

The 2013 Principles of Distributed Computing Doctoral Dissertation Award

The abundance of excellent candidates made the choice very difficult. Even after narrowing the list down, the committee still decided to split the award between two winners, listed next alphabetically by last name.  Dr. Shiri Chechik completed her thesis “Fault-tolerant structures in graphs” in 2012 under the supervision of Prof. David Peleg at the Weizmann Institute of Science. Dr. Danupon Nanongkai completed his thesis “Graphs and geometric algorithms on distributed networks and databases” in 2011 under the supervision of Prof. Richard J. Lipton at the Georgia Institute of Technology.
The thesis of Dr. Chechik includes a comprehensive and deep body of work on fault-tolerant graph spanners and related structures. It contains many strong results, one of which received a best student paper award, and one solved a long-standing open problem. In one of these results, Dr. Chechik shows that it is possible to compute, ahead of time, a compact routing table that provides good routes even if several edges fail. The thesis targets an area of research that has been well studied, but Dr. Chechik’s contributions advances the area significantly and promises to have a deep and long-lasting impact.
The thesis of Dr. Nanongkai shows a useful approach to make communication complexity a powerful tool for establishing lower bounds bounds for distributed computing. It also contains several sophisticated almost matching upper bounds. The thesis shows that this tool is applicable in diverse contexts, such as random walks, graph problems, and more. Besides being technically deep, the thesis combines distributed computing, communication complexity, and theory of random walks, in natural and novel ways. These results suggest and open the path for much exciting follow-up work on distributed communication complexity and distributed random walks.
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. This year it will be presented at DISC 2013.
Principles of Distributed Computing Doctoral Dissertation Award Committee, 2013:
Marcos K. Aguilera,       Microsoft Research
Rachid Guerraoui,          EPFL
Shay Kutten (Chair),      Technion
Michael Mitzenmacher,  Harvard
Alessandro Panconesi.  Sapienza

05-Aug-13: Best papers awards announced

DISC 2013 Tutorial: Software-Defined Networking (SDN)

The Evolution of SDN and How Your Network Is Changing

Speaker: Teemu Koponen – Nicira/VMWare

Date and time: Monday, 14 Oct at 15:30.


Network data planes have greatly evolved since the invention of Ethernet: the port densities, forwarding latencies and capacities of modern switches are all at levels no one would have predicted.  Yet at the same time, the principles of network control planes have remained unchanged; over the past decades, network control planes have been a story of distributed algorithms and manual configuration.

As seen in the trade press and networking conference proceedings, Software Defined Networks (SDN) is quickly challenging this, and in networking, the past few years have been all about the evolution of the control plane, almost to the point that it’s difficult to tell what SDN is!

In this tutorial, I’ll cover the evolution of the SDN: its beginning, current state, and where it might be heading next.  Using the industry use cases as examples I’ll discuss the management challenges SDN is solving today, as well as how the implementation of SDN control planes has evolved, how ‘logical centralization’ doesn’t remove aspects of distribution (but exactly the opposite!) and most importantly, how SDN has opened new avenues for the design of network control.  In the end, it may turn out the network community is now more receptive for new distributed algorithms than ever before!.

Short bio:

Teemu Koponen was the chief architect at Nicira Networks before joining VMware as a part of Nicira acquisition in 2012. Teemu received his PhD from Helsinki University of Technology in 2008 and ever since has been indecisive enough to remain active within the network research community while working for the industry. He received the ACM SIGCOMM Rising Star Award 2012 for his contributions on network architectures.


29-Jul-13: Registration is open

Accepted papers

James Aspnes and Keren Censor-Hillel. Atomic snapshots in expected $O(\log^3 n)$ steps using randomized helping

George Giakkoupis, Maryam Helmi, Lisa Higham and Philipp Woelfel. An O(sqrt n) Space Bound for Obstruction-Free Leader Election

Yuval Emek and Roger Wattenhofer. Frequency Hopping against a Powerful Adversary

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni and Leslie Lamport. Adaptive Register-Allocation with a linear number of registers

Mohsen Ghaffari and Fabian Kuhn. Distributed Minimum Cut Approximation

George Giakkoupis, Anne-Marie Kermarrec and Philipp Woelfel. Gossip Protocols for Renaming and Sorting

Mohsen Ghaffari and Bernhard Haeupler. Fast Structuring of Radio Networks for Multi-Message Communications

Ittai Abraham, Danny Dolev and Joseph Halpern. Distributed Protocols for Leader Election: a Game-Theoretic Perspective

Flavio Junqueira and Marco Serafini. On barriers and the gap between active and passive replication.

Bojun Huang and Thomas Moscibroda. Conflict Resolution and Membership Problem in Beeping Channels

Li Lu and Michael L. Scott. Generic Multiversion STM

Kunlong Zhang, Yujiao Zhao, Yajun Yang, Yujie Liu and Michael Spear. Practical Non-blocking Unordered Lists

Ashish Choudhury, Martin Hirt and Arpita Patra. Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity

Paul Bunn and Rafail Ostrovsky. Secure End-to-End Communication with Optimal Throughput and Resilient Against Malicious Adversary

Johannes Dams, Martin Hoefer and Thomas Kesselheim. Sleeping Experts in Wireless Networks

Alex Kravchik and Shay Kutten. Time Optimal Synchronous Self Stabilizing Spanning Tree

Mohsen Lesani and Jens Palsberg. Proving Non-opacity

Silvio Frischknecht, Barbara Keller and Roger Wattenhofer. Convergence in (Social) Influence Networks

Cyril Gavoille, Christian Glacet, Nicolas Hanusse and David Ilcinkas. On the Communication Complexity of Distributed Name-Independent Routing Schemes

Sebastian Kniesburges, Andreas Koutsopoulos and Christian Scheideler. CONE-DHT: A distributed self-stabilizing algorithm for a heterogeneous storage system

Danny Hendler, Alex Naiman, Sebastiano Peluso, Francesco Quaglia, Paolo Romano and Adi Suissa. Exploiting Locality in Lease-Based Replicated Transactional Memory via Task Migration

Emanuele Guido Fusco, Andrzej Pelc and Rossella Petreschi. Use knowledge to learn faster: Topology recognition with advice

Sebastian Daum, Seth Gilbert, Fabian Kuhn and Calvin Newport. Broadcast in the Ad Hoc SINR Model

Gadi Taubenfeld. Fair Synchronization

David Woodruff and Qin Zhang. When Distributed Computation is Communication Expensive

Nuno Diegues and João Cachopo. Practical Parallel Nesting for Software Transactional Memory

Ittay Eyal, Idit Keidar, Stacy Patterson and Raphael Rom. In-Network Analytics for Ubiquitous Sensing

Erez Petrank and Shahar Timnat. Lock-Free Iterators

Sagar Chordia, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam and Kapil Vaswani. Asynchronous Resilient Linearizability

Olivier Bournez, Jonas Lefèvre and Mikael Rabie. On trustful population protocols

Chen Avin and Robert Elsässer. Faster Rumor Spreading: Breaking the log n Barrier

Faith Ellen and Philipp Woelfel. An Optimal Implementation of Fetch-and-Increment

Erez Kantor, Israel Cidon and Shay Kutten. Prudent Opportunistic Cognitive Radio Access Protocols

James Hegeman and Sriram Pemmaraju. A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location

Tomasz Jurdzinski, Dariusz Kowalski, Grzegorz Stachowiak and Michal Rozanski. Distributed Broadcasting in Wireless Networks under the SINR Model

Lélia Blin and Sébastien Tixeuil. Compact Deterministic Self-Stabilizing Leader Election: The Exponential Advantage of Being Talkative.

Michael Dinitz and Merav Parter. Braess’s Paradox in Wireless Networks: The Danger of Improved Technology

Brief Announcements

Hammurabi Mendes, Maurice Herlihy and Christine Tasson. The Topology of Asynchronous Byzantine Colorless Tasks

Marcin Bienkowski, Nadi Sarrar, Stefan Schmid and Steve Uhlig. Dynamic Forwarding Table Aggregation without Update Churn: The Case of Dependent Prefixes

Carlos Gómez-Calzado, Alberto Lafuente, Mikel Larrea and Michel Raynal. Revisiting Dynamic Distributed Systems

Trevor Brown, Faith Ellen and Eric Ruppert. A General Technique for Non-blocking Trees

Chen Avin, Michael Borokhovich, Zvi Lotker and David Peleg. Distributed MST in Core-Periphery Networks

Faith Ellen, Rotem Oshman, Toni Pitassi and Vinod Vaikuntanathan. Private-Channel Models in Multi-Party Communication Complexity

Danny Dolev and Christoph Lenzen. Silence is Golden: Communication-Efficient Consensus Without a Common Clock

Aravind Natarajan and Neeraj Mittal. A Concurrent Lock-Free Red-Black Tree

Sergio Rajsbaum, Michel Raynal and Julien Stainer. What Can Be Computed in the Presence of Concurrent Solo Executions

Nuno Diegues and Paolo Romano. Time-warp: lightweight abort minimization in Transactional Memory

Yonina Eldar, Idit Keidar and Stacy Patterson. Distributed Compressed Sensing for Sensor Networks

Gregory Chockler, Dan Dobre and Alexander Shraer. Consistency and Complexity Tradeoffs for Highly-Available Multi-Cloud Store

Nhan Nguyen, Philippas Tsigas and Håkan Sundell. ParMarkSplit: A Parallel Mark-Split Garbage Collector Based on a Lock-Free Skip-List

Christian Cachin, Dan Dobre and Marko Vukolić. BFT Storage with 2t+1 Data Replicas

Heger Arfaoui and Pierre Fraigniaud. Local Decision and Verification with Bounded-Size Outputs

Marco Canini, Petr Kuznetsov, Dan Levin and Stefan Schmid. The Case for Reliable Software Transactional Networking

Cédric Auger, Zohir Bouzid, Pierre Courtieu, Sébastien Tixeuil and Xavier Urbain. Certified impossibility results for Byzantine-tolerant mobile robots


2013 Edsger W. Dijkstra Prize Announced

TADDS 2013 workshop website is on-line

Disc 2013 Sponsors