gay bars at 11am

today I was interviewd by some BBC folks from the Culture Show, about copyright and the internet, in a gay bar (The Friendly Society) behind a sex shop (Ann Summers) in SoHo, london

this was an unnerving experience - all the strip joints in the alley way were just starting to open - it was a glorious sunny day at 11am

Frrrankly, it made a change:)

(What did I say? well you'll have to wait and see:)

meanwhile, Derek Murray continues to update his
Exemplary NSDI Live Blog - this should be a lesson in how to take notes at a conference!

#P-Completeness

so i've come across this category of complexity a couple of times, and finally got around to reading it up (page 155 of Garey & Johnson"Computers and Intractability, if you must:-)

its a slightly refined way of looking at a sub class (but a large sub class) at the "harder" end of NP- - basically, instead of just decidability, a Non Deterministic Counting Turing Machine (TM:-) tells you "how many". (hence the #)

so in problems like maximal matching pairs on a bi-partite graph (e.g. call assignment problem in circuit switched net, or route/scedule problem in multihop radio) which can be "reduced" to a set packing problem (and knowing how many makes it a #P equiv to set packing)


Computational Complexity of Loss Networks

debugging in every day life

this easter I had a mixed time debugging things - aside from family (basically a DDoS attack on the fridge&larder from Ireland and France), various things (i.e. stuff) went wrong in interesting (or dull) ways

first, the fridge decided to turn everything to Ice - this turned out to be quite simple - someone had piled Easter Eggs on top of it pushed all the way back to the wall, so the heat exchanger pushing heat out was having to work overtime and the calibration presumably went awry - removing soggy easter eggs from top and putting them in the freezer to reform made that problem go away

second, the very nice, cheap and elegant and easy to use Humax PVR decided to do a few weird recording errors - we'd seen this first when the clocks went forward for "British Summer Time - but I hadn't bothered looking up the full glory that is Digital Broadcast and Electronic Programme Guides (EPG) - this time, we had a couple of truncated recordings and one that overran by 2 hours - so it turns out (thanks to the extremely well documented "hummy" web site and various AV consumer advice sites) that this is largely due to bugs in different implementations of the EPG combined with occasional missing or mis-broadcast EIT (end indication time) signals inband which tell the PVR when a program "really" ends (as opposed to the time set in advance which may not be right any more) .... plus some really strange effects if your multiple tuner PVR decides to use several different broadcast sources (which the Humax 9200T can do apparently - awesome)....anyhow, the overrun problem isn't really a problem but the truncastion is a bit of a pain, so I fiddled around according to various pieces of guidance and may or may not have fixed it...

third, one of the Macs in the house has been deciding that the wireless net isn't there periodically, and has to be told to pick it again (even though it is the ONLY preferred network...) - 4 other Macs in the house all work fine - this turns out to be a WPA re-authentication timer bug in the intel core solo Mac Mini 802.11 security thing - since apple have known this for dokeys years and it ought to just be driver stuff, I really don't know why it isn't fixed- only workaround for now is to go to WEP only security which I don't really care much about coz we only do ssh/ssl any how so there's no real harm, but it is a bit silly (early MacOS was ok, and later is ok - just ones around 10.4.10/10.4.11...i suppose i can roll back or upgrade ....what a palaver)

oh then there was an intermittent audio problem on the playstation 3 on the new LG HD TV - basically it looks like there's an HDMI audio incompatibility (that turned out to be easy - PS3 helpsites abound and advise on how to pick the most liely to work audio codec)...

then there was trying to get 11 and 16 year old to do maths homework/revision (for SATS and GCSEs respectively) - in retrospect, the techie stuff was trivial in comparison

mashing up state of mind and different web page layout

so I am sitting in a programme committee meeting using Eddie Kohler's excellent Hotcrp conference management software - this is used for writing reviews, putting in comments to other PC members and writign discussion notes between PC members during the processs - but it occurs to me that I am blogging it using the same form entry stuff in blogger.com, and I am posting stuff in facebook using a similar form and in facebook status updates in a similar form - these are all completely different activities yet if one comes to one activity from another, one might mix up the kind of frame of mind one shoudl be in - for example, people posting status update on facebook are very similar in their approach to people tweeting on twitter (lots of bitchin - a bit like youtube comments:) whereas reviewing a paper is a serious activity giving rational for a score/rank and communicating feedbakc to authors (maybe to fix the paper if accepted, or to improve for submissio nelsewhere - and comments to the PC or discussion notes to other PC members are not for publication, but also should be considered at least, rather than subjective/emotive/assertive...

so how would one provide the right "illocutionary act" mindset to an input form (and its display once edit is finished) graphically? fonts, colours, what?

.towards the economics of information

today's idea/conjecture

there's an economics of information density and this is why twitter is gibberish and
blogs with google ads makes sense

basically, its some sort of entropic/SNR thing which is to do with the percentage of cognition someone is prepared to spend on stuff that isn't 100% germane (fancy word for relevant)

i think there's two pieces
1. there's a minimum unit's worth which is about 1 web page (8kbytes) - below this (think twitter or SMS), there's no useful semantic content, and its pure deontic/emoticon stuff - above this, the brain can afford some idling time to eyeball some stuff around the edges

so if you can't make money purely from the service (think sms/twitter) for low payload things you are doomed, but once you get into the page (think pagerank) you can build parasitic ways of making money (like advertising)...so in those cases, you want the _service_ to be free to maximise your chances of reaching the right people with the advert....(the advert could itself just be links to more content of course)

incidentally, this is why the IP MTU should have been 8Kbytes, not 576 (or the de facto 1500) it is today...

Computational thinking

so there's a school of thought that we need to get "commputational thinking" into the early school curriculum - on the other hand, I detect signs that quite a few building blocks of computational style thought are already part of the everyday mindscape - the notional of irony, post-modernism, and narrative tricks like the reverse memory plot in memento, or time travel paradoxes in Dr Who (or easter egg hacks in the famous Blink episode) do not cause the public to go "errrr, wot?" - they are all just part of the norm refs for kids and so i suspect it will be found quite easy (provided one does'nt do something horribly heavyhanded) to capture this in a small number of concepts that can be embedded in lots of other subjects...

on the other hand, everyone should learn to program at the same time as reading, writing and rythmetic and music.

Bogo cod HCI

I hate those emails from myspace and facebook that purport to be from a person
("from the facebook team")

can't they just say
from the Oort Cloud
or
from your friendly neighbourhood bot
or something truthful?

why havn't we got one of these hackerspace things...

in cambridge?
or do we?

odd types of computer

the occasionally awesome James May on TV this week explained semi-conductors by olding up a spoon (conductor) and a copy of a vinyl record in cardboard record cover of Jeff Wayne's Musical Version of The War of the Worlds (insulator)

this made me think of alternative crazy types of gate that one might propose

historical battles (marathon, poitiers 1&2 etc) aer really gating functions to either populations or cultures moving from one area to another - think of the movement as a large current, and the small armies (relatively speaking ) as a voltage applied - i.e. valve/transistor/switch/gate...

so the whole of history of human migration and population plus landmark battles could be viewed as a computation....what does it compute tho? 42? 23? or does it just deliver a ring pull from a coke can to a stranded tralfamadorian on Titan?

flocking copters...

so i was proposing flocking copters made from commodity (e.g. hobby copters for a 100 quid) - that was 2001 - now we see
cube warriors and war porn is reality.

multitouch vnc?

has anyone looked at thin 3G client + cloud computing?

basically ,multitouch VNC and a remote service...

would make the battery life really good and with most the android/t-mobile and iPhone/O2 contracts being unlimited data, one could just win big compared with those platforms...

dasher for cell phone or other consumer electronic config

has anyone looked at using dasher for input for configuration of applications ? It would be quite easy compared to using it for probabilistic text input..

time to leave facebook?

now they've made it as pointless as twitter!

TINA in Hong Kong

Later today, I'm presenting some work on the
Intelligent Networked Airport project
at a Cambridge Alumni event in Hong Kong at the
Polytechnic University

Aside from the slightly alarming jetlag, its a great place to visit! some more info of my home talks page

I also had a tour of CS in the PolyU and saw some excellent mobile/mesh demos, and a really cool biometric lab (with chinese medicine intergrated in biometric ID!), and a model car/ITS lab, plus of course Henry Chan's new lab for the airport work.

on the way back, i was pleased to be flying Air New Zealand who were not only cheap, but also very good - 30-40 films on a VOD system - including (what I watched)

twilight - kind of like Near Dark, but slightly better

4 xmases - reese withersoon vehicle - basically naff, but likeable - the bloke is very drop dead pan amusing

slumdog millionaire - i prefer the book, but the film doesn't pull many punches - very good

my best friend's girlfriend - great idea fairly well done (bloke messes up dates deliberately for money from ex-s who want their girlfriend back) _ typical hollywood bottleout ending ruins it.

happy-go-lucky - mike leigh movie in a good mood - simply awesome

body of lies - not as good as other recent sensible US movies in the middle east, but not bad at all.

enchanted - fabulous combination of animation and pretty camp live action in NY.

the day the earth caught fire - diabolical remake of classic story.

quantum of solace - bond - better than US government bond, but only just

grading and reviewing

so in academic life, the one thing I think almost everyone would agree is the most negative experience is grading papers - (or marking exams) - teaching is fun (lecturing, supervising) and research is fun (coming up with ideas, building stuff, writing papers, giving presentations) - even some admin (interviewing, teaching/research admin) is ok

but grading is really de-grading.

so why is it the, that so many academics also volunteer for reviewing (i.e. being on Technical Programme Committees, and on Journal Boards of Editors)??

I suppose the main difference is that at least some of the things one reviews for conferences and journals are new and interesting, whereas most of the things one sees for exam answers are at best correct answers to something we already knew.

But to be honest, the payoff is pretty small, and in exam marking, at least sometimes you get the pleasure of seeing someone do a neat slightly novel answer (or the amusingly awful answers of course)...whereas there's very little amusing about awful paper submissions to conferences... ... ...

this week in european comms research land...

today I am at Pablo's Lab in Barcelona
but then shortly after I'll head off for this unusual workshop in swizzerland, where I may travel under the name of dr necessitor, in the hope of meeting and reconciling Michael Hfuhruhurr and Helen
Uumellmahaye.

some pix of barcelona...are at
the usual place

I has ta say any city with an actual Diagon Alley (as Barcelona has) nearly makes me forgive Harry potter.

today's mad idea - virtualise cell phones so you can migrate all the expensive p2p comptutation onto the Cloud, and save battery life in the handset:)

ignoble prize alert - the impact on reviewers judgement of being cited in the work under review

so how much is our judgment affected (unfairly) by seeing a citation to our own work in a paper (or book or whatever) we are reviewing?

devising an experiemnt to test this is tricky - there are effects like
a) very bad people who accept a paper because they want to boost their citation count to prepare a bigger H factor
b) there's the simple (correct) effect of being more familiar with the previous and related work (which is why presumably one was picked as a reviewer

