Coordinating Asynchronous Actors – from Tuple Spaces to Tweetflows

The coordination of asynchronous actors has always been a major problem in distributed systems and parallel computing. About 20 years ago, David Gelernter and Nicholas Carriero have introduced the coordination language Linda. The most important difference to existing approaches was that they treated the coordination problem seperately from the computation problem.

Linda implementations offer the four basic operations in, out, rd, and eval for access to a virtual shared memory called the tuple space. Developers do not have to worry about network protocols or message formats because coordination is achieved just by reading data from and writing data to the tuple space. This is facilitated by the facts that read operations block by default until data is available and data can be consumed when read.

Today, another worldwide space connects millions of asynchronous actors: The Twitter network has some features very similar to a tuple space, and it supports basic operations as well. One major difference is that Twitter users do not use the system for coordination in a uniform way so far. Tweetflows could be a solution that not only coordinates human actors, but also integrates computer-provided services.

Another interesting difference between Linda implementations and Tweetflows lies in the type of coupling provided by each system and the resulting semantics: As mentioned before, Linda’s actors are only coupled by the data put into the space — Tweetflows on the other hand implement some kind of message-passing.

Tweetflow NLG – Progress

Hi guys.

I just want to blog some progress i have made. I have now implemented some kind of a game for translating the Tweetflows. For the game you have to fill in the correct article for the service and translate every single attribute given as inputdata. The game part ist that the keyboard which is used randomizes its input keys every time one is pressed, as mentioined in the Score 13 meeting. The buttons differ from each other and each one allways looks the same. For example an „a“ is a blue circle. So you can train to get faster.

But actually, during my testing, it turned out to be quite annoying :D .

Other game ideas i have had, had all in common that you have to „collect“ the letters you want to use. For example in some jump’n'run game like in Donkey Kong Country where you had to collect the „KONG“ letters to get extra points. Implementing such a game would be an own project, but I wanted to get some proof of concept running in my practical lab.

If humans play games, its only a question of time when someone tries to cheat. In a game with a purpose its essential to prevent any cheating, otherwhise the whole game looses its signification. To prevent people from entering a wrong translation, the translation is only persisted if several people have entered the same one. Additionally the people are given known translations to enter so I can test if they are honest, or just try to earn points easily. Hence every person has some trustworthyness value. This value can be used to check how high the probalility is, that the persons update is a valid translation. In the case that some wrong translation achieved it to get persisted to the dictionary, several updates from persons with a high trustworthyness value can correct the wrong translation.

At the moment, I can persist the translated attributes in an local SQLite database, from which the dictionary is backed. Hence the lokal update process is finished.

My next step is implementing the central dictionary which will be realized by a GAE application. After that, the only thing remains will be polishing the UI :) .

Cu.

Bootstrapping Scientific Collaboration

After working several years at university, I find it fascinating that I still don’t know what other people in this huge organization are doing in their research. I was (and still am) busy finishing my PhD thesis and this is probably one of the main reasons for this lack of knowledge. Everyone is busy minding their own affairs and simply has no time to “look around” what other people are doing in their research. You might ask yourself: why would one have interest in the work of others? I think that this question can be easily answered if we regard university as a “knowledge-generating “enterprise”. In companies with knowledge workers it is of paramount importance that knowledge flows through the company. This ensures that people are kept “in the loop” and know what is going on. Moreover, awareness of the work of others has a high potential to generate ideas for one’s own work. Ultimately this leads to more (and more interesting) scientific output and consequently to an improvement of the public awareness of scientific work at universities.

So, what can we do to do improve our internal collaboration and awareness of other scientific works? First of all, we can write about this. And by writing I do not necessarily mean to write more papers (which apart from a few people in the community are not read by a wider audience). I propose to make the scientific process to some degree visible for a bigger audience by simply blogging about the work (see my blog posts explaining idea of public paper writing). This would open the door for collaborations: simply by reading blogs from other groups what their current research is. nother possibility would be to use visual representations like tag clouds to give an overview of their work on their web pages. This often helps to get a quick impression of current group activities. There are additional outlets in social networks as well: Twitter, Facebook or Google+ could be used. Alternatively, the university could set up a Twitter Server (e.g., Status.net) of their own and create accounts for all staff members and students.

