Atomicity in network protocols

Hi Don, this scenario has been addressed in the tcp protocol (rfc793,

Dimier

------------------------------------------------------ Dimiter Popoff Transgalactic Instruments

------------------------------------------------------

Yes, the server can detect the broken connection and, presumably, clear the locks held by that connection (as well as "void" the contract that was created for that connection).

But, there still is the possibility of a misbehaving (buggy) client taking a LOCK and never releasing it (*without* crashing to the point that the network stack would be reset, releasing all open connections).

I.e., the LOCK/UNLOCK approach just seems like bugs waiting to happen. I like a buggy client to be the *only* client affected by its misbehaving. It's "rude" for its bad behavior to compromise the rest of the system :-/

Transmit the validity information (from the query) back to the server along with the set. If the validity information has changed, the server rejects the update (possibly sending the new validity data back to the client with the reject). The client then tries again. IOW, you're implementing atomic Compare-and-Swap.

Alternatively, you might consider using some token that represents the validity data, rather than the validity data itself. Perhaps a counter that increments every time a setting changes. Then you return the state ID/number and the update fails unless the server is in the same state. This is basically the same approach, but tracks the changes slightly differently.

Hmmm, well, this has no plain fix. One door - one key - key held by the offender. :-)

I would consider exchanging those heartbeat messages over the connection again; the server can challenge the client and if the client misbehaves in a detectable way close the connection (having an open tcp connection to it is enough of a lock information, probably). If the client deliberately misbehaves and keeps the connection alive this will not work. But this is other territory, I guess. (?)

Dimiter

------------------------------------------------------ Dimiter Popoff Transgalactic Instruments

------------------------------------------------------

I don't see how this buys me anything. The server already *knows* (before the client) that the old "status" is no longer appropriate. When the (first) "set" is acted upon, this changes the current configuration of the "device" -- with repercussions in the ranges of values for all the parameters (possibly).

What the server *doesn't* know is that the client who issued the query will be using *that* value (or, some other related value that is now invalidated by the other client's "set") in a subsequent "set". And, there is no way to asynchronously inform that client of this fact UNTIL he tries to do something that is now "not compatible" with the new configuration.

But this is just the same problem with a different interface. I.e., the client knows something has changed because the decision it made based on its earlier query is no longer considered valid.

Note that the client needs to see the result of the query in order to decide what "set" action to take. So, the client is always doing something like: QUERY SET And, while it is ing, there is the possibility of another client coming in and doing a SET that effectively changes the result of that QUERY.

Note that there are no other actions that another client can initiate that "restrict" the range of choices available to this first client. QUERYs are passive and anything else either is a deliberate abandonment of that other client's existing contract (e.g., RESET ) or an unintentional "reset" (closing the connection, etc.)

I had considered (originally) allowing the client to specify multiple parameters in a single SET (i.e., effectively a "LOAD CONFIGURATION" command). But, as parameters interact with each other, it wouldn't be possible for the client to determine what combinations of parameters are legal.

E.g., the device might operate over a range of [0,1000] with accuracies in the range of [1,5] (percent). But, the 1% might only apply to the [10,20] range so specifying a range of [5,500] with an accuracy of 2% would yield an unexpected error ("Gee, I know the device can operate over a range of [1,1000] -- and [5,500] is fully contained within that range -- and the 2% accuracy I am requesting lies within the [1,5]% range advertised... so, why am I getting an error??")

In the current protocol, the client sets *one* parameter at a time. I.e., even the "data range" is specified as LOW and HIGH limits (two SETtings). This is because some devices might have configuration options for "data ranges" like: [1,10] [2,50] [3,80] [5,100] etc. As such, specifying a LOW value of 3 means the device can only offer you a HIGH value of "80 or less". Similarly, specifying a HIGH value of 12 (before specifying a LOW value) means the device can offer you a LOW value of "2 or more".

