Beta Thoughts

SIGPIPE

2010-03-04T02:45:00.000-08:00

I was changing a send call to a writev and ran into an annoying problem. On the send call I had set the MSG_NOSIGNAL flag to stop any SIGPIPE signals if the socket I was writing to was closed, unfortunately I cannot set the same flag on writev! (I had originally switched from using write to send to be able to set the flag) On some systems (BSD) you can set the socket option SO_NOSIGPIPE to get a similar effect, but on Linux it doesn't look like this option is supported. The other option is to set the system to ignore a SIGPIPE, but there are issues with this if you do it naively, see Suppressing SIGPIPE in a library.

iphones and people

2010-03-03T04:00:00.000-08:00

I have noticed the number of iphones increasing among the people I know. It is particularly interesting is that a lot of people who are non-geeks now have iphones, this is because the iphone is now available on cheaper mobile plans; the geeks were prepared to pay the premium to get the iphone early. I know of one person who now reads their e-mail because they have an iphone, previously they were too busy to sit down at a computer. This means that the iphone is actually increasing the number of people who are actively using the internet and the WWW!

ExtraHop

2010-02-24T02:52:00.000-08:00

Some guys I worked with at F5 Networks created a start up called ExtraHop. It was clear that whatever these guys did it was going to be impressive and run very fast - they did not disappoint. They built an appliance to monitor your network: hang it of your network, spend 15 minutes configuring it and there you go, it will learn all about your network and tell you when things are not running smoothly and why. It works at layer 7, so it knows when a database is not running properly, or when a CIFS server is mis-behaving, or when a HTTP server tps has dropped. The really amazing thing - it runs at 10GbE! Years talking to BIG-IP customers was not wasted. They also have a cool service where you can upload you pcaps and their magic software will analysis it for you!!

There are also some videos of their stuff in action.

A History of malloc

2010-02-23T02:47:00.000-08:00

I was reading up on malloc. I had naively assumed malloc was a system call, it's not. Under the covers malloc uses brk or sbrk to request memory from the kernel. However, malloc does not always have to use brk/sbrk, if it has memory in its "free list" that can fulfill the request then no system call is needed. So you do not always have to pay the price of a system call when you use malloc.

Another interesting thing about malloc is that it cannot return memory to the kernel unless the memory that is freed is at the top of the heap. If you malloc some memory at the start of your program, malloc some more later and then free the original memory, malloc/free cannot return the original chunk of memory to the kernel until the second piece of memory is freed.

The first malloc was written in "The Old Testament" - K&R, it's about 200 lines of code. They managed the free list by using a union with the memory that was actually stored in the free list - this saved space, an important requirement when the amount of memory available was very limited.

Poul-Henning Kamp re-wrote malloc for FreeBSB 2.2 and documented it in Malloc(3) Revisited, this malloc is known as pkmalloc. By this time systems where using virtual memory, this meant that in the K&R approach a chunk of memory on the free list could be paged out to disk, now the free list was embedded in these chunks of memory so when malloc came to look for memory on the free list it would have to page all this memory back in, killing performance!! Kamp's version of malloc was 1136 lines of code long and had a good reputation for performance.

Then came fast multi-processor machines with large memory, and another re-write of malloc. Jason Evans re-wrote malloc for FreeBSB and his version is known as jemalloc, he wrote about it in A Scalable Concurrent Malloc(3) Implementation for FreeBSD. Now the issues are less about paging to disk but fast locks and worrying about NUMA issues (trying to allocate memory close to the CPU that you think will be using it). Firefox are attempting to use jemalloc internally for their memory management.

There are quite a few malloc implementations out there, Google have one called tcmalloc in their perftools bundle. It's very easy to swap the malloc your code uses, all you have to do is link against the library with the new malloc. Though this can sometimes lead to trouble :-)

Ubuntu + D-Link + linkedin == Trouble

2010-02-19T03:14:00.000-08:00

Hit this bug yesterday when trying to access Linkedin, weird nearly all other web sites I visit don't exhibit this problem! Went with the set "MTU to 1360" hack. If I have time I will look into this some more - network bugs can be very weird.....

Post Modern Programming

2010-02-18T03:36:00.000-08:00

Varnish is a reverse Web proxy cache. What makes it interesting is how it was designed. The argument is that people are programming like it's 1975, treating RAM and disk as two separate memory pools, instead Varnish views them as a single memory pool with the RAM acting just like a cache. It does this by mmap'ing a large file, the threads just read and write to this memory happily unaware that it is being backed to disk. This has the advantages of reduced complexity, no requirement to manage a RAM and disk cache, and also a lot less system calls (no read/write to disk). It also means that they have to use lots of threads because any memory operation could cause a thread to block because of a page fault - so they have a thread per connection model. This is contrary to how a lot of people develop these kinds of applications, they have an event driven system with only a couple of threads, or just one thread, and they focus on making sure that thread never blocks.

Am I a bad Web Citizen?

2010-02-17T04:23:00.000-08:00

I noticed in my previous post I did not include any links. There were many things in the post I could have referenced, but I did not, because I was lazy. I am relying on the extra level of indirection that Google provides - if someone is interested in something then they can Google it. This is wrong for two reasons.

First, I can include links that back up my case. Google may turn up links that weaken my case and reduce my credibility.

Secondly, the Web depends on links and they are of fundamental importance to the Web.

Mea Culpa

What does it mean?

2010-02-17T03:15:00.000-08:00

I was reading Warren Buffet's entry on wikipedia the other day and came across this phrase: "Price is what you pay, value is what you get".

I don't understand the phrase, or rather I do understand the phrase, but don't get the message it is trying to convey. I haven't Google'd the phrase but left it to stew in my brain to see if I could come up with the significance of the phrase, unfortunately it is still stewing.

The phrase is a tautology, it states a definition of two words, price and value, that is in no way controversial. So why does it make Mr Buffet's Wikipedia entry?

I really like phrases like this. They can convey so much information with so few words. I would not be surprised to find a book with the title "Price is what you pay, value is what you get", or that its an essay question on some Economics degree course. You can use phrases like these as names for ideas, names that are self explanatory.

An equivalent phrase from the software development world is "Premature development is the root of all evil" - you just have to quote this and everyone understands and rolls their eyes. (As an aside people often attribute this to Knuth, but it originally came from Tony Hoare and Knuth quoted him in "Structured Programming using GOTO statements", Knuth's repost to Dijstra's "GOTO considered harmful").

An interesting difference between the two phrases is that one is (nearly) a tautology and the other is obviously untrue - premature optimisation did not throw up Hitler. The fact that it is a tautology I think adds value, it almost says the message I carry is also a tautology - which it probably isn't.

I look forward to the day in some meeting I can say "Price is what you pay, value is what you get", hopefully no one will say WTF do you mean?

A personal favorite phrase of mine is "The talent is in the choices", I have used it in a couple of talks I have given and I am pretty sure that is all people remember from the talks; that they remember anything from one of my talks I see as a success. I have never been able to find out who first said this, but I know Robert De Niro used it. The choices an actor makes reflect his talent, talented actors make good choices - apparently he agonized for three months as to whether or not to have a moustache in Godfather part II. A software engineer is often faced with choices about how to design or implement something, good engineer's make good choices and clearly experience plays a part in this. And sometimes an obvious choice is not the correct one, and good engineers will recognize this. This is also why Agile development is so successful, you make a bunch of choices, they turn out to be bad, you refactor.

