1st Workshop on Storage, Control, Networking in Dynamic Systems (SCNDS)


Sunday, November 5th, 2017 in Boston, MA, USA

Co-located with SSS 2017

Workshop address:
Boston University Photonics Center

We are excited to announce the 1st workshop on Storage, Control, Networking in Dynamic Systems (SCNDS). The workshop is interdisciplinary and touches storage systems, control systems, distributed computing as well as networking. It is intended as a forum where people with different backgrounds can learn from each other. We want to attract both industry relevant papers as well as papers from academic researchers working on the foundations of dynamic systems.

"Dynamic system" is defined broadly here. Following are some of the areas of interest, but not strictly limited to these topics:

Storage in dynamic networks, e.g., MANET, VANET

Control in dynamic systems

Erasure-code based storage systems

Consistency and erasure-codes

Consistency in dynamic networks

Web caching

Storage in data-centers

Big Data in clouds for IoT

Data storage in Fog/Edge Computing

Archival storage systems

Cryptocurrency systems

Cloud storage

Design, implementation, evaluation, and deployment of storage systems

Performance evaluation of networked storage systems

Fault-tolerant storage in dynamic networks

New directions on networking techniques


Keynote

Title:        Message-Passing Implementations of Shared Data Structures
Speaker:    Jennifer Welch, Texas A&M University
Abstract:
Message-Passing Implementations of Shared Data Structures
Edward Talmage and Jennifer L. Welch
Department of Computer Science and Engineering
Texas A&M University

Distributed storage, or shared data, is a vital mechanism for communication among processes in distributed systems, and facilitates the development of higher-level applications.  Although shared data is a convenient abstraction, it is not generally provided in large-scale distributed systems.  Instead, processes keep individual copies of the data, and communicate by sending messages to keep the copies consistent.  After providing background on this topic, we will focus (separately) on two intriguing aspects:  systems that experience churn, where the set of participating processes changes dynamically; and target data structures whose specifications are relaxed.

We will present a recent algorithm for implementing a shared register in a dynamic system with ongoing churn that works in an asynchronous system.  The algorithm is correct as long as the number of processes entering and leaving during a fixed time interval is at most a constant fraction of the current system size. The algorithm tolerates process crashes as long as the number of failed processes in the system is at most a constant fraction of the current system size.  We also show a lower bound on the crash-resilience for this problem.  This work is by Attiya, Chung, Ellen, Kumar, and Welch.

Finally, we will consider distributed implementations of shared data structures with relaxed specifications.  Strongly consistent implementations of shared objects with strict semantics are provably expensive, fueling interest in relaxations.  A data type relaxation adds a small amount of non-determinism to the specification which can reduce the required frequency of expensive synchronization. We will present recent algorithms for different kinds of relaxed queues as well as lower bounds on the worst-case and amortized operation latency for the problem.  Our results show that the algorithms are asymptotically optimal and that there is an inherent complexity gap between different levels of relaxation.  This work is by Byrnes, Talmage, and Welch.

Tutorial

Title:         Erasure Coding in Consistent Object Stores: Advantages, Challenges and Opportunities
Speaker:     Prakash Narayana Moorthy and Kishori Konwar, MIT
Abstract:
Distributed storage systems is at the heart of storing large volumes of data in almost every sphere of life. Replication based storage algorithms provides fault-tolerance and consistency. Erasure codes are increasingly being use to achieve fault tolerance, data durability and scalability. However, combining erasure-codes and consistency mechanisms is challenging. This tutorial will focus on use of erasure-codes on consistency algorithm, the state-of the art techniques and potential challenges leading to interesting research problems.. This brief tutorial with introduce concepts on consistency, erasure-codes followed by some algorithms and existing practical systems, such as, Giza, OpenStack Swift. The talk will be accessible to anyone with a background a basic knowledge on algorithms or programming.

Invited Talks

Title:         Event Driven Cloud Architectures for IoT
Speaker:     Mohan Muppidi, iRobot
Abstract:
Industry is always in the quest for scalable, resilient, and economical computational resources. Emergence of cloud computing changed the way companies dealt with their computational infrastructure needs. On-demand resources and "pay for what you use" model of cloud computing made it easy to build scalable and resilient systems with very minimal operational costs. Serverless computing is a new paradigm in cloud computing where most of the infrastructure pain points like scalability, maintenance etc., are taken care of by the cloud vendor itself. Now serverless resources can be used to build resilient systems with further reduced costs. Event driven architectural patterns stand out in serverless world. In this talk, I will give a brief introduction to serverless computing, event driven architectural patterns and examples on how AWS serverless computing resources can be used in building event driven backend for IoT.

