Assignment Overview

This assignment is about social networks, phone apps, and networking. We'll build a simple, serverless, social network intended to exploit two strengths of social networks: friends as content creators, and friends as content filters. Our system is called SNet.

SNet is a community, a relatively small number of people. Within the community, individuals have friends, which in SNet simply means people whose content and filtering decisions are followed. Friend is not a symmetric relationship in SNet, to avoid having to build a protocol to support symmetry of friendship. Making someone your friend in SNet also doesn't require their agreement, which is handy as we try to debug. Friend is more like the inverse of the subscriber relationship in Twitter than more usual uses of "friend". I'm still calling it "friend," though.

SNet members can take photos, which are then shared. Each member can have no more than one current, shared photo that s/he has taken. Taking a photo replaces the previously taken one. I'll call this the member's my photo, here and in the code.

Additionally, each member has up to one, current chosen photo. This is a photo picked from among the my and chosen photos of all friends There are not set criteria for choosing a photo, but the intent is to pick one that the member thinks his or her friends would also like to see. A side benefit of choosing a photo is that it guarantees the photo remains available, even if the member who originally took it takes another photo.

SNet stores the most recent my and chosen photos of the user and of the user's friends in some directory (whose name and location is implementation dependent). We call this directory the SNet gallery. It contains photos only for the user and for friends of the user, and at most one my and one chosen photo for each.

Photos are shared by gossiping, using a pull scheme. Each member may contact anyone in the community. From that contact they learn what the contacted member knows about who the community members are and what their my and chosen photos are. The unstructured nature of this communication is gossiping. The fact that members ask for updates others may have made is pull; in a push scheme, when a new photo was taken that member would try to push it out. In SNet, taking a new photo doesn't itself cause any communication.

Describing what actually happens when SNet is used is pure speculation, but the basic idea is that "good" photos should propagate more widely than uninteresting ones. In the extreme, some mesmerizing photo might be viewed by every SNet member. In more common circumstances, the fact that each member sees photos only of his/her friends may result in more localized propagation.

This means I'm not sure how many friends you should have. I have in mind "two to four." I don't have in mind that everyone makes everyone else their friend. If the number of friends is too small, the graph over which photos can flow will likely be disconnected. If too large, SNet is less interesting.

You're given some code that implements utility functions, and requires that your implement a standard interface on which grading scripts can rely. The utility code runs in both console and Android modes, but the goal of this assignment is to have an Android application; the console functionality is for debugging. We provide a fully implemented but extremely primitive console test harness that lets you invoke the individual SNet operations of your implementation.

Basic Elements of the Implementation

Community members have names that are identical to the DDNS names of the device(s) they use. At a minimum, your group has one name, the name of your zone. It's attractive to create at least one name for each group member, though (because sharing a name causes unfortunate conflicts in the global SNet application).

Photos are slightly trickier. We need names for them that can be shared, allowing a caller to ask a callee to send a specific photo it wants. The usual character string names for files aren't suitable for this, because they can't be shared across systems reliably. Instead, the names we use are hashes of the file's contents. In particular, we use an MD5 hash, which produces a 32-bit value having the property that it's extremely unlikely that two distinct photos will hash to the same value.

Data Storage

SNet needs some non-volatile storage, because information about community members and photos should survive the phone being turned off. Utility code is provided for this. It presents a simple abstraction of record-based files. There is a file for members, and a file for photos. They contain a record for each member or photo currently known to the SNet instance. You access a particular member or photo record by giving its key value to a read() function. The key value for a member is a fully qualified DDNS name. The key value for a photo is its hash. In addition to its key value, each type of record contains a small number of additional fields. For members, these are a generation number (explained shortly), the names of the member's my and chosen photos (i.e., hash values for them, with value 0 used to indicate "no photo"), and a boolean indicating whether or not this member is a friend. For photos, there is a reference count (the number of times the photo is named in the member table), used for garbage collection, and and the character string name for the file on the local system. (Character string file names are never transmitted to other systems.)

Generation Numbers

The generation number associated with each member provides ordering on the photos advertised by that member. Each time that member takes a picture, or chooses one from among those shared by friends, that member's generation number is increased. Thus, higher generation numbers are assigned to more recent information, and are preferred.