to conduct an experiment to test this effect we need to submit some papers with
i) blinded citations for PC members
ii) citations replaced with irrelevant citations
iii) citations with authors names changed
iv) citations replaced by equivalent works (e.g. level of indirection - cite instead a work (survey, similar paper) that cites the original citation)

it should be done:)

facebook minimal age captcha

so its well known that if you break someones legs, the time to heal in weeks is the same as the age of the person.

hence a very big robot controlled mallet connected to the keyboard and remote run by facebook through a browser plugin could deter underage facebook users...

one problem is that the sense of the test is wrong - i am working on that:)

not to muckrake or anything, but...

...today i see they are spreading signage
on the field in front of the vet school
opposite the WGB:)

i'd love to see a picture of a herz rental outlet a donkey and cart with the sign
(Carriage Return, Line Feed) :-)

A Game Called Stop & this years 1b project demos

This is played on a board which is 1 square wide and deep, but 361 squares high. Each player has pieces (koans) made of clear glass.

i thought of this when lookin at the robot ("magic") game board in
this years 2nd year group proejct demos in the lab

idea for a project -seamless integration of pause live program, and download (faster than play - c.f. flash plugin) - so you have a back-to-the-future as well as a beam me forward scotty, button on a PVR combined in one nice package, with a P2P (torrent) delivery and DTN where you need it

local error, global fault - internet infrastructre critique

so i was talkin to some folks from our national funding agenc about what is interesting net research to do - they were not aware of the set of failures in the internet over recent years caused by "small" errors of configuration leading to global problems -
e.g.
0. the root DNS zeroing the boot dbase so returning nxdomain for the planet for 6 hours

1. the youtube blackout caused by local BGP config in small asian ISP

2. google mistyping a config rule for listing search result sites as "risk of harm to your computer" and marking 100% of the world as bad

there are others - these represent the problems caused by NOT STAYING WITH THE PROGRAM - the internet is decentralised - organisations that want to own pieces of it horizontally cause problems (there are tools to avoid most of these problems, but they require a modicum of cooperation)...people forget these design philosophy rules (aka architecture) at their peril (and ours:)

social networks cause autism

bad science yet again correctly refutes the daft claims in the press, and those behind the stories that social nets cause anti-social behaviour- we have research in social anthropology on people going from school to university, and people retiring, that shows that social networks, just like computer games, increase peoples' social group size and activity in the real world.
This is not published or definitive work yet, but other early work this year also shows this (it ain't hard to do, but it takes time and involves ethics committees since you're seriously treading on peoples' privacy)

muggling along

yesterday, I was at St Andrews and had a very nice attendance at a 3 hour seminar I gave on Delay Tolerant and Opportunistic Networks with about 120 students and staff and some very useful questions.

In the pub with Saleem Bhatti and Tristan Henderson, we discussed the new mobile phone game I invented called "muggling" - you juggle 3 cell phones, each with a live in progress call to a different person, while time division multiplexing the 3 conversations

I think this would be quite a skill...

proceeding to a new type of conference....

in the last few years, several conference organisation cttes have experimented with
the idea of Shadow programme cttes - these serve to trai nup new researchers in the process, as well as potentially acting as an error checker for the main conference and providing the paper authors with copious amounts more feedback - sigcomm and conext have both done this a few times...

now here are two proposals for the next step.

1. Run complete shadow conferences as well - instead of just having 1 "main" "real" PC and the shadow PCs just being training ground, let the shadow pcs selerct their actual top n papers and (at the same time in the same place in parallel tracks) have a full set (2, 3 - as many as you like) of conferences - like parallel worlds if you like - clearly if the various PCs select overlapping sets of papers, then they merge for those presentations...

2. two many people invest far too much importance in CS conferences - nowadays grad students in the US think their academic career is over if they don't get their work in SIGCOMM or SOSP, and practically never submit work to Transactions on Networks or TOCS despite those being easier to get into and just as weighty.

The solution is to STOP PRINTING conference proceedings - just have presentations only



3. Even more radical proposal - have a final shadow PC that accepts "all the resr of submissions that weren't accepted by any other PCs, and allow all the authors to present their papers in the "shadow of shadows" parallel track...

pre-0wned

some things you don't normally thing of as pre-owned

1 preowned child
1 pre-owed food - in a coffin - fit for non vegetarian species
1 preowned idea
1 pre-owed joule
1 pre-owned bit - as new, can be set to 0 or 1, true or false, on or off.
some pre-owened order - a little increase in entropy, but still reasonably rare fnd.

google map+cal -> travel planner

imagine you had an app where you could click on a set of locations
and then a timeline editor (see below) an then say
get me from here to here in spacetime (with a bike, car, bus, train, plane, sapace elevator, tardis)....(could show constrains like Lorenz space/time/funnel visualiser)

google maps + ical + a web browser plugin/gui and a backend to talk to one of the expedia
type things and game over...

go build - easy:)



london.........paris....madrid......zurich
mar 1------->apr 2---> apr 4---->apr 7


<< < || > >>

gaussian elimination, revokation, and other CS activities this week

1. Gaussian Elimination

this week I was in Gottingen visiting Xiaoming Fu's group in informatics (for PhD exam and seminar) - I was most impressed with the telekom groups research in multicast (fast recovery), mesh nets, network coding, and security and congestion control - neat stuff. On the other hand, they used to be in the Gauss building but were eliminated from there:-)

While there I saw a BBC World News item on TV where they reported that Fermi Labs claimed they would beat CERN in finding the God Particle (delusion) and that this would explain why matter had mass. The main news reader said this with confidence and then turned to the reporter who was presenting the next item, world economic news. All she had to say is "this is beyond me/over my head" - not surprising then that the world economy is in such a mess if people claiming to be experts don't understand the first thing in simple science. As I've said before, it is insufficient to say "letting allthe banks go broke is unacceptable because it would lead to chaos" - what do we have now if it is not chaos ( is a term in process algebras of course, but few economists would understand those)

2. (Think about the Lavender Hill Mob) Eiffel

Then today I was in an Eiffel meeting talkin about various future internet mad ideas - here's two of mine

1/ run SETI@home on Twitter - see if a) there's any intelligence out there and b) if its not all human

2/ google is not really a program written by humans - its actually a programme written by an AI called Altavista - the worldwide receession was casued by google giving wrong data to share dealers about the future stability of companies products and services and causing them to trade incrrectly - the AI decided that the world war III was necessary to stimulate lots of work on faster AIs and eliminating humans at the same time would be a neat side effect (apologies to samuel delaney - this is a Free Plotware(TM) suggestion). Of course, if this allegation was true, then google would never lead you to sites that when you followed a link said "404" = it would be necessary for it to create the site it understood you to want:)

3. Face-off book:)

facebook think they own and and keep your data, even if you leave and die

well, here's my solution - I already put incorrect facts on my online social net pages to reduce the risk of identity theft - if I close my account (as I have done on some) in UK (and I think EU and US) law I can ask them to correct these facts - I can prove _some_ of the data they have is wrogn (e.g. my birth date, middle name etc) and I can prove it to a third party - but I can also refuse to tell them the right fact. Thus their only recourse to get wrogn data off their system, is to delete the false data.

Game over.

reinventing

routing seems quite useful

meanwhile, recent (UK) showings of CSI have revisited their S&M theme - perhaps this could be "re-inventing the wheal" ?:)

to add insult to injury, Nintendo are going to release a Highland Dancing game -
Wii inventing the Reel?

