4005-730 Distributed Systems
Lecture Notes -- Module 6. P2P and Serverless Systems

Distributed System Architectures

• A three-dimensional space

• Dimension 1: End-to-end communication patterns

                           One-to-many
  One-to-one               Many-to-one              Many-to-many
  0-----1-----2-----3-----4-----5-----6-----7-----8-----9-----10
  

• Dimension 2: Servers

  Central servers                             No central servers
  0-----1-----2-----3-----4-----5-----6-----7-----8-----9-----10
  
  

• Dimension 3: Address configuration

  Preconfigured                                           Ad hoc
  0-----1-----2-----3-----4-----5-----6-----7-----8-----9-----10
  
  

Serverless Systems

• Client-server system
  • End users' machines (clients) talk only to the central machine (server)
  • End users' machines do not talk directly to each other
  • The left end of each architectural dimension

• Get rid of the central server
  • Instead of an architecture with one almighty server and a bunch of puny clients . . .
  • We have all machines the same; they are peers
  • Peer-to-peer (P2P) system
  • Now the end users' machines (peers) have to talk directly to each other
  • The right end of each architectural dimension

• Content distribution
  • Central server based
    • Client makes one connection to server and downloads entire content
    • Web, FTP, RSS, email, etc.
  • P2P based
    • Peer makes one connection to one other peer and downloads entire content -- Napster, Kazaa/FastTrack, Gnutella, etc.
    • Peer makes multiple connections to multiple other peers and downloads different pieces of the content from different peers -- BitTorrent

• Real-time audio/video -- phone calls, videoconferencing
  • Central server based -- most products
  • P2P based -- Skype

• Instant messaging and chat
  • Central server based -- most systems; Internet Relay Chat (IRC), AIM, MSN, Facebook, etc.
  • P2P based -- Direct Client-to-Client (DCC)

BitTorrent

• BitTorrent Protocol Specification. http://www.bittorrent.org/beps/bep_0003.html

• Index of BitTorrent Enhancement Proposals. http://www.bittorrent.org/beps/bep_0000.html

• The origin peer, who wants to make a file available:
  • Splits the file into pieces
  • Computes the SHA-1 hash of each piece
  • Sets up a seed file (.torrent file)
    • Name of the file
    • Length and hash of each piece
    • URL of the tracker
  • Publishes the seed file somewhere, e.g. a web site

• The tracker is a central server
  • Keeps track of which peers have which pieces of the file

• The swarm peers, who want to download the file:
  • Gets the seed file
  • Contacts the tracker
  • Tells the tracker to add itself to the swarm
  • Gets other peers in the swarm from the tracker
  • Downloads pieces of the file from peers
  • Notifies the tracker which pieces it has downloaded
  • Uploads those pieces to other peers

• Trackerless BitTorrent
  • Torrent information is stored in a distributed hash table (DHT) instead of a central tracker
  • The Kademlia DHT is used
  • The DHT key is the SHA-1 hash of the piece of the file
  • BitTorrent DHT Protocol. http://www.bittorrent.org/beps/bep_0005.html

• In theory, as time goes on, the peers download more and more from each other and less and less from the origin peer

• Pros
  • Eliminates big server with enormous bandwidth, needed to download entire file to every user
  • Faster downloads due to multiple simultaneous connections with different peers

• Cons
  • For the system to work well, peers must upload as well as download file pieces
  • Leecher peers that only download and never upload can degrade the system
  • To combat leechers, detect peers that don't upload enough and refuse to download to them (tit for tat)
  • But this unfairly penalizes users with limited upload bandwidth (like home users)
  • There is little to no security against malicious peers

Ad Hoc Collaborative Applications

• Every so-called P2P system has a central server lurking in it somewhere
  • Napster: Central directory of peers and files
  • BitTorrent: Web server with seed file; tracker
  • Trackerless BitTorrent: Web server with seed file
  • DHTs and many other systems: Bootstrapping server

• The Curse of the Internet
  • Internet-wide file sharing is doomed to require some kind of central server because of the Internet architecture
  • If we truly want to get rid of central servers, we must give up the notion of Internet-wide network applications