Phrases like these can also be used in a kind of harmful way. I remember at one meeting when we were talking about using a new technology that was rapidly evolving at the time (Web Services :-() and someone said we are building on sand, this was quickly and cleverly countered with "Yes, but its a better quality sand". By the time people had processed this statement and released it was complete crap the debate had moved on.

A brief history of Consensus, 2PC and Transaction Commit.

2007-06-13T14:42:00.000-07:00

This is a potted history of consensus, transactions and 2PC. Reading the literature on consensus is difficult because the language changes (consensus was originally called agreement), the results come in an order that isn't logical, and the whole framework for describing distributed algorithms evolved in parallel with the work. Also, there are few books other than Lynch's Distributed Algorithms that cover the subject.

Papers are discussed in the order that makes most sense, not in the order they were published.

The first instance of the consensus problem that I am aware of is in Lamport's "Time, Clocks and the Ordering of Events in a Distributed System" (1978), though it is not explicitly declared as a consensus or agreement problem. In this paper Lamport discusses how messages take a finite time to travel between processors and draws an analogy with Einstein's special relativity. Discussing Einstein's theory with respect to distributed systems is popular recently in the blogsphere, but in 1978 Lamport give a complete analysis with space-time diagrams and all. The issue is that in a distributed system you cannot tell if event A happened before event B, unless A caused B in some way. Each observer can see events happen in a different order, except for events that cause each other, ie there is only a partial ordering of events in a distributed system. Lamport defines the "happens before" relationship and operator, and goes on to give an algorithm that provides a total ordering of events in a distributed system, so that each process sees events in the same order as every other process.

Lamport also introduces the concept of a distributed state machine: start a set of deterministic state machines in the same state and then make sure they process the same messages in the same order. Each machine is now a replica of the others. The key problem is making each replica agree what is the next message to process: a consensus problem. This is what the algorithm for creating a total ordering of events does, it provides an agreed ordering for the delivery of messages. However, the system is not fault tolerant; if one process fails that others have to wait for it to recover.

Around the same time as this paper, Gray described 2PC in "Notes on Database Operating Systems" (1979). Unfortunately 2PC would block if the TM (Transaction Manager) fails at the wrong time. Skeen showed in "NonBlocking Commit Protocols" (1981)that for a distributed transactions you needed a 3 phrase commit algorithm to avoid the blocking problems associated with 2PC. The problem was coming up with a nice 3PC algorithm, this would only take nearly 25 years!

Fischer, Lynch and Paterson showed that distributed consensus was impossible in an asynchronous system with just one faulty process in "Impossibility of distributed consensus with one faulty process" (1985), this famous result is known as the "FLP" result. By this time "consensus" was the name given to the problem of getting a bunch of processors to agree a value. In an asynchronous system (where processors run at arbitrary speeds and messages can take an arbitrarily long time to travel between processors) with a perfect network (all messages are delivered, messages arrive in order and can not be duplicated) distributed consensus is impossible with just one faulty process (even just a fail-stop). The kernel of the problem is that you cannot tell the difference between a process that has stopped and one that is running very slowly, making dealing with faults in an asynchronous system almost impossible. The paper was also important because it demonstrated how to show something was impossible: show that all algorithms that solve the problem must have some property, then show that this property is impossible, ie proof by contradiction. (This approach was only re-learned as Turing used it in the halting problem)

By this stage people realized that a distributed algorithm has two properties: safety and liveness. Safety means nothing bad happens, while liveness means that something good eventually happens. 2PC is an asynchronous consensus algorithm, all processes must agree on either commit or abort for a transaction. 2PC is safe: no bad data is ever written to the databases, but its liveness properties aren't great: if the TM fails at the wrong point the system will block.

Also by this stage people thought of distributed systems as being synchronous (processes run at known rates, and messages are delivered in known bounds of time) or asynchronous (processes run at unknown and arbitrary rates, and messages can take unbounded time to be delivered). The asynchronous case is more general than the synchronous case: an algorithm that works for an asynchronous system will also work for a synchronous system, but not vice versa. You can treat a synchronous system as a special case of an asynchronous system that just happens to have bounds on the time it takes to deliver a message.

Before FLP, there was the "The Byzantine Generals Problem" (1982) paper. In this form of the consensus problem the processes can lie, and they can actively try to deceive other processes. This problem looks harder than the FLP result, but it does have a solution for the synchronous case (though when the Byzantine Generals paper was written the distinction between asynchronous and synchronous systems was not explicit). The solution is expensive in the number of messages exchanged, and the number of rounds of messages required. The problem originally came from the aerospace industry: what would happen if sensors gave false information on an plane (clearly the system could be treated as synchronous).

In 1986 there was a get together of the distributed systems people who were interested in consensus and the transaction people. At the time the best consensus algorithm was the Byzantine Generals, but this was too expensive to use for transactions. Jim Gray wrote up a note on the meeting: "A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem." (1987) .

The paper contains this in the introduction :-)

"Prior to the conference, it was widely believed that the transaction commit problem faced by distributed systems is a degenerate form of the Byzantine Generals Problem studied by academe. Perhaps the most useful consequence of the conference was to show that these two problems have little in common."

Eventually distributed transactions would be seen as a version of consensus, called uniform consensus (see "Uniform consensus is harder than consensus" (2000)). With uniform consensus all processes must agree on a value, even the faulty ones - a transaction should only commit if all RMs are prepared to commit. Most forms of consensus are only concerned with having the non-faulty processes agree. Uniform consensus is more difficult than general consensus.

Eventually Lamport came up with the Paxos consensus algorithm, described in "The Part-Time Parliament" (submitted in 1990, published 1998). Unfortunately the analogy with Greek democracy failed badly with people finding the paper very difficult to understand, and the paper was ignored until its case was taken up by Butler Lampson in "How to Build a Highly Availability System using Consensus" (1996). This paper provides a good introduction to building fault tolerant systems and Paxos. Later Lamport would publish "Paxos Made Simple (2001).

The kernel of Paxos is that given a fixed number of processes, any majority of them must have at least one process in common. For example given three processes A, B and C the possible majorities are: AB, AC, or BC. If a decision is made when one majority is present eg AB, then at any time in the future when another majority is available at least one of the processes can remember what the previous majority decided. If the majority is AB then both processes will remember, if AC is present then A will remember and if BC is present then B will remember.

Paxos can tolerate lost messages, delayed messages, repeated messages, and messages delivered out of order. It will reach consensus if there is a single leader for long enough that the leader can talk to a majority of processes twice. Any process, including leaders, can fail and restart; in fact all processes can fail at the same time, the algorithm is still safe. There can be more than one leader at a time.

Paxos is an asynchronous algorithm; there are no explicit timeouts. However, it only reaches consensus when the system is behaving in a synchronous way, ie messages are delivered in a bounded period of time; otherwise it is safe. There is a pathological case where Paxos will not reach consensus, in accordance to FLP, but this scenario is relatively easy to avoid in practice.