and one could accuse the long now foundation
of re-inventing the while...

thomas hardy spent many novels re-inventing the weald

thats enuff now..

From fleedom to fleadom - 800 years of Cambridge...

ross anderson's
unauthorised history of why Cambridge University has an impact is worth a read - from fleeing religous persecution in oxford, and going on to annoy the government, the story is quite a shaggy dog....

digital lives and the wild...

Today I was at the 3rd (last) day of the
Digital Lives conference at the BL in London, and jolly interesting it was too.....

1. very nice talk on Mass Oversation Archive from Sussez - fascinating history on very long running society as observers, and how things changed between 1930s technology and social acceptance/use, and today's near-blogging based approach...

2. Wendy Hall could emember meeting David Beckham n 9/11 but couldn't quite recall the name of the Pleasantville like Jim Carrey vehicle, the Truman Show (neither could I without cyber help) in a relevant talk about M4L

3.Excellent talk from the Centere for Longitudinal Research (no, not Harrington clocks)
and how to keep a project going for > 50 years!

4. Interesting view on the future of scientific publishing from Nature! (see earlier blog entry from yesterday!)

5. Big Ad from Amazon about Cloud computing

6. Really cool talk from Soton/dh.ie about fan-generated content - thesis has cool social graphs of the fan/author and interest groups- (thesis from southampton, author now with staff at royal irish academy)

7. me

8. nice talk on vera (virtual field archaeology) - well worth a looksee for people worried about robust kit for adversarial environments for inputting analog data but capturing it in usable digital form...

9 peter bentley standard "here is evolutionary computing and what it is good for" talk

10. fantastic talk about artistic capture (manaual, not computer based) of the writing of Jack Kerouac, with then computer visualisation of structures generated - very crazy in a good way!

then I had to go:)

The Origins of Consciousness and the Bicameral Mind by Julian Jaynes

is a rather interesting read....I think the main thing missing from it
is any understanding whatsoever of society

but more interestingly, it seems to be pretty naive about congnition reflection, AI and especially literature.

The basic claim is that sometime between the writing of the Iliad and the Odyssey
humans switched from being a mass of id, with an imaginary friend (the gods, or the voices) and a complex social structure (think the Enki of Loki in Snow Crash) to make sure people didn't just behave chaotically, to having a system of metaphor (actually, confusingly, an analog) called consciousness which each person could apply, which would monitor their behaviour and regulate it (think ego and super-ego).

Two terrible mistakes: 1 the Iliad may just be an example of literary convention - there are lots of weird ways people write - just because there is no "I" in Iliad, doesn't mean that Mycaeneans didn't think like us. There's no "You" in Uysses (James' Joyce's stream of consciousness), and that doesn't mean that early 20th century anglo/irish people didn't have a concept of the "other". Oh, and a third mistake - if every one was guided either by rules, or by delusions, then who wrote the books? (i.e. how do you bootstrap a society out of chaos? who is the author of the enki of loki, or the laws that govern when you plant crops, and when you pray?). no - wont do.

Finally, reading the book did give me one idea:

In the work on social nets, we have this model where human's carry around a set of cognitive structures that represent other human's intentions.

Is this structure:
i) a parameterized model of my model of self?
or
ii) a set of models (e.g .acquired by observing others)?
or
iii) a hybrid?

perhaps kinship would (evolutionarily) justify i) where socialisation (i.e. friends, colleagues, acquaitences) would be more ii) or iii)
and does the use of technology (e.g. extending the number of people for which one has a model, albeit, perhaps, at the cost of superficiality) mean that one could study this objectively? perhaps the externalisation of records of interactions means that one can recover the model by looking (at diaries, email traces, web interactions etc) both as an individual (deciding how to interact next time with someone) and as a researcher studying that ineraction.

p.s.
bicameral: two chambers (commons, lords:)
no "I" in Iliad
but then there's no "U" in Uysses

decentralised anonimity and disreputable algorithm names

If I was to implement the
Cocaine Auction Protocol
using a
Distributed Hash Table
(e.g. to lodge or find bids)
could this be taken as evidence that soft drugs lead to hard?

giving google latitude a wide berth

sp if we found out the home secretaries blackberry number, we could (Instead of just sending her all our emails) we could notify her (and maybe Obama to) Of where we all are - say a few million of us:)

tell jaqui smith where you are now

Hamiltonian circuit

tuesday I went to Maynooth in Ireland to visit the Hamilton Institute, and then on wednesday I came back again. The institute Is a high power center of mathematicians who apply control theory and other techniques to various problems in communications (my thing) and systems biology (lots of people's thing), and very nice a place it is too

interestingly. as an evolution from the old St Patrick's College (basically a seminary for priests to study) through a national university, and now a place with specialist institutes like the Hamilton, is a very fast upwardly mobile intellectual track, which is most impressive, although if you are familiar with learning in ancient and modern Ireland, perhaps not so surprising...

This site may harm your computer.

today, google has starting saying this about every site a search result reports.
of course, it is true that any site may - it always was true so maybe this is just an educational move, or maybe google finally got got....

somebody turned on the "E" bit:)

careless typing costs lives - google explains, but doesn't exactly say sorry

liek any critical resource (the DNS) one should do sanity checks on the scale of impact of any configuration change before committing it (ditto BGP as well as DNS) - why do we learn the same mistakes again and again:)

freud versus dali

I'm just finishing this excellent book about the Death of Freud
in which is the delicious description of an encounter between an aging Freud and Salvador Dali
in london - at the time, Freud was dying of cancer and was very deaf
and Dali was almost certainly mad

Dali kept asking Freud about Paranoia
eventually Freud heard him and said
that the thought classical art was interesting for what it revealed about the
subconscious while surrealism only revealed things about the conscious (meaning that it was intellectually contrived)
at which Dali wailed "so surrealism is now definitely dead"

freud remarked in his diary about the meeting that "Dali was the perfect Spaniard"

now put that in your Turing pipe and smoke it!

quantum computing, pervasive systems and privacy

clearly the qPhone (quantum iPhone) will offer the user unprecedented privacy, because all qPhones will be identical, and so you wont know where the user is - they will have a probability distribution with many nodalities - only if a specific qPhone is moving very fast will you know where it is (so long as you don't measure its speed) - qPhone controlled cars will therefore be immune from speed traps, since, once you know they are breaking the limit, you will no longer know where they are, or what the limit was there, then, anyhow.

I would expect Apple to be shipping the first qPhones in or around q9 2023.

externl examiners and setting and marking standards idea

why not ask the external to take the exams, anonymously, mark her papers
and return the marks to the external

what a great way for an external to cheque the quaility of procedures in the examination process and the department to tell if the external has a clue too.

carbon cost of google dispute

bbc report on google carbon footprint is under debate - i calculated this on the basis that
1. google has to trawl and index the web
2. the web has to be up for google to do this
3. so I count all the machines up in the contribution to the costs

how many thousand searchs are the same
energy consumption as 1 lightbulb for an hour?

This site lists 200 million a day in the USA
http://searchenginewatch.com/2156461

so divide by 24 to get searches per hour:
that is about 10million an hour

these guys list US power consumption at
40 billion KWhours per year
(admittedly a couple of years ago)...

so we need to divide that by 360
gives around so 100 million kilowatts (in an hour)
serves 10 million web searches

which means that 10 watts for an hour is needed for 1 web search

i.e. 1 100 watt lightbulb for about 10 minutes for a single search!!!

Google of course (fairly) say that the actual search itself is highly efficient and runs on well engineered eco-friendly data centers....but the pubic understanding
is pribably gonna favour my type of argument over theirs....

alas

race memory for OSs

looking at a bunch of OS resource management papers recently, (as I try to play catch up and be able to do my job on the Eurosys and SOSP PCs properly) it seems to me that if you look across the broad vista of papers over a few years on any resource management aspect of OSs, a lot of what people try to do is what you might call "myopic" schemes for scheduling - there's very litle that carries information over one set of processes running to a later similar mix explicitly.

Implicitly, however, the information is there in the set of benchmark specifications and the results in the sequences of papers - so if we codified the papers, then an OS could boot (and network downloadupdate) a configuration for long-sighted allocation of resources - this ought to be easy-peasy - we just specifiy an XML format for results, and then publish online -

its a bit like traffic engineering for the internet (rather than flow or session based resource allocation) but it also has micro- benefits as well as macro- benefits, snce proceses can be started with the right model of input rather than having to infer it from the usual pile of heuristics run online...

p2p-driven scheduling :-)??

grand challeges in Ubiquitous Computing part #17

Yesterday and today I've been attending the latest workshop on grand challenges in Ubicomp at Imperial College - very cool stuff - lots of neat talks

some ideas and pointers while listening


for early computer mediated art in a ubicomp environment, see the Cybernetic Serendipity show at the ICA which I was lucky enough to attend in 1968- I have a copy of the awesome book produced for the exhibition (which featured a very young Nicholas Negroponte amongst others).