In this way, the client can see the consequences of each SETting he makes (I couldn't think of an easy way of exporting every possible set of configuration options that a device might support :< )

The "lock" doesn't have to actually mean anything; it can just be an "opening bracket", a syntactic token which indicates the beginning of the transaction.

Of course. But the semantics matter!

I don't see how this is an improvement. It just lets the server roll back all of the SETs when/if the transaction fails. It also assumes clients will always bundle their interactions with the server -- setting forth *all* of their (immutable) requirements at the same time.

The only difference (besides deferring the actual hardware configuration dialog) between this approach and the current implementation is the consequence of an incompatible SET command -- in one case, the client knows about it as soon as it is attempted; in the other, the client gets surprised by the fact that the transaction fails at some later time (despite the fact that it *appeared* that the SET was going to succeed).

In either case, the client has to be prepared to handle the failure. And, there is no way (in either case) for a client to *ensure* that his interactions *will* succeed.

The current implementation consults a "table of capabilities" for the device in question. This essentially enumerates all of the "specifications" for each "mode" (a generic term that acknowledges the fact that devices can be configured to operate in different ways and with different contractual guarantees) that the device can operate in.

The server maintains a "configuration_t" for each client indicating the constraints that the client has specified (SET) for the device. From the intersection (or union, depending on how you look at the venn diagrams :> ) of these configuration_t's, the server drives the *actual* device's Configuration such that all of the requirements of each of the clients are met simultaneously.

When a SET would cause a client's configuration_t to become incompatible with *all* of the enumerations in the "table of capabilities" for that device, then the SET is rejected.

The server is responsible for interacting with the device to put it

The "hardware" (device) typically doesn't/can't provide the functionality that this "service" provides. I.e., you can tell it "operate in the [1,1000] range" but it *won't* tell you that it is now operating at "5% accuracy". That information is gleaned from datasheets/manuals and hand-coded into the server ("table of capabilities").

Yup. There's only so much you can protect against. OTOH, you don't want to *invite* abuses...

For the most part, connections will tend to remain "active" as long as the client needs the data. I.e., once the characteristics of the connection (accuracy, range, etc.) are negotiated, the client will typically sit in a loop GETting current data from the device.

I can't protect against a rogue client configuring the device for some incredibly restricted (un-useful) operating configuration (e.g., range [0.0,0.0000001]; accuracy 0.00000000000000001%; etc.) and then just sitting with the connection open but idle, indefinitely.

But, there would be no point in a client behaving this way.

What I really want to do is discourage laziness on the part of coders: "Gee, I don't want to have to worry about the possibility that some other client might configure the device in a manner that makes *my* job more difficult. And, I don't want to have to deal with retry and recovery logic. So, I'll just grab the device (LOCK) in the first line of code -- so I can be reasonably certain of *getting* it -- and then I'll go about my normal startup routines and figure out what I really want from the device. Once I *know* I have what I need, *then* I'll release the device so other clients can figure out how to adapt to the configuration constraints that *I* have imposed..."

I.e., make it easier for folks to "do the right thing" than it would be for them to "do the wrong thing"!

I was suggesting altering the protocol to something along the lines of how you'd implement many of the lock-free algorithms in multi-threaded applications. IOW, by providing a robust way for the client to see that another update has happened, it can then retry. Obviously that has multiple-update issues (just as do lock free algorithms), but in this application it's easy enough to encode multiple updates (just like DCAS allows you to implement many more lock-free algorithms than does straight CAS).

Ah, OK. But, the client will still *infer* that something has changed simply because his SET failed.

I can't see a way to do what I want with my current protocol (or minor perturbations of it). I should probably rethink the entire protocol with an eye on supporting a means of specifying

As The King would say, "Is a puzzlement"

While I don't know if this applies in your situation, that would not usually be adequate. Consider the case where the client knows the server is in state A, and therefore wishes to set state B. In the mean time, another client sets the server to state C. Setting the server from C to B may be perfectly valid (thus not generating an error), but might not be what the first client actually wanted. The idea being that the update works if the server was in the state expected by the client, and only then.

Not the case, here.

The server is always in a "valid" state (i.e., if you equate the configuration that the server is imposing on the actual "device" as being the state of the server).

SETs can only move the server to another valid state (else they fail).

SETs can bring the server to a more restricted or *less* restricted state. I.e., if a client changes *his* current configuration to one that is more tolerant (e.g., changing from 1% accuracy to 5%) then the server (device) can (possibly) move from a more tightly defined state to a more permissive one (e.g., at 5% accuracy, the range of measurable data values might be greater than it was at 1%).

Note that actions of another client can never invalidate the *current* configuration for any of the connected clients. E.g., if client1 wants 1% accuracy and the other clients want 5%, then the device still operates at 1% even though "most" of the clients don't need/want that accuracy.

However, if one of those clients has dropped his accuracy to 5% in the hope of increasing the measurement range to something larger, that SET RANGE can be denied -- because the device might be forced to remain in a narrower range in order to satisfy the needs of the "1%" client.

A "problem" with this whole scheme is that clients are deliberately isolated from the needs of other clients. Instead, the responsibility of coordinating their requirements lies with the system designer. I.e., if you designed a (single CPU) system with multiple consumers of a particular data, it would fall to you to ensure each consumer had the right data, with the right accuracy, timeliness, etc. -- even *if* those consumers all knew about each other.

Then instead of letting the client set a server's state, let a client tell the server its requirements. The server then keeps track of what each client wants, and adjusts its behavior appropriately. If a client specifies requirement that are incompatible with what the server can do (presumably because conflicting requirements have already been set), you'd have to fail them at that point.

Add a periodic poll to make sure each client still existed, so that you can delete requirements when a client dies. Obviously if the client told you it was going away, you'd do the same.

Yes, this is how it works currently.

A client (initially) knows nothing about a server's (i.e., the device that the server is managing for the client(s)) capabilities.

A client (recall there can be multiple) connects to the server.

It then queries the capabilities available for that device (low/high measurement limits, accuracy, error, latency, rate, resolution, precision, etc.).

The current protocol allows *one* parameter at a time to be queried (simplifies the protocol and also avoids the issue of "what param values fit with which other param values) or set.

The client can query the "ideal" limit of the device (i.e., as if NO contracts have been established), the *current* configuration of it's connection (contract) or the current "best case" value for a parameter (taking into consideration all other contracts in effect at that instant). These are just different verbs in the protocol which map to different "configuration_t" structs in the server.

So, if a device has operating ranges of {[1,10], [5,50], [10,100]} queries for the *ideal* LOW and HIGH limits would yield "1" and "100" regardless of WHEN they are issued. If a client had previously (successfully) issued "SET LOW 7", then a query of the *current* LOW would be reported as "7". In the absence of any HIGH contractual obligations BY ANY CLIENTS, a query of the *best* LOW would report "1" (because the [1,10] and [5,50] ranges can satisfy the "LOW of not greater than 7". However, if some other client had requested a HIGH limit of 40, then the *best* LOW would be reported as "5" (because the [1,10] range would not be capable of handling this "HIGH of at least 40" and "my" LOW of 7 -- but, the [5,50] range

The client can RESET any or all of it's configuration parameters (i.e., for *its* contract). (It can also issue another SET for a parameter that has already been SET -- subject to the same constraints)

So, typically, a client would connect and then start querying the device (server) about the parameters of greatest interest to it. Typically, you are most interested in the range of values that can be reported. So, you query the HIGH and LOW limits (two queries) available. [actually, you query just *one* limit since SETting that limit could affect the choices available to you for the other limit... imagine a device supporting 3 ranges: [1,10], [5,50], [10,100] -- clearly, your choice of HIGH limit will determine the LOW limit possibilities]

Then, you SET the limits as per your requirements. If there is no intervening SET activity from other clients, these SETs will succeed.

The server now knows what it must do to satisfy your *range* of values. So, it can rule out certain operating configurations for the device based on those choices. Of the configurations that remain, it has a potentially narrowed set of options for the other parameters (accuracy, resolution, etc.).

The client then queries the *next* most significant (to it) parameter and makes a configuration choice accordingly.

In this way, it incrementally queries the server for the device's capabilities *and* informs it of its requirements.

A client can RESET any or all of the parameters in its contract. It can also close the connection. Or, the connection can be

If a client wants to guarantee a particular configuration remains available, it must hold the connection open for the duration (since a closed connection allows the server to revise how it configures the device based on *new* clients connecting to the service)

What you really want to be able to do is send a list of potential configurations/requirements where each is accompanied by a suitable predicate. So, you can, in effect, tell the server: "Give me this configuration. But, if you can't, then *this* would be my second choice -- unless you can't satisfy that ACCURACY requirement, in which case you can try this one, instead..."

Doing this in a comm protocol seems inappropriate. Instead, let the client make those decisions "in code" and just convey its prioritized choices, in order, *sequentially* to the server as each one is rejected.

Again, this works *great*. It is lightweight, cheap to implement (both in the protocol and the server), and easy to map your "requirements" onto a (previously unseen) device's "capabilities".

The problem I'm having is trying to forget about how I would do this if these "client connections" were just "competing *tasks*" operating on a uniprocessor. I.e., in that case, you would put a mutex (or a monitor) around the "configuration" and

But, in a distributed system, nothing is "quick". And, the clients are developed by a greater number of personalities (some of which might be less cooperative/skilled than others).

I believe that's inevitable if you support multiple clients and none of them are allowed to hog the system.

The alternative is that, once you've "made an offer" (i.e. returned information which implies that a particular operation will succeed), you have to keep that offer open for as long as the client takes.

The key word, there, is "hog".

We all inherently know you don't disable interrupts for long periods of time. And, you keep aware of how long you hold a shared resource. If we (i.e., the tasks we write) weren't "civil" towards each other, things wouldn't work -- or, would work poorly/suboptimally.

But, on a uniprocessor (et al.), we tend to *know* who all the players are at compile time. And, they have a shared stake in the outcome.

OTOH, with a dynamic, distributed system, these same assumptions don't necessarily follow. E.g., the whole point of this sort of "service" is to provide flexibility in how *unanticipated* clients interact with the system infrastructure. Unlike a "closed system", that interaction isn't know a priori -- so, the sorts of guarantees that you can make become more tenuous (including "that doesn't work")

This is an interesting way to look at the ^^^^^^^^^^ query result! I.e., if this was a shared object governed by a mutex, you wouldn't consider *examining* the object to be "an offer". Rather, it would be "an inspection/query".

I need to rethink things with this different conceptual model and see what other solutions present themselves...

(clearly not an option since the client's actions are unbounded)

How about implementing timeoutable locks with some reasonable countdown time size.. lets say 1 - 5s. So basically, when some one takes control it has to finish its configuration on a manageable time.... And all other requests are kept, and processed when the actual "negotiation" is over... That would impose that every slave should be automated (and not human driven). And that would possibly leads to a slow response to clients if they are all trying to configure the system all the same time. Thats would be a fair system, as this slow response would happen just when configuring the system, what i supose does not happen all the time. Your problem would be to chose the countdown time to allow evey client to configure it on a maneageble time.

--------------------------------------- Posted through

Imposing timing constraints on network protocols is A Bad Idea. I.e., the connection can *legitimately* stall for A Long Time through no fault of the client or server. So, an *initial* message from a client may be delayed -- meaning the client's notion of how long it has been since the message was "issued" is now incorrect. A server's reply may be delayed -- eating into the "time budget" for the client to issue followup requests. A followup request from a client may be delayed (beyond the valid time window -- despite the client *thinking* it had been very prompt in issuing the followup message!).

I.e., the network (and stack) would have to have contractual agreements with clients and servers if you wanted to rely on time to any extent (if you still have to handle failures brought about by "time confusion", what have you gained?)

No, I think I need to consider ways to request groups of parameters/constraints in single messages (get the atomicity

Why? A lot of protocols have strict timing constraints. Almost all master-slave protocols have very strict timing constraints.

If you are the designer of the system/protocol, why can't you specify there will be no long stalls and design the system accordingly?

Your problem of many nodes asking for a service on power up can be perfectly solved by random time-outs and random delay times within a relatively short window.

Meindert