Tuesday 6 April 2010

The Byzantine Cake Problem

It's Dereks birthday! As is the normal case for these events, we "secretly" have a collection and the person who collects up the money, goes and "secretly" buys a cake for the birthday boy.

This was until my boss, Craig, sent this out to the office by email...

"Can someone go to shop please as I’m busy all afternoon."

This results in an interesting logical problem.

There is an implied condition in the phraseology he's used that the person that goes is therefore not busy all afternoon. If they're not and he doesn't know about it, they are admitting being covertly lazy!

Aside from this immediate conflict of interest, all of the listeners who received the message (which by the way is not guaranteed) have no way to discuss in public who is going to go to the shop, as the targets act as listeners also and must not be aware of any discussion.

Now every time someone leaves the room, there is no way to tell if they have gone to get the cake. Craig is already gone as he is apparently "busy", but so is the money. No-one can know for sure whether he, or an another unknown "shopper" has taken it.

(Incidentally, Derek who's birthday it is, has now just left and so potentially he's stolen the money and is away to buy a cake, or new car, for himself. A potential security problem here too.)
In the end, the money acts a flag, but without some form of centralised co-ordination everyone in the office can go as far as the point of contention, all standing in the queue at Sainsburys with cakes and no money, either waiting eternally for Craig to turn up, or a race condition if he does, resulting in abandoned cake purchases and dead bodies all over the place.