Clearly dividing systems into synchronous and asynchronous is too broad a distinction, and Dwork, Lynch and Stockmeyer defined partially synchronous systems in "Consensus in the presence of partial synchrony" (1988) . There are two versions of partial synchronous system: in one processes run at speeds within a known range and messages are delivered in bounded time but the actual values are not known a priori; in the other version the range of speeds of the processes and the upper bound for message deliver are known a priori, but they will only start holding at some unknown time in the future. The partial synchronous model is a better model for the real world than either the synchronous or asynchronous model; networks function in a predicatable way most of the time, but occasionally go crazy.

Lamport and Gray went on to apply Paxos to the distributed transaction commit problem in "Consensus on Transaction Commit" (2005). They used Paxos to effectively replicate the TM of 2PC, and used an instance of Paxos for each RM involved in the transaction to agree whether that RM could commit the transaction. On the face of it, using an instance of Paxos per RM looks expensive, but it turns out that it is not. Paxos Commit will complete in two phases for the fault free case, ie it has the same message delay as 2PC, though more messages are exchanged. A third phase is only required if there is a fault, in accordance to the Skeen result. Given 2n+1 TM replicas Paxos Commit will complete with up to n faulty replicas. Paxos Commit does not use Paxos to solve the transaction commit problem directly, ie it is not used to solve uniform consensus, rather it is used to make the system fault tolerant.

Any argument that distributed transactions should not be used because 2PC is blocking is a void, because Paxos Commit addresses the blocking issue.

Recently there has been some discussion of the CAP conjecture: Consistency, Availability and Partition. The conjecture asserts that you cannot have all three in a distributed system: a system that is consistent, that can have faulty processes and that can handle a network partition.

We can examine CAP by equating consistency with consensus. For an asynchronous system we cannot reach consensus with one faulty process, FLP, so we cannot have consistency and availability for an asynchronous system!

Now take a Paxos system with three nodes: A, B and C. We can reach consensus if two nodes are working, ie we can have consistency and availability. Now if C becomes partitioned and C is queried, it cannot respond because it cannot communicate with the other nodes; it doesn't know whether it has been partitioned, or if the other two nodes are down, or if the network is being very slow. The other two nodes can carry on, because they can talk to each other and they form a majority. So for the CAP conjecture, Paxos does not handle a partition because C cannot respond to queries. However, we could engineer our way around this. If we are inside a data center we can use two independent networks (Paxos doesn't mind if messages are repeated). If we are on the internet, then we could have our client query all nodes A, B and C, and if C is partitioned the client can query A or B unless it is partitioned in a similar way to C.

For a synchronous network, if C is partitioned it can learn that it is partitioned if it does not receive messages in a fixed period of time, and thus can declare itself down to the client.

Paxos, Paxos Commit and HTTP/REST have been combined to build a highly available co-allocation system for Grid computing, details of which can be found here HARC, there are also more references in this paper: "Co-Allocation, Fault Tolerance and Grid Computing" (2006).

What are ReferenceParameters for?

2007-03-01T15:48:00.000-08:00

What are ReferenceParameters for?

This mini-rant was inspired by the W3C Workshop on Enterprise computing

You get ReferenceParameters in WS-Addressing EndpointReferences, also known as EPRs. Kinda like this:
<wsa:EndpointReference> <wsa:Address>http://www.crapola.com/SoapSink</wsa:Address> <wsa:ReferenceParameters> <SessionID>25324523</SessionID> <ResourceID>1434123421</ResourceID> <UserID>mark</UserID> <UserServiceRating>Gold</UserServiceRating> </wsa:ReferenceParameters> </wsa:EndpointReference>
A few things about ReferenceParameters. First, given an EPR you should treat the ReferenceParameters as opaque; you should not reason about them. Second, the ReferenceParameters get stuffed into SOAP Headers, and are sent along to the service that the EPR addresses. Third, the thing in the wsa:Address is an identifier, not a location, you de-reference the identifier to a location before sending the message.

So what might you do with ReferenceParameters? Well, if you are using WSRF you might use them for a bit of identification. Have all the SOAP messages arrive at the endpoint identified by the wsa:Address element, then direct the messages to particular WS-Resources based on the ReferenceParameters; ResourceID in the example.

Or you might decide to use ReferenceParameters to support sessions. You want to track a particular client's usage of a service, then give him an EPR with a session identifier, SessionID in the example, embedded in the ReferenceParameters. The session identifier will be carried in the SOAP header each time the client sends a message to the service. You could even carry some information to identify the client; UserID or UserServiceRating in the example.

All these uses of ReferenceParameters are possible, though the W3C TAG frowns on the first. ReferenceParameters are a bit like HTTP cookies in functionality; cookies can do all the above for HTTP. So, what is the problem?

Well, given an EPR that has ReferenceParameters you should NEVER share it with anyone else. You cannot know what those ReferenceParameters are for. They could be there for some identification purpose, in which case it would be OK to share them, but you cannot know that for sure. They could actually be for identifying a particular session, or client. Sharing EPRs with ReferenceParameters would be like sharing your HTTP cookies; you simply wouldn't do it. Now, imagine a Web were you were not able to share URIs.

Beta Defining SOA, or adding to the pollution.

2007-02-23T05:33:00.001-08:00

Defining SOA, or adding to the pollution.

Someone sent me this link to a movie on SOA. Those gold disks look pretty expensive. And I hope the red bouncing balls don't have to change colour, or shape; it could break the expensive gold disks.

My immediate response to anything about SOA is SnakeOil. This is because I have never found a good definition of SOA that I really liked; something really visceral that you can chew on. Mostly I have found the definitions to have too much hand waving, with high minded terms that I don't really understand. Or else, too obvious to be of any use.

REST is more tangible, for example, anything that can have an identity can be a resource. OK then, I have this thing, not really sure what this thing is, but at least I can give it a URI. However, REST does have a few glib phrases: "hypermedia as the engine of application state", but they add spice.

I have been challenged to provide my own definition of SOA. Normally, I am loathe to create definitions as it pollutes the world and causes confusion. It is always better to reference an existing definition. Even this concept is RESTful, if you reference an existing definition you get the same network effects as linking; the more people that "link" to that definition the more authoritative it becomes. This doesn't always work though, the definitive definition of REST, Dr. Fielding's thesis, is not the top hit in Google for the term REST. However, in any debate Dr. Fielding always has the last word on what REST means, though he may of course be wrong in what he asserts in his thesis; REST is his word, and his definition is the only correct one. Of course his definition may change over time, but this is just as unhealthy as creating new definitions in terms of confusing people.

So what is my definition of SOA. An architecture for a distributed system based on services, is nice and vapid, though logically sound. The key, then is to define a service.

