PODC 2014 Workshop
July 15, 2014
TADDS is glad to announce the 4 invited speakers that will give lectures:
- Idit Keidar, Dept. of Electrical Engineering, Technion (Haifa, Israel)
- Anne-Marie Kermarrec, Inria Rennes – Bretagne Atlantique (Rennes, France)
- Paul Spirakis, Department of Computer Engineering & Informatics, University of Patras, School of Engineering (Patras, Greece)
- Roger Wattenhofer, TIK, ITET; ETH Zurich (Zurich, Switzerland)
- 13:30-14:15 : Roger Wattenhofer, joint session with DSDN 2014
- Managing Dynamic Networks: Distributed or Centralized Control?
- Abstract: What if a node or edge of a network fails? What if traffic between two nodes grows or shrinks? Clearly this is a case for distributed algorithms! After all, the Internet and its protocols are decentralized by design. Thanks to redundancy and distributed communications, Paul Baran suggested that the Internet could operate even if many of its links and nodes had been destroyed by a “nuclear attack”. However, it turns out that distributed control leaves quite some efficiency on the table. Recently several companies started to organize their enterprise networks in a centralized fashion, separating data and control planes by means of software-defined networks (SDNs). So we might soon see a world where a (possibly fault-tolerant but nevertheless) centralized controller is making all routing and transport decisions, using SDN-switches to implement these decisions. Is this the death of distributed network algorithms? In my talk I will discuss why this is not necessarily true, that is, why even central control may learn from distributed computing when dealing with network dynamics.
- 13:15-15:00 : Idit Keidar
- The subtle differences among models with infinitely many processes.
- Abstract: We study wait-free constructions in asynchronous models with infinitely many processes. We show that a key distinguishing factor among known models lies in the existence of multi-writer registers. In fact, in previously defined shared memory models with infinitely many processes, implementing such registers from single-writer ones is impossible. We show that this impossibility can be circumvented by switching to a dynamic model, where process arrivals are pre-announced via explicit add operations; a similar model was previously used by DynaStore in emulating shared memory in a message-passing model with infinitely many processes. DynaStore is wait free in a dynamic model with finite concurrency, where the number of process additions that overlap any operation is finite. We show that such emulation is not possible, however, under infinite concurrency. To circumvent the latter impossibility result, we enhance the model with a failure detector oracle.
(joint work with Alexander Spiegelman)
- 15:00-15:30 : Coffee Break
- 15:30-16:15 : Anne-Marie Kermarrec
- Catch me if you can; Privacy-Preserving Dissemination in Micro-Blogging
- Abstract: Online micro-blogging services and social networks, as exemplified by Twitterand Facebook,have emerged as an important means of disseminating information quickly and at large scale.A standard mechanism in micro-blogging that allows for interesting content to reach a wider audience is that of reposting (i.e., retweeting in Twitter, or sharing in Facebook) of content initially posted by another user.
Motivated by recent events in which users were prosecuted merely for reposting anti-government information, we present riposte, a randomized reposting scheme that provides privacy guarantees against such charges.
The idea is that if the user likes a post, riposte will repost it only with some (carefully chosen) probability; and if the user does not like it,riposte may still repost it with a slightly smaller probability.These probabilities are computed for each useras a function of the number of connections of the user in thenetwork, and the extent to which the post has already reached those connections.
The choice of these probabilities is based on results for branching processes, and ensures that interesting posts (liked by a large fraction of users) are likely to disseminate widely, whereas uninteresting posts (or spam) do not spread.
We quantify riposte’s ability to protect usersin terms of differential privacy and provide analytical bounds on the dissemination of posts.We also report on experimental results based on topologies of real networks, including Twitter, Facebook, Renren, Google+ and LiveJournal.
(joint work with G. Giakkoupis, R. Guerraoui, N. Mittal)
- 16:15-17:00 : Paul Spirakis
- Dissemination and Connectivity Issues in Temporal Networks
- Abstract: We consider here Temporal (aka Dynamic) Networks both from a Distributed Computing and a Structural point of view. Such networks are defined by a labeling L assigning a set of discrete time-labels to each edge of the graph G of the network. The labels indicate the discrete time moments at which the edge is available. We first study the propagation of influence and computation in temporal networks that are possibly disconnected at every instant. We focus on a synchronous message-passing communication model with broadcast and bidirectional links. Our network dynamicity assumption is a worst-case dynamicity controlled by an adversary scheduler, which has received much attention recently. We only impose minimal temporal connectivity conditions. Based on this, we define several novel metrics for capturing the speed of information spreading in a dynamic network. Moreover, we investigate termination criteria in networks in which an upper bound on any of these metrics is known.
We exploit our termination criteria to provide efficient (and optimal in some cases) protocols that solve the fundamental counting and all-to-all token dissemination problems. We then focus on path problems of temporal networks. We begin by giving efficient algorithms for computing shortest time-respecting paths. We then prove a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally we propose two cost minimization parameters for temporal network design. One is the “temporality” of G, in which the goal is to minimize the maximum number of labels per edge and the other is the temporal cost of G, where the goal is to minimize the total number of labels used.
Optimization of these parameters is subject to some connectivity constraints. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graphs like rings, trees, directed acyclic graphs. We also examine how hard is to compute (even approximately) such costs.
(joint work with O. Michail, G.B. Mertzios, and I. Chatzigiannakis)
Following five successful TADDS workshops — at DISC 2009 in Elche, Spain; at DISC 2010 at Cambridge, Massachusetts; at DISC 2011 in Rome, Italy; at OPODIS 2012 in Rome, Italy; and at DISC 2013 in Jerusalem, Israel — and the successful 1st International Workshop on Dynamicity (DYNAM 2011) co-located with OPODIS 2011 in Toulouse, France — we are happy to announce the sixth TADDS Workshop to be held in July 2014 in Paris, France, co-located with PODC 2014.
TADDS 2014 has its focus on the dynamic aspects of distributed systems, encompassing systems in existence today and looking into the future development and deployment of dynamic distributed systems, with sound theoretical foundations in mind. Distributed systems are rapidly evolving, and the advent of new classes of applications and technologies, such as VANET, Airborne Networks, Social Networks, Smart Environments, P2P, broad area supercomputing, and distributed cloud services, is radically changing the way we think about them. Dynamic distributed systems have structures that are self-defined at any instant by entities that might autonomously decide to participate in the same distributed application. These systems are characterized by dynamic arrival and departure of participating entities and normally it may not be possible to assume anything about the universe of participants, their identities, capabilities, or reliability. Understanding the fundamentals of how to master this dynamic dimension is of primary importance to design of robust, dependable, and predictable distributed systems.
This workshop, held in conjunction with the Symposium on Principles of Distributed Computing (PODC), is intended to both motivate further concerted study and analysis of dynamic distributed systems and to present current accomplishments in this area. The meeting will include a couple of invited presentations that will provide views of the main achievements in this area to date, and motivate research by reviewing key challenges and formulating new directions. Topics of interest cover all aspects of dynamic distributed systems, including, without being limited to:
- Modeling dynamic systems
- Suitable environment assumptions (e.g., churn, failure models,…)
- Suitable platform assumptions (e.g., communication paradigm,…)
- Assumptions about the initial knowledge of participants
- Communication and Coordination Abstractions and Services for Dynamic Distributed Systems
- Algorithms in, and structure of, dynamic systems
- Computation paradigms and algorithmic patterns
- Membership/participation in the computation
- Algorithms: dependability, resilience
- Algorithms for Unmanaged applications
- Efficiency of dynamic systems
- Measuring efficiency and scalability
- Complexity measures for dynamic systems
- Application domains for dynamic systems
- Sensor Networks
- Mobile networks
- Cloud computing federation
- Internet supercomputing
- Smart environments
- Social Networks
- Fault tolerance for dynamic systems
- Self-stabilizing Algorithms
- Self-* computation
The steering committee is composed of
- Roberto Baldoni, Università La Sapienza di Roma (Italia)
- Lélia Blin, LIP6 / Université d’Ervy (France)
- Yann Busnel, LINA / Université de Nantes (France)
- Alexander A. Shvarsman, University of Connecticut (USA)