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.
Category Archives: Uncategorized
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
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.
Abstract:
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.
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