A service interface is defined by the set of messages it can process, and the set of messages it emits. The set of messages it can process, MessagesIn, and the set of messages it emits, MessagesOut, can change over time. There may exist a mapping of a subset of MessagesIn to a subset of MessagesOut, such that if the service receives a message from this subset of MessagesIn it will emit a message from the subset of MessagesOut. A service interface description describes a subset of the MessagesIn that a service can process, a subset of MessagesOut that a service can emit and any mapping between the subsets of MessagesIn and MessagesOut that it describes. A service interface description only defines sets of messages at a particular time, so a service may have a series of service interface descriptions. A service interface description is incomplete if it does not include the compete set of MessagesIn and MessagesOut for a service at a particular time. Since it is only possible to communicate using messages, and as messages must take a finite time to travel between sender and receiver, a client can never know if a service interface description is still valid (assuming the service interface description is in the MessagesOut set). A service interface description is faulty if it describes a set of input or output messages that includes messages which are not in MessagesIn or MessagesOut.

A service may also have internal state, and can be modelled by a state machine. This state machine may or may not be deterministic. The mapping of input to output messages may depend on the internal state of the machine, and the mapping may change over time.

Service developers should make the set of messages MessagesIn as large as possible, preferably it should be an infinite set to make interoperability and service description easier. Service developers should constrain the size of MessagesOut to be as small as possible, preferably a set with no members, as it makes interoperability and service description easier. (The last two clauses are a form of Postal's Law). Service developers should make the internal state of their service as large as possible, preferably of infinite size because then they will be better than Google, and can charge a lot for advertising. If a service developer achieves this, an infinite set of MessagesIn, a zero size set of MessagesOut with an infinite amount of internal state, then they will have created God.

The WSRF CurrentTime is 5.41pm

2007-02-20T10:12:00.000-08:00

CurrentTime kills caching for WSRF
We have been fixing a bug in our AJAX to REST/WSRF stuff.
The bug was that IE6 did not update the properties properly. Bruno discovered that IE6 was not invoking the HTTP GET because the URI had not changed, we had not included any cache control HTTP Headers, but I assumed that would mean "don't cache". The HTTP spec is hard going wrt caching but Section 13.4 states "If there is neither a cache validator nor an explicit expiration time associated with a response, we do not expect it to be cached, but certain caches MAY violate this expectation (for example, when little or no network connectivity is available)".The solution was to add HTTP Headers which explicitly said don't cache this. Adding metadata cannot be a bad thing I guess.

The next issue was should we do caching properly? There are a lot of advantages, especially for the AJAX client, as we could support conditional GETs. I had a vague idea how to do it too, put in a hook for the developer to attach his caching policy/code. But then I remembered CurrentTime; WSRF defines a ResourceProperty, CurrentTime, so that a client can find out the time when the WS-Resource had a certain set of properties. So one of our properties is always changing; so we cannot cache!

CurrentTime is a bad name, because almost by definition it is not the current time -- its some time later, Lamport's clocks. HTTP uses a HTTP Header, Date, to convey the same concept, and the concept really is the time at which the message was created. Its metadata about the message, it should not really be part of the message.

The good thing is I do not have to write the hooks for supporting caching, the bad thing is that we cannot do caching.

A Solution to a Distributed Systems Problem

2007-02-14T09:10:00.000-08:00

The solution to this puzzle is:

Any protocol that solves this problem is equivalent to one
in which there are rounds of message exchanges: first A (say)
sends to B, next B sends to A, then A sends to B, and so on. We
show that in assuming the existence of a protocol to solve the
problem, we are able to derive a contradiction. This
establishes that no such protocol exists.

Select the protocol that solves the problem using the fewest
rounds. By assumption, such a protocol must exist and, by
construction, no protocol solving the problem using fewer rounds
exists. Without loss of generality suppose that m, the last
message sent by either process, is sent by A.

Observe that the action ultimately taken by A cannot depend on
whether m is recieved by B, because its receipt could never be
learned by A (since it is the last message). Thus, A's choice of
action alpha or beta does not depend on m. Next, observe that the
action ultimately taken by B cannot depend on whether m is
recieved by B, because B must make the same choice of action alpha
or beta even if m is lost (due to channel failure).

Having argued that the action chosen by A and B does not depend on
m, we conclude that m is superfluous. Thus, we can construct a new
protocol in which one fewer message is sent. However, the existence
of such a shorter protocol contradicts the assumption that our
original protocol used the fewest number of rounds.

A Distributed Systems Puzzle...

2007-02-14T09:04:00.000-08:00

A Distributed Systems Puzzle
I like this little puzzle taken from Distributed Systems:

Two processes, A and B, communicate by sending and
receiving messages on a bidirectional channel. Neither
process can fail. However, the channel can experience
transient failures, resulting in loss of a subset
of the messages that have been sent. Devise a protocol
where either of two actions alpha or beta are possible,
but (i) both processes take the same action and (ii)
neither takes both actions.

Can you show that there is no solution?

Google does the Impossible!

2007-02-09T15:17:00.000-08:00

Google does the Impossible

I often wondered whether Google would hire me, until now I had doubts. Google only hire people who are smarter than the average Googler, and given my lack of a CS background I would feel at a further disadvantage given a question like "What is the most efficient way to sort a million integers?"; I might blurt out "With a computer". With this kind of attitude you might start to think they are a bit arrogant.

However this paper on the Chubby Lock Service gives me hope! I was interested in it because it uses the Paxos algorithm, and I am pretty interested in Paxos from our work on HARC. This section in the Chubby paper introduction caught my eye.

Readers familiar with distributed computing will recognize the election of a primary among peers as an instance of the distributed consensus problem, and realize we require a solution using asynchronous communication; this term describes the behavior of the vast majority of real networks, such as Ethernet or the Internet, which allow packets to be lost, delayed, and reordered. (Practitioners should normally beware of protocols based on models that make stronger assumptions on the environment.) Asynchronous consensus is solved by the Paxos protocol [12, 13]. The same protocol was used by Oki and Liskov (see their paper on viewstamped replication [19]), an equivalence noted by others [14]. Indeed, all working protocols for asynchronous consensus we have so far encountered have Paxos at their core. Paxos maintains safety without timing assumptions, but clocks must be introduced to ensure liveness; this overcomes the impossibility result of Fischer et al. [5].

Lets start with the first sentence, "asynchronous communication; this term describes the behavior of the vast majority of real networks, such as Ethernet or the Internet, which allow packets to be lost, delayed, and reordered.". This definition of asynchronous communications, in the context of a discussion on Consensus, is wrong. Let's grab the Fischer et al. paper for our reference. This paper, famously known by the initials of the authors names as FLP, is one of the most important in distributed systems literature; we will see why it is so important in a bit. The full title of the paper is "Impossibility of Distributed Consensus with One Faulty Process",pretty arresting stuff! From the paper:

"In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable - it delivers all messages correctly and exactly once. Nevertheless, even with these assumptions, the stopping of a single process at an inopportune time can cause any distributed commit protocol to fail to reach agreement."

The paper goes on to describe an asynchronous system:

"Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processes or about the delay time in delivering a message. We also assume that processes do not have access to synchronized clocks, so algorithms based on time-outs, for example, cannot be used. (In particular, the solutions in [6] are not applicable.) Finally, we do not postulate the ability to detect the death of a process, so it is impossible for one process to tell whether another has died (stopped entirely) or is just running very slowly."

So "asynchronous communication" actually means that there is no upper bound on how long a message can take to be delivered. You can have asynchronous communications and a perfect network: messages are always delivered, they are delivered in order and delivered only once, but it can take an infinite time for them to be delivered. This is the FLP model. (For previous rants on asynchronous, synchronous and partially synchronous see this blog entry: Asynchronous?.) Of course in synchronous communications you can have message losses, message delays and message re ordering, but it is easier to deal with in this environment: if I don't get a message in the next 30 seconds I know there has been a fault.

The FLP paper is important for two reasons: it says something fundamental about dealing with faults in distributed systems, and it demonstrated how to show some problems in distributed computing are impossible to solve. Dealing with faults in an asynchronous system is very difficult, because you cannot tell whether a processor is very slow or faulted. You need to use time, or fault detectors. To show that a problem is impossible to solve FLP uses proof by contradiction: show what properties an algorithm that solves the problem must have, and then show that there is some contradiction in the properties. After FLP people had lots of fun showing stuff was impossible.

The next phrase in the Chubby paper is: "(Practitioners should normally beware of protocols based on models that make stronger assumptions on the environment.)" This seems a bit rich! With respect to timing models, you can choose between synchronous, asynchronous or partially synchronous, then you can choose the fault model, for example Byzantine or non-Byzantine. As we will see Chubby system actually does make stronger assumptions about the timing model, it is actually depending on the system being partially synchronous.

The next line in the Chubby paper is: "Asynchronous consensus is solved by the Paxos protocol [12, 13].". The wording is a bit loose here, there are various versions of the consensus problem with different fault models and requirements, for example Uniform Consensus or even the Byzantine Generals, however most people would take this statement to mean the consensus problem as defined by FLP. But FLP showed consensus in an asynchronous system is impossible with only one faulty process! (Consensus is straight forward without faults, so is not really considered a problem).

Now skipping to the last sentence from the Chubby extract: "Paxos maintains safety without timing assumptions, but clocks must be introduced to ensure liveness; this overcomes the impossibility result of Fischer et al. [5]." The logic of the last part implies that Fischer et al. are wrong, or else Google have achieved the impossible! However if we wind back a bit, they introduce clocks and once you do that the system is no longer completely asynchronous. They don't overcome the impossibility result of Fischer et al., they are using a different model which isn't completely asynchronous.

So why all the confusion? Lamport clarifies it as follows: "Asynchronous consensus algorithms like Paxos maintain safety despite asynchrony, but are guaranteed to make progress only when the system becomes synchronous - meaning that messages are delivered in a bounded length of time." Paxos is an asynchronous algorithm because it doesn't use time, but the timing of events in the system must conspire for it to terminate.

Butler Lampson summarized the timing requirements nicely in "How to build a highly available system using consensus.":

"It [Paxos] terminates if there is a single leader for a long enough time during which the leader can talk to a majority of the agent processes twice. It may not terminate if there are always too many leaders (fortunate, since we know that guaranteed termination is impossible ).". The last part is FLP.

There is a pathological case in Paxos were two leaders compete to get a value chosen and you effectively end up with livelock, however it is not difficult in practice to avoid this. Lampson describes how to use a sloppy leadership election to try and make sure there is only one leader, it doesn't matter if the sloppy leadership election screws up because we know Paxos is safe with multiple leaders. The pathological case corresponds to the FLP result.

"Consensus in the Presence of Partial Synchrony" provides details on the conditions that are required in order to reach consensus.

I have only a practical interest in Paxos in order to solve the problems addressed by HARC. I am not sure I fully understand the proofs behind it, or FLP, but the main ideas behind it are important to get right. Which is why I am so disappointed by the Chubby paper, more people will read it than FLP, or the Paxos papers, and it will only cause confusion. As if the "The Part-Time Parliament" doesn't do enough of that!

Perfect Code

2007-02-07T07:21:00.000-08:00

Jim Gray's disappearance has lead me to reflect on the things he has written that have stayed with me. One them is perfect code. In
Transaction Processing: Concepts and Techniques Jim talks about perfect code; code without bugs. He even gives an example, a simple function of a few lines that adds two numbers together. In fact it took him a couple of attempts to get it right! Jim makes the point that perfect code is possible, just very expensive. He goes on to talk about the cost of code in terms of dollars per line. NASA pay the most, but their code still has bugs! The astronauts board the shuttle with a bug list, an example of which was not to use the two keyboards on the shuttle at the same time because the inputs would be OR'd! Perfect code is possible, just really expensive.

Most people are surprised when I say that perfect code is possible, they just assume that all code contains bugs. I was reminded of this while following the Nearly All Binary Searches and Mergesorts are Broken thread on binary search implementation bugs. At the time I hit the library to check Knuth's version of binary search; he didn't let me down. Someone who invents their own ISA to express their algorithms isn't going to get caught by an overflow.

I am sure the attitude that all code contains bugs must have a detrimental effect on programmers, it has on me. It is also re-enforced by the open source mantra "release early, release often". Testing doesn't solve all the problems either: "Testing can only prove the existence of bugs", Dijkstra.

I recently re-read the History of System R. The name Franco Putzolu cropped up, Jim mentioned him in the acknowledgements of "Transaction Processing: Concepts and Techniques" as someone who had made huge contributions to the field of transactions and databases but who never got the public recognition as his name was not on a lot of the famous papers.
From the System R history (Copyright attached):
Mike Blasgen: The RSS didn't have any bugs. [laughter] No, it's true, the reason is because much of the RSS was written by Franco. No, it's really true; Franco never wrote a bug. Except for one, right, Bruce? Did you find one? Bruce Lindsay: One. Mike Blasgen: He wrote about half of RSS, and I think we found one bug. And that was after nine years.

RSS was the storage part of System R and used B-Trees. It was 35,000 lines of code to solve some pretty hairy problems, and had only one bug! Remember too that the tool support back then must have been terrible compared to today. Pretty perfect then.

Copyright (c) 1995, 1997 by Paul McJones, Roger Bamford, Mike Blasgen, Don Chamberlin, Josephine Cheng, Jean-Jacques Daudenarde, Shel Finkelstein, Jim Gray, Bob Jolls, Bruce Lindsay, Raymond Lorie, Jim Mehl, Roger Miller, C. Mohan, John Nauman, Mike Pong, Tom Price, Franco Putzolu, Mario Schkolnick, Bob Selinger, Pat Selinger, Don Slutz, Irv Traiger, Brad Wade, and Bob Yost. You may copy this document in whole or in part without payment of fee provided that you acknowledge the authors and include this notice.

Idempotent Messages

2007-01-19T09:34:00.000-08:00

There has been quite a bit of internal discussion of Pat Helland's paper at Mancs. Although Pat sees the usefulness of idempotent messages, I wonder if he has considered the fact that though a message may be idempotent, a sequence of idempotent messages may not be idempotent. Lamport thought about this in his paper on Generalized Consensus and Paxos, he also considered if messages could commute before bundling them. A HTTP GET will commute with another HTTP GET, but I am not sure about the other methods.

Below is a fragment of the discuss we are having on idempotent and at-least-once messaging...

Say a state machine has a possible sequence of state changes
A->B->C and once it reaches C it cannot change state, and A is the
inital state. The state machine accepts two types of message
<a->B and <b->C>. If the state machine is in state B, it can
ignore messages <a->B> because it inherently knows it has processed such a message before. Therefore it doesn't need to store message IDs to achieve at-least-once delivery.

In the above system the two messages are inherently idempotent,
as designed. Out of order delivery is interesting, if the
sequence <(A->B),(B->C)> is delivered out of order then both
messages will fail to cause a state change. Nothing bad happens?

If we replaced the two messages with a single <ChangeState> message, then it is not idempotent, and we would need to include message IDs
to achieve at-least-once delivery. Out of order delivery MIGHT now
cause unwanted side effects, depending on the system and what clients expect.

The second approach to messaging appears simpler because there is
only one message no matter how many states the state machine has,
the first case has N-1 messages were N is the number of states.

Clearly message design has a big impact on the behaviour of the system!!!

For an application to "know" that it has processed a message, it
must be in a state that it can only have reached by processing that
message. There seems to be two approaches to achieve this: design your system to use idempotent messages, or design it so that progress
from one state to another makes messages idempotent. An interesting question is whether these two approaches are equivalent? If you
used both approaches would you come up with the same design.

The messages <a->B> and <b->C> map to PUT(B) and PUT(C) in HTTP, while <ChangeState> maps to POST(ChangeState).

In a programming language the operation might be implemented as
stateMachine++. stateMachine++ is interesting because it looks like ,
but the underlying system (CPU and memory) views it differently:

retrieve value stored at address "stateMachine", increment value, put new value back to address "stateMachine"

However latency is zero, or at least is masked to appear as zero.
Partial failures are not possible. In a multi-thread environment
locks would have to be introduced, but without partial failures this
isn't a problem (a processor holding a lock cannot die without the
rest of the system noticing, or failing).

