Category Archives: Distributed Systems

Link

This seems like an interesting venue for work on edge network distributed systems. Nice to see that we are not the only ones who think that the edge is area worth researching.

 

CFP: Fog Networking for 5G and IoT workshop

>>>>> In conjunction with SECON 2015 <<<<<

=========================================

22 June 2015, SEATTLE – USA

http://secon2015.ieee-secon.org/workshop-program

Important dates

Submission deadline(Hard): April 1st, 2015

Notification of acceptance: April 15th, 2015

Camera Ready: April 30th, 2015

Workshop: June 22nd, 2015

Scope:

Pushing computation, control and storage into the “cloud” has been a key trend in networking in the past decade. Over-dependence on the cloud, however, indicates that availability and fault tolerance issues in the cloud would directly impact millions of end-users. Indeed, the cloud is now “descending” to thenetwork edge and often diffused among the client devices in both mobile and wireline networks. The cloud is becoming the “fog.”

Empowered by the latest chips, radios, and sensors, each client device today is powerful in computation, in storage, in sensing and in communication. Yet client devices are still limited in battery power, global view of the network, and mobility support. Most interestingly, the collection of many clients in a crowd presents a highly distributed, under-organized, and possibly dense network. Further, wireless networksis increasingly used locally, e.g. intra-building, intra-vehicle, and personal body-area networks; and data generated locally is increasingly consumed locally.

Fog Network presents an architecture that uses one or a collaborative multitude of end-user clients or near-user edge devices to carry out storage, communication, computation, and control in a network.

It is an architecture that will support the Internet of Things, heterogeneous 5G mobile services, and home and personal area networks. Fog Networking leverages past experience in sensor networks, P2P and MANET research, and incorporates the latest advances in devices, network systems, and data science to reshape the “balance of power” in the ecosystem of computing and networking.

As the first high-quality IEEE workshop in the emergent area of Fog Networking, this workshop’s scope includes:

–       Edge data analytics and stream mining

–       Edge resource pooling

–       Edge caching and distributed data center

–       Client-side measurement and crowd-sensing

–       Client-side control and configuration

–       Security and privacy in Fog

–       Fog applications in IoT

–       Fog applications in 5G

–       Fog applications in home and personal area networking

Accepted and presented papers will be published in the IEEE FOG Networking Proceedings by the IEEE Computer Society Conference Publishing Services and IEEE Xplore Digital Library.To be published in the IEEE FOG Networking Proceedings an author of an accepted paper is required to register for the workshop at the full (member or non-member) rate and the paper must be presented by an author of that paper at the conference unless the TPC Chair grants permission for a substitute presenter arranged in advance of the event and who is qualified both to present and answer questions.  Non-refundable registration fees must be paid prior to uploading the final IEEE formatted, publication-ready version of the paper.  For authors with multiple accepted papers, one full registration is valid for up to 3 papers.

Workshop Co-Chairs:

Mung Chiang

Arthur LeGrand Doty Professor of Electrical Engineering

Director of Keller Center for Innovation in Engineering Education

Princeton University

Sangtae Ha

Assistant Professor, Computer Science Department

University of Colorado at Boulder

Junshan Zhang

Professor, Electrical and Computer Engineering Department

Arizona State University

Workshop Technical Program Committee:

Bharath Balasubramanian (AT&T Labs)

Suman Banerjee (University of Wisconsin)

John Brassil (HP Labs)

Gary Chan (Hong Kong University of Science and Technology)

Tian Lan (George Washington University)

Athina Markopoulou (UC Irvine)

Rajesh Panta (AT&T Labs)

Chunming Qiao (University of Buffalo)

Moo-ryong Ra (AT&T Labs)

Tao Zhang (Cisco)

Release of “ARC: Analysis of Raft Consensus”

 “ARC: Analysis of Raft Consensus” is now available online as a UCAM technical report. 
http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-857.pdf

Abstract

The Paxos algorithm, despite being synonymous with distributed consensus for a decade, is famously difficult to reason about and implement due to its non-intuitive approach and underspecification. In response, this project implemented and evaluated a framework for constructing fault-tolerant applications, utilising the recently proposed Raft algorithm for distributed consensus. Constructing a simulation framework for our implementation enabled us to evaluate the protocol on everything from understandability and efficiency to correctness and performance in diverse network environments. We propose a range of optimisations to the protocol and released to the community a testbed for developing further optimisations and investigating optimal protocol parameters for real-world deployments.

Thank you everyone for your feedback.

Seeking Feedback on “ARC: Analysis of Raft Consensus”

My undergraduate dissertation “ARC: Analysis of Raft Consensus” will be submitted as a UCAM tech report. A draft is available here and I would be very grateful of any feedback.