Title:         Characterizing and Adapting the Consistency-Latency Tradeoff in Distributed Key-value Store
Speaker:     Muntasir Raihan Rahman, Microsoft Azure
Abstract:
The CAP theorem is a fundamental result that applies to distributed storage systems. In this article, we first present and prove two CAP-like impossibility theorems. To state these theorems, we present probabilistic models to characterize the three important elements of the CAP theorem: consistency (C), availability or latency (A), and partition tolerance (P). The theorems show the un-achievable envelope, that is, which combinations of the parameters of the three models make them impossible to achieve together. Next, we present the design of a class of systems called Probabilistic CAP (PCAP) that perform close to the envelope described by our theorems. In addition, these systems allow applications running on a single data center to specify either a latency Service Level Agreement (SLA) or a consistency SLA. The PCAP systems automatically adapt, in real time and under changing network conditions, to meet the SLA while optimizing the other C/A metric. We incorporate PCAP into two popular key-value stores: Apache Cassandra and Riak. Our experiments with these two deployments, under realistic workloads, reveal that the PCAP systems satisfactorily meets SLAs and perform close to the achievable envelope. We also extend PCAP from a single data center to multiple geo-distributed data centers. This is joint work with Lewis Tseng, Son Nguyen, Indranil Gupta, and Nitin Vaidya.

Title:         Distributed Statistical Learning in Adversarial Settings
Speaker:     Lili Su, MIT
Abstract:   
We consider the distributed statistical learning problem over decentralized systems that are prone to adversarial attacks. This setup arises in many practical applications, including Google’s Federated Learning. Formally, we focus on a decentralized system that consists of a parameter server and m working machines; each working machine keeps N/m data samples, where N is the total number of samples. In each iteration, up to q of the m working machines suffer Byzantine faults – a faulty machine in the given iteration behaves arbitrarily badly against the system and has complete knowledge of the system. Additionally, the sets of faulty machines may be different across iterations. Our goal is to design robust algorithms such that the system can learn the underlying true parameter, which is of dimension d, despite the interruption of the Byzantine attacks. In this paper, based on the geometric median of means of the gradients, we propose a simple variant of the classical gradient descent method. We show that our method can tolerate q Byzantine failures up to 2(1+ \epsilon)q ≤ m for an arbitrarily small but fixed constant \epsilon> 0. The parameter estimate converges in O(log N) rounds with an estimation error on the order of max{ \sqrt{dq/N},  \sqrt{d/N}}, which is larger than the minimax-optimal error rate \sqrt{d/N} in the centralized and failure-free setting by at most a factor of \sqrt{q}. The total computational complexity of our algorithm is of O((N d/m) log N) at each working machine and O(md + kd log3 N) at the central server, and the total communication cost is of O(md log N). We further provide an application of our general results to the linear regression problem.

A key challenge arises in the above problem is that Byzantine failures create arbitrary and unspecified dependency among the iterations and the aggregated gradients. To handle this issue in the analysis, we prove that the aggregated gradient, as a function of model parameter, converges uniformly to the true gradient function.

Accepted Papers

Title: Jointly Optimal Routing and Caching for Arbitrary Network Topologies (Extended Abstract)
Authors: Stratis Ioannidis and Edmund Yeh
Abstract:
We study a problem of fundamental importance to ICNs, namely, minimizing routing costs by jointly optimizing caching and routing decisions over an arbitrary network topology. We consider both source routing and hop-by-hop routing settings. The respective offline problems are NP-hard. Nevertheless, we show that there exist polynomial time approximation algorithms producing solutions within a constant approximation from the optimal. We also produce distributed, adaptive algorithms with the same approximation guarantees. We simulate our adaptive algorithms over a broad array of different topologies. Our algorithms reduce routing costs by several orders of magnitude compared to prior art, including algorithms optimizing caching under fixed routing.

This is an extended abstract of paper "Jointly Optimal Routing and Caching for Arbitrary Network Topologies" that appeared in ACM ICN 2017 in Berlin, Germany.

Title: Formalizing Distributed Ledger Objects
Authors: Antonio Fernandez Anta, Chryssis Georgiou, and Nicolas Nicolaou
Abstract:
In his PODC’ 2017 keynote address, Maurice Herlihy pointed out that despite the hype about blockchains and distributed ledgers, no formal abstraction of these objects has been proposed. To face this issue, in this paper we provide a proper formulation of a distributed ledger object. In brief, we define a ledger object as a sequence of records, and we provide the operations and the properties that such an object should support. We then provide a variation of the ledger – the validated ledger – which requires that each record in the ledger satisfies a particular validation rule. A (validated) ledger is distributed if it is implemented on top of multiple (possibly geographically dispersed) computing devices.
Link: TBA

Title: Joining Local Knowledge to Communicate Reliably (Extended Abstract)
Authors: Aris Pagourtzis, Giorgos Panagiotakos, and Dimitris Sakavalas
Abstract:
A fundamental primitive in distributed computing is Reliable Message Transmission (RMT), which refers to the task of correctly sending a message from a party (or player) to another, in a network where some intermediate relays might be controlled by a Byzantine adversary. We address the problem under the realistic assumption that the topological knowledge of players is restricted to a certain subgraph and specifically study the role of local information exchange in the feasibility of RMT. We employ the General Adversary model of Hirt and Maurer and the recently introduced Partial Knowledge Model which subsume all known models for the adversary and local knowledge respectively. Tight feasibility conditions, naturally involving the network topology, the adversary and the local knowledge of players, are presented.
Link: https://arxiv.org/abs/1711.01725

