4003-543/4005-742 Ad Hoc Networks Module 2. Collaborative Applications -- Lecture Notes Prof. Alan Kaminsky Rochester Institute of Technology -- Department of Computer Science Tuple Space -- A 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 Sun, GigaSpaces, and IntaMission all provide commercial implementations of the JavaSpaces specification   Ken Arnold In 2003, Alan Kaminsky invented a variation of tuple space called Tuple Board Designed for a serverless ad hoc networking environment First generation implementation by Chaithanya Bondada in 2004 Second generation implementation by Yutao Cheng in 2006 Third generation implementation by Alan Kaminsky in 2006 PKI-based group security implementation by Kyle Morse in progress A different network communication layer is future work Alan Kaminsky 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 (but not both) is empty, there is a match (wildcard) If a template slot and the corresponding tuple slot are both empty, there is no match 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) Tuple Board -- Concepts Tuple Board (TB) An abstract place that contains tuples, like a bulletin board Shared by all devices in an ad hoc network Don't think of a TB as a "server," think of it as an abstraction   Tuple -- same as in TS   Operations on TB (atomic) -- a bit different from TS post (tuple) -- Put a tuple on the TB Non-blocking withdraw (tuple) -- Take a tuple off the TB Non-blocking Only the device that posted a tuple can withdraw the tuple If a device goes away, all of the device's tuples are implicitly withdrawn read (tuple) -- Read a tuple but leave it posted on the TB Blocks until a matching tuple is present There is no take operation   Tuple matching on reads -- nearly the same as TS When read is called, the caller supplies a tuple that acts as a template It finds a tuple on the TB that matches the template The tuple's class must be the same as the template's class or a subclass thereof 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 or both is empty (null), there is a match (wildcard) If a slot's type is itself a tuple, recursive matching is performed When a match is found, the read operation returns the matching tuple -- the template is filled in   Iterators Read all tuples that match a template Each matching tuple is returned just once   Listeners Call a method on a listener object when a tuple that matches a template is posted Call a method on a listener object when a tuple that matches a template is withdrawn   Processes decoupled in space Poster doesn't know who reader is Reader doesn't know who poster is   Processes decoupled in time A tuple can be posted before anyone reads it A tuple can be read before anyone posts it (the read will block) However, both the posting device and the reading device must be present at the same time for the read to succeed Ad Hoc Collaborative Application Design With a Tuple Board Tuple Board Library download page   Tuple Board Library Javadoc   How to write code for the Tuple Board -- See package edu.rit.tb   Design guidelines:   Don't try to simulate message passing with tuples In some sense, posting a tuple is like sending a message, and reading a tuple is like receiving a message But tuple board applications designed this way tend to be far more complicated than they need to be More effort to design and code, more defect prone, more difficult to debug   Don't post tuples to report events The problem is, in an ad hoc setting, devices can come and go at any time A device that posts an "event tuple" might go away immediately thereafter, and other devices might not see the event A device that joins the network might not read previously posted "event tuples" How long to leave the "event tuple" posted before withdrawing it to ensure that all devices have seen it? No way to know.   Do post tuples that give the current state Each device posts a tuple or tuples with its own piece or pieces of the state The complete application state is the combination of all the individual device states When a device's state changes, withdraw the old state tuple and post a new state tuple A new device joining the network can simply read all the state tuples to get "pumped up" with the current application state   Do use a logical clock to put state tuples in order if necessary A logical clock puts items into order in a distributed system without needing a central server A vector clock is an alternative with different ordering properties For further information, see: Distributed Systems I Lecture Notes -- Distributed Algorithms   Do have devices post copies of each others' tuples For persistence of the application state, if necessary Chat Version 1 Package edu.rit.chat01 Interface ChatUIListener -- source code Class ChatUI -- source code Class ChatMessageTuple -- source code Class Chat -- source code   Operation Each chat message is posted as a ChatMessageTuple {user, message, logical clock} Each device has a post listener for ChatMessageTuples Whenever another ChatMessageTuple is posted, the listener is notified, and the chat message is added to the UI Chat messages are added to the UI in logical clock order   Device arrival When a new device arrives, its listener is notified of all existing ChatMessageTuples This "pumps up" the new device with the state of the chat session No extra initialization code needed!   Network partitions If the network partitions, devices on either side of the partition continue to post ChatMessageTuples When the network partition heals, all devices' listeners are notified of the ChatMessageTuples from the other side of the partition This "merges" the partitioned chat session states No extra merging code needed!   Device departure When a device departs, its ChatMessageTuples are implicitly withdrawn This does not affect the existing devices' displays But later arriving devices will not see the departed device's ChatMessageTuples   Security Default: Chat message tuples are not encrypted Specify a secret key on the command line: All chat message tuples are encrypted A user can see only chat message tuples encrypted with the same key Key management must be done outside of the chat application   Limitations of Chat Version 1 There is only one chat room; everyone is in it New devices cannot see departed devices' chat messages Chat Version 2 Package edu.rit.chat02 Interface ChatUIListener -- source code Class ChatUI -- source code Class ChatMessageTuple -- source code Class Chat -- source code   Operation Same as Chat Version 1, plus . . . Each device posts a copy of every other device's tuples, for persistence   Device arrival Same as Chat Version 1   Network partitions Same as Chat Version 1   Device departure When a device departs, its ChatMessageTuples are implicitly withdrawn But the remaining devices still have copies of these tuples posted Later arriving devices will see the departed device's ChatMessageTuples If all devices depart, all the tuples vanish   Security Same as Chat Version 1   Limitations of Chat Version 2 There is only one chat room; everyone is in it Online Survey Version 1 Package edu.rit.survey01 Interface SurveyUIListener -- source code Class SurveyUI -- source code Class NewSurveyDialog -- source code Class SurveyTuple -- source code Class SurveyVoteTuple -- source code Class Survey -- source code   Operation For each survey, each device posts a SurveyVoteTuple: SurveyTuple (nested tuple) Survey name Question First answer Second answer Third answer Fourth answer Index of the answer the user voted for When the user selects or changes a vote, the device withdraws the old SurveyVoteTuple and posts a new SurveyVoteTuple The device has a post-withdraw listener for SurveyVoteTuples When a SurveyVoteTuple is posted, the device adds the survey to the UI if necessary When a SurveyVoteTuple is posted, the device adds the vote to the vote count When a SurveyVoteTuple is withdrawn, the device subtracts the vote from the vote count Logical clock not needed   Device arrival When a new device arrives, its listener is notified of all existing SurveyVoteTuples This "pumps up" the new device with the states of all the surveys No extra initialization code needed!   Network partitions If the network partitions, devices on either side of the partition continue to post SurveyVoteTuples When the network partition heals, all devices' listeners are notified of the SurveyVoteTuples from the other side of the partition This "merges" the partitioned survey states No extra merging code needed!   Device departure When a device departs, its SurveyVoteTuples are implicitly withdrawn Thus, the departed device's votes disappear However, any surveys the departed device created will remain in the other devices   Security Same as Chat Version 1   Limitations of Survey Version 1 Departed devices' votes disappear Online Survey Version 2 Package edu.rit.survey02 Interface SurveyUIListener -- source code Class SurveyUI -- source code Class NewSurveyDialog -- source code Class SurveyTuple -- source code Class SurveyVote -- source code Class SurveyVoteTuple -- source code Class Survey -- source code   Operation For each survey, each device posts a SurveyVoteTuple: SurveyTuple (nested tuple) Survey name Question First answer Second answer Third answer Fourth answer Survey vote Encapsulates all users' votes in the survey Mapping from tuple board ID to vote and logical clock value When the user selects or changes a vote, the device withdraws the old SurveyVoteTuple and posts a new SurveyVoteTuple The device has a post listener for SurveyVoteTuples When a SurveyVoteTuple is posted, the device adds the survey to the UI if necessary The device merges the new survey vote object into the existing survey vote object for that survey For each tuple board ID, keep the vote with the highest logical clock value   Device arrival Same as Survey Version 1   Network partitions Same as Survey Version 1   Device departure When a device departs, its SurveyVoteTuples are implicitly withdrawn But the remaining devices still have the departed device's votes posted in their own SurveyVoteTuples Later arriving devices will see the departed device's votes If all devices depart, all the surveys and votes vanish   Security Same as Chat Version 1   Pix Package edu.rit.pix Class AlbumTuple -- source code Class DisplayList -- source code Class PictureFileTuple -- source code Class PictureId -- source code Class PictureMap -- source code Class PictureTuple -- source code Class SharePix -- source code Class ShowPix -- source code   Class SharePix is a main program that shares a picture album with other users. The album consists of all JPG and PNG files (files whose names end in ".jpg", ".jpeg", or ".png") in a directory specified on the command line. The album's name, owner, description, and date are given by command line arguments. The program is primarily intended to illustrate how to design a collaborative application using the Tuple Board, not to be a full-featured picture sharing program. The program posts on the Tuple Board one AlbumTuple for the album itself. The program posts on the Tuple Board one PictureTuple and one PictureFileTuple for each picture. The program then sits there until killed externally.   Class ShowPix is a main program that displays a slide show of pictures in albums that other users have posted. The program is primarily intended to illustrate how to design a collaborative application using the Tuple Board, not to be a full-featured picture display program. The program reads from the Tuple Board all the posted PictureTuples and PictureFileTuples and displays the pictures as a slide show. Ad Hoc Networks • 4003-543-01/4005-742-01 • Spring Quarter 2007 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2007 Alan Kaminsky. All rights reserved. Last updated 19-Mar-2007. Please send comments to ark­@­cs.rit.edu.