The question that remains is how to bootstrap such a process? Well, if you read this (and work at university), you are already taking part in this process. Do this with your own group: start a blog. Tweet about your work. Invite colleagues and students to follow your blog and your twitter account. Make others aware of your work.

your ikangai science team

Making Twitter Secure

A student of mine (Michael Jaros) had the interesting idea to use a public key crypto system to encode tweets. The idea is very simple – just encode the tweet with the public key of the person you want to contact on twitter. Let me illustrate this approach with a simple example: Bob wants to write Alice a private message on Twitter. Thus, Bob looks up Alice’s public key and encodes the Tweet with Alice’s public key. Alice receives Bob’s Tweet and decodes it with her private key. Et voilá: Alice got Bob’s message that nobody else can decode to read it.
There are, however, some details to consider. First of all, public key crypto systems need a certain key length to be secure. This results in messages that are longer than 140 Bytes. This is a problem for Twitter, because encoded messages are longer than 140 Bytes. A potential solution is either to break up the message into several Tweets or simply use a different Twitter Server (e.g., Status.net) where you can change the message length. Alternatively, a text hosting service can be used: an encoded message is put on an external text hosting server and the message URL is posted on Twitter.
This approach works well for peer to peer communication (Bob writes Alice encoded messages). If a message has more than one recipient, this approach does not work anymore. Unless the message is encoded several times (using each recipient’s public key) each receiver must have either the same private key. Or, and this is certainly interesting from a mathematical point of view, there is a way to generate a generic public key from the receivers public keys and to encode the message with this “composite-key”. Every owner of a part of the composite key could then decode the message with their respective private key, without the other recipients knowing this.

your ikangai science team

your ikangai science team

Context and Tweetflows

A master student of mine – Michael Jaros – had an excellent idea how to integrate context information into Tweetflows. Simply by adding a prefix to a Tweetflow command we can easily add arbitrary context information. For example, it is possible to add worker qualifications (similar to Amazon Mechanical Turk) to Service requests:

? {level=native speaker, language=english}:proofread.blogEntry http://www.ikangai.com/blog

A different way to look at this kind of language extension is to regard the prefix as namespace. This, however, requires that the namespace is declared “somewhere”. For example, it can be done like this:

? bquali{level=native speaker, language=english}:proofread.blogEntry http://www.ikangai.com/blog

Each Tweet after the previous one, could use the namespace bquali without having to define it:

? bquali:proofread.blogArticle http://www.ikangai.com/article

Another interesting possibility is to create nested namespaces, which provide for a stepwise refinement:

? bquali.cs{subject=computer science, level=phd}:proofread.blogArticle http://www.ikangai.com/article

We are going to continue our work in this area and will rework the Tweetflow specification in the next weeks.

your ikangai science team

ASCII Art Bar Codes

Bar codes are used on all kind of items. Typically, they encode additional information about the item like a number or an external link.
With the wide spread use of mobile phones, bar codes can be easily scanned by everyone and they are used on a ever growing number of physical “items” like billboards or news papers.

Inspired by ASCII art like

███─█─███─█─█──┏┓┏ ┳┣┓┏┏┫┏┓┗┳┛
█─█─█─█───█─█──┗┛┣ ┃┃┃┣┗┛┣┫ ┃
███─█─█───█─█───────@cerridan─
█───█─███─███────────

we thought of creating bar codes with a different medium, other than images. In particular, we aim at creating bar codes that are made from ASCII symbols which can be read by OCR tools and do not require dedicated bar code reader software. In addition of reusing existing software, we also want to address a weakness of bar codes: unless you scan a bar code, you do not know what is in the bar code. Our idea is to include information that can be read by people into the bar code. We foresee a small text region that explains the bar code content. For example, a text like “http” explains that the bar code points to a web page, “tel” could indicate a telephone number and so on. We believe that we could reuse URL schema for this purpose.
However, there are some challenges that we need to address. First of all, we need to find a design which can be used to include this kind of information seamlessly into the bar code. We consider this as main challenge, because this will need lots of creative work :-) .
Second of all, we need to decide how much data will be encoded in the bar code. Generally speaking, the smaller the amount of data the better. For this purpose, we plan to build an URL shortener that is able to handle different kind of data, besides Web links. In doing so, we use only a few bytes, because we only encode the pointer to the data.

your ikangai science team