Asynchronous?

2007-01-19T05:29:00.000-08:00

As I do not have a CS background I have always been confused
when people used the term asynchronous. This entry has been
prompted by Dave Orchard's description of SOA

HTTP is a network protocol. HTTP is asynchronous. It uses a
Request-Response pattern, a client sends request and the server
sends a response. However there is nothing in the protocol about
how long the response will take, therefore it is an asynchronous
protocol. TCP is a synchronous protocol, there are various timeouts
specified in the standard and, agents are supposed to react in
specified ways to these timeouts.

However most HTTP libraries use synchronous function calls: a client
makes a call to a function in the HTTP library, the library sends a
request to a HTTP server and returns the response message to the
client using the return mechanism of the function. Most HTTP
libraries allow the client to pass a timeout value to the library,
if the server does not respond within the timeout then the library
reports an error to the client. The timeout is specified by the client,
not by the HTTP standard.

Some HTTP libraries support asynchronous function calls: for example
the client makes a function call to the HTTP library, the call does
not block but returns immediately, the client can do some other processing
before making another function call to pick up the HTTP response.
LWP::Parallel is an example of such a library. There are also terms like
blocking/non-blocking etc which can be used to describe function calls.

So there are two concepts of asynchronous/synchronous at play here: one
that is used by people like Lamport and Lynch to describe distributed systems
and one used by people to talk about programming models. As I don't have a
background in CS this confused me for a long time, I was never sure how people
were using the term. The issue is further complicated by the fact that if you
are building an asynchronous system, per Lamport and Lynch, then using an
asynchronous programming model is more suited to the task.