Title: When Cars Meet Distributed Computing: Data Storage as an Example
Authors: Lewis Tseng, Takamasa Higuchi, and Onur Altintas
Abstract:
As cars are ubiquitous they could play a major role in a next generation communication and computation framework. In the last years, the development of vehicle-to-vehicle communication and vehicle-to-infrastructure communication took huge steps forward and therefore gives us the tools to build “mobile computing service” on cars equipped with computation capabilities. Recently, several groups of researchers independently proposed the design of “vehicular clouds” that materializes the concept. In this paper, we introduce a new paradigm of the vehicular clouds, followed by a case study of data storage on top of the proposed cloud. Finally, we present several challenges and opportunities in the intersection of vehicular clouds and distributed computing.

Registration

All non-student attendees must register through the registration website of SSS 2017 at https://sss17.eventbrite.com/. There are several registration packages, so make sure that you choose one that covers (possibly among other activities) the workshops.

Note: Students' participation in the workshops/tutorials will be free of charge.

Please also fill out the Google sign-up form so that we can keep track of the number of attendees: https://goo.gl/forms/6kRRnptNF7PLHh5H3


Schedule


12:00~12:30  -- Lunch*

12:30~1:30   -- Keynote by Jennifer Welch
                        Title: Message-Passing Implementations of Shared Data Structures

1:30~2:40     -- Tutorial by Prakash Narayana Moorthy and Kishori Konwar
                        Title: Erasure Coding in Consistent Object Stores: Advantages, Challenges and Opportunities

2:40~2:50     -- Break

2:50~3:20     -- Mohan Muppidi
                        Titile: Event Driven Cloud Architectures for IoT

3:20~3:45     -- Muntasir Raihan Rahman
                        Title: Characterizing and Adapting the Consistency-Latency Tradeoff in Distributed Key-value Store

3:45~4:10     -- Stratis Ioannidis and Edmund Yeh
                        Title: Jointly Optimal Routing and Caching for Arbitrary Network Topologies

4:10~4:20     -- Break

4:20~4:45     -- Antonio Fernandez Anta, Chryssis Georgiou, and Nicolas Nicolaou
                        Title: Formalizing Distributed Ledger Objects

4:45~5:10     -- Aris Pagourtzis, Giorgos Panagiotakos, and Dimitris Sakavalas
                        Title: Joining Local Knowledge to Communicate Reliably

5:10~5:35     -- Lili Su
                        Title: Distributed Statistical Learning in Adversarial Settings

5:35~6:00     -- Lewis Tseng, Takamasa Higuchi, and Onur Altintas
                        Title: When Cars Meet Distributed Computing: Data Storage as an Example

6:00~            -- SSS Reception*


* Lunch and Reception are only available to those who paid the SSS registration fee.


Call for presentations

We invite submissions of extended abstracts describing recent results relevant to the workshop. We especially welcome extended abstracts describing new insights and/or application studies even if these are not fully formed. A major goal of the workshop is to explore new directions and approaches; thus, we encourage the submission of ongoing work. Selected contributors would be asked to present, discuss and defend their work at the workshop.

By default, the submissions will be evaluated for either oral or poster presentation, though authors may indicate in their submission if it should be only considered for one of the presentation types.

Submissions should be in PDF and include title, author information, and a 2-page extended abstract (plus references). Shorter submissions are also welcome, particularly for poster presentation.

Please use the following EasyChair submission link:
https://easychair.org/conferences/?conf=scnds2017


Important Dates

Oct. 10, 2017 - Extended abstract submission deadline, 23:59 Honolulu time
Oct. 20, 2017 - Decision notifications
Nov. 5, 2017  - Workshop


Note: The workshop will include an electronic published proceedings (citable). However, we welcome submissions of extended abstracts describing work that has appeared or is expected to appear in other venues. Please indicate clearly with the submission if the work has already been presented/accepted elsewhere.


Program/Organizing Committee

Antonio Fernandez Anta - IMDEA Networks Institute, Madrid, Spain
Dongjae Kim - Twitter
Kishori Konwar - Massachusetts Institute of Technology (Co-Organizer)
Chung-Wei Lin - Toyota InfoTechnology Center, USA
Prakash Narayana Moorthy - Massachusetts Institute of Technology
Nicolas Nicolaou - University of Cyprus
Lili Su - Massachusetts Institute of Technology
Muntasir Raihan Rahman - Microsoft Azure
Paul Rimba - Data61|CSIRO
Lewis Tseng - Boston College (Co-Organizer)