Q and A – ? and !

In our last blog post, we discussed the use of +1 in Tweetflows to indicate a recommendation. Now, we are pursuing this idea further by extending the Tweetflow syntax with two additional syntax modifications. We think of representing a Service request(SR) by simply using a question mark. In a similar manner, the publication of a Service (SP) is represented with a exclamation mark. The reasoning behind this is that a Service request is basically a question like Can someone provide me with a Service?. The publication of Service can be regarded as answer to a Service request which was sent to an “audience” (i.e., Twitter followers): Hey, here I am! I can help you with that.
The two examples below show how we intend to use the syntax. The first command represents a Service request to proofread a blogentry:

? @joahnnes2112 proofread.Blogentry http://www.ikangai.com/blog

The second command indicated the completion of the task:

! @ikangai didProofread.Blogentry http://www.ikangai.com/blog

It is worth noting that the exclamation mark can be used to represent the Tweetflow logging syntax (LG) as well.

We will continue our assessment of Tweetflow commands and will look for additional syntax modifications that can help making the syntax more concise and useable.

your ikangai science Team

Distributed Clipboard – file sharing components

Hey again! Since I used my last post to show you the difficulties I experienced during implementing Drag&Drop in combination with JavaFX 2.0, I today want to introduce my file sharing components. After a DropEvent is registered on the GUI (see last post), a new thread responsible for transferring the dropped files is launched. Creating a socket with the receiver´s address enables the actual communication. After a standard handshake,  the receiver itself lauches an own file-receiving thread, in order to provide simultaneous  up- and download of two users.

Before sending the first actual file, the number of all files, including directories, is sent. Why I just don´t send the number of actual files? Well, to provide maintaing the folder structure of the transferred files and to also enable dragging of multiple, nested folders (by holding cmd during selection) I took the following considerations: a folder (also known as root) and all of its nested files and folders share a common prefix of the path (like C:\Users\XYZ\Downloads\rootFolder). The DropEvent return a list of files. In case of one folder being sent, it just contains a single file object. I then sort the list, that all single files (files that were solely selected) appear at the beginning, and folders are attached to its end. Morever, each folder is recursively searched for its contained files.  If you now iterate through this list, printing the absolute file paths, you have a tree like structure.

To be able to rebuild the folder structure I just need to iterate through this list, filter out the directories with a simple if (file.isDirectory()) and then calculate the difference getAbsolutePath().length() – getName().length(). This offset is sent to the receiver, and then all contained files of arbitray nested depth are sent. Before the actual file content is transferred, I have to send the absolutePath. On the receiver´s side I then just have to create a new file for each incoming file, with the correct path of just invoking receivedAbsolutePath.substring(offset) . Of course I have a few more conditions checks, for sending and parsing the offset, and of course there is also a difference in processing single selected files, or files that are nested inside a folder, but basically, this offset is the key to victory.

The file transfer itself uses the standard Java best practice approach: By opening a FileInputStream on each file, they are opened and read in blocks of 16384 bytes into an array of the same size. Before that, by creating a Serversocket on a random port, and sending this random port to the receiver, a new data-channel is set up, which is used for transferring the files. The aforementioned blocks are continually sent by invoking the Outputstream.write() of the socket´s output stream, to which the receiver is bound. After a successful transmittance, streams and socket are closed.

The receiver part of the implementation is of course very similar: I run a for loop, as long as it´s loop-variable reaches the value all files being sent. For each file
being sent, the name is received as well as the port for this specific file. After that, as mentioned above, a new file using  receivedAbsolutePath.substring(offset) is created. Instead of opening a FileInputStream, a FileOutputStream is opened to write the received content into the just created file. Writing the actual file content is then exectued by invoking read() of the socket´s input stream, and writing the received blocks of 16384 bytes via FileOutputStream.write().

As always stay tuned and thanks for your tuning in! :) There will be one more blog entry about the final look&feel of the GUI soon – watch out!

Tweetflow Natural Language Generation

Hi,

My Praktikums-Topic is about creating an Android client for generating natural sentences out of Tweetflows. As you might have read already, Tweetflows are used to create mobile workflows. Tweetflows should be useable by humans, but actually they have a quite technical syntax. If you are not familiar with it and may have not a lot of technical background, you would not know what you should do if you read a Tweet like this:

SR @hare recommend.club location=Vienna&music=electro

I want to create a natural English sentence of this like

„Hare, can you recommend a club with electro music in Vienna?“

to improve usability.

Obviously, the natural sentence is understandable for everyone who reads the Tweet. Creating natural sentences out of some data is called Natural Language Generation (NLG).

There are several challenges which have to be tackled. For example we have to know the correct article for „club“ which is „a“. Then we have to know that music=electro should be translated to „electro music“ and not just a generic phrase like „music is electro“. The last thing is an English grammar challenge, namely writing prepositions of times at the end of a sentence.

Usually NLG uses some kind of dictionary files. We also have to do that here, but its not easy to cover every phrase from the beginning. The idea is now to implement a learning mechanism for the dictionary. But who would feed the dictionary with new entries, if services with new attributes are requested or new services are published? Well, lets delegate it to the users – classical Crowdsourcing. But the question remains the same, who would do that?

So Martin came up with the idea of games with a purpose (gwap). There are some problems in computer science which are very hard for computers, but actually quite trivial for humans.Now I want to wrap a game around the problem of updating the dictionary too. For example I could show a skeleton text like
Hare, can you recommend ____ club music=electro location=vienna?

Where you have to enter the correct article and rewrite/sort the attributes. You could get points for that, but actually its really boring.

At the moment I am thinking about a good game which entertains the user while he creates the correct phrases. Obviously some kind of reward like a highscore list will increase the motivation. Maybe in times where esthetic plays also some role, its enough if the userinterface for entering the correct words is just really fancy. Or would you like the idea of several minigames which means everytime if you are asked to update the dictionary another (yet not known) minigame starts. What do you think?

Going one step further with crowdsouring could be to implement an plugin mechanism to allow Android developers create there own games for updating the dictionary. So users would allways be excited which game they are playing next.

My next steps will be thinking about an appropriate game so that the user stays entertained while actually doing some boring „finding correct articles and phrases“. I will post my game ideas here to get some feedback about it. After that I will implement the game and the dictionary, where the latter may be maintained centralized for example in an Google App Engine Application.

Cu

Distributed Clipboard – JavaFX and Drag&Drop

Hey again! Although i promised to publish my third blog entry already the week before, I have to admit that I wasn´t able to write about my filesharing and chat components as announced, because I ran into some serious problems the last 2 weeks, regarding the further implementation of the GUI. The main aim of my application is to easily share files between users in a Local Area Network, so it´s clear, that the basic user interaction involves dragging files or folders from the OS filesystem to the GUI. Of course, some may argument, that there are GUI components like filechoosers and so on, but hey, I want to make a clean, proper and fancy GUI, so working with this kind of components was never an option – drag and drop is definitely a must.

When I began to develop my Clipboard, I asked Martin, if he had some experience with GUI programming, since the only “real” GUI I ever designed and coded all myself, was the “Einstiegsbeispiel” for SEPM 2 years ago ;)  I have some experience with Ruby on Rails web application programming, and also PHP, but HTML, CSS and Javascript of course can´t be compared to real GUI coding. I really digged deeply into Swing/AWT, because it was my first GUI and I was really interested in it, but after some days I had a LOT of code, some nice things working, but all in all, it was an ugly-looking, grey window, with some tabs, textfields and a scrollable and editable list. When I then began to add functionality to it, I had to refactor lots of things, erase cool features, because they wouldn´t work hand in hand with the rest of my code. Needless to say, that I wasn´t being elected to be responsible for the GUI in the further progress of SEPM. ;)

So before choosing the GUI Framework for Distributed Clipboard and Swing/AWT was not an option, I read some articles about state-of-the art technology, and finally, in consultation with Martin, I ended up with choosing the public beta of the upcoming JavaFX 2.0 version, as I already told you earlier. Choosing a framework with is especially built for developing RIAs and GUIs, I never even thought of running into problems concerning user interaction and look and feel of the application. I developed a simple GUI and then began to code all the logic needed: UDP and TCP Listener Threads, UDP and TCP Worker Threads, classes for saving the application state (because I don´t use a database), the discovery and so on. When I finished all these tasks the week before, I first coded the chat-component of the app (remember to NEVER code nice-to-haves before you´ve finished your main targets ;) ), and was really pleased, how easy I was able to merge existing logic, with the new chat logic and the GUI – awesome!