So reading Dave Orchard's blog entry on SOA I am wondering what he means
by advocating "asynchronous". He is describing an approach to
distributed computing called SOA, so I guess he must be talking about
the Lynch/Lamport definition of asynchronous. This has consequences,
namely that you won't be able to do very much.

In an asynchronous system it is impossible to reach consensus with just one
faulty processor, even with a perfect network. Consensus is the problem of
getting a set of processors to agree a value. Consider the case of submitting
a purchase order in an asynchronous system, you send the request but the
request can take an infinite time to reach the server, the server can take
an infinite time to process the message and the response can take an infinite
time to return. How can you tell if the server failed? On the Web this is
equivalent to hitting the submit button and nothing happening - what do you
do? Wait a bit longer, wait for an e-mail, re-try the submit button,
ring/e-mail the server administrator etc, some internal clock triggers an action.
In an asynchronous system you just wait, if you include timeouts then it is
no longer asynchronous.

There are three timing models in distributed systems: synchronous,
partially-synchronous, and asynchronous. For definitions see

Consensus in the Presence of Partial Synchrony:

synchronous: In a synchronous system, there is a known fixed upper
bound on the time required for a message to be sent from one processor
to another and a known fixed upper bound on the relative speeds of
different processors.

asynchronous: In an asynchronous system no fixed upper bounds exist
on the time required for a message to be sent from one processor
to another, nor on the relative speeds of different processors.

partially-synchronous: Fixed bounds are known to exist but are not
know a priori, or in another version the fixed bounds are known
but are only guaranteed to hold starting at some unknown time.

Designing algorithms for asynchronous systems is attractive because
they will work in any system, synchronous or partially-synchronous.
So using an asynchronous model for the internet makes sense, but you
are restricted in what you can do. It is interestingly to note that
some Web Service specifications are synchronous. For example WS-Security
uses time ranges to define how long a message is valid for,
messages that arrive outside this range are not processed. This causes
problems when systems that have a large clock skew, I have seen many weird
bugs arise due to this including messages arriving before they were sent!

So choosing an asynchronous timing model for your distributed system
may not be so attractive after all. Perhaps Dave meant an asynchronous
programming model? At first this doesn't make sense, since he is talking
about an architecture for a distributed system, how you write code
for such a system should be an orthogonal issue. However looking through
the discussions of SOA I can see a pattern.

Remote Procedure Call, RPC, as introduced in IETF RFC 707, introduced an
abstraction which allowed programmers to think that invoking a remote
service was the same as invoking a local function call. The abstraction
was extended by the concept of distributed objects, the programmer could
think of a remote object as being just like a local object. The idea
behind this thinking is that programmers are familiar with procedure
calls and objects, and so RPC and distributed objects will be an easy
path into distributed computing for a programmer already familiar with
procedure calls and objects. However this abstraction was shown to be
a bad one, perhaps most famously by Waldo et al. By pretending remote
things are just like local things, the programmer is lead to ignore
latency and partial failures. (Though it is hard to imagine people like
Jim Gray and Butler Lampson would fall into this trap.)

There has been a lot of debate in the past with issues like SOA != RPC
and WS != Distributed Objects. However I think there are two different
issues, one is the architecture of a distributed system, the other is
the programming model. I can take a good architecture, for example REST,
and use a bad programming model, for example RPC, to build a client
library.

A Web services toolkit can attempt to hide the complexity associated
with distributed systems, and it may initially be easy and familiar to use,
but ultimately it will betray the programmer by misleading him just like RPC.
Or you can design a better programming model, which does not mislead the
programmer but would probably be more a difficult programming environment.
A naive programmer might think the first is better because it is easier
to use. There is a balance to be struck.