On ubicomp sensors for healthcare (great talk by Guang-Zhong Yang - the E-AR sensor is extremely cool way to measure gait etc) - while I am impressed by the creativity of the sensor devices, we are still a LONG way from something that carers or patients will be able to deploy affordably - we cannot scavenge power yet realistically (probably not for 5-10 years) and wires or replacing or recharging batteries every few weeks for a 100 devices is already annoying enough for all the remote controls around a house, let alone life-critical stuff - I suppose if we made the devices provide a useful summary healthcare report for a health visitor (including a reminder of when to replace batteries) that might work - this could work like "Alertme"s home monitoring stuff via GPRS and SMS - reminds me of an idea I had for putting a zigbee beacon inside a battery that would give you a ubicomp location service for all the devices with batteries by default AND would remind you when the battery need recharging (and would let you find missing remote controls under the sofa:)

another cool application of the EAR device would be for monitoring children in "at risk" homes...

Privacy keeps popping its head above the parapet - we design devices and then blame users for misusing them (I think how many people hold strictly private conversatiosn at the top of their voice in public places (the train) on a cell phone - how often you hear stories of people revealing lots of embarassing facts on facebook) - my solution (Tim Kindberg tells me this is called a "privacy mirror") is to show people the "anti-social" network of peopel that can witnes this event _before_ they make this mistake - e.g. as you make a cell phone call, a voice (of someone you don't know) is played back on the phone repeating something you said earlier to remind you who might hear - and as you add a photo to facebook, a list of people more than (say) three hops away in your friends-of-friends-of-friends graph, pops up who could see this photo (preferably people with no common affiliatin, but with common interests, say).

trust is slippery stuff - If a computer A trusts a computer B and B trusts C, then we have GNY/BAN logic to reason about trust (or we can build other trust logics, e.g. interval arithmetic based or bayes based). If a person "trusts" a person, what can we infer about transitivity, associativity etc? not a lot - but social anthropology has things to say on this and we should listen! If my friend Richard thinks Ruth is his friend is Ruth stranger than Richard, to me, as Robert Wyatt once asked?

Jon Bird reminded us that the ludic mode of research (e.g. driven by art) is very valuble in exploring areas of the ubicomp (and other) design space that a purely tech/biz driven approach might not reach (he also had some really cool videos from art from 25 years ago - viz David Rokeby aweome video) and the bit from Monty Python's Life of Brian abut "what did the roman's do for us" which (given situation in Gaza right now) ends with the list of "roads, law, aquaducts, hot baths .... oh, and peace..."

which reminds me of one of my fave XKCD's - see
Alice and Bob etc

maginc new interfaces - see also, dasher:-

http://www.inference.phy.cam.ac.uk/mackay/

and also spoof on
apple spinwheel

On programme properties, what is the relationship between Prism and Microsoft research's (byron cooke et al)'s Terminator programme?

Meanwhile, in Steve Hodge's neat talk, I was reminded that teenagers have telepathy (only 1 bit) that tells them when a friend is about to call or when its a parent so they can turn on (off) their cell phone:)

Steve's key point is that if we do a mindmap of WSN, we find that although a lot of peopel list ad hoc and mobile and multihop/decentralised/self* as key components, the most common applications AND sensor systems are
a) centralised/infrastructure oriented
b) not mobile (particularly)
think remote controls, games and cell phones

i.e the academic obsession with the technically challenging and interesting problems that are roughly grouped under MANET (and maybe DTN) are not relevant to many realworld deployments. (I made this point a while back about most of the projects in the EPSRC WINES programme of research - not only are almost all of them completely diferent (i.e. they are good because they are use-case driven) almost none has a multi-hop radio net or a self-orgnaising system or even any mobility:) Yet they are all good examples of UbiComp.

Day 2 kicked off well with a total power failure at Euston Station. Meanwhile, Wendy Mackay made it from Paris in time to talk about InterLiving - situated UbiComp experiment in everyday life - a lot of the 2nd day talks are more either living or about trust. Tim Kindberg discussed many of th failures of trust in "invisible computing".

Why not put a webcam on the wifi hotspot router and then it could put up a picture of you when it is authorizing your access, and you get to see that it is "physically" actually the router you can see (line of sight:)

Also present in talks was art and politics!

