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 a 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 "about 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.

This assignment requires that projects 3 and 4 work at some basic level. The project 5 protocol is based on RPC, and uses DDNS to keep track of where community participants are currently located. The DDNS use is quite basic, though, just simple resolution of names like htc.jz.cse461. Additionally, we're willing to hoist the names you want to use for this project into the root server (create A or NS records for them there), so that you won't need to keep a server running, and to reduce name resolution to the simplest possible case.

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.

SNet needs some non-volatile storage, because information about community members and photos should survive the phone being turned off. I've written some utility code 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 specifying 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.)

The generation number associated with each member is basically a sequence number. Each time that member takes a picture, or chooses one from among those shared by friends, the generation number is increased by one. Suppose some member, foo, calls member bar, and bar has a record for member jz.cse461 with generation value 15. If foo's current record for jz.cse461 has a generation number less than 15 (or doesn't exist at all), bar returns its record, which foo then uses to update what it knows about jz.cse461. Conversely, if foo's existing record is generation greater than 15r, bar doesn't return a record for jz.cse461, but instead updates its own record. (If foo's existing record also has generation number 15, bar neither returns its record not updates it.)

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, and that I'm sometimes inconsistent in my taste for case.)

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 a possibly vain 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, ...]})

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 }

"jz.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 foo to a member bar for whom foo is not a friend, bar will know the hashes of foo's photos but will not have copies of them. bar may then pass foo's member information on to member alice, who then learns foo'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, photodata: encodedData} fetchPhoto(int photohash)

The sole argument is the hash of a photo the caller is requesting. If the callee has the photo, it returns a JSONObject repeating the photo's hash and giving an encoded form of the photo's data. The encoding is needed because JSON is string based, while photo data is binary. The encoding used by SNet is Base64. We distribute a library that can do the encoding and decoding as part of the assignment code.

Errors

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 zero or more times. 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. In my reference implementation, I implemented no scheme. I leave it up to the user to explicitly select a member and start an update exchange. This wouldn't be handy in a real implementation of an SNet-like application, but is fine for this assignment.

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 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, 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.

Implementation Code Structure

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 OS and its services, but they're there, and the SNet implementation relies on them.

This structure is motivated, in part, by the desire to debug the bulk of the code as a console application. Nearly all of the SNet logic is in the controller component, which runs on both Android and desktop Java. The two Android-specific SNet Activities merely draw the screen and field button clicks. Additionally, taking and viewing photos are system specific (requiring use of the camera and a photo browser). All calls that read or modify the community or photo tables are in the portable controller component, however, as is the code that executes the SNet protocol.

My console implementation is intended merely to exercise the controller, allowing it to be debugged. The console UI accepts text commands that correspond to the button clicks of the Android UI, except that the console app has no camera or gallery viewer. I add photos by moving them into the gallery directory and then giving a command naming them. That replaces the camera. Similarly, I choose photos using a command line that specifies the file name, rather than using a photo viewer. You can write a console version if you think it will reduce overall development time, but it's not required by the assignment.

On Android, there are two important types of data and control flow. One is simply Java control flow, shown by the black lines in the figure above. The other is the instantiation of new Android Activities, shown by the red lines. You invoke new Activities using Intents. The new Activity can be code in your own app (e.g., "SNet 2nd Activity" in the figure), or it can be an entirely separate app (e.g., the camera and gallery apps). Intents push the Activity on the stack maintained by Android, which implements the behavior the user expects when s/he hits the back button (which is to return to the previous Activity). When you write an additional Activity within your own app, you can define a new Layout object for it, which provides a GUI for composing the screen.

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 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.

What to Turn In

These instructions cover both content and format. We'd like to automate the routine parts of the grading process (for example, loading your executable on a phone). It will help if you can adhere to the format restrictions, in particular, the placement and naming of files.

Executable

Turn in a .apk file that we can load onto a phone an run. An .apk is an Android executable. Android requires that .apks be signed. Instructions on the process are at http://developer.android.com/guide/publishing/app-signing.html.

Put your .apk in the top level of your turn-in; that is, submit it as an individual file. There should be only one .apk.

Source

Do a clean and then create a .tar.gz file of your entire project (e.g., tar czf jz.tar.gz). Submit that file, again at the top level.

Report

The filename for your report should begin with report. The extent should be appropriate for the type, e.g., .pdf. Once again, submit this at the top level.

Your report begin with the names of the team members, and the name of your application - the name it will appear as when we install your .apk on a phone.

After that:

1. Briefly explain what each of projects 2, 3, and 4 has implemented. For project 2, explain what "the layer below" provides; what is it built on, and what does that provide that project 2 depends on? For all projects, explain what they provide to the layer above. The explanation for each project is probably just a line, or a few lines, but should make clear why the project was needed (or at least was very useful) to move on to the next project.

2. Project 5 claims to be "serverless social networking." (a) What does that mean? (b) Briefly explain a motivation for building such a thing. (c) Briefly describe two advantages of using a server, as compared to the approach Project 5 took.