An asynchronous programming style forces the programmer to
think about the system more carefully as a distributed system,
perhaps this is why Dave is advocating asynchronous. However to
me, someone who uses raw sockets a lot, it muddies the discussion
on architectures of distributed systems.

REST doesn't prescribe a programming model it is focused purely on
the architecture of the system, you can write bad HTTP clients and
services, or you can write good ones like LWP. SOA/WS-* has had its feet
stuck in the debate about programming models, which has caused
me confusion.

Pat Helland Discovers REST - the hard way!

2007-01-08T08:57:00.000-08:00

Pat Helland has an interesting paper on scalability and transactions called: Life beyond Distributed Transactions: an Apostate’s Opinion. First, it raises questions about our use of Paxos Commit to solve the co-allocation problem in HARC. However, we don't expect co-allocation to ever involve more than a few resources and we do not expect a heavy demand on the service, also we are quite loose about serializability.

The more interesting aspect of the paper is the similarity of the ideas in it and the concepts in REST. The paper discusses "infinite scalability", yet never mentions the Web, which must be the best example of infinite scalability in a distributed application (Fielding uses the term anarchic scalability which I prefer as it sounds even more daunting). I guess this reflects Pat's background as a transaction guru; he is interested in scaling out the systems he knows.

The paper introduces the concept of "entities" which are identified by keys and to which messages are sent. This maps to resources and URIs, the issues of primary keys and secondary keys wrt to scalability can be handled more elegantly and transparently using DNS trickery and re-directs. The paper also talks about the usefulness of the concept of recognising that some messages are idempotent, for example reads - hello GET and PUT! He misses the usefulness of caching though, I am sure he might like it.

Also the seperation of the application into two layers, with only the lower layer needing to be scale aware maps to the Web. The developer writes the scale agnostic layer that interfaces with the scale aware layer through the "Scale Agnostic Programming Abstraction".
This means he does not have to worry about scaling issues and can leave them to the developer of the scale aware layer. On the Web, a Web developer can use a Yahoo API (the Scale Agnostic Programming Abstraction, which is of course RESTful), to write applciations which have no idea about the scale of Yahoo or how the internals of Yahoo works.

SAML and URNs

2006-12-08T08:19:00.000-08:00

SAML
I am reading through the SAML specifications in an effort to understand Shibboleth. OpenID seems to be a competing technology to solve the single sign on(SSO) problem. OpenID is a grassroots effect, while Shibboleth is industry lead, so it will be interesting to see who wins this one. Shibboleth offers more functionality by going beyond just supporting idenity, it can also provide attributes about the user that can be used by a service for making authorization decisions. The cost of this is complexity and performance: lots of XML that has to be signed and encrypted.

One interesting thing in the SAML specs is that it states that Web proxies should not cache certain messages. Is it worth while saying this, can you really trust proxies to do what you ask them? (Byzantine faults) What are the consequences if they do cache them?

The real point of this post is this URI from SAML 2.0:

urn:oasis:names:tc:SAML:2.0:status:Success

Tried clicking on it? First it should be a http URI

Second I am concerned about the 2.0. Has success been redefined since SAML 1.0?

Now for a bit of HTTP bashing. Even toddlers know what HTTP 200, 404, 201 etc mean. But can we reuse them in other specs. Maybe if they were URIs! Why are the error codes in HTTP not URIs? Anything that can have a URI can be a resource, surely 404 deserves to have URI.

WS-Security, simple enough to shoot yourself in the foot with.

2006-12-02T04:45:00.000-08:00

WS-Security, simple enough to shoot yourself in the foot with.
Gunnar Peterson's critiques REST security in terms of WS-Security, I just have to comment. Frist I have helped implement WS-Security in Perl, in particular signing, so I got to know the specs pretty well. Some good things about message level security and WS-Security:

1) The WS-Security spec is pretty good and well thought out by people who know the issues. It was a learning experience for me.

2) Message level security is much more flexible than transport layer security. You can go beyond simple client/server architecture,
so you can go beyond what REST. For example in the Grid world you could use message level security to build a resource broker:
client submits a job submission message to a resource broker, resource broker picks resource and sends message to resource, resource authenicates message and runs job. (OK there is a whole issue of what the hell you do with the WS-Addressing headers, if the client signs the wsa:To then how do you forward the message on).

Now the difficult stuff: how many people know why you must sign the X509 token you use to sign a message? Reason: mutiple certificates
can share the same public key but have different authorization levels, you don't want someone switching certificates and getting different access rights. How many people know you need to include a timestamp to avoid repeat attacks when signing messages? You will also need a unique message ID along with that timestamp, luckily WS-Addressing provides one - did you know that you need to sign WS-Addressing headers to secure messages? You better record those timestamps & message IDs, so you are gonna need transactional writes. Also signing/encrypting at the XML level is pretty slow - so many bits to sign, all that XML Canonicalization etc, so you might need a few extra servers; of course with them all accessing the same stable storage for every message to check message IDs and timestamps. Oh, and better make sure the client/server clocks are synch'd, cause it can be a pain to debug if not.

Of course the toolkits will handle this for you. Wrong. In WSRF::Lite it automatically included and signed the X509 cert and timestamp, part of WS-Security spec strongly recommends this. Then someone from a huge(TM) company asked if this could be turned off on the client side as the service developed using some big name toolkit didn't use this. I pointed out that this could be a security vulnerability and that they should also be signing WS-Addressing headers, I got a "well I duno anything about that, but the client wants it this way" - well I hope they are using that gigantic hole in the firewall, AKA SSL. People too often think that just turning on WS-Security will make their application secure.

As for REST, XML signature and encryption can be used in REST. In fact it might be eashier as you don't get caught in the flat structure of SOAP Header/Body - you can use a Russian doll model (or onion model) of embedding XML in XML, each service peels of the layer it is interested in before passing the message onto the next service. No service has to understand the XML in any other layer but its own. This is the model that we had planned for HARC, it will be interesting to see if it works ;-)

For more pain on this subject see: Taverna and Security

A REST hall of shame...

2006-11-23T06:49:00.000-08:00

More GET madness!
You might think I am looking for examples of the misuse of GET but they just keep appearing, and from Apache products too. This time it is Tomcat which can be managed, and even parts of it undeployed, with HTTP GET. Maybe there should be a REST hall of shame.

The GETs are ment to be used from scripts written by sys admins. In a universe far, far away Grid people are trying to solve this using WS-Management or WSDM, which without looking at either I can guarantuee are going to pretty complex. There must be some middle ground.

There is no reference implementation of WSRF

2006-11-22T08:20:00.000-08:00

There is NO reference implementation of WSRF.
Reading this paper on co-allocation presented at SC06 I came across this:

We have implemented a prototype of the proposed system
as a set of cooperative Grid services using Globus Toolkit 4
(GT4) [Globus ], that is a reference implementation of WS-
Resource Framework [WSRF ],...

GT4 is not a reference implementation of WSRF, there is no reference implementation and GT4 is not WSRF compliant. The reviewers should have caught this.

Bruno Blogs

2006-11-22T07:49:00.000-08:00

Bruno Blogs
Bruno from Manchester Computing has started bloging with a salvo at WSRF