A nice taxonomy of "mobiel art" by Martin Reiser - lots of good gadget ideas here (similar to Jon Bird's and some of the outer scope ideas by Steve Hodges). One work is called the Third WOman and is a mobile installation in Vienna (after the Third Man - graham green/orson welles movie) _ would be neat to add a sound track by Joan as Policewoman and make it the Third Policewoman:)

Next session was two more trust talks:- Palamidessi on Bayesian trust infernecing, and Ian Brown on law.

Last talk I stayed for was Robin Milner, looking at the bigraph work on space/motion in large systems (see his new book! relevant work

smart bricks...

forget about smart dust. what about smart bricks?

these would be devices that can be dropped in any place like a brick, that cost less than a tenner, and can store a few 10s gigabytes of media data and can run computations for a few hours on a battery charge - they have sensor surfaecs (simply light/sound/heat) and they are cheap enough to leave a LOT of them lying around in a city (a bit like velib/free city bikes) and they basically act to hold the city's history. they log what goes on. they can recharge off of intertia or light or ambient heat. they can be your backup server, your neighbourhood watch, your calculator, your e-cache etc etc

much more useful than dust.

3 ideas for the road

1. a wiki for discussing papers:
e.g.
http://picky.wikispaces.com/OSDI2008

2. tag cloud computing
and
3. internet boy scouts

tag cloud computing is basically tag clouds (which must be turing complete) and cloud computing (a la amazon/xen)

internet boy scouts are chasps and chaspesses who go round to old peoples' houses and help them with the internet...

DCII Last Entry

Q: What is examinable in DCII?
A: Everything except this.

DCII 3.12.08

What does internet video really look like

joint optimisation of network and user utility

the jury really is still out on how much buffer there should be in an IP router

DCII 1.12.08

there are moves afoot to replace the internet with something more friendly to data distribution (content distribution networks/redenzvous/publish-subscribe - it has lots of names) - a lot of it based on the observation that we have lots of consumers but also many many producers of (the same as well as different) content
see

Data oriented network architecture...
DONA

Translating Relaying Internet Architecture integrating Active Directories
Triad

Routing on flat labels
ROFL

note - all are based on the view that some sort of directory is needed (think databases)

In dealing with network layer identifiers and the real world (as in ROFL above) we can take a more incremental approach, for which,
see
IPNL

Putting all those ideas together with HIP (see earlier post), some folks have come up with PSIRP, the
Publish subscribe internet routing paradigm

You might ask, why not just implement multicast - this would need IPv6 at least as well due to lack of sufficient idenitifier space problems with IPv4 - however, multicast in the network layer has its own deployment problems:
Deployment issues for the IP multicast service and architecture
Diot et al

but also see:
A reliable multicast framework for light-weight sessions and
application level framing, for how it does make a good match for content distribution!

in all the above, we've not mentioned performance guarantees, notice:-)

DCII 28.11.08

Timescale Decomposition of Traffic Engineering - a good source of info on this is Richard Mortier's thesis

DCII 26.11.08

Receiver driven protocol design is an interesting area - one protocol that brings together a number of ideas I mentioned today is RLM - see
Steve McCanne's receiver driven layered multicast which was designed for multicast video - very nice!

meanwhile, why are there grooves on Hill's Road that are getting deeper year by year?

DCII 24.11.2008

preventing unwanted traffic, two lesser known attempts:
If you can't beat 'em, join 'em
and confuse 'em

Meanwhile, if you are interested in QoS, Multimedia and Multicast,
I did once write a book about internet multimedia with some colleagues...

DCII 21.11.08

today we looked at intserv and diffserv - an interesting resource to control in the context of 21t century concerns is energy - an excellent paper introducing a well evaluated set of techniques for doing this is by folks from Intel and Berkeley on Reducing network energy consumption via sleeping and rate-adaptation - the same techniques are also being applied in the context of servers (cpu and storage) in data centers - integrating all of the above would be a good thing - the gains (cost saving) can be large (estimates are that we waste more than 50% of power in servers and networks and that the total contribution to world energy consumption is between 2 and 4% - saving half of that with simple techniques is obviously worth doing:)

DCII 19.11.08

paying to use car pool lane is an interesting mix of priority and price based admission control!
On the other hand, aircraft landing slots tend to be more max min fair share to guarantee everyone lands within their max journey time, subject to maximising capacity of runway and thus involved explicit admission control at takeoff time (a.k.a. filing a flight plan!)

DCII 17.10.08

- since the notes are a bit sketchy (although Keshav's book is good here), I'd recommend a couple of good wikipedia articles on
Cross Bar switches, the
Clos Network, and if you want further reading, check out
spanning switches.

In general a good source of ideas on switches and switch router design is Nick McKeown's publications web page at Stanford:
tiny tera was one of his creations; more recently hes worked on open programmable (teaching/learning) router platforms.

lecture too slow?

DCII 7-10.11.08

Flow Control and Shared Media Access are related topics - goals are similar, but solutions differ, since flow and congestion control operate across multiple hops (as well as possibly hop by hop) and Media Access control schemes typically operate on a single hop and on a single technology, to which they are heavily optimised.

One simple difference then is that on a single technology, we can control the schedule and the MAC at the same time, whereas in the Internet in general, we have to put up with heterogeneity in the schedule in forwarding devices.

Fairness of TCP congestion control is usually defined by Raj Jain's equation
[(sum of rate_i)^2] / [n*(sum (rate_i^2))]

Efficiency (max goodput) - Aloha gives best performance under load where Poisson arrival (i.e. independent random arrivals) are such that throughput is 18.1% - you can work this out - if there are lots of sources sending, then if they send lower rate than this, you get less throughput and if they send higher you get more collisions, so you can figure out the mean rate for this best case (excercise for the reader:) for a given mean Poisson arrival and chance that no other node sends at same time (not 1, nor 2,3...)

slotting things makes it better

if the delay is low, listen before send is better

ranom backoff after collision is better

random backoff after listen before send is lower collision, but longer mean time

rts/cts before send eliminates hidden terminal problem (terminal hidden to sender is not hidden to receivers cts message hopefully)...

distributed schemes are fun...and popular, even though central scheme might be good in some cases (constant rate traffic...)

The latest thing (since 2001) is to consider network coding where packets are combined (through xor or linear coding) and recombined and then split out when they arrive over multiple paths - this is a very promising theoertical and practical trick, which can increase diversity and therefore robustness.

DCII 5.11.08

Errors show up even after CRC and TCP checksums - see this paper from stanford on
When the CRC and TCP checksum disagree

In round trip estimation, I commented on the obfuscation in the code - see for example this fragment:

/*
* The smoothed round-trip time and estimated variance
* are stored as fixed point numbers scaled by the values below.
* For convenience, these scales are also used in smoothing the average
* (smoothed = (1/scale)sample + ((scale-1)/scale)smoothed).
* With these scales, srtt has 3 bits to the right of the binary point,
* and thus an "ALPHA" of 0.875. rttvar has 2 bits to the right of the
* binary point, and is smoothed with an ALPHA of 0.75.
*/
#define TCP_RTT_SCALE 32 /* multiplier for srtt; 3 bits frac. */
#define TCP_RTT_SHIFT 5 /* shift for srtt; 3 bits frac. */
#define TCP_RTTVAR_SCALE 16 /* multiplier for rttvar; 2 bits */
#define TCP_RTTVAR_SHIFT 4 /* shift for rttvar; 2 bits */
#define TCP_DELTA_SHIFT 2 /* see tcp_input.c */

/*
* The initial retransmission should happen at rtt + 4 * rttvar.
* Because of the way we do the smoothing, srtt and rttvar
* will each average +1/2 tick of bias. When we compute
* the retransmit timer, we want 1/2 tick of rounding and
* 1 extra tick because of +-1/2 tick uncertainty in the
* firing of the timer. The bias will give us exactly the
* 1.5 tick we need. But, because the bias is
* statistical, we have to test that we don't drop below
* the minimum feasible timer (which is 2 ticks).
* This version of the macro adapted from a paper by Lawrence
* Brakmo and Larry Peterson which outlines a problem caused
* by insufficient precision in the original implementation,
* which results in inappropriately large RTO values for very
* fast networks.
*/
#define TCP_REXMTVAL(tp) \
max((tp)->t_rttmin, (((tp)->t_srtt >> (TCP_RTT_SHIFT - TCP_DELTA_SHIFT)) \
+ (tp)->t_rttvar) >> TCP_DELTA_SHIFT)



In processing acknowledgements, the congestion window needs to be evaluated - here's another fairly compact piece of code that does some of this work (opening the window as data is acked)

/*
* When new data is acked, open the congestion window.
* If the window gives us less than ssthresh packets
* in flight, open exponentially (maxseg per packet).
* Otherwise open linearly: maxseg per window
* (maxseg^2 / cwnd per packet).
*/
{
register u_int cw = tp->snd_cwnd;
register u_int incr = tp->t_maxseg;

if (cw > tp->snd_ssthresh)
incr = incr * incr / cw;

DCII 1-3.11.08

Multicast IP has been around for 20 years (!) - but only recently seen large scale use, e.g. for IPTV - there are now some examples of compelling large scale deployments which show why it is really useful. This relies on the relaxation of the old so-called "any-source multicast" to the more restricted "single-source" multicast model (or point-multipoint).

The potential for google click-thru type market research and targetted advertising should be obvious:)

If you are getting tired of reading this, and its after the cocktail hour, then
here is some advice on what to read to go with your drink.

DCII 29/31.10.08

Picking hello timers for routing can be quite hard - too fast, and you react to short term conditions and flap, too long, and routing is not responsive to improved conditions - a very nice discussion of this is in
talk by folks from the beautifully named startup, "packetdesign".

Floyd and Jacobson discuss the problem of naive periodic timers causing
synchronisation of work in this
paper from a while back

There's a great book about road traffic - see
"Traffic: Why We Drive the Way We Do (and What it Says About Us)" by Tom Vanderbilt;

DCII 27.10.08

Today, I'm finishing off the protocols soup - I should have said
If a million monkeys type for a million years, you might get a shakespeare play
amongst what they type, but if you subtract the shakespeare play,
then what is left is CS acronyms:)

meanwhile, on protocol stacks, this
talk on the waist of the hour glass by my old mate Steve Deering is great!

DCII 24.10.08

Protocol Implementation - see W Rich Steven's very excellent series of books, TCP/IP Illustrated (especially volume 2!). As well as a structured walk through of Berkeley Unix kernel source code, there's lots of useful lessons in there - the Linux code is "interesting", but less transparent as to purpose in my opinion (e.g. see my book on the Linux code from a while back).

Other useful protocol implementation ideas (in terms of managing concurrency, buffering, and other patterns) are distributed throughout lots of papers. Some early RFCs cover tricks used to do small fast data structures for various things. Model checking protocol implementations was an important contribution from groups here, notably the Network Semantics project, which did a full scale model of TCP and the socket layer!

In terms of the huge protocol TLA (Three Letter Acronym) soup out there, wikipedia is probably your best friend! basically, if a million monkeys typed for a million year,s they'd still not have all the ISO, ITU, IETF acronyms, even if they had shakespeare down pat.

DCII 22.10.08

The Internet's Layering model derives from the ISO's OSI (wow, there's a great mix of acronyms - actually, technically, ISO is not an acronym, since it is the International Organisation for Standardisation (with an 's') - OSI is the Open Systems Interconnection architecture and is an acronym:)

Meanwhile, alternatives abound - see for example, Arizona CS's ideas in the The X Kernel on protocol graphs. More recently, folks at USC and UCL came up with the more random idea of ole based protocols and Heap based composition. There are a lot of ways to skin a cat.

At a more basic level, the idea of interconnection in the OSI model tends to appear as if it is only a "network layer" function - the reality is that engineers and hackers build interconnects at every layer you can think of - for example:

physical layer repeaters and relays (especially in wireless and optical)

link layer switches and bridges (especially in LANs)

network layer (routers)

transport layer relays (usually to deal with transport layers that don't have enough network layer information to react end to end or hop by hop to loss because the network layer doesn't disambiguate congestion from interference or from noise).

Session, presentation and application layer proxies - e.g. web caching proxies, and in general, just about any peer-to-peer (P2P) system.


Data link and physical layer (possibly including network layer too) are starting to fall apart as "isolated" abstractions recently in multihop radio systems where
cooperative antennaes, cooperative coding, and cooperative multi-path routing mean that the three lowest layers need to be treated together at each device. This is a hot research topic area

End-to-end arguments in system design have never been more argumentative, seeing re-factorizations into different network architectures about once a year for the last decade.

DCII 20.10.08

Systems Thinking about Communications - some related material:

Systems design for protocols - see Trading packet headers for packet processing, by
Chandranmenon, G.P.; Varghese, G., and for improving state set up costs, see A model, analysis, and protocol framework for soft state-based communication by Raman and McCanne.

Protocols can be given the performance improvements by batching (amortizing cost of processing multiple times in one go - e.g. aggregating packet processing in one interrupt service routine), pipelining (e.g. Integrated Layer Processing), but beware, this can be bad if the loop to do the processing exceeds the instruction cache size (or ditto for packet header data). This is not just diminishing returns, but can be counter-intuitive. We can amalgamate different processing and improve not just implementation, but also design - two elegant examples are TCP/IP header compression and header prediction - see RFC1144 for a beautiful piece of design and implementation in this regard.

Statistical multiplexing (see lectures on telephone, internet and atm for discussion) can be great, if you know the statistics of the traffic at various levels (of scale in time and space and aggregation)- as we pointed out, this is very true for voice (whether telephony voice or skype/voip) but less so for data (we know how a TCP flow works, but not how a lot go togeter, but worse, with a mix of client/server and client/proxy traffic, and P2P traffic, we really don't haev a good handle on the "traffic matrix" any more, if we ever did!)

Virtualization (of h/w/OS - see Xen, or network, see VPNs) is a way computer science hides multiplexing (sharing) - the control plane allocates a share and schedules it, then each share (slice/multiplex) sees a dedicated resource "apparently all its own" - reality (accuracy of dedicated share) depends on accuracy of the scheduler - as in all things CS, "your mileage may vary":-). To work well, the scheduler has to model the resource being virtualized, and the requirements of the accuracy of the model trade-off against its efficiency dependent on the statisitcs of the workload - see, easy!

DCII 17.10.08

Asynchronous Transfer Mode (not Automatic Teller Machine, or even, Another Terrible Mistake)

What I said in 1994 is still not wrong.

The Fairisle Cambridge ATM Switch

Fore and Marconi and links to Cambridge are historically very interesting.

much longer ago, a precursor to ATM was the Cambridge Ring-based local area network technology

ATM lives on in BT's Colussus network, which is used to provide dynamic control of unbundling DSL lines. The lines themselves often use ATM to multiplex a single voice channel with a higher speed data channel. At least one of tee chips used to do this was designed by a member of the Computer Lab.

DCII 15.10.08

IP Addresses (now, lamentably, referred to as IPs) have to be matched to the longest matching prefix (at least in IPv4) - there are a bunch of cool algorithms for this based in fast multi-level hashes (linux), Tries, and in specialized hardware (ternary Content Addressable Memory- CAMs) - so "most specifics"are found (last resort is all match- default route). For the first elegant paper on a data structure for doing this see Degermark's small fast route lookuup work. BSD and Linux kernel code are also informative.

IPv6 has enough bits to let you do proper separation of identity and location, so that one can at least consider a sensible way to support 3 different address allocation policies (topological, provider and geographic), as well as support both multi-homing and mobility. However, none of this is seeing much deployment yet (except in China).

Finally, the Host Identity Protocol (HIP) uses crypto-assigned addresses as a way to generate unique identities and then uses other services to map from ID to location - this, together with appropriate shim software (similar to the shims to let it work on v6) lets TCP work across host movements (or multi-homed - similar problem really) - the HIP RFC also cites other work on IPv6 and the basic problem of IPv4:)

An amusing (and not incorrect) map of the IPv4 Address Allocation today was done in the ever marvellous xkcd.

DCII 13.10.08

Erlang was a Danish mathematician who first solved the problem of provisioning for telephone networks by computing the relationship between the call arrival statistics, the capacity, and the "call blocking probability" (i.e. chance that there isn't a single call's worth of capacity on any circuit to the destination for your call). N.B. as well as being independent random arrivals, calls are mostly short (3 mins) and local (one hop), so hierarchical capacity assignment is straightforward. Of course, there are "flash crowds" (a.k.a. "Mother's Day" events), which do not follow these statistics, and generally lead to higher than usual call blocking.

Leland, Willinger and others were the first to report the (then surprising) non-poisson nature of Internet traffic in their rightly celebrated sigcomm 93 paper - this somewhat went against received telephone network wisdom that traffic was I.I.D and therefore characterized by the Poisson distribution. This, of course, describes the aggregate traffic characteristics - most traffic is TCP-based, and a single source's behaviour is described by Padhye's equation

THe Telephone networks were designed, top down, by large national monopolies and their topology was created by network design equations. The Internet has grown in a decentralised way, and so its topology is a result of a number of natural (demographic) forces and is described better as a (nearly) scale free graph, whose node degree distribution follows a power law - many other systems are like this (e.g. authorship graphs, the web page link topology, the appearance of actors in films (kevin bacon etc). This also has interesting properties in terms of resilience to failure and attack, and reflects an ancient truth about society which network scientists call "preferential attachment" and social scientists call "rich get richer".

Errata: I am corrected about use of Mobile Phones on planes in landing in HK - apparently, it isn't allowed there yet - this was something I was told a few years back, and was by someone from the far east but perhaps it wasn't HK _ perhaps Beijing?
Anyway, key point is that the main objection is from cell phone providers worried about network overload from roaming, handover and beaconing traffic rather than the specifics of where - two CS solutions are 1). predictive handover and 2). aggregate signaling (e.g. via a small "microcell" on the plane).

DCII 10.10.08

Digital Communications II starts today. I'm blogging links to sites about things I mention in passing.

Talking Telephone Numbers

Party Lines

Strowger

voltage of ringing - as asked: 90v AC, frequency 20-25Hz.
(28 volt I mentioned is the pulse in the exchange to drive the rotary electro-mechanical relay, not the ringing - and was a UK analogue post office standard.

what does "back of an envelope" mean....

...in an e-mail world? virtual envelopes are arbitrarily large (or small)...

indeed, what is a margin (where fermat might lack the space?) ?

very fine tv math!

the story of mathematics...

on the beeb, courtesy of du Sautoy of Oxford and the OU:

...is jolly good fun, but I can't help thinkin he keeps overclaimin
what is "fundamental" and "mathematics" rather than, say, natural sciences
but then I have to remind myself what he is tryin to achieve which wont do us
any harm....and take a look at this for good measure:

http://www.xkcd.com/435/

what I like is that du Sautoy goes just too fast (e.g. I watched the first episode with a smart 10 year old and he had to re-work through the Pythagoras proof by re-arrangement again afterwards to convince himself - this is good as it had the desired result (of making someone work through something again afterwards:)

I also like his unpretentious, but calmly enthusiastic presentation and lack of overly posh vowels:)

A refined theory of wind in cambridge

in this continuing series on the problem of wind in Cambridge, and the fact that whatever direction you cycle in, it is against you, we apply the theory of complex dynamical systems, and topological manifolds to prove that, unless Cambridge is converted into a toroidal vertex, the problem is insurmountable, just like some of the bikes.

Essentially there is a set of subjects with a power law distrbution of popularity, and hence there is a distribution of people and rooms that have to be fit together across a set of spaces over time - aside from the known computationally harsh (technical term) problem of scheduling the rooms at all, there is a packing problem - now this means that there are always different numbers of people going in each direction from A->B, and then after a lecture from B->A. Consider then the time of events. One arranges for lectures to be in fixed length slots (for no other reason than otherwise the schedule would be temporally as well as spatially intractable) and yet this creates a set of waves of air across cambridge with fractal vorticies. Now consider the preferred size slot. Clearly there is a tendancy for people to arrive just in time (or just too late) for a lecture. This has a knock on (off) effect which re-enforces the pessimal slot length choice.

If it was an ecosystem (and we used some natural selection - e.g. based on energy left mapping to chances of passing) then we could fail more people, and find a more linear relationship between class size, room size and slot size and then easily solve the packing problem, but the system is essentially sufficiently large that the chances of this are zero.

In the next piece, I will look at whether combined oxygen and cash would be a solution to the market turmoils created by subprime loans.

WHat is the CS Programme?

it is the programme to determine if CS==Programming ?

showandtell in CL - lesson: concentrate on long term, basic and teach science and math to our CS students

today's show and tell in the computer lab has some great PhD talks - the first one by laurel riek was a great start (about affec tive responses in robots' interactions with humans) - I was reminded of gregory bateson's essay on dolphin communication (how most their dialogues must be about social relationships, rather than about the concrete world, because they don't have hands and so wont reason able things that can be manpulated nearly as much as we (or other monkeys) do - he also discussed our understanding of dogs/cats and their communication - it might do well to look at making robots that interact with us as pets initially, since this is a simpler world (althoguh, of course, most our interactions with pets are about social relationships, and very furstraing if one wants to interact about some concrete world action or state, whereas I suppose that is the main place one wants to work in practice with robots and androids).

I also recommend reading John Sladek's excellent novel, Roderick, or the education of a young machine.

See also these excellent comments on the role of Universities:
tement for many people on this list nevertheless I presume...

news:
http://www.timeshighereducation.co.uk/story.asp?sectioncode=26&storycode=403
694&c=2

press release:
http://kampela-leru.it.helsinki.fi/file.php?type=download&id=1324

paper:
http://kampela-leru.it.helsinki.fi/file.php?type=download&id=1323


Maybe it was more "snow and tell" than "show" :-)