Title: ARC: Analysis of Raft Consensus

Abstract:
The Paxos algorithm, despite being synonymous with distributed consensus for a decade, is famously difficult to reason about and implement due to its non-intuitive approach and underspecification. In response, this project implemented and evaluated a framework for constructing fault-tolerant applications, utilising the recently proposed Raft algorithm for distributed consensus. Constructing a simulation framework for our implementation enabled us to evaluate the protocol on everything from understandability and efficiency to correctness and performance in diverse network environments. We propose a range of optimisations to the protocol and released to the community a testbed for developing further optimisations and investigating optimal protocol parameters for real-world deployments.

EDIT 1: Regarding the difference between this tech report and my dissertation. I have cut out material i didn’t believe would be of general interest, such as how i used VC or lessons learned. If you would like a copy of the original dissertation (probably because your a Part 2 student yourself), just email me and I’ll be happy to provide you a copy.

EDIT 2: I’m pretty much happy to take feedback by any format, Comment below or email me at hh360 @ cam . ac . uk

EDIT 3: A massive thankyou to everyone who has provided feedback and help to disseminate this draft (by retweeting it)

EDIT 4: The code is open source (MIT licence) and available on GitHub. I’ve not linked to as its currently undergoing a refactoring / documenting process ready for release of v0.1. My plan is split the code base into two separate libraries, one will be a event-based simulator for distributed system and the other will be a standalone Raft implementation. I’ll update this blog (& twitter) when the code is ready

EDIT 5:  Wow. The response to this draft has been much greater than I expected (300+ downloads so far). Thank you so much to everyone in the community and of course Diego Ongaro. Diego’s Raft paper is online here and the Raft consensus site is here.

 

Dreaming of a new life on the edge network

Motivation

The internet has abandoned the end-to-end principles on which it was established. With IPv4 addresses depleted, devices are left behind NATs, with the transition to IPv6 yet to restore their public identity. Users have been left isolated by their ISPs, they are pushed to depend on opaque centralised services boosting usability and availability. However, data breaches, DDoS attacks, censorship and mass-surveillance have made individuals re-evaluate their decisions and look for alternatives, a search hindered by data lock-in and network externalities.

The infrastructure exists for building secure distributed systems over a user’s personal cloud of devices. Current approaches require intricate configuration to deal with the diversity of devices, middleboxes and network environments. Developers each try to re-implement solutions to establishing authenticated identities, distributed consensus and availability in the face of mobile nodes, pervasive network partitioning, asymmetric channels and Byzantine failures. Applications sit on top of an unstable stack, which without modification and violation, falls down in the face of everyday challenges, fails to utilise the resources available and slow at deploying new protocols. For example, without Explicit Congestion Notifications wireless traffic is unnecessarily throttled in the face of interference and without Multi-path TCP multiple NICs offer no resilience/speedup for a connection.

With trust in internet services wavering and ever more private data becoming available from the Internet of Things, we must improve on today’s opaque terms of service which minimise legal responsibility and offer few availability guarantees. Can we build a new representation for legally binding contracts between applications and their users, which provides upfront guarantees that are understandable to the user and provably enforced by the application?

State of the Art

Most of the time, devices are underutilised: CPUs idle, storage to spare and bandwidth unused. The premise that the required physical infrastructure already exists, relies in part, on people being willing to share their resources given a good incentive model. BitTorrent will reward you for sharing files with faster downloads, Bitcoin will trade your computation and storage on the blockchain for cryptocurrency and BOINC allows you to contribute to scientific research. Project Tor allows you to share your bandwidth with people around the world seeking anonymity or bypassing censorship, whilst the Public Access WiFi Service (PAWS) allows you to share bandwidth with your local community.

Giving data back to its owners allows individuals to make informed decisions about how exactly to distribute their data. Even if the owner chooses to utilise cloud storage for their data, they can still remain in control with systems like Priv.io which allow the user to provide their own cloud storage and grant 3rd party apps access via their browser. Community efforts to address the usability challenges often involve packaging a collection of P2P alternatives into a plug and play solution such as Freedom Box and arkOS

Approach

Inspired by the previous work in SLAs and financial contracts, I dream of replacing opaque terms of service with a formally defined contract in a domain specific language (DSL). This would allow it to be easily understood by users, stand up in a court of law and be dynamically enforced by the verified applications. But why would service provider choice to adopt such as scheme? Perhaps to minimise expensive legal battles with customers who argue that they didn’t give informed consent} and the poor publicity that follows. Or to difference themselves from the competition, by bowing to users pressure. Ultimately if adopted by a sufficient minority, then regulatory changes could make it the new norm.

