CSCE 242 Sign Up Now, Please!

As of this writing exactly two students have signed up for my CSCE 242: Client Server Computing class. With so few students signed up we will have to cancel the class, and I will be bummed.

I find it strange that there is so little interest when nearly all programming jobs nowadays require at least some web development, whether it is using a REST API, developing a web front-end, a mobile web front-end, or actually building a complete web application. Plus, javascript is a boatload of fun! Where else can you modify the inheritance hierarchy at runtime?

Maybe someone can comment and explain this lack of interest to me?

Mobile posting

I am posting this from my iphone using an app that connects to blogger using their REST API. One service in the cloud, multiple frontends: I think we shall see this a lot more often. If you want to learn how to build these services , sign up for 242!

Master and Undergraduate Projects

I have posted a list of MS thesis and undergraduate projects that I am interested in working on. If you are an undergraduate or graduate student interested in doing some research please check them out.

NSF Award for Negotiation Networks Research

I am honored to have just received NSF award 0829580 to continue my research into negotiation networks. The total award is for $234K over the next 3 years. This research is under the Theoretical Foundations program, and the Scientific Foundations of the Internet's Next Generation (SING) sub-topic.

We hope that our research will lay the scientific foundations for the Internet's next generation of protocols and deployment strategies. The project summary of theproposal explains our goals:

We propose to develop automated negotiation protocols for autonomous agents in negotiation networks, which we define as a type of bargaining problem where every agent must negotiate with a fixed set of other agents in order to arrive at a unique deal. Negotiation networks are, in effect, a natural re-formulation of a winner determination in combinatorial auctions problem as a negotiation problem. They thereby distribute the costly winner determination computation among the agents and avoid the need for unnecessary exchange of currency or trusting of third parties.

Intellectual merit: Since the problem of negotiation networks combines features of characteristic form games and bargaining games from game theory, combinatorial auctions and distributed mechanism design from Economics, network exchange theory from Sociology, and distributed algorithm design from computer science, its solution should be a significant contribution to all these fields. While several parts of the proposed problem have been studied in the various disciplines, we will bring these disparate parts within one framework and provide solutions for this very important problem. Our approach is fresh in that we focus on algorithmic solutions for the dynamic, distributed problem of resource allocation among self-interested parties, in contrast with game theory and Economics' solutions which are typically steady-state axiomatic solutions. Success in this research is potentially transformative as it will provide the foundation for the engineering of protocols and efficient algorithms for distributed resource allocation, which is a pervasive problem in our ever-growing highly-interconnected society.

Broader impacts: The negotiation networks problem is not only significant from a research perspective, it also has some very immediate applications. One such application is the multiagent enactment of workflows for the growing SOAP and REST-based (Web Services) service Internet where complex tasks are dynamically and automatically bid for and allocated among arbitrarily large number of agents. Such systems would revolutionize just-in-time manufacturing and purchasing practices by automating not only the paperwork but also the allocation of resources and contract negotiation. Another near-term application lies in the development of incentive-compatible routing mechanism for the new Internet which would provide the proper incentives for companies to deploy more bandwidth and to make their existing bandwidth available to others without having to worry about freeloaders. Further down the road, negotiation networks could even eliminate the need for predefined workflows and lead to much more efficient and dynamic allocation of resources in our economy. These adaptive supply chains would be resilient to local failures and attacks as they dynamically re-negotiate deals in response to environmental changes. In fact, with slight modifications these distributed resource allocation algorithms could be used to coordinate first-responders in an emergency situation, to program distributed environmental sensor networks, and to instruct automated robotic swarms.

Marriage Problem

In the marriage problem we have an equal number of men and women who we want to pair up (it is presumed they are all heterosexual). Each one has an ordered list of their prefered mates. The goal is to find the set of marriages such that no two people would rather get divorced and marry each other. That is, not two prefer each other over their assigned mates.

This problem can be solved with a simple algorithm where all the men propose to the women. Then, each woman with more than one proposal rejects all but her most preferred which she temporarily accepts. The bachelors then repeat the process by asking their most favorite woman who has not rejected them. The process continues until all women have a partner. I have a NetLogo implementation of the marriage problem that illustrates this process.

It is interesting to notice that while the women are the ones that get to turn down the men, the men do overwhelmingly better than the women. I mentioned this to my wife and she said that is why she proposed to me. Of course, in the end it is always the women who propose to us.

I am interested in finding distributed algorithms that arrive at stable solutions, that is, those where no two people would rather be married to each other than to their partner. Here is a link to a set of slides that goes into more detail on the marriage problem, in case you want to learn a bit more.

Trading Houses

Imagine that all students are assigned dorm rooms in some ad-hoc way. After each one has a room, two students might find that they both prefer the room the other one has, thus they could switch rooms and both be happier. Similarly, three students (A,B, and C) might find that A prefer's B's room, B prefers C's room, and C prefers A's room. These three students might also trade rooms in a cycle. This can go on for even larger cycles. But, how do we find these cycles?

A very simple algorithm, proposed back in the seventies, is to have each agent point to its most preferred choice. If the resulting graph has any loops (it will) then all the agents in the loops exchange rooms and drop out of the game. The remaining agents then point to their most preferred room and we repeat the process until there are no more agents left.

