zaitcev.mee.nu

Prof. Bridges opened the meeting by passing around a tray of Moteiv's Tmote Invent for students to grab. Our assignment turned out to make the real hardware work. It's certainly more fun this way, too bad for those who have installed TOSSIM already (like myself and Mohammed). Brian grabbed two, he wants to play with the radio, which turned out to be ZigBee compatible (802.15.4 actually). Tuan was absent.

Assignment is due on 2009/2/24. We are to read temperature and light sensors, and lit up LEDs according to readings.

Next meeting (Thursday 2/12) is replaced with 1-to-1 meetings, where we present our projects and get them discussed in the space of 15 minutes. Since I (still) have two, this is challenging: 7 minutes to present, hear feedbacks, and then make a decision to proceed on one of them.

Tags: cs-591-005

Posted by: Pete Zaitcev at 08:38 AM | No Comments | Add Comment
Post contains 143 words, total size 1 kb.

Talked about TinyOS concepts a bit. I'm sure everyone has read the papers, but nobody dared to stop Prof. Bridges. We just waited him out, until he moved on interesting stuff, like routing.

Next, we had a (very) brief look into the history of CSMA staring from ALOHA. It was useful to structure the vision of the world, e.g. a reminder that Ethernet detects collisions, and that big benefit of CSMA is the lack of central coordinator (IIRC ALOHA did have a lead station, although only to sync slot clocks, but what's important here is that it did not do arbitration). Nobody mentioned Appletalk's CSMA/CA, heh.

Issues in Wireless:

• Hidden Terminal problem: triangle, two initiators cannot hear each other and collide at the receiver, cannot back off each other. In WiFi receiver has RTS.
• More losses: Principally, the transmitter in Ethernet can assume that once the message is out, it was delivered. In wireless, MAC ACKs are essential.
• Dynamic routing: Needed for multihop networks, but the change rate may be much greater than in wired networks.

The last bit is the worst. So, we talked the routing problem (including "count to infinity" for DV, etc.). Although "very well mined", the wireless problem seems intractable in general. Therefore, apparenly all successful systems work by introducing asymmetry: a base station of some kind. It either flattens the topology like in 802.11, or creates enough asymmetry to break loops. For sensors, Direction Diffusion and Collection Tree Protocol are notable. The only symmetric thing that flops around is "AODV": Ad-hoc, On-demand Distance-Vector.

Homework: Read Trickle paper (Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks). It's Levis and Culler again, applying the gossip model to motes. Bet Brian will love it.

Speaking of homework, we submitted our 1-paragraph ideas. Amusingly, it looked like nobody submitted by e-mail. When I printed out my ideas (I had two), I thought that maybe it's all right for me to use dead trees, I'm positively ancient for a student. No idea what everyone else's excuses were. Oh well.

Also, Matthew said that he has a class blog, and he was "too lazy" to reply to my message with a URL. *goggle eyes*

Tags: cs-591-005

Posted by: Pete Zaitcev at 05:57 PM | No Comments | Add Comment
Post contains 371 words, total size 3 kb.

Meeting 4 was cancelled.

Real quick:

* Masterless 2-phase commit exists. Requires NxM traffic. See Quicksilver, a distributed DB.

* Need to investigate the so-called "moon machines" just in case.

* Proposals should be done by end of February.

We were asked to submit a one-paragraph description of our class project.

Tags: cs-591-005

Posted by: Pete Zaitcev at 05:21 PM | No Comments | Add Comment
Post contains 56 words, total size 1 kb.

I'm done with the MapReduce: Simplified Data Processing on Large Clusters by Jeffrey Dean and Sanjay Ghemawat. It's a classical paper and an enjoyable read, although it has no specifics. The insight about the application of a suitable restricted programming model is pure genious. So many people tried to create super complex systems from OpenMosix to MPI before. Well, MapReduce library is far from trivial itself, but at least its applications are isolated from all the mechanics. This is the hallmark of successful modern web services in general, too, such as Google BigTable, Amazon AWS (S3/EC2), etc.

The biggest import for the class, I think, is how MapReduce is high in the food chain. To work, it needs a cluster management solution, a job scheduling solution, and a distributed filesystem with coherency and atomic operations. Prof. Bridges likes to talk about "running MapReduce on a network of parking meters", but show me a network of parking meters that has the minimum infrastructure required by MapReduce. To be fair, he may mean for us to play with restricted programming models in general, and to think out of the box, but even so this seems a bit far fetched. Or maybe I'm just too old and crusty.

Pondering if I should read the Sinfonia thing. The class wiki says that we only have the public mobile applications remaining before project discussions and presentations, so maybe do that instead.

Tags: cs-591-005

Posted by: Pete Zaitcev at 05:14 PM | No Comments | Add Comment
Post contains 241 words, total size 2 kb.

Today's cancelled meeting was supposed to be about vehicular networks. The assigned papers illustrate the subject pretty well, I think. Might as well move to MapReduce et.al. for the next class. Read that paper.

Tags: cs-591-005

Posted by: Pete Zaitcev at 10:01 AM | No Comments | Add Comment
Post contains 41 words, total size 1 kb.

Spent the meeting discussing the power grid issues and its relevance to CS, albeit in very general terms. The Astrolabe paper was the reading, and as usual the TCP haters really made my blood boil. Their protocol is squarely aimed at ignoring the congestion, and thus poisoning the well for everyone else (by taking a constant bandwidth it effectively reduces the bandwidth available for congestion control). Prof.B.'s critique of the it centered on the tendency of Astrolabe people to attempt to apply their tool to all problems (e.g. if you have a hammer, everything is a nail), which is clearly valid too.

N.B. Prof.B. says they were working "pseudo-multicast" RTP, which kinda looks like a "galactic expansion" RTP. Alternatively, an RTP on top of a spanning tree. I didn't follow the RT proto area, V.curious.

Obviously any such thing is going to be complex. Van Renesse, IIRC, comes from the Tannenbaum school of simple solutions. Aside from Amoeba, which was infamous for encoding the Intel i82586 inter-packet gap bug into its high-level protocols, he also worked on reliable broadcast based on sequential numbers. That might have burned him off any super-RTP and begat Astrolabe.

We also talked about energy spot markets, cooperative behaviours, etc. As usual the privacy/secret protection was a big question.

N.B.2 Until Prof.B. explained it, I forgot that tracker was involved into BitTorrent's economic model. For some reason I thought that peers simply accounted what they received. Not so. They also report to the tracker how much they receive from others, and pull this information to include into decisions to throttle. So, a global data space, but with no central calculation.

By Thursday: Mandatory: Kosch, Timo ; Adler, Christian ; Eichler, Stephan ; Schroth, Christoph ; Strassberger, Markus : The Scalability Problem of Vehicular Ad Hoc Networks and How to Solve it. Heavily suggested: Prashanth Mohan, Venkata N. Padmanabhan, and Ramachandran Ramjee, TrafficSense: Rich Monitoring of Road and Traffic Conditions using Mobile Smartphones.

Soon: One paragraph about the selected project. It's ahead of the project proposal paper.

Tags: cs-591-005

Posted by: Pete Zaitcev at 12:37 PM | No Comments | Add Comment
Post contains 345 words, total size 2 kb.

I got TOSSIM running by repeating instructions like a trained monkey. Since I run Fedora on the laptop, the installation was a piece of cake. Builing of a sample application Blink was simple too.

About the only trick I had to learn was that an empty line ends an indented block in Python when entering interactively into the interpterer. Result looks like this:

1
1
DEBUG (32): LEDS: Led0 off.
1
DEBUG (32): LEDS: Led1 off.
1
DEBUG (32): LEDS: Led2 on.
1
1

TOSSIM itself is a funny animal, which took a few moments to grok. It's an event-driven sim, so the Levis' "Nido" paper scared me with this:

• Time: While TOSSIM precisely times interrupts (allowing things like bit-level radio simulation), it does not model execution time. From TOSSIM’s perspective, a piece of code runs instantaneously. Time is kept at a 4MHz granularity (the CPU clock rate of the rene and mica platforms). This also means that spin locks or task spin locks will never exit: as the code runs instantaneously, the event that would allow the spin to stop will not occur until the code completes (never).

My first reaction was, honestly, "what is this crap?!". Only after reading the older Levis/Culler's paper, I understood what this is about. The thing is, TOSSIM is not intended to emulate hardware. It just does some of that because they want the applications unmodified. But mainly, TOSSIM emulates the network. All the talk about getting gdb attached got me confused. Also, I wrote a share of CPU emulators in my life (with circuit, cicle, and instruction resolutions), and that experience provides a wrong framework to think about TOSSIM. It's not qemu at all.

Anyway, I'm going to turn to that energy grid paper now.

Tags: cs-591-005

Posted by: Pete Zaitcev at 03:29 PM | No Comments | Add Comment
Post contains 299 words, total size 2 kb.

I might blog the meeting later (e.g. the Byzantine failures), but for now just the summary:

Mailing list is set up, use cs591embedded@mail.cs.

By next class: Ken Hopkinson and Ken Birman, "Overcoming Communications Challenges in Software for Monitoring and Controlling Power Systems".

Also, it's high time to get TOSSIM and nesC toolchain running, with MapReduce testbed on its heels. The coming weekend sounds like a good time for it.

Tags: cs-591-005

Posted by: Pete Zaitcev at 01:04 PM | No Comments | Add Comment
Post contains 74 words, total size 1 kb.

Well, that was a good blast from the past. I thought I've left systems with 512-byte RAM sizes behind in 1980s when I tinkered with the 8008, but I guess not.

Many elements of TinyOS remind me about old frameworks with which I worked back then. The tasks, commands, and events bear a striking resemblence of the driver model of OS MISS that was the topic of my, for the lack of a better word, sempai's Vladimir Butenko PhD thesis. As I suspect, he was moved to create his framework because his target system, Bull Mitra-225, lacked a hardware stack. The result resembled TinyOS's stackless architecture.

Well, nothing is to it but get it over with quickly. The biggest issue, I suspect, is going to be learning the pitfalls of nesC and getting TOSSIM to run. The paper itself, "System Architecture Directions for Networked Sensors" bypasses the topic entirely, but there's a book-cum-document that may help, "TinyOS Programming".

Tags: cs-591-005

Posted by: Pete Zaitcev at 05:21 PM | No Comments | Add Comment
Post contains 163 words, total size 1 kb.

According to the syllabus, blogging the class is a requirement, and counts towards a big 50% block of the grade that deals with the main project (the final is a 8-10 pages paper on it). Sounds like a perfect opportunity to use the Meenuvia.

First meeting was mostly a class overview by Prof. Patrick Bridges, and the class is mostly a project, after we start up with readings on MapReduce etc. Project areas are:

• Distributed computation to collapse the sensor data for storage, save "interesting" things, discard the rest.
• Cellphone-based applications: MegaGaydar (Prof. Wenbo He's pet project), traffic congestion (using cellphone density as a proxy).
• Power grid (fridges that cooperate, kinda fishy stuff).
• Traffic systems (traditional, government and ground-based).

Alternative projects are allowed too, as long as they are distributed and/or embedded.

The most interesting project is definitely the gaydar thing. I'm thinking about something like Nintendo Pictochat, only running constantly on your cellphone (over Bluetooth), and on your Nokia 880/XO/netbook/etc. (over WiFi). This should include some mesh capability, cross-media routing (with Bluetooth enabled netbooks serving neighbouring cellphones), etc. Prof. Bridges' thoughts went in a different direction: he wants cellphones routing each other web access (e.g. in case Verizon coverage works but not AT&T). IMHO that's kinda low level, but he probably has a better feel for constraints of a one-term project. Heck a regular Linux device driver gestates for 6 months, and here we only have 2 to 3.

The most important part that makes MegaGaydar interesting is how it's a consumer oriented application not sponsored by an outside entity. Everything else (save for the utopical fridges talking) is a pretty hideous Big Brother kinda stuff. Why don't we have people who are paid to do it, do it? Right?

Right here I'm going to invoke the Hypoctitic Oath and mention my alternative project, "Hail", which is, unfortunately, in black-out in this time. I may be getting paid to do it, too. Details are exceeding hazy at this point anyway.

By next class: Read: J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister, "System Architecture Directions for Network Sensors". If possible the remaining articles (I'm going to start with the MapReduce one: the 2nd homework is to write a working MapReduce app — by 1/29?). So, next meeting we'll discuss... something. Architecture Directions, or our projects.

By next Tuesday: Select the project. I suspect it's a bit premature, especially since we'll be handed our first homework then, so the 2nd week is busted; project presentations only start 1/29 or later. Not that I'm worried, I narrowed the field to 2 candidates already. However, we'll need to write a project proposal too.

Tags: cs-591-005

Posted by: Pete Zaitcev at 10:45 AM | No Comments | Add Comment
Post contains 448 words, total size 3 kb.