Building a personal cloud of devices, ultimately depends on establishing and revoking layers of trust between devices. A popular technique is public key infrastructure, as used in SSL and DNSSEC, but this relies heavily on a trusted certificate authority and sensible key management. I intend to develop an alternative such as utilising a web of trust scheme such as PGP, authenticating a host’s public key by observing it from a range of network vantage points as used in Perspectives or authenticating hosts by consensus as used in Unmanaged Internet Architecture.

I dream we will put aside many of the assumptions which have dominated the discussion on distributed systems, to focus on life at the edge, to build a new federated layer for applications. One which provides consensus algorithms, so data will always be consistent no matter where it is accessed from, even if malicious agents try to gain control of the system. One which puts users first and manages their data responsibly. Unifying an individual’s collection of devices into a secure resilient personal cloud with incentive systems to stimulate fair sharing of excess resources, improving utility and fault tolerance.

Evaluating the project will begin with building applications such as social networking, content distribution or micro blogging over the personal cloud and testing there performance on typical set-ups, against that of centralised services and popular P2P alternatives. Followed by, formal verification of many of the components such as the enforcement of the term of service, as defined by the DSL and the consistency, availability and fault tolerance of distributed system. While a threat model will consider the authentication, encryption and confidentiality properties.

The problem with consensus

A distributed system is collection of nodes, each which there own local memory, which are able to communicate via message passing, cooperate to perform a computation. CAP theorem [1,2] argues that its not possible to achieve consistency, availability and partition tolerance. But machines will fail and there failures are tolerated (to varying extents) by replication. These replicates now need to agree on consistent worldviews, leading to the problem of consensus, originally proposed by [6], Consensus is when these nodes agree on a value, applications for this include:

  • mutable exclusion locks
  • committing a transaction to a database
  • distributed storage such as NFS
  • Implementing reliable broadcast
  • leader election

A protocol for consensus must provide the following to be “correct”:

  • Agreement: all correct nodes arrive at the same value, (the safety property)
  • Validity: the value chosen is one that was proposed by a correct node, (the non-triviality property)
  • Termination: all correct nodes eventually decide on a value, (the liveness property)

A correct node is a node that will eventency make progress so its hasn’t yet and will not experience any of the failures listed below:

QUESTION: Some papers [7] , list a 4th condition called unanimity, stating that if all nodes propose the same value, this will be the value chosen. It appears to me that this is just a case of validity, since the value chosen must have proposed by a node, so if all nodes propose the same value then there is only one possible value to be chosen, according to the validity condition. But this used in a few paper so I can’t be right, so why ? 

The following failures are possible:

  • Fail-stop – nodes may stop but will not restart
  • Fail-recover – nodes may stop and restart
  • Byzantine – nodes behavior unexpectedly, from fault or malicious

Assuming synchronous communication (reliable unicast with known bounded message delay and execution of nodes)  and less than 2/3ds of nodes experience Byzantine failures , we can achieve consensus [3] but a completely asynchronous consensus protocol cannot guarantee consensus with just a single fail-stop node [4], the intuition behind this is that you can’t detect a fail-stopped node, as it my just be slow or its messages not yet delivered. This can be masked by trying to detect failures with waiting on unresponsive nodes, comprising liveness or timeouts/heartbeats comprising accuracy. All consensus algorithms provide consistency but for this they comprises partition tolerance and/or availability.

Henceforth, I would like to consider processes communicating over TCP/IP, making the following assumptions:

  • Nodes have local state, no shared memory and local clocks (though they may be shared when processes are running on the same host)
  • If a path is available, message passing is reliable unicast with unbounded delay (thanks to TCP’s reliable delivery, data integrity and in order delivery) but network partitions are possible
  • Failure detection methods don’t need to be accurate, thus its ok to use timeouts and assume a node is dead when it is infact live
  • A node can tell which node sent a message (e.g. MACs/IPs) so a Byzantine node cannot forge a message which appears to come from an honest host

Approaches:

Two phase commit is depend on a single node, whereas three phase commit [5] can tolerant half its nodes failing but not network partitions or unbounded network delays.

My next post will consider some more complex approaches meeting the above requirements

 

[1] Brewer, E.  Rowards Robust Distributed System. Symposium on Principles of Distributed Computing (PODC).(2000).

[2] Gilbert, Seth, and Nancy Lynch. “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services.” ACM SIGACT News 33, no. 2 (2002): 51-59.

[3 Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine generals problem.” ACM Transactions on Programming Languages and Systems (TOPLAS) 4, no. 3 (1982): 382-401.

[4] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374-382.

[5] Skeen, Dale; Stonebraker, M. (May 1983). “A Formal Model of Crash Recovery in a Distributed System”. IEEE Transactions on Software Engineering: 219–228

[6] Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2) (April 1980) 228–234