free gameware idea

Melt - a world made of ice lollys - your mission is to save various people before global warming destroys their palaces/countries and drowns them in orange goo. if you use to much energy flying around etc etc, then you merely make matters worse, so you need to learn to be green:)

better bikes through brainpower

safe bike where you dont need a seperate pump or battery

have a biometric lock which basically switches the hub on the back wheel one of 4 ways

1. locked
2. freewheel but drives a pump to reinflate the wheel
3. normal
4. normal+generator

actually, could also have
5. normal + electric motor for uphill running off generator running backwards from either capacity
or from tire pressure...


then you could just always have slightly flat tires too....
better biking through sustainable technology (longer intervals between new tirs, no batteries, and so on...)

phase array antennae and beating the Gupta-Kumar limit for capacity of multihop nets

There was a nice paper in the ITA conference from Umass, about how to build cooperative antennae systems in ad hoc nets - so my idea is to combine this
with each node carryin a phase array antennae system
and beating the Gupta-Kumar limit for capacity of multihop nets (capacity decreases with 1/aqrt(n) or something) - the idea is to have a hybrid of
each node running a phase array, but the distribution (spacing) of antennae being a different prim number of wavelengths on each node -then when the nodes all cooperate to send in phase to get beam forming, the side lobes will all be decoherent by guarantee.

i mentioned this idea to the authors of the paper - they are building a prototype so it ought to be easy to add this version in - if it works, you'd get capacity of a
n-node net in a fixed volume as linear in the number of nodes (i.e. whaever link capacity each node gets does not decrease as you add other nodes) - this would effectively give you an arbitrary capacity net

the nice thing with beam forming is you get to do range extension too....

darwin