After that, I developed filesharing logic, at first on sender, then on receiver side. I remembered, that during my first JavaFX 2.0 API journeys, I read something about DropTarget Interfaces in the  Scene class, which is simply all the content of the top level container (called Stage in FX, corresponds to our beloved JFrame in Swing). I again searched for it in the API, and was kind of surprised, that there are no get( ) or set( ) Methods for these type. So I tried to look for static fields or methods – nothing. Since there was an entry in the API, called scene.Scene.DropTarget, I tried to dig into with the help of Eclipse and Cmd+Space – and found that the field, or embedded class, or WHATEVER they did, was simply private – OUCH – why would you put something into your Documentation, when noone ever has access to it (since there were no getters and setters)?

This was the first time I experienced a real problem with FX, but I thought: “well, of course there is a way to drag and drop, I just haven´t found it yet”. The next days I spent hours in the official Beta Dev Forum, reading and reading and reading. I quickly found some snippets, that showed how to drag files from outside into the GUI, but they all used FX 1.3. I tried to look for the classes people used in version 1.3, but the whole package isn´t available in FX 2.0 so far. At this point I had already spent a lot of time with this problem, and therefor I began to simple try things, but that didn´t take me any further either (which I noticed few days later ;) ). I then accepted that there is no way, getting drag and drop to work over the current provided public Beta. Just a little note: Of course, FX provides some classes, which deal with dragEvents and dropEvents, but they all just work, if your DragEvent STARTS inside the GUI. I tried to manually instantiate DragEvents, but this is not possible. I managed to drag and drop entry of two lists in the SAME window with 3 minutes of looking into the API and 4 lines of code. The crucial thing, is that you need to start a Drag-Gesture on a JavaFX Object with an invocation of the startDragAndDrop( ) method, otherwise, it is not registered. I guess, that this would have been the perfect time to reconsider my attitude towards filechoosers – but I didn´t, since I wanted Drag and Drop from outside – nothing else.

The next day I noticed a new package in the new buid of the public Beta: javafx.embed.swing. It just holds a single class, calles FXPanel, and all you can do with it, is to set the aforementioned Scene (main content) to be displayed inside this panel. As the packagename embed.swing already tells, FXPanel can be embedded into an ordinary Swing JFrame. I was kind of freaking out, because of course there are a lots of options to register drag and drop events on a JFrame. At first I refactored everything, to be not placed in the native JavaFX Top-Level-Container, but in the FXPanel instead. To be able to show my GUI again then, I just had to extend another own class from JFrame, and set the FXPanel there. I then implemented an awt.DropTargetListener interface and set it onto that JFrame. At this point I was able to detect things being dropped on the window, but except invoking event.getX( ) respectively getY( ), I was not able to detect, where on my FX ListView object (which displays currently online users), the Drop has actually occured, since they are not detected by FX.

I then again struggled hard for two or three days, until I found a working solution: The main problem is, that my GUI now runs in 2 threads: one for JavaFX, to which i have to switch, if I want to update a listcell or alter something else on the GUI, and one for Swing/AWT, which just helds the JFrame, and the registered DropTargetListener. If I drag a file from outside into the GUI, the applications registers it on the Swing-Thread, and saves the path. After that I switch back to the FX-Thread. My ListView is populated via a custom cellFactory, which is responsible for instantiating, drawing and changing the listCells. I added an mouseMovedListener to each of the cells, which is just activated, if the path, that I can get via the drop-gesture, is set via the Swing-Thread. In the moment I release the mousebutton, the applications switches back to the FX-Thread, recognizes the actually hovered ListCell, saves the path internally and sets it null again (to deactivate the listCell Mouse Listeners) and returns the actually hovered cell – and – AFTER MORE THAN ONE WEEK OF WORK AND READING – I have the path of the files to send, and the listcell, which is bound to the name and the IP-address of the receiver at the same time, at one place in my application :D

Nevertheless, filetransfer and chat are working now, I was able to get rid of most of the bugs and added a SystemTrayIcon, which displays incoming messages and incoming download requests in the typical bubbles. I registered ActionListeners on these Bubbles, to provide a nice workflow, but since its not completely ready, I will tell you more towards the end of the week – as always, stay tuned, and thanks for tuning in!