For example, suppose some member, bert, contacts member ernie, and ernie has a record for member elmo with generation value 15. If bert's current record for elmo has a generation number less than 15 (or doesn't exist at all), ernie returns its record, which bert then uses to update what it knows about elmo. Conversely, if bert's existing record has generation greater than 15, ernie doesn't return a record for elmo, but instead updates its own record. (If bert's existing record also has generation number 15, ernie neither returns its record not updates it.)

There are many ways of creating an increasing sequence of generation numbers. SNet requires that a very particular scheme be used. That scheme is discussed on the SNet generation number implementation page

The SNet protocol is designed so that both the caller and callee can update their member tables whenever one contacts the other, and so both end up with the most current member information possessed by either of them no matter which direction the call takes place in. In contrast, photos move only from the callee to the caller (pull). This will be clear when you look at the details of the protocol, which are described next.

The SNet Protocol

SNet communication is via RPC. There are only two calls, shown below using a form of JSON notation. The application name (for use in RPC calls) is snet. The method names are those used in the description below. (Remember that everything is case sensitive.)

The assumption of the protocol is that member information is small, but photos are big. A standard pull by one member from another involves first calling fetchUpdates, providing the caller's complete set of member records plus an array of hash values of photos the member is trying to locate. The callee responds with a set of member records it has that are more up to date than those of the caller, plus a list of hashes for photos the callee can supply. The photos' data is not returned, however.

Once it has the list of available photos, the caller can then make fetchPhoto calls to retrieve photo data, one photo at a time. The protocol makes many calls (and so suffers many RTTs and other overheads) in an attempt to keep each message small. This is motivated by the limitations of Android devices and Android. Because our RPC system must have all message data in memory at once (i.e., RPC cannot stream data from or to a file), and because photos can be big, it's possible to run out of memory at the sender or the receiver. In fact, it's likely, unless some care is taken. (We discuss this in a bit.)

fetchUpdates

{communityupdates: {MemberField, ...}, photoupdates: [int, ...]}
    fetchUpdates(community:{MemberField,...}, needphotos:[int, ...],
                 srcname: String, destname: String)

The srcname field is the SNet name of the caller. The destname field is the SNet name of the callee.

The community argument field is a JSONObject where the keys are members' names, and the value is a JSONObject containing most of a member record:

MemberField ::= membername: {generation: int, myphotohash: int, chosenphotohash:int }

"elmo.cse461": {generation: 12, myphotohash: 1753847829, chosenphotohash: -183347503}

The needphotos argument is a JSONArray of the hash values of photos the caller would like to find the data for. The caller may know about photos for which it has no data because each member stores and exchanges member information about everyone in the community, but stores photo data only for its friends. Thus, if some member information passes from, say, member bert to a member ernie for whom bert is not a friend, ernie will know the hashes of bert's photos but will not have copies of them. ernie may then pass bert's member information on to member alice, who then learns bert's photo hashes and now wants to find copies of their data.

The returned values have the same format as the arguments. The callee compares the community member information passed to it against the information it stores, and returns (only) those records for which its own information is more up to date. The photoupdates array is a hash of photos the callee has that it thinks the caller might be interested in. This must include at least those photos given in the needphotos argument for which the callee has a copy. It may, optionally, include additional photo hashes the callee thinks the caller will soon want - for instance, photos mentioned in the records returned via communityupdates. The caller is expected to, but not obligated to, fetch these photos' data using the fetchPhoto call.

fetchPhoto

{photohash: int, offset: int, length: int, photodata: encodedData}
    fetchPhoto(String srcname, String destname, int photohash, int offset, int maxlength)

fetchphoto allows the caller to retrieve a photo file in chunks of limited size. This is essential on many Android devices, as a single image file may be larger than the amount of memory available to the application.

The first two arguments are the SNet names of the caller and callee. The third argument is the hash of a photo the caller is requesting. The remaining arguments define a contiguous block of image bytes to be returned: the up to maxlength bytes starting at byte offset in the image. offset must be non-negative. maxlength must be positive.

The returned offset and length describe the data returned. The returned offset should always match the argument offset. The returned length indicates the number of image bytes actually returned. If the offset lies beyond the end of the image data, length is zero. Otherwise, length can be any positive value no greater than maxlength; that is, the callee may return fewer than the maximum allowed number of bytes, even if that many bytes exist in the image data.

If the callee has the photo, it returns an encoded form of the requested byte sequence. Encoding is needed because JSON doesn't support transfer of binary data. The encoding used by SNet is Base64, which translates binary data into a sequence of ASCII characters. We distribute a Base64 library as part of the assignment code, in the util project.

Error Handling

If you're unable or unwilling to complete a call, you should return an exception. The protocol doesn't specify any particular exception formats, so we rely just on RPC's generic exception return.

Using the Protocol

The basic idea is to choose some member, call its fetchUpdates method, and then call its fetchPhoto method to retrieve zero or more files. Because SNet is a community, all members are willing to respond to calls from any other member.

The protocol does not specify how often you should call fetchUpdates, or who you should contact, so you are free to implement any scheme. You're asked to briefly describe and justify your scheme in a short writeup you'll turn in.

Learning the Community

You need some way to enumerate the names of all community members. We do this dynamically, using a simple learning approach that happens as a side effect of the protocol described above.

When the non-volatile community records table is initialized, two entries must be put into it, the member whose instance this is, and the root. The very first time your instance comes up, the root provides a way to learn about other members: a fetchUpdates call to it will (a) let it know you now exist, and (b) return the members the root knows about that you don't. Thus, if everyone contacts the root occasionally, we'll all learn about each other. (You might also learn about new members through other paths, but the root is some glue that makes it easy to announce yourself and find out who else exists.)

Your code must implement the calls that enter you and the root into the community table. The library supporting the table provides a handy interface for this, registerMember(String member). It creates a record for the named member if one doesn't already exist, and otherwise does nothing. This means you can call it every time your application starts, without worrying about whether or not the database already existed or is just being created.

SNet Functionality - The Android UI

This is just an overview of the UI in the reference implementation, to help make what the SNet does more concrete. You do not need to build exactly this interface; it's just an example. You should build something you like.

The interface presented when my implementation launches looks like this:

It shows thumbnails of the user's most current my and chosen photos, and provides buttons for the most common activities (which, during debugging, are taking photos and choosing photos). The Take Picture button's implementation requires only the bit of code needed to launch the built-in Camera application. (How to do that is explained on a separate page.) Similarly, the Choose Picture button leads to the built-in Gallery application. Again, almost no code. Finally, the misnamed Update Pictures button leads to another screen of buttons enabling other actions:

At the top is a drop-down list (called a Spinner in Android) with the names of all community members this instance knows about. (I added a bit of code so that "root" is a synonym for the null string. You can do that, but it's optional.) Befriend marks the member as a friend; this instance will try to fetch its photos. Unfriend unmarks it. Contact causes a fetchUpdates call to be made to the member, followed possibly by fetchPhoto calls.

The button at the bottom, FixDB, runs code that looks for inconsistent state in the community and photo tables and tries to fix them. The code behind FixDB is distributed with the project files. It looks for photo records naming files that don't exist; for files in the application's gallery that aren't named by any photo record; for photo records whose stored photo hash doesn't match the file's hash; for photo records that exist but aren't referred to by any community records; and the like. It is destructive. It will modify and delete records in tables. It will also delete photo files. In the worst case (that fixing the DB renders it completely unusable), if you uninstall your app on the phone (or delete the database file for console mode), you'll be starting fresh, with an empty database, so there's not much harm if things go wrong with FixDB.

Implementation Code Structure: Android

The figure below shows the code structure of the Android implementation of the sample solution. You don't have to follow this structure, of course, but it helps explain the main components and how the ones we provide might fit in with your code. Not shown are the Net components and other services from previous projects, but they're there, and the SNet implementation relies on them.

The Android-specific SNet Activity code draws the screen and fields button clicks, but doesn't implement any substantial part of the SNet application logic. We use existing Android applications for taking and viewing photos. This is done using Android Intents, which bear some resemblance to process creation in more conventional system. Intents push a new Activity on a stack maintained by Android, which implements the behavior the user expects when s/he hits the phone's back button.

The BitmapLoader we provide knows how to convert between the size of an image stored in a file and some size desired for display. I used it to create the thumbnail images on my solution's main screen. It's only a few lines of code, taken from the web, and has only one useful function: loadBitmap().

The remainder of the components are system independent. The bulk of the SNet logic is implemented in the SNet Controller. It does all the things you'd expect, based on the description of SNet above.

The Base64 library converts between the raw bytes of an image file and a Base64 encoded String, suitable for transmission using JSON.

The SNetDB461 component provides the record-based files in which member and photo information is stored. Its essential functionality is very simple. The only table operation methods are read(key), readAll(), write(record), and delete(record). The first returns a single table record, the one whose key value is given by the argument. The second returns all records in a table. The third writes a single record, replacing any existing record in the table with the same key value, if one exists. The final method deletes the table record whose key is given in the record argument. Of course, for the actual implementation to be convenient, it has to be a bit more complicated. (For example, it has to define classes representing table records.) A full description is given on this page.

Implementation Code Structure: Console

The console architecture looks like this:

What to Turn In

Turn in:

• Android executable
  You create an Android executable (a .apk file) by right-clicking on the Android project, selecting Export..., then selecting Export Android Application (expand the Android header if it isn't already), and then following the directions. You'll need to create a keystore and key. The passwords for these can be anything you want. We'll install your application on an Anroid 2.3 phone using a command like adb install AndroidApps.apk. You should verify that this will work. One way to do that is to bring up the phone emulator and then to issue that command. (The adb executable is in the platform-tools subdirectory of your Android SDK installation.)

• Source code
  We'd like your entire project. You can try simply zip'ing or tar'ing it all up and submitting it. If that either fails or the upload takes too long, you can substantially reduce the submission size by omitting the Lib and .metadata directories. (The easiest way to do that is to make a copy of everything, then delete those two directories, and then package up what is left.)