• Proximal file sharing
  • A file sharing application that runs on a collection of nearby (proximal) devices
  • There are many useful examples of proximal file sharing
    • Folks at a party all want to look at each other's digital photo albums stored in their cameras, PDAs, laptops, etc.
    • My PDA's screen shows your camera's photos -- What You See Is What I Get
    • I want to listen to my MP3 player playing a song stored on your MP3 player -- What You Hear Is What I Get
    • A group authoring session -- everyone uses their own laptop to edit the same file, everyone immediately sees everyone else's edits
    • Group calendar scheduling -- find a free time slot in everyone's calendars stored on their PDAs, schedule a meeting on everyone's calendar
    • Slide presentations with or without a projector -- slides appear on everyones' laptop screens
  • By the way, these proximal file sharing applications should use wireless networking (no cables) and ad hoc networking (devices not preconfigured with each other's addresses)

• Ad hoc collaborative applications
  • A generalization of the above
  • Any distributed system involving a group of nearby devices, many-to-many communication, ad hoc networking, and no central servers

Sidney Harris. "You Want Proof? I'll Give You Proof!" W. H. Freeman and Company, 1991.

Tuple Space -- History

Invented by David Gelernter, Yale University, in the early 1980s "Tuple space" was the concept, "Linda" was the language "Generative Communication in Linda" paper published in January 1985 "Mirror Worlds" book published in 1991 Many implementations of tuple spaces and Linda followed, for C and similar languages The Java language was introduced in 1995 In 1998, IBM released a Java version of a tuple space called TSpaces		David Gelernter
In 1999, Sun Microsystems released a Java version of a tuple space called JavaSpaces along with Jini Network Technology JavaSpaces design team led by Ken Arnold JavaSpaces actually predated Jini, and was an important motivation for developing Jini JavaSpaces is deployed as a Jini service Open source implementations of tuple space Apache River (Java) Blitz JavaSpaces (Java) PyLinda (Python) Rinda (Ruby) SemiSpace (Java) SQLSpaces (Java, C#, PHP, Prolog, Ruby) Commercial implementations of tuple space The Fly Object Space (Java, Ruby, Scala) GigaSpaces (Java, .NET, C++) TIBCO ActiveSpaces (Java, C, C++)		Ken Arnold

Tuple Space Concepts

• Tuple Space (TS)
  • An abstract place that contains tuples
  • Shared by all processes
  • Don't think of a TS as a "server," think of it as an abstraction

• Tuple
  • A record consisting of some number of slots (fields)
  • Each slot has a type
  • Each slot may be empty or contain an actual value of the type

• Operations on TS (atomic)
  • write (tuple) -- Put a tuple into TS
    • Non-blocking
    • Gelernter called this operation "out", JavaSpaces calls it "write"
  • take (tuple) -- Take a tuple out of TS
    • Blocks until a matching tuple is present
    • Gelernter called this operation "in", JavaSpaces calls it "take"
  • read (tuple) -- Read a tuple but leave it in TS
    • Blocks until a matching tuple is present

• Tuple matching on takes and reads
  • When take or read is called, the caller supplies a tuple that acts as a template
  • It finds a tuple in TS that matches the template
  • The tuple must have the same slots and types as the template
  • If a template slot and the corresponding tuple slot both have an actual value, and the values are equal, there is a match
  • If a template slot or the corresponding tuple slot is null, there is a match (wildcard)
  • When a match is found, the read or take operation returns the matching tuple -- the template is filled in
  • (Note: JavaSpaces matching uses a slightly different criterion)

• Processes decoupled in space
  • Sender (writer) doesn't know who receiver (taker) is
  • Receiver doesn't know who sender is

• Processes decoupled in time
  • A tuple can be written before anyone takes it
  • A tuple can be taken before anyone writes it (the take will block)

What is "Tuple Space" really?

• From Gelernter's papers, I get the sense that TS is a communication and coordination mechanism
  • Gelernter speaks of "tuple space," not "a tuple space" or "the tuple space"

• From the JavaSpaces spec, I get the sense that TS is a server or even a database
  • JavaSpaces spec speaks of "a space" or "the space"

• Question: Suppose a process writes a tuple, then the process exits or the host disconnects. What happens to the tuple?

Applications for Tuple Space

• Locks and semaphores

• Shared variables
  • You get atomic updates of a single shared variable (tuple) "for free"

• Message passing

• Distributed data structures
  • Distributed array
  • Distributed linked list
  • Distributed FIFO queue
  • These all fail if tuples can disappear spontaneously
  • Thus, these tend to make sense only if the TS is an independent server

• Master-worker pattern
  • Task bags
  • Result bags
  • Tasks directed to any idle worker (natural load balancing)
  • Tasks directed to a specific worker

• Workflow pattern
  • Similar to master-worker, except a task goes through a sequence of workers

Implementing Tuple Space

• Centralized (server) implementation
  • Almost all the tuple space implementations of which I'm aware use a central server

• P2P implementation
  • Much harder to achieve
  • I'm aware of only a few research implementations
  • A. Murphy, G. Picco, and G. Roman. LIME: a coordination model and middleware supporting mobility of hosts and agents. ACM Transactions on Software Engineering and Methodology, 15(3):279-328, July 2006.

• Yet -- a P2P implementation of tuple space would be an ideal platform for ad hoc collaborative applications

Distributed Systems 4005-730-01 Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2011 Alan Kaminsky. All rights reserved. Last updated 09-OCt-2011. Please send comments to ark­@­cs.rit.edu.