The question from a protocol design point-of-view (given the Two Generals problem and it's proof of impossibility) is... "Has Craig mitigated the uncertainty inherent in the communication channel to an acceptable degree?"

Update: Craig has returned to the office, put on his coat and left.

Update 2: He's back! With a cake!

Tuesday 23 March 2010

Lock This! (not)

Having witnessed numerous demonstrations of all manner of concurrency gotchas at the recent DevWeek, I thought I would focus on one particular construct that I see quite often, and admittedly have been responsible for introducing in the past.

Joe Duffy, in his otherwise excellent (and extremely thick) book "Concurrent Programming on Windows", advises us to "Use the C# lock and VB SyncLock for all synchronized regions. Following this guidance ensures that locks will be released even in the face of asynchronous thread aborts, leading to fewer deadlocks (statistically speaking)."

There is a problem here, and the problem is that the lock keyword in C# is in league with Satan. It is as evil as the dreaded "On Error Resume Next" in VB. I cannot think of a single case where its use is justified (so if you can, let me know!). Let’s see why. As always the devil is in the detail.

Let’s look at what the lock keyword actually does. Look at the decompiled MSIL (using Reflector):

L_0009: call void [mscorlib]System.Threading.Monitor::Enter(object)
// synchronised code goes in here...

L_0052: leave.s L_005d
L_0054: ldloc.s CS$2$0001
L_0056: call void [mscorlib]System.Threading.Monitor::Exit(object)
L_005b: nop
L_005c: endfinally

So... when you use the lock keyword, or its even more evil mutant twin, [MethodImpl(MethodImplOptions.Synchronized)] - the true dark lord of attributes - what you are actually doing at an IL level is the equivalent of...

Monitor.Enter(syncLock);
try
{
//do something
}
finally
{
Monitor.Exit(syncLock);
}

Would you write code like this yourself? Would you?

Well not really... Calling Monitor.Enter() with no timeout value means the thread will block until the lock becomes available. Why is this bad? Well... blocking threads are the archenemy of concurrency!

As an example, if you are using the built in threadpool, when a thread becomes blocked the threadpool will start a new thread in anticipation of any new work items that come in. Now, what happens if your synchronised code block calls some resource on the network with a 5 minute timeout? "Kaboom!" is the technical term for it. So really whilst appearing as if it's being defensive, its lack of a timeout naturally leads to unreliable code. So much for using lock to help us wrangle threads.

So... if you really really really must block a thread (and you often don't where you think you do)... Please! For the sake of the children... use something more like this...

if (Monitor.TryEnter(syncLock, 1000)
{
try
{
//do something here
}
finally
{
Monitor.Exit(syncLock);
}
}

There's always time for a Timeout :-)

Friday 19 March 2010

:-0:-0:-0:-0:-0:-0:-0:-0:-0:-0:-0:-0

There was a phrase coined here by the original rockstar programmer Jamie Zawinski (JWZ) back in 1997 (ancient history in web terms)!

"Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems."

Given, this rather interesting post, do we now have an infinite number of problems, simultanously?

NerdParade

Just back from DevWeek 2010!

There was the run-of-the-mill-glitziness surrounding the Entity Framework, Silverlight and the AJAX Client Framework, all of which have had some fairly interesting improvements of late. AJAX expecially so. It's now at one" with jQuery! Yay!

Whilst these, mostly demo-based, sessions contained the usual mix of "gosh that's clever" and "oh dear", I feel that the issues surrounding data and binding things to other things in UI are mostly solved problems. The much more interesting topics to me were more around the "high art" end of distributed computing. As the worlds software evolves from a collection of client/server based applications towards a collection of dynamically enlisted services hosted on the web/cloud, problems of identity, security and trust, scalability and parrallelism become more and more important.

I saw a number of presentations which were genuinely facinating. Some fairly high level (on Windows Identity Foundation), some lower (on Multi-Threading). 2 talks on Security by Dominick Baier were very good and Christian Weyers Demonstration of the Azure Service Bus was the highlight for me. Christian certainly understands how to hold an audiences attention, and even got a round of applause for something which could have been seen as quite dry material if delivered by a lesser presenter. Great stuff.

Also, thanks to the very smart Jeff Richter. I now fully understand how the "volatile" keyword in C# works. Thank you Jeff!

Monday 18 January 2010

jQuery for you and me. Ab-sol-u-tiv-e-leeee.

Everyone who knows me knows why I'm a fan of jQuery (clear separation of concerns and CSS-style selectors), but jQuery 1.4 builds on one of the best javascript libraries to make it even better.

The new release not only brings with it the standard maintanence type stuff such as better performace and a couple of new functions, but some good enhancements across the library.

You can now bind multiple event handlers at once, so instead of chaining a load of binding methods together, you can pop them all into the same call, like so:

$('#myClass').bind({
mouseover: function() {
// do something on a mouseover
},
mouseout: function() {
// do something on a mouseout
}
});

The new.detach() method allows you to remove elements from the DOM. It works exactly the same way as the.remove() method but unlike.remove() it doesn't destroy any data held by jQuery on that element (including any event handlers added by jQuery).

This can be useful when you want to remove an element, but you know you'll need it again later on, so you can write code like:

var myClass = $('#myClass');

// Bind an event handler
myClass.click(function(){
alert('Hello World!');
});

myClass.detach(); // Remove it from the DOM

// … do stuff here as if the item no longer exists.

myClass.appendTo('body'); // Bolt it back on to the DOM
myClass.click(); // alerts "Hello World!"


As far as DOM traversal goes, there is a new .unwrap() method which does the opposite as 1.3's .wrap() method, you can now query the DOM to check if an element .has() sub elements and also there is a new .until() method for limiting traversal of the DOM tree.

There's a new .delay() function for the queue, so you can get your animations the way you want them and you can now deal with JSON encoded attributes, so you can build up jQuery objects without needing to go through the process of adding .attr() to everything.

$('<div>', {
id: 'myClass',
css: {
fontSize: 20,
color: 'red'
},
click: function(){
alert('myClass has been clicked!');
}
}).text('Click Me!');


Last (and probably least) there are new .focusIn() and .focusOut() events which allow you to take action when an element, or a descendant of an element, gains or loses focus, so writing watermarked text boxes should be (only fractionally) easier :-)

For further information you can, RTFM here! :-). Also there is an 14 day long online event going on here that will get you up to speed with the changes.

Yum.