The Lost Update and HTTP

2006-11-20T09:01:00.000-08:00

The Lost Update and HTTP
This is a very good description of how to handle the "lost updates" problem when using HTTP. I have never understood etags until now: Editing the Web - Detecting the Lost Update Problem Using Unreserved Checkout. WS-RF and WS-RT of course do not have support for this, you would need to compose with WS-AtomicTransaction or WS-BA.

Me, A Web Fundamentalist!

2006-11-20T08:59:00.000-08:00

Web Fundamentalist
I think I might be one of Ian's Web Fundamentalists!

I will take it as a complement :-)

His defintion of fundamentalism is worth repeating:

Fundamentalism is a continuing historical phenomenon, characterized by a sense of embattled alienation in the midst of the surrounding culture, even where the culture may be nominally influenced by the adherents' religion. The term can also refer specifically to the belief that one's religious texts are infallible ...

Within in the Web community I guess that is a good way to catagorise the REST people: they think a lot of the Web is being done badly eg cookies and GETs with side effects. We also have our religious texts, which we think is infallible.

However Ian is mixing the MEST heads (aka POST everything through the one URL) with the REST people, and tarring them with the one brush. Sorry Ian, REST v MEST is a seperate battle ;-)

Unfortunately Ian doesn't 'get' REST. The unifrom interface is not just a set of HTTP methods, first HTTP is just protocol to which REST has been applied to the design of, not REST itself, and second the uniform interface goes beyond just operations; it includes things such as how you identify resources|objects|Grid services. Many of the ideas behind OGSI can be mapped to REST, it was just a question of
application. Ian your a RESTafarian, you just don't know it ;-)

In the end there is not much difference between OGSI, WS-RF and WS-RT; as if to illustrate the point people are even talking about using XSLT to create interoperability between WS-RF and WS-RT! There is not enough difference to waste all those years on anyway. In fact the point could be made that OGSI is better than WS-RF/WS-RT because it has support for identification which the others lack.

The whole stateful/stateless argument was a red herring. OGSI is a stateless protocol, just like HTTP and NFS. If you needed stateful interactions on top of OGSI you could compose with WS-Context, just like you can use cookies with HTTP.

Is REST the right approach to Grid computing? For some parts yes, for others no (Jabber is an interesting option that we have been playing with). REST is an architectural style for building a large scale distributed hyper-media system, where that overlaps with Grid computing it should be used, where it does not a different approach should be used. Would it be possible for a Grid architectural style? That is the huge challenge which I guess the OGSA group is facing.

For me, I have demonstrated that for RealityGrid a REST approach was better than the WSRF approach: Combining AJAX and WSRF for Web-browser based Grid clients. I have also demonstrated that REST can be used to solve
complex Grid problems like the co-allocation problem in a fault tolerant way that is beyond the fu
nctionality provided by the WS-* specs:
Co-Allocation, Fault Tolerance and Grid Computing, addressing the charge that it is only suitable for trivial problems.

Well at least Ian called me a Web fundamentalist in a RESTful way. I might use it in my e-mail signature, maybe he could include it in a reference for me too :-)

Axis2: This Ain't REST

2006-11-20T08:56:00.000-08:00

This Ain't REST
I have been playing around with Axis2 to create some sample services for the Taverna people to chew on when I looked closer at the "REST support"....

Running the Client ================== - From your browser, If you point to the following URL: http://localhost:8080/axis2/rest/StockQuoteService/getPrice?symbol=IBM You will get the following response: 42.0 - If you invoke the update method like so: http://localhost:8080/axis2/rest/StockQuoteService/update?symbol=IBM&price=100 And then execute the first getPrice url. You can see that the price got updated.

So you use GET to update the price! I think not. GET is safe, it should have no
side effects. This is bad because it is a toolkit advocating an approach, and
to think that it comes from the Apache foundation.

Beta Thoughts

2006-11-20T08:54:00.000-08:00

Taverna Meeting
Had a good meeting with June and some of the developers of Taverna to discuss security and the requirements. They are keen to improve support for security within Taverna but will be doing it on a case by case basis, ie you provide a service that uses some form of security and they will add support for it to Taverna.

I will create a service that uses HTTPS with mutual authenication and WS-Addressing EPRs and see if the Taverna guys can connect to it. Maybe later decorate the WSDL with some WS-SecurityPolicy.

Three weeks down, two to go....

2006-11-10T09:02:00.000-08:00

Three weeks down, two to go

Elise as completed her third week of radiotherapy! The time has flown by so fast it is hard to believe, only two more weeks to go. She has had no side effects yet: skin damage, bowel problems, eating problems nor tiredness, which is great. And to think how worried we were at the start...

Preview doesn' work too good...

2006-11-10T08:10:00.000-08:00

Beta Thoughts
Mmmh, looking at my last post it seems the preview doesn't work too well. Must find something better...

Taverna and Security

2006-11-10T07:28:00.000-08:00

What does Taverna need to support security?

Read over 200 pages of WS-* specs to try and understand what is required for Taverna to support security. The horror, the horror.

Taverna is a workflow tool that came out of the MyGrid project that
has got a lot of good press. We are thinking about using it for the NanoCMOS project. Unfortunately Taverna doesn't do security, and we have a strong requirement for security; the good news is that they are working on it!

Downloaded and played with Taverna, and it looks pretty good.
Noticed that many of the services for which Taverna is pre-configured have lots of get* type operations. We need one GET to rule them all!

I have been asked to look into what is needed by Taverna to support
security given my experience implementing WS-Security for Perl.
Beyond support for WS-Security, WS-SecureConversation and HTTPS it looks like the following specs are important:

WS-Addressing (signed SOAP Headers for end-2-end security, also
policy can be stuck in the meta-data of the WS-Addressing EPRs),

WS-Policy and WS-SecurityPolicy(the language for declaring security policy, I thought this was pretty cool as it included support for saying things like "I want mutual authentication over HTTPS" etc.),

WS-PolicyAttachments (were you find policy, for example tells you how to extend WSDL to include policy)

WS-MetaDataExchange (policy can be found and retrieved using WS-MEX, unfortunate dependence on WS-RT which is getting a rough reception at the W3C).

Of course WS-SecurityPolicy had no support for declaring policy with
respect to Proxy certificates, more work for the OGF then. Other specs that may have an impact, but which I haven't looked at are
SAML, WS-Trust, and I am sure there are others.

If all this stuff worked and the tools consumed it with eash then it would be pretty powerful stuff, big if though.

Globus GT 4.0.3 Not WSRF compliant!

2006-11-10T06:10:00.000-08:00

Downloaded Globus GT4.0.3 to evaluate it for the NanoCMOS project. Unfortunately it uses really old versions of the WSRF and WS-Addressing specifications. This means that GT 4.0.3. is not WSRF compliant. It also means that services developed with GT 4.0.3 are not WSRF compliant either!

I asked when it would become compliant, but have got no response yet.

I cannot recommend that we use GT4 until we know what its timelines are. Once it does become compliant there is a strong chance older versions will not interoperate, making existing code and services obselete. Also many other WS-* tools are using the correct version of WS-Addressing, so they won't play nicely with GT4.