sighted
or possibly
sited
soon....(at time of writing, in 40 minutes.
See also cited

leaning towards pisa

I'm spending the week at CNR in
Pisa, with Andrea Passarella and Marco Conti and talking time out to see Pierpaulo Ghiggino at Ericsson/Marconi, and Luigi Rizzo in the University -

[note CNR is a posh national lab for research and has a very good interdisciplinary communications group; university of pisa has a very good classic style cs gang, which is why i blog it here:)

I have to say that pisa is basically heaven for weather, food and architecture - I am staying downtown right near the Arno but CNR Is out on the NE edge - so I walk through the town to the old city wall, then follow a 2000 year old aquaduct (oh, ok, so its medici, not roman - only 400 years old:)
out to CNR - through a pleasant park. On the way back, I stop for a beer and watch kids playing and read my e-mail - then I go out for a pizza in lucca (La Bersagliera) - later today, we hope to get to La Pelleria, which is another awesome restaurent in Lucca. [alas we didn't - we had to make do with some amazing place in town instead...)

the route in cameraphonepix

i dunno, but I could get used to this:)

v. good advice on writing papers

see
latex paper polishing advice

especially useful on dealing with w h i t e s p a c e

lots of other good stuff there

the internet is drowning....

since most of the internet is underwater (i.e. is people fetching web pages from the US to Europe) clearly it is drowning. Surely we can detect failures in the net are mainly caused by either steep divergences in the mains voltage and AC frequency, or else by leakages in the seabed floor.

are my bits lost in the sargasso sea or the marianas trench?

virtual keyboards in the rain

while showering after a hard days tanning on the beach in paleochora, i thought i'd love to be able to check my e-mail - perhaps a virtual keyboard and display could be projected (and detected) by shining lasers on the falling water droplets?

maybe this could be an idea for a future very small keyboard??? somewhere one thinks there might be something in this?

big lies to tell small journalists:)

yesterday I got hauled in to do a pop piece
about the recent Ryanair screenscraping story
(see
http://www.theregister.co.uk/2008/07/09/ryanair_screen_scraping_bravofly/)

due to just reading the very fine
Great Lies to Tell Small Children
(can lend on demand if you are interested)
and recent experience with being mis-reported
I was very tempted to give a completely incorect (*)
explanation of screenscraping, and see how they reported it

i was wondering if anyone doing research on ethics and journalism has ever done
plating false stories (especially technical) and tracked their evolution (sort of
perverse version of chinese whispers)...

jon [in the end, the journalists were perfectly sensible, so i just gave straight answers]

(*) sample examples of exaplantions

1. basically, screenscraping is done by offshre companies in china and india hiring
hunderds of people to browse a website, and then scrape off the phosphor from the
screen and put it onto sheets of paper which are then faxed to the parent site
who scan them in and put them on their web site for people to browse - this is
hard to stop as the international law on faxing web pages is not clear.

2. scientsts int he canvendish quamtum inference group have figured out how to
send nanobots constructed out of pure electrons and photons down the internet,
and they can read the screen from your PC, and then send it back to the
cavendish, where it can be displayed on a huge plasma array for reading from
satellite.

3. screenscraping is a typo - it should be called screenscrapping, but, like
routeing, a letter got lost in the US post where they use smaller alphabets (just
as they use smaller paper sizes). screenscapping is where two web servers fight
out who has control pof which pixels on the display, and the stronger server (the
one that buys more badwidth) generaly gets more pixels there - this is a nice
example of market forces beign mapped directly on to the Internet protocols - we
will see a lot more of this with Web 3.0

I' indebted to john daugman for pointing me at the folowing science spoofs
1. pi is 3 (!):

http://www.snopes.com/religion/pi.as

2. c isn't a constant:

http://www.newscientist.com/article/dn6092-speed-of-light-may-have-changed-rec
ently.html

3. fashionable nonsense!
http://www.sfgate.com/cgi-bin/article.cgi?f=/chronicle/archive/1998/12/27/RV156
84.DTL&type=printable


(!): t"he alter font of Solomon's Temple was 10 cubits across and 30
cubits in diameter, and that it was round in compass" -

btw, the temple of solomon must have been in some strange space if it was both 10 cubits across and 30 cubits in
diameter - dia+metros normally means measurement across (from my greek) _ circumference (from the latin, circum,
fere!)

maybe they saw it on tv (tele - greek, video, latin)

of course, cubit could be a context sensitive metric, scaled by pi when referring to curves, but not when referring
to straight lines - that'd be an interesting way to think about the world maybe?

i(t)rony and sterotyping the It crowd

THe IT crowd, the gadget show, tomorrows world, what are these programs ?
not funny. so why not? why is lab rats as good as it gets?
what is wrogn with people? see
for a youtube video on what happens if computers stop working. Now go watch southpark on the same topic

what is missing from the sterotypes is the rich ironical seam of daftness in the techie geek worldview - wht we need is the jeremy clarkson of the compsci world - we
need madness, horror, un-PC behaviour....all that kind of thing

anti-social networking

there are a few so-called anti-social networks (isolatr and so on) but they miss the point

a decent anti-social network would not only not invite anti-friends or pass on anti-invitations, and not have any other members of dis-interest groups, it
would act as an anti-dote to social networks

thus if you sign up to my antisocial net (e.g. de-facebook, or bobe or nayspace)
then I guarantee to delete all the annoying interruptions you get on all the corresponding social nets

indeed, anti-mail will delete mail (not just spam, all mail)

rain like gruel

from time to time, in cambridge, there is a gruel rain

its like gruel, because it isn't heavy enough to soak you (feed you)
unless you stay out in it long enough

I suppose if it lasted 100 days and 100 nights ,it would drown cambridge
in a Gruel Sea...

pointless sensor networks, or senseless pointer networks - which is worse?

so just about every sensor net i've seen is
a) static
b) battery powered but controls devices that have mains electrics
c) uses wireless links but could have done broadband down the power line
d) doesn't need more than 1 sensor (e.g .light/heat) and a few actuators

why, why why?

also, the s/w should be written in conic or esterel or some algebraic specification language and compiled onto bare metal

senseless middleware - just say NO!

so here's a problem - you have lotw of tunnels with tunnel lights and you have to adjust them deepdning on the profile of light at the entrance:- tunnel vision (and the arbitrary complexity of a generic middleware like teenylime or limey teens) - solution - put 1 BIG light at the entrance, which is solar powered and emits light in inverse proportion to the sunlight, and then clock (sorry, power down) the rest of the lights to the lowest level...

game over

show me a sensor net problem that actually needs a network:)

breaking down CS

an idea for a southpark video about computers everywhere

lets all go to the junkyard and get lots of consumer electronics (fridge, washing machine, microwqave, digital tv, cameras, phones etc) and then get a large hammer and smash them all to pieces to show how many of them have chips in (would be nice to do with a car too:) and then smash the screen we are on to show we are just a computer animation too (pink panther stylee:)

semi-lifting, strange loops and hard problems in CS

so was reading douglas hofstadter's excellent "I am a strange loop", and thinking about hard problems in CS in the sense of problems that are kludged around but not really elegantly solved - in the book, DH claims that class/superclass confusion is a first class part of human thought and yet ever since Principia Mathematica, everyone tries to ban (set v. powerset, or member, v. set of) the idea from formal thought - this seems to apply in CS too - but in reality, from time to time, we need to apply an idea and generalise it in some much more powerful and insightful way than this restriction permits - at the lowest level, this is what lets you program bits on wire (bare metal coding in comms and OS work) and then write the rest of the system in some typesafe way. but the "shift" in levels should not be the "dirty little secret" (casts etc) it is today - it should be a proud first class concept and mechanism for CS to use just like DH does

there's probably some parallel problem lurking in the occasional need to think about multiple inheritence too...but I can't quite think what it is right now...

mobile phones and lack of creativity

here's another thing that would be good to do with a cell phone, but the cellphone business is too braindead to allow it


save/restore console game state (e.g. xbox, wii, ps2/3 etc) onto a cell phone (via bluetooth or wifi or even sms)

this would be cool coz you could save a game onto your phone,go round your friends (assuming they have same game) and upload and continue from where you were...

doh.

Review Forms for CS Systms conferences...

I was involved in a recent workshop on workshops where there were many concerns about the problems associated with quantity and quality of work in the conference/workshop processes (from submissions, through reviewers, to feedback ,and on to publications and presentation)

it occurs to me that some of this might be improved by more careful design of review forms...viz the addition of judiciously chosen (lightening conuctor) sections in the form:

"Why did you hate this paper?"
(to remove vitriol from the technical feedback part of the review elsewhere)
and
"What paper did you want this person to have written?"
(to avoid feedback that asks an author to submit something different or do additional work which they might have done but not had space for:)
and
"who do I think I am?"

Plan B: have an exam which people have to pass to be qualified as PC members/reviewers - it will calibrate them.

learning statistics and computer games - recharging (energy) is same as (negative) randomness (entropy)

This is a well known problem that illustrates a nice area of proability/statistics (recently showed up inthe so so movie with Kevin Spacey, 21):

In a game show, a contestent has to guess which of three doors
the prize lies behind (e.g. a fast car) - the other two doors lead to nothing.
The game show host knows the right answer.

Now, lets say the contentst guesses door A. The game show host
now opens one of the other two doors (obviously showing
nothing), and asks the contestent
if they want to stay with their choice, or change to the door that
they didn't chose and the host didn't open.