I have implemented a simple demonstration of this top trading cycle algorithm using a simple distributed cycle detection protocol. Its fun to watch!

My Programming Languages History

As faculty members in Computer Science and Engineering we often discuss the pros and cons of languages and which ones we should teach. The Tiobe software index shows us how the popularity of certain languages ebbs and flows. I think it is clear that it does not really matter which specific language you learn first or second, what matters is that you learn how to think clearly. And that you learn how to learn new languages.

As a demonstration, I thought I'd take a trip back memory lane and list the languages I learned (and forgotten) while still in school:

1. BASIC - Freshman year in high school I took a summer class on Basic programming using the old Tandy PET (I also had the Atari 2600 basic programming cartridge, but it kinda sucked). Next year, my new Apple IIe had basic built in. I should also mention that back then it was common for high schools to teach Basic programming, Power Point and Excel did not yet exist.
2. 6052 Assembly language - Of course, I wanted to write games and the only way to get any kind of animation in the Apple IIe was to progran in assembly.
3. APL - I only worked with this extremely strange language for two weeks.
4. Pascal - Somehow I got a hold of a copy of a Pascal compiler for the Apple IIe. I was surprised to learn that you could write programs without line numbers and GOTO/jmp statements.
5. Scheme - I used it in my freshman year at college. Scheme is the simplest language I have seen. It is beautiful.
6. CLU - In college we had to do our software projects using CLU. It is a pre-cursor to object-oriented languages.
7. Emacs Lisp - I learned it for a summer job. This rss feed will be turned into HTML automatically by an Emacs Lisp function I wrote.
8. C - Learned it for an OS class in graduate school.
9. Lisp - thesis work.
10. Tcl/tk - thesis work.
11. C++ - thesis work.
12. Java - I wanted to write some applets, for fun.

Those are just the major programming languages I encountered while still a student (pre 1998), I also learned bits and pieces of countless scripting languages (awk, sed, bash) or special purpose languages (latex, um-prs, sql). The point is, my experience is not uncommon. A good computer scientist or software engineer will learn at least one new language every year or so. After a while, one notices how they are all not that different but how each one teaches us something about the way we think, the way we solve problems. Writing software is about how we think, and how we translate these thoughts to meet the capabilities of the machine at our fingertips.

Thus, there is no need to get too hung up on which programming language you should learn first. If you choose software as a career, you will likely learn over 100 languages over your lifetime. I can only imagine what we will be using 10 years from today!

If you also have fun writing programs then maybe you would like to try to solve some of my programming questions.

Fast Bidding in a Distributed Combinatorial Auction

Walmart needs stuff moved from point A to B, for many A's and Bs. Also, these deliveries have other possible requirements: one might need a refigerated truck, one might be a night drop off, one might be a rush order, etc. Similarly, trucking companies have complex requirements about where and when they can deliver. Put these millions of orders together and you have a complex resource allocation problem. If you are willing to have everyone send their requirements to a centralized auctioneer then, maybe, you can solve this problem.

However, what it you don't want to trust, or can't afford to pay a centralized auctioneer? We are studying automated incentive-compabile negotiation protocols for distributed resource allocations. I know this is a mouthfull but all it is saying is that we are developing algorithms that automated agents can use to negotiate with each other and solve these type of problems. Think of it as moving all buy/sell transaction to the web (we are nearly there) and then using software to decide who to buy what from and at what price. We can show that this will lead to more efficient solutions, that is, everybody wins.

Anyway, our latest paper detailing our efforts is

• Benito Mendoza and José M. Vidal. Approximate Bidding Algorithms for a Distributed Combinatorial Auction (Short Paper). Padgham and Parkes and Müller and Parsons ed.In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, May; 2008.

  Distributed allocation and multiagent coordination problems can be solved through combinatorial auctions (CAs). However, most of the existing winner determination algorithms (WDAs) for CAs are centralized. The PAUSE auction is one of a few efforts to release the auctioneer from having to do all the work. The pausebid bidding algorithm generates myopically-optimal bids for agents in a PAUSE auction but its running time is exponential on the number of bids. We present new approximate bidding algorithms that not only run in linear time but also increase the utility of the bidders as result of small decrement in revenue.

Check it out, approximation mechanism let ut achieve 1000-fold speedups at only a small cost in utility.

A NetLogo Introduction

I will be speaking tomorrow Thursday January 10 6:30pm at the Columbia Linux User's Group about NetLogo. It will be an informal introduction. I will try to show why it is a great language for both learning to program and for building simulations that can be used to engage students in active learning of other subjects: such as physics, chemistry, economics, sociology, etc. The meeting is open to all.

The Internet, Growth, and Students

Today I gave a 1-hour talk to our freshmen on the history an future of the Internet. Obviously an impossible task but I did my best. I hope I conveyed to them the endless possibiblities that the Internet has opened up.

In preparation for this talk I have been asking our students: how much do you think the .com bubble affected the growth of the Internet? The general belief is overwhelmingly clear. Students believe the bubble had a large impact on the Internet growth. Of course, this is completely wrong. Check out my chart:

The bubble had absolutely no impact on the growth of the Internet which continues to grow exponentially, doubling every three years. The number of websites is doubling at least every two years. The implications of these facts are mindboggling! But, the general public, even our students, still seems to feel that software is done. Oh well, it just means more money for those of us who can program!