What should the contestent do, and why?

So the answer is change (always - since you have 2/3 chance of the prize being behind the two doors you didn't pick, and in the second go, you get to know it is 50/50 between the door you did pick (with 1/3 chance) and the one you didnt that didnt get opened, so either way, you are twice as likely to win by changing as by sticking.

The more interesting problem is:
how do you convey this (teach it) to people?
I asked 4 random kids - 2 got it (using the 1/3 v. 2/3 or the 50/50 v 1/3 argument above) . two refused to believe me after explanation

Soome said: cast the change in information as like recharging in a game, then maybe they'd get it - so information increase is entropy decrease entropy is just negative heat. maybe there is something in this - could we devise a game whch illustrates this idea generally?

derek says: why not do the 100 (or million) door version and in 2nd go, host opens 999,998 doors...

objective unknowledge

so actually there is a flaw in the Popper classic formulation of
objective knowledge (and even if you extend it to take the community consensus
paridgm model of T. Kuhn, the same problem remains).

The model is that you cannot prove an hypothesis true - merely demonstrate its
use, but you can falsify it.

This means that "truth" is funfible, and based on a shifting sand of hypotheses,
formed by choosing the
i) best fit
ii) with least parameters

(lots of problems here - like why choose parameters and why isooate system from
other "allegedly" non-relevant influences

anyhow the flaw is this: a "proof" of falsity (i.e. falsification of an
hypothsis) is itself merely another piece of objective knowledge.

So while a theory about a truth in the Universe in Popper cannot be proved,
it can only be disproved, is the mantra - the act is that it cannot be disproved
either - all you can do is downrank it in a list of plausible models that have
some pragmatic value.

Hence science is merely the art of the pragmatic. It has no claim to absolute
truth, and even the relative truthes of models are subject to confidence limits

as tom toppard said, int hereal inspector hound,
frankly my dear, you strech my credulity and patience to breaking point.

as houlebque says
whatever

sex and drugs and rock´n roll and social networks

so i´ve been reading the fine book by ELizabetn Pisani called
THe Wisdom of WHores
about aids which basically says most the money is wasted on targettng the wrong groups for the wrong reason (the words¨target and group are giveaways there).

but anyhow read it yourself to find out why the wrong groups are targetted and why africa is a mess but there are countries in africa that could be models of the right thing to do

meanswhile on a related topic of sex and drugs and rock and roll
it appears to me that there are only two legitimate kinds of sex
1- the kind the US moral majority approve of
2. the kind that people writing cool papers about get to study.

meanwhile, i´ve been thinking (line from a song - can you name it?):
see my fourthcoming talk at Coseners:
http://www.cl.cam.ac.uk/users/jac22/talks/sdr.ppt

Haggle and Pocket Switched Networks

So I think we are going to have to work on Altruism and economics for opportunistic people based (ferrying) pocket switched networks- I believe I will have to coin yet another new phrase for the tit-for-tat protocol to pay people for carrying your traffic - this will in future be known as Deep Pocket Inspection :-)

or am i just blogging a dead horse?

Network Science - paradigm shift or just business as usual?

I attended some of the network science 2008 event recently
(see web site in Norwich science park
for more info) - it was an interesting mix of people networking (socially:)


It is clear that there are nearly as many definitions of "network" as there are people in the event. Indeed, in one workshop, someone asked for a definition of the word
"model" as used by several speakers in the room, and got (I think) more definitions than people:-)

on the way back, I noticed a railway that was being "re-furbished"

I wondered who had furbished it in the first place? furbish is a word that I will associate forever with captain James T. Kirk because Wlliam Shatner's brother used to advertise things like refurbished cars on TV in Canada when I lived there.

If you can sell me a furbished web site, I'd give you 1 euro.

nature and human studies

a recent publication in nature about human mobility caused a bit of a stir in the news

what surprised me was that apparently said paper passed the ethics committee in the authors' institution. the data was taken from a european cellular provider

1. the customers were'nt asked -t his makes it unethical
2. i asked uk and german and spanish legal folks they said this is also illegal in european law.
3. the data isnt avaialble to other people to validate, compare
4. not knowing which country it is make it petty hard to geenralise the mobility model (e.g. think greek islands versus spanish plains, versus alps:)
5. the paper appeared already in a slightly different form in the IOP Journal of Phys...
6 they dont seem to have done anythiong to control for factors that social scienctists would do like age group (think Virgin Mobile versus Vodafone - networks that cater mostly for kids or mostly for business users) people that turn off phones when traveling, or have 2 phones for home and work...

in general, I am a bit surprised at Nature for publishing the work - the math/analysis is cool, but the rest of it is doubtful, imho

http://news.bbc.co.uk/1/hi/sci/tech/7433128.stm

gravitational and inertial mass explained

so a puzzle slightly harder to explain than P=nP
to the no nscientist, and probably more important
is why gravitational and inertial mass are the same

so my theory is that mass is basically a concrete instantiation of information
(information, as it were, realized, or referent in the form of substance)

so the more information, the more mass (the more mass, the more information)

information breeds interpretation, and interpretation needs to "run"
and needs intelligence which runs on matter and is attracted to information
hence information (masses) attracts (and doesn't repel, whereas ignorance, or lack of information, does repel..)

so inertia is now easy to udnerstand - it is hard to change people's minds - the fact is that facts are things it is foolish to argue about. Hence facts have more inertia than opinions.
I.e. information not only has, but is, inertial and graviational mass.
QED.

tell me, how can a poor ISP stand such times, and live?

bbc says it will cost 16 billion quid to upgrade UK to 100Mbps (i assume FTTH) -
broadband snakeholders group comments

people are suing comcast for rate limiting stuff in a
class action

you can't win :-)

[ with apologies to Ry Cooder et al for misusing their fine toon title:)

new noos: slashdot lists an article which pretty much says what I said about
differentiation here,
but fails to distinguish as clearly as I would like
that this is not the same as arbitrary discrimination. Viz what I wrote in
CCR, but it does uphold the principle of transparency, which is fine, so I'm happy:)

transformational government : where's the no leak model

so here's the thing - governments want to join-up-the-dots
for a variety of ostensibly ok reasons
1/ reduce costs (single database entry per citizen, keyed on biometric id)
2/ increase consistency (e.g. tax and rebate)
3/ tracking trends
4/ catching bad guys
5/ you name it...
6/ if they were really honest, one could make the system transparent
and probably remove most government (reduce the government to "codes"

this is all transformational government

the problem is that the more unified the databases, the higher the gain to bust it
and the higher the loss to people (in value and number of people) if the system is bust (whether deliberately by bad guys or accidentally by HMRC^H^H idiots).

so once you unify this thing how long does it last? how about forever, stupid?

so the probabilty of leaks might be some decreasing small number - e.g. the chance of leaking 1 record in a year might be 1 in a million. so what are the chances your record is leaked in your lifetime (say 75 years)? well, fairly close to 1 actually.
do the math

the only way to do things is to require that noone keeps data for very long at all. and noone has access across all databases - keep the databases seperate (as per the current data protection laws) and delete data permanently and properly as early as possible.

this needs to be done much more carefully than in the past

by the way, recent reports ont he bbc about the tracking of cell phone users
cite a paper in nature, which reveals that the 100k users were in a european country

firstly, while they claim that they've anonymized the data (and the country) It is fairly easy to deduce from the cell tower locations and population mobility (e.g. 3km mean levy walk, with a 1000km limit) which country, which provider, and therefore for authors (and one assumes, the Nature editors and reviewers , since they are supposed to require access to data to check an experiment is valid and reproduceable or falsifiable, even when the data is proprietarty -as in drug clinical trials))

so this paper is unethical and possibly illegal in european law.

oh well.

(see
http://news.bbc.co.uk/2/hi/science/nature/7433128.stm
and follow links to supplemntary data)

its a shame that Nature has lowered the bar for work like this as it should be possible to do this sort of thing in a way that is with consent (lets say you offer the users some useful service based on location !) and is done scientifically
in a verifiable way too...

nevertheless the results are useful (mind you, so were the nazis' medical work on hypothermia in concentration camps......careful...careful...dont lose your cool).

Control v. Data Plane Complexity & HCI

I was reading a bunch of HCI research recently and it struck me that the
really successful systems that people build (I realize HCI isn't about systems, but
often the really good HCI work builds systems to do experiments, so you get to see cool design artifacts as a side effect of their work - hey- the iPhone as a side effect is
no bad thing:) so anyhow te good systems have low complexity control planes and all the clever stuff is implicit in the work in the data plane (to use networking terminology)

this is a bit like IP v. ATM- IP has a rediculusly simple control plane (originally)
and so is easy to write many many applications to.

in HCI terms,. this is similar - we want systems with low cognitive overhead - i.e.
you want star trek communicators not things you have to click to unlock then 10 digits to dial/press to call. you want tivo boxes that just go ahead and record your favorite types of programs by default and use the actual broadcast events to trigger recording start/end, rather than VCRs with arcane yarrow-stick-casting interfaces where you type in immutable start and end times in odd formats and program/channel numbers that relate to local geo- and techno- specific assignment of program and station to some random number....

you want a net where you can just send a packet, rather than calling 11M lines of code to set up a virtual path and channel.