Indirect Communication

Direct vs Indirect Communication

Everything in the earlier Parts was direct communication. With sockets (Part III) a process sends bytes to one particular address and port; with request-reply, RPC and RMI (Part VI) a client invokes one particular server. In every case the sender aims at a specific receiver, and that receiver has to be present, running and reachable at the moment the message arrives.

That rigidity causes problems. A client that is bound to one server cannot easily switch to an equivalent server. If that server fails, the client sees the failure directly and has to handle it itself. And if the people you want to tell something are an unknown, changing crowd (everyone currently watching a share price, say), naming each receiver is impossible. Indirect communication solves this by putting something in the middle.

The intermediary takes a different form in each paradigm, and the five forms are the five topics of this Part. A group delivers a message to all its members (§7.4–7.6). A channel or topic delivers an event to everyone who subscribed (publish-subscribe, §7.7–7.8). A queue holds a message until one consumer takes it (§7.9). Shared memory lets processes read and write common data by address (§7.10). A tuple space lets processes leave data for others to find by its content (§7.11).

Check yourselfWhich of these is direct communication?

1. A Java RMI client invoking lookup("Shapes") and then calling a method on the stub
2. A process posting a message on a JMS queue
3. A process joining a JGroups channel and sending to it
4. A process writing a tuple into a JavaSpace

A. Once the client has the remote reference, every invocation goes to that one server object, which must be running; the RMI registry only helps the client find it. The other three all go through an intermediary (a queue, a group, a tuple space), and the sender never names a receiver.

Space and Time Uncoupling exam

"No direct coupling" can mean two quite different things, and the exam expects you to separate them. A sender can be freed from knowing who receives (space), and it can be freed from needing the receiver to be alive at the same moment (time). An intermediary may give one, both or neither.

The four combinations

Because the two dimensions are independent, crossing them gives a 2×2 grid. Every paradigm in the subject sits in one cell, and a common exam question asks for an example of each.

Three cells are easy. Sockets, RPC and RMI are coupled both ways. Message queues, tuple spaces, persistent DSM and durable pub-sub are uncoupled both ways. IP multicast (sending one IP packet to a multicast address that any host may join, from Part III) is space-uncoupled, since the sender only knows the group address, but time-coupled, since a host that has not joined when the packet passes simply never sees it. The same holds for group communication and pub-sub when they keep no history.

The space-coupled but time-uncoupled cell is the subtle one. CDK leaves it as an exercise (Ex 6.3/6.4), and the usual answers are email sent to a named mailbox and queued RPC, as in the Rover toolkit for mobile clients. In both, the sender names exactly one recipient, but the recipient does not have to be running: the mail server, or Rover's queue, keeps the message until it next connects.

Time uncoupling is not asynchronous communication exam

These two ideas sound alike and are easy to mix up, but they are different properties. Asynchronous communication, also called synchronization uncoupling, means that send does not block: the sender carries on immediately instead of waiting for the message to be received. Nothing in that says the receiver may be absent. Time uncoupling means the receiver need not exist at all when the message is sent.

A UDP datagram shows the difference. DatagramSocket.send returns at once, so UDP is asynchronous; but if the destination process has crashed, the datagram arrives at a port nobody owns and is lost. A producer that puts a message on a persistent queue and exits is different: a consumer started tomorrow will still get the message.

The two properties are orthogonal: either can occur without the other. UDP is asynchronous but time-coupled. In the other direction, a blocking receive on a queue is synchronous communication over a time-uncoupled indirect service, and so is JGroups' MessageDispatcher (§7.6), where the caller blocks waiting for replies from the group.

Check yourselfSelf-test Q1: define indirect communication, and explain space and time uncoupling with an example of each combination.

Indirect communication is communication through an intermediary, with no direct coupling between the sender and the receiver(s). Space uncoupling means the sender does not know who the receivers are. Time uncoupling means the sender and receivers have independent lifetimes, so they need not exist at the same time.

• Coupled in space and time: RMI, sockets.
• Space-uncoupled, time-coupled: IP multicast.
• Space-coupled, time-uncoupled: email, queued RPC.
• Uncoupled in both: message queues, tuple spaces.

In every case, time uncoupling needs persistence.

Check yourselfSelf-test Q2: is asynchronous communication time-uncoupled?

No. Asynchronous communication means only that the sender does not block; the receiver must still exist, so a UDP datagram sent to a dead process is lost. Time uncoupling means the receiver may not exist yet, which needs persistence. The two are independent: a blocking receive on a queue, for example, is synchronous yet time-uncoupled.

Check yourselfA colleague says: "Our chat app uses a pub-sub broker, so offline users will get their messages when they reconnect." What must be true of the broker for this to hold?

The broker must provide time uncoupling, which pub-sub gives only with retained events and durable subscriptions: it has to store events for a subscriber that is not connected. A plain broker gives space uncoupling only; an event published while a user is offline is delivered to nobody and lost.

When Indirection Helps and Hurts

An extra party in every conversation is not free. Before choosing an indirect paradigm you should be able to say what it buys and what it costs, and a 5-mark "advantages and disadvantages" question asks exactly that.

When it helps

When it hurts

Indirection hurts in four ways. First, there is a performance overhead from the extra level: every message makes an extra hop and may be stored. Jim Gray's remark sums it up: any performance problem can be solved by removing a level of indirection. Second, the system is harder to manage: without direct coupling it is hard to tell who received what, and debugging is harder too. Third, it is hard to reason about end-to-end properties such as real-time behaviour, security and quality of service (QoS, guarantees about latency and throughput), because the intermediary sits between the two ends. Fourth, a centralised intermediary becomes a bottleneck and a single point of failure.

Check yourselfSelf-test Q3: give the advantages and disadvantages of indirect communication.

Advantages. Indirection handles volatility, allows dissemination to unknown receivers, and lets participants be replaced or replicated. It also helps with fault tolerance, integration and load balancing.

Disadvantages. There is a performance overhead from the extra level, and systems are harder to manage. End-to-end properties such as real-time behaviour and security are hard to guarantee, and a centralised intermediary is a bottleneck and single point of failure.

Check yourselfA high-frequency trading system needs a guaranteed delivery time of under one millisecond between two known processes. Is indirect communication a good fit?

Probably not. The two processes are known and fixed, so space uncoupling buys little, while the intermediary adds a hop (performance overhead) and makes an end-to-end real-time guarantee hard to reason about. This is the situation Jim Gray's remark is about: removing the level of indirection is the performance fix.

Group Communication exam

Suppose three replicas of a bank server must all apply every update, or a stock feed must reach every dealer's screen. Sending to each one separately is clumsy and, as we will see, unsafe. Group communication lets a sender address the whole set with one name and one operation.

Groups are used in four broad ways: for reliable dissemination of information, such as financial data; for collaborative applications that need every user to share a common view, such as multiuser games; for fault tolerance, through the consistent update of replicas and highly available servers; and for monitoring and management, for example load balancing.

The programming model

Processes join and leave a group, and send to it with a single multicast operation, written aGroup.send(aMessage). Mind the terminology: a multicast goes to the members of a group, a broadcast goes to all processes in the system, and a unicast goes to exactly one process.

The slides list the group API as: create and delete a group; list and search groups; join and leave; list the members; and multicast.

Why one multicast beats N unicasts exam

A sender could reach a group of N members by looping over them and unicasting a copy to each. A single multicast operation is better for two separate reasons, and a full answer names both.

1. Efficiency. A multicast puts at most one copy on each link, because it travels over a distribution tree (the routers copy the packet only where paths split). It can also use hardware multicast, such as Ethernet multicast, and it gives lower total latency. CDK's example: a host in London sends to two hosts on an Ethernet in Palo Alto.

2. Group-wide guarantees. With N separate sends there is nothing to make the group behave as a unit. If the sender crashes midway through its loop, some members have the message and others never will. And when two senders send at once, the order in which their messages reach different members is undefined. A multicast operation is a single action that the middleware can make reliable and ordered.

Process groups vs object groups exam

Groups come in two kinds, which differ in what the members are and how much the middleware does for you. In short, process groups are at the level of sockets, and object groups are at the level of RMI.

In an object group the member objects process the same invocation concurrently, and each one replies. So what does the caller get back? Electra, built on CORBA, offers two answers: its "transparent" mode returns the first reply, so the call looks like an ordinary single-object call, and its "non-transparent" mode returns all the replies, so the caller can, for example, compare them.

Other distinctions exam

Groups can be classified in three further ways. The first is who may send to the group.

The second distinction is whether groups may overlap. In overlapping groups an entity can belong to several groups at once. That is the realistic case, but it complicates ordering, because a process in two groups receives two streams of messages that must somehow be interleaved. In non-overlapping groups each entity belongs to at most one group.

The third distinction is the system model. Group algorithms must handle both synchronous and asynchronous systems (Part II: in a synchronous system message delays and processing times have known bounds; in an asynchronous one they do not). The choice changes the algorithms significantly, for example in how failures can be detected.

Check yourselfSelf-test Q11: compare closed and open groups, and process and object groups.

In a closed group only members send, as with cooperating servers; in an open group outsiders may send, as with event delivery.

Process groups deliver byte arrays to processes, with no marshalling or dispatching, as in JGroups. In object groups, a proxy multicasts invocations, which are marshalled and dispatched to the replica objects, so replication is transparent, as in Electra.

Check yourselfA message sent to every process in the system is a…

1. multicast
2. broadcast
3. unicast
4. anycast

B, broadcast. A multicast goes to the members of a group, and a unicast goes to one process. (Anycast is not a term this subject uses.)

Check yourselfA replicated object group returns the first reply to the caller. Which mode is this in Electra, and why is it called that?

The transparent mode. Returning one reply makes the replicated call look exactly like a call on a single object, so replication is hidden (transparent) from the client. The non-transparent mode returns all the replies, which exposes the replication.

Reliability and Ordering in Groups exam

The previous section showed what goes wrong with N unicasts: some members miss a message, or members see messages in different orders. Group communication promises to prevent both, and this section says precisely what it promises. Reliability (does every member get the message?) and ordering (in what order?) are specified separately.

One word needs care first. A message arrives (is received) at a member's group-communication layer when the network hands it over; it is delivered when that layer passes it up to the application. Between the two, the layer may keep the message in a hold-back queue until it is safe to deliver. Every guarantee below is about delivery.

Reliability: integrity, validity, agreement

Reliable group communication is defined by three properties, which you should be able to state precisely.

Check yourselfSelf-test Q4: why use one multicast operation rather than separate sends? Define the reliability properties of reliable multicast.

One multicast is more efficient: it sends one copy per link over a distribution tree, it can use hardware multicast, and it has lower latency. It also allows group-wide guarantees. Separate sends give no all-or-nothing delivery if the sender crashes partway through, and no consistent ordering.

Reliable multicast has three properties. Integrity means a message is delivered correctly and at most once. Validity means every message sent is eventually delivered. Agreement means that a message delivered to one member is delivered to all.

Ordering: FIFO, causal and total

Reliability says nothing about order: every member could get every message, but in different orders. So ordering is specified separately. There are three standard orderings, each with its own implementation technique.

FIFO ordering

FIFO ("first in, first out") ordering only cares about messages from the same sender: they must be delivered in the order that sender sent them. The implementation numbers each sender's messages 1, 2, 3… (a per-sender sequence number). Each member remembers, for every sender, which number it expects next, and a message that arrives early is held back until the gap is filled.

Causal ordering

Causal ordering is about cause and effect between messages, even from different senders. Message m1 happened-before m2 if the same process sent m1 before m2, or if the sender of m2 had already delivered m1 when it sent m2 (so m2 might be a response to m1), or through a chain of such steps. Causal ordering says: if m1 happened-before m2, every member delivers m1 before m2. Two messages with no such link are concurrent, and causal ordering lets members deliver them in either order.

The implementation attaches a vector timestamp to each message: a list of counters, one per member, recording how many messages from each member the sender had delivered (or sent) at that point. A receiver holds a message back until it has delivered every message the timestamp says came causally before it. CDK's bulletin-board example (Ex 6.6) shows why this matters.

Total ordering

Total ordering asks for something different: every member delivers all messages in the same order, whatever that order is. The slides' implementation uses a sequencer, a process that gives each message a global sequence number; members then deliver in sequence-number order, holding back any message whose predecessor has not yet arrived. Here two senders, P and Q, send messages to the group, and we watch two members B and C.

How the orderings relate

There is a pitfall in how these relate. Causal ordering implies FIFO ordering: two messages from the same sender are causally related (the sender sent one before the other), so causal order already keeps them in order. But total ordering implies neither, since it promises only "the same order everywhere", and that same order could put a sender's second message first, or an answer before its question. That is why hybrids exist: FIFO-total and causal-total ordering.

Causal vs total: the distinguishing example

Continue the bulletin board. Now A posts m3 and C posts m4 at the same moment, neither having seen the other's message, so m3 and m4 are concurrent. Causal ordering has nothing to say about concurrent messages, so it allows different members to deliver them in different orders. Total ordering does not.

Total ordering is what you need when replicas apply updates. If "deposit $100" and "add 10% interest" reach two replicas of an account in different orders, the replicas end up with different balances, and from then on they are no longer replicas of anything.

Check yourselfSelf-test Q5: explain FIFO, causal and total ordering with their implementations, and give an example that distinguishes causal from total.

FIFO ordering preserves each sender's order and is implemented with per-sender sequence numbers. Causal ordering respects happened-before, is implemented with vector timestamps, and implies FIFO. Total ordering gives the same order everywhere, is implemented with a sequencer, and does not imply causal ordering.

To distinguish causal from total: under causal ordering a reply must follow its question, but two concurrent messages m3 and m4 may arrive in different orders at different members. Total ordering does not allow that.

Check yourselfWhich statement is true?

1. Total ordering implies causal ordering.
2. Causal ordering implies FIFO ordering.
3. FIFO ordering implies total ordering.
4. Total ordering implies FIFO ordering.

B. Messages from one sender are causally related, so causal order preserves them. Total ordering implies neither FIFO nor causal (A and D are the classic traps), and FIFO says nothing about messages from different senders, so it cannot give one global order (C).

Check yourselfA multiplayer game multicasts each player's moves. A player's own moves must never appear out of order, but moves by different players may be shown in any order. What is the weakest ordering that suffices, and how is it implemented?

FIFO ordering: it only constrains messages from the same sender. Each player numbers its messages with a per-sender sequence number, and every receiver holds back a message until it has delivered that player's earlier numbers.

Check yourselfIn the bulletin board, B delivers m1 "Question" and then posts m2 "Answer". A member delivers m2 before m1. Which ordering guarantee is violated, and which is not necessarily violated?

Causal ordering is violated, because m1 happened-before m2 (B had delivered m1 when it sent m2). FIFO is not violated: m1 and m2 come from different senders, and FIFO only orders each sender's own messages. Total ordering is violated only if some other member delivered them in the other order.

Group Membership and JGroups

A sender addresses "the group", but the network can only deliver to actual processes. Something has to know, at every moment, which processes are in the group, notice when one crashes, and turn the group's name into that list. That is the group membership service. This section describes it and then looks at JGroups, the Java toolkit that packages all of the above.

Group membership management exam

In the picture, a sender addresses the group only by its identifier g. The membership service tracks joins, leaves and failures, and address expansion turns the identifier into the current set of members.

A group membership service has four tasks.

1. An interface for membership changes, so that groups can be created and destroyed, and processes added and withdrawn.
2. Failure detection: it monitors members for crashes and unreachability, marks them Suspected or Unsuspected, and excludes suspected members. (In an asynchronous system a slow member and a crashed one look the same, which is why the service can only suspect.)
3. Notifying members of joins and exclusions.
4. Group address expansion: expanding the group identifier into the current members. It coordinates delivery with membership changes, so that each message's set of recipients is decided consistently.

Check yourselfSelf-test Q6: list the tasks of a group membership service. Why is IP multicast weak?

A membership service provides an interface for membership changes; detects failures, suspecting and excluding members; notifies members of changes; and performs group address expansion, coordinated with those changes.

IP multicast is weak because it offers only join and leave and address expansion. Members have no knowledge of the membership, and delivery is not coordinated with membership changes.

Case study: JGroups

JGroups is a Java toolkit for reliable group communication, descended from the research systems ISIS, Horus and Ensemble. It uses process groups: members are processes that exchange messages. Its design has three parts: channels, building blocks and a protocol stack.

A channel is a socket-level handle on one group. Calling connect("name") joins the group, creating it if it is new; disconnect leaves it, and close closes the channel. Messages go out with send and come in with receive. getView returns the current members, and getState returns the group's history so that a newcomer can catch up; this gives an optional form of time uncoupling. Despite the name, a JGroups channel has nothing to do with "channel-based" pub-sub (§7.7).

There are three building blocks on top of channels. MessageDispatcher.castMessage sends a message and blocks for n replies, a majority, or all of them (which is why it counts as synchronous communication over an indirect service, §7.2). RpcDispatcher invokes a method on all members. NotificationBus is a distributed event bus, used for example to keep a replicated cache consistent.

The third part is the protocol stack, made of composable layers, each with up(Event) and down(Event) methods. All members share the same stack. CDK's example stack, from top to bottom, is CAUSAL (causal order), GMS (membership views), MERGE (re-merging after a partition), FRAG (fragmentation, 8,192 bytes) and UDP (IP multicast and UDP unicast, or TCP for WANs).

The fire alarm in JGroups (CDK Fig 6.5)

import org.jgroups.JChannel;
import org.jgroups.Message;

public class FireAlarmJG {                              // CDK Fig 6.5
    public void raise() {
        try {
            JChannel channel = new JChannel();          // default protocol stack
            channel.connect("AlarmChannel");            // join group
            channel.send(new Message(null, null, "Fire!")); // dest null = all members
        } catch (Exception e) { }
    }
}
// Receiver: same connect, then  Message m = (Message) channel.receive(0);  // block

Line by line: new JChannel() creates a channel with the default protocol stack. connect("AlarmChannel") joins the group of that name, so the alarm raiser becomes a member. new Message(null, null, "Fire!") builds a message whose first argument, the destination, is null, meaning all members; the second is the source (filled in by JGroups) and the third the payload. send multicasts it. A receiver does the same connect and then calls channel.receive(0), which blocks (0 means no timeout) until a message arrives. Newer versions of JGroups use a receive callback instead.

Check yourselfIn CDK's JGroups stack, which layer re-merges a group that was split by a network partition, and which provides membership views?

1. MERGE; GMS
2. GMS; MERGE
3. CAUSAL; FRAG
4. FRAG; UDP

A. MERGE re-merges after a partition; GMS (group membership service) maintains views. CAUSAL gives causal order, FRAG fragments messages at 8,192 bytes, and UDP is the transport.

Check yourselfWhich JGroups feature gives an optional form of time uncoupling, and how?

getState. It returns the group's history, so a process that joins late can catch up on what it missed. Without it, JGroups is time-coupled, as the fire alarm shows.

Publish-Subscribe: Model and Subscriptions exam

Groups suit a fixed, known set of members who all need everything. Many applications instead have a large, changing crowd of receivers, each interested in a different slice of a stream of happenings: this dealer wants IBM prices, that one wants anything over $100. Publish-subscribe lets each receiver describe what it wants and leaves the matching to the middleware.

Applications include financial systems, live feeds such as news and RSS, cooperative working, ubiquitous computing (with events from sensors or about location), and monitoring. The standard illustration is the dealing room: an information provider process for each external source publishes every price update as an event, and dealer processes subscribe to the stocks they care about and display the notifications they receive.

The programming model exam

The interface is small:

• publish(e) publishes event e.
• subscribe(f) registers interest through a filter f (the pattern), and unsubscribe(f) cancels it.
• notify(e) is how the system delivers e to the matching subscribers.
• advertise(f) and unadvertise(f) are optional. They let publishers declare, or revoke, the kinds of events they will publish in future.

Subscription models exam

Subscription models differ in how a subscriber describes the events it wants, which is the same as asking what part of an event the filter may look at. The slides use a single event to illustrate them: topic weather/melbourne, type TemperatureReading, location = "Melbourne", temperature = 31. The figure shows how a subscriber would select that event under each model.

A few terms from the table. A hierarchical topic is written like a path, so weather/melbourne sits under weather alongside, say, weather/sydney. A predicate is a true/false test on an event's attributes. Type-based subscription works on the event's programming-language type, so a subscription to TemperatureReading also matches events of any subclass, and the compiler can check the subscription.

There are further models as well. With objects of interest, as in Jini events, a subscriber watches the state of one particular object; because this uses a direct connection to that object, it loses the uncoupling. Context-based subscriptions select on context, for example location. Concept-based subscriptions filter on the semantics (meaning) of events, which helps with heterogeneity when publishers use different words for the same thing. Finally, complex event processing looks for patterns across many events, which may be logical, temporal or spatial; an example is "river level up 20% at three sites and flood risk predicted".

Characteristics

Four characteristics shape how pub-sub systems behave.

Heterogeneity. Components that were not designed to interoperate can still cooperate, because all they have to do is publish event types or handle notifications.

Asynchronicity. Publishers never synchronise with subscribers: a publish call does not wait for anyone to receive the event.

Delivery guarantees are chosen per application. With at-most-once delivery, a lost event is not redelivered; that is fine for a game's latest position, since the next update will arrive anyway. At-least-once delivery retries, so duplicates are possible. The dealing room needs reliable delivery for the sake of fairness, so that all the dealers of a stock see the same data. Guarantees can also be mixed: Mushroom is a hybrid.

Applications with real-time needs, such as a power station or a patient monitor, need bounded low latency, which is achievable in synchronous systems.

Coupling. The broker gives space uncoupling, but time uncoupling comes only with retained events and durable subscriptions (the broker keeps events for subscribers that are not currently connected).

Check yourselfSelf-test Q7: describe the pub-sub programming model and the subscription models.

The programming model consists of publish, subscribe, unsubscribe and notify, plus advertise and unadvertise. The subscription models are channel-based, topic-based (which can be hierarchical), content-based (predicates over attributes) and type-based (matching types and their subtypes). There are also concept-based and context-based models, and complex event processing.

Check yourselfA subscriber wants "every reading whose temperature is above 40, from any city". Which subscription model can express this directly?

1. Channel-based
2. Topic-based
3. Content-based
4. Type-based

C, content-based, with the predicate temperature > 40. Topic- and type-based filters cannot look at attribute values, and a channel delivers everything on it. With those you would have to receive every reading and filter in the application.

Check yourselfWhy do "objects of interest" subscriptions, as in Jini events, lose the uncoupling that pub-sub normally gives?

Because the subscriber watches one particular object through a direct connection to it. It must know that object's identity (no space uncoupling) and the object must be there (no time uncoupling), which is direct communication in disguise.

Check yourselfA multiplayer game publishes each player's position 30 times a second. Which delivery guarantee fits, and why is the dealing room different?

At-most-once fits the game: if one position update is lost, the next one arrives a moment later and supersedes it, so retrying would only waste bandwidth. The dealing room needs reliable delivery for fairness: every dealer of a stock must see the same prices.

Implementing Publish-Subscribe exam

The event service is easy to describe and hard to build at scale. Every event must be matched against possibly millions of subscriptions and carried to the right subscribers without flooding the network. This section covers where the service runs and how events find their way.

Centralised, distributed or peer-to-peer

There are three broad ways to build the event service, and they trade simplicity against scale and resilience.

• A centralised broker stores all the subscriptions and matches every event against them. It is simple, but it is a single point of failure and a bottleneck.
• A distributed broker network uses cooperating brokers. It survives failures and works at Internet scale, but the subscription and routing state must be distributed among the brokers.
• In a peer-to-peer design there is no distinction between publishers, subscribers and brokers, and all nodes take part in routing. It is fully decentralised, but complex.

The architecture in layers (CDK Fig 6.10)

CDK splits a distributed implementation into four layers. Each layer offers several interchangeable techniques.

Routing: why content-based is hard

Channel and topic schemes map simply onto groups: one group per topic, and publishing is a multicast to that group. Content-based subscription cannot be mapped this way, since every subscription is a different predicate (there could be one "group" per subscriber), so it needs content-based routing (CBR). There are five approaches:

• Flooding sends every event to all nodes and does the matching at the subscribers, or alternatively floods subscriptions to the publishers. It is simple but wasteful.
• Filtering forwards events only along paths that lead to matching subscribers. To do this, brokers propagate subscriptions towards the publishers, and each broker keeps a neighbours list, a subscription list (its local subscribers) and a routing table that maps each neighbour to the subscriptions reachable via it.
• Advertisements are propagated towards subscribers, so that subscriptions need not be flooded everywhere: a subscription only travels towards brokers whose publishers advertised matching events.
• Rendezvous routing partitions the event space among the nodes (see below). It is often built on a DHT.
• Informed gossip is a probabilistic exchange with neighbours, guided by content. It works well under churn (nodes constantly joining and leaving).

Filtering-based routing exam

The algorithm each broker runs is short. "x" is whoever the message came from, and match(e, list) returns the entries whose subscriptions e satisfies.

upon receive publish(e) from x:   notify(e) to match(e, subscriptions)
                                  publish(e) to match(e, routing) - x
upon receive subscribe(s) from x: if x is a client then add x to subscriptions
                                  else add (x, s) to routing
                                  subscribe(s) to neighbours - x

Read it as two rules. When an event arrives, notify every local subscriber it matches, and forward it to every neighbour whose routing-table entry it matches, except the one it came from. When a subscription arrives, record it (as a local subscriber if it came from a client, or as a routing entry "neighbour x leads to s" if it came from another broker), then pass it on to all other neighbours. The stepper traces CDK's example.

Rendezvous routing

Rendezvous routing takes a different approach: instead of spreading subscriptions along paths, it gives each part of the event space a meeting point. Two functions decide where things go. SN(s) names the node or nodes that store subscription s, and EN(e) names the node or nodes that match event e. For this to work, an event and every subscription it matches must meet somewhere, so the scheme requires EN(e) ∩ SN(s) ≠ ∅ whenever e matches s. This is the mapping intersection rule.

Step by step (CDK Fig 6.12): when node i receives subscribe(s), it computes SN(s); if i is in that set it stores s, otherwise it forwards s to those nodes. When node i receives publish(e), it computes EN(e); if i is in that set it matches e against its stored subscriptions and notifies any matches, and it forwards e to the rest of EN(e). Having SN and EN return several nodes adds reliability, since a match can still happen if one node fails.

Example systems

The example systems show different points in this design space.

The slides add modern systems: Kafka, a durable log with replay and per-partition ordering; RabbitMQ and IBM MQ; MQTT, which is lightweight, topic-based, aimed at the Internet of Things, and offers QoS levels; and SNS + SQS, where a topic fans out into durable queues.

Check yourselfSelf-test Q8: compare centralised and distributed pub-sub, and explain filtering-based routing.

A centralised broker is simple, but it is a bottleneck and a single point of failure. A broker network or a peer-to-peer design is scalable and resilient, but complex.

In filtering-based routing, subscriptions propagate through the brokers, and routing tables record which neighbour leads to which subscriptions. Events are then forwarded only along matching paths, which means less traffic than flooding. Rendezvous routing over a DHT, and advertisements, are alternatives.

Check yourselfWhy can topic-based pub-sub be implemented with one group per topic, while content-based pub-sub cannot?

A topic is a fixed name shared by many subscribers, so "everyone subscribed to topic T" is a natural group and publishing is a multicast to it. In content-based pub-sub every subscription is its own predicate (price > 100, price > 120 AND stock = "IBM"…), so there is no small set of groups to map onto; the system needs content-based routing such as filtering or rendezvous.

Check yourselfIn rendezvous routing, what does the mapping intersection rule require, and what goes wrong if it is broken?

It requires EN(e) ∩ SN(s) ≠ ∅ whenever e matches s: at least one node that stores the subscription must also receive the event. If it is broken, the event and the matching subscription are sent to disjoint sets of nodes, no node ever compares them, and the subscriber silently misses the event.

Message Queues exam

Pub-sub hands every event to every interested subscriber. Many business tasks need the opposite: an order must be processed by exactly one warehouse system, reliably, even if that system is down for the night. Message queues provide this point-to-point, store-and-forward service.

The programming model exam

Producers have one operation, and consumers have three ways of getting messages, plus an acknowledgement:

• send puts a message on a named queue, and may block if the queue is full.
• A blocking receive waits until a message is available.
• A non-blocking receive (poll) returns a message, or "none", immediately.
• Notify issues an event when a message is available, so the consumer need not wait or keep asking.
• acknowledge, which the slides add, confirms that a message has been processed so that it can be discarded.

As the figure shows, many producers and consumers can share a queue, but each message goes to only one consumer. These competing consumers give load balancing. The queue is FIFO, usually with priorities (a higher-priority message jumps ahead), and consumers may also select messages using predicates over their metadata.

A message consists of a destination, metadata such as priority and delivery mode, and an opaque body: the queue never looks inside it. The body is serialized and can be as large as about 100 MB. In Oracle AQ, queues are database tables and messages are rows, so they can be queried in SQL.

One message, start to finish

The stepper follows one message through a queue manager (the server process that hosts the queue). Watch for time uncoupling: the consumer is offline when the order is sent, and the producer exits before the consumer collects it, hours later.

Properties exam

Message queues have four main properties.

• Persistence. Messages are stored until they are consumed, and are committed to disk. This gives time uncoupling, along with validity and integrity (each message is delivered once), but there is no timing guarantee: a message may sit in the queue for hours.
• Transactions. Send and receive can be placed inside all-or-nothing transactions, for example "take order, update DB, send shipping request".
• Message transformation. A message broker can convert between formats, for instance byte order, or between SOAP and IIOP (two different message formats used by web services and CORBA). This supports heterogeneity and EAI.
• Security. WebSphere MQ, for example, provides SSL, authentication and access control.

Compared with message passing exam

Ordinary message passing (sockets) also has queues, but they are implicit: buffers inside the sender's and receiver's operating systems. Message queues are explicit third-party entities with their own names and storage, and that is what gives them space and time uncoupling.

WebSphere MQ (IBM MQ)

A single central queue manager is simple but becomes a bottleneck, so WebSphere MQ distributes its queue managers. The design has four elements.

• Queue managers host the queues, and applications talk to them through the MQI (Message Queue Interface: MQCONN, MQDISC, MQPUT, MQGET, i.e. connect, disconnect, put a message, get a message).
• A client channel links an application to a queue manager. The client library acts as a proxy, and MQI calls go to the queue manager by RPC. The slides call this the "MQI channel".
• A message channel is a unidirectional, asynchronous link between queue managers, run by message channel agents. Together with routing tables, message channels allow arbitrary topologies.
• In a hub-and-spoke topology, clients connect over a LAN to a local spoke, and the spokes relay messages to the hub, which hosts the services. A client blocks only until its message reaches the spoke, and delivery across the WAN is then asynchronous but reliable. The hub is a bottleneck, which queue manager clusters address.

Java Messaging Service (JMS)

JMS is a specification (an API standard, not a product), implemented by ActiveMQ, OpenMQ and JBoss, and also over WebSphere MQ. Its contribution is that it unifies pub-sub and message queues through two kinds of destination. A Topic is used through a TopicPublisher and a TopicSubscriber, and every subscriber gets a copy of each message. A Queue is used through a QueueSender and a QueueReceiver, and each message goes to one receiver.

A program reaches a destination through a chain of objects. It looks up a connection factory via JNDI (the Java Naming and Directory Interface, a name service) and uses it to create a connection, which is either for topics or for queues, not a mix of the two. From the connection it creates a session, which may be transactional, and the session creates the producers, consumers and messages.

A JMS message has three parts: a header (destination, priority, expiry, ID, timestamp), properties that carry user metadata, and an opaque body. Consumers may filter with a message selector, which is a subset of SQL evaluated over the header and properties but not the body. They receive messages either with a blocking receive() or through a MessageListener.onMessage() callback.

The fire-alarm consumer below uses a selector so that it only waits for alarms at one location.

import javax.jms.*;
import javax.naming.*;

public class FireAlarmConsumerJMS {          // after CDK Fig 6.18, plus selector (Ex 6.14)
    public String await(String loc) {
        try {
            Context ctx = new InitialContext();                       // JNDI
            TopicConnectionFactory f =
                (TopicConnectionFactory) ctx.lookup("TopicConnectionFactory");
            Topic topic = (Topic) ctx.lookup("Alarms");
            TopicConnection conn = f.createTopicConnection();
            TopicSession s = conn.createTopicSession(false, Session.AUTO_ACKNOWLEDGE);
            TopicSubscriber sub = s.createSubscriber(topic, "location = '" + loc + "'", false);
            conn.start();                                             // begin delivery
            return ((TextMessage) sub.receive()).getText();           // blocking receive
        } catch (Exception e) { return null; }
    }
}
// Publisher: s.createPublisher(topic); msg = s.createTextMessage("Fire!");
//            msg.setStringProperty("location", "B7"); pub.publish(msg);

Line by line, it walks the chain from the figure:

1. new InitialContext() opens the JNDI name service.
2. ctx.lookup("TopicConnectionFactory") fetches the factory, and ctx.lookup("Alarms") fetches the destination, a Topic named Alarms.
3. f.createTopicConnection() creates a connection for topics only.
4. createTopicSession(false, Session.AUTO_ACKNOWLEDGE) creates a session; false means not transactional, and AUTO_ACKNOWLEDGE means messages are acknowledged automatically when received.
5. createSubscriber(topic, "location = '" + loc + "'", false) creates a subscriber with a message selector: for loc = "B7" the selector is location = 'B7', so only alarms whose location property is B7 are delivered. (The final false is JMS's noLocal flag: it does not suppress messages published on this same connection.)
6. conn.start() begins delivery; nothing arrives before it.
7. sub.receive() is a blocking receive; the result is cast to TextMessage and its text ("Fire!") returned.

The publisher, in the comment, creates a publisher on the same topic, makes a text message "Fire!", sets the property location to "B7" (so selectors can see it) and publishes it.

Check yourselfSelf-test Q9: describe the message-queue model and its reliability, and compare it with pub-sub.

A message queue offers send, blocking receive, poll and notify. Because the queue is persistent, it provides validity and integrity, though no timing guarantee; it also supports transactions and message transformation.

A queue is point-to-point, with one consumer per message. Pub-sub, by contrast, is one-to-many, filtered, and often non-persistent. JMS offers both, through its Queue and Topic destinations.

Check yourselfA consumer wants to check the queue and carry on with other work if nothing is there. Which operation does it use?

1. Blocking receive
2. Poll (non-blocking receive)
3. Notify
4. Acknowledge

B. Poll returns a message or "none" immediately. Blocking receive would wait; notify would have the queue raise an event later (also workable, but the question asks to check now); acknowledge confirms processing of a message already received.

Check yourselfA JMS subscriber uses the selector body LIKE '%Fire%' to catch fire alarms. Why will this not work, and what should the publisher do instead?

Message selectors are evaluated over the header and properties only, not the body, which is opaque to JMS. The publisher should put the information in a property, for example msg.setStringProperty("type", "fire"), and the subscriber should select on type = 'fire'.

Check yourselfThree image-resizing workers share the work of a photo site. Should uploads be sent to a JMS Topic or a JMS Queue?

A Queue. Each photo must be resized once, by whichever worker is free: that is competing consumers on a point-to-point queue, giving load balancing. A Topic would give every worker a copy, so each photo would be resized three times.

Distributed Shared Memory exam

The last two paradigms are state-based abstractions: instead of sending messages, processes share state. They differ in how that state is accessed. DSM shares bytes, which are accessed by address, while tuple spaces (§7.11) hold semi-structured data, which is accessed associatively, that is, by content.

Why would anyone want shared memory across machines? Because programmers already know how to write parallel programs where threads share variables (Part IV), and rewriting them with explicit messages is laborious. DSM keeps the shared-variable style even when the threads run on different computers.

The shared memory is a logical address space, not a central memory. The data is spread across the computers and replicated (cached) among them, and the runtime exchanges messages to locate data and keep the copies consistent. So underneath, DSM is still message passing; the programmer just does not see it.

DSM is meant for parallel applications that share data directly. It is unsuitable for client-server systems, where resources are abstract data accessed by request, for reasons of modularity and protection: a server does not want clients poking at its memory. Persistent DSM outlives the processes that use it, which gives time uncoupling. Apollo Domain is an example: there, hosts map shared files into their address spaces.

DSM vs message passing exam

DSM is easiest to understand by contrast with message passing, and a "compare" question expects several of these rows.

On efficiency, DSM can be comparable to message passing for some programs on about 10 nodes, but this depends on the sharing pattern.

Check yourselfSelf-test Q10: compare DSM with message passing.

DSM shares data directly with no marshalling, uses familiar locks and semaphores, and can be persistent, so lifetimes need not overlap. On the other hand, it gives no protection between processes, makes heterogeneity hard, and hides the cost of communication.

Message passing uses marshalling, which handles heterogeneity; it keeps address spaces private; and its costs are explicit. However, lifetimes must overlap. For some parallel programs on small clusters the two have comparable performance, but this depends on the sharing pattern.

Implementing DSM middleware

This material (CDK 4th ed. chapter 18, referenced from CDK §6.5.1) is the background for the 2016 exam question on DSM middleware, worked at the end of this section.

Consistency model. A consistency model says which values a read may return when there are concurrent writes. The usual target is sequential consistency (all processes see all memory operations in one single order consistent with each process's own program order), because strict (atomic) consistency, where every read returns the most recent write in real time, is too expensive. Weaker models such as release consistency cut traffic by propagating changes only when a lock is released.

Write-invalidate is the multiple-readers/single-writer protocol: many processes may hold read-only copies of a page, or one process may hold a writable copy. The trick is the virtual-memory protection bits. A page held read-only is mapped read-only, so a write to it causes a page fault (a trap to the operating system), which the DSM runtime handles.

• On a read fault, the process requests the page from its owner and maps it read-only.
• On a write fault, it invalidates every other copy, collects the acknowledgements, takes ownership, and then maps the page read-write.

Write-update is the alternative: instead of invalidating, multicast each write to all copies. That needs totally ordered multicast (§7.5) so that all copies apply writes in the same order. With pages it is costly, because every single write must be trapped.

Messages and the protocol that carries them

These should be carried by a lightweight request-reply protocol over UDP (Part VI), for three reasons. Faults are short, latency-critical, blocking exchanges, with no stream to set up, so TCP's connection setup would be pure overhead. Read fetches are idempotent (doing them twice has the same effect as once), so they can simply be retransmitted on timeout, although ownership transfers need duplicate filtering. And multicast speeds up invalidations. Owners are found through a central manager, a hash-based distributed manager, or "probable owner" forwarding (each node remembers who it thinks owns the page and forwards requests along that chain).

Granularity: false sharing and thrashing

Large pages amortise the cost of each message (one fetch brings a lot of data), but they cause false sharing and thrashing, where a page ping-pongs between writers.

What the operating system must provide

Page-based DSM leans heavily on the OS (Part V):

• Paged virtual memory.
• Delivery of page faults to a user-level handler, either as a signal handler or through an external pager as in the Mach microkernel.
• Calls to map/unmap pages and to change their protection: read-only to detect writes, and no access to detect reads.
• Threads, so that a faulting thread can block while a server thread answers remote requests.
• Efficient networking.

Check yourselfUnder write-invalidate, process A holds page 3 read-only and writes to it. Put the events in order: (i) A maps the page read-write; (ii) INVALIDATE to other copy holders; (iii) page fault traps to the DSM handler; (iv) INV_ACKs collected; (v) PAGE_REQUEST(3, write); (vi) PAGE_REPLY with ownership.

iii, v, ii, iv, vi, i. The write traps, the handler requests the page for writing, all other copies are invalidated and acknowledged, the page and ownership are sent, and only then is it mapped read-write and the instruction restarted.

Check yourselfWhy is a read PAGE_REQUEST safe to retransmit blindly, while an ownership transfer is not?

A read fetch is idempotent: fetching the same page twice leaves everything as it was, so a lost request or reply can just be repeated. An ownership transfer changes state (who owns the page, who holds copies), so executing a duplicate could transfer ownership twice or invalidate a fresh copy; it needs duplicate filtering (e.g. request ids).

Check yourselfA team proposes DSM so that web browsers can share a bank server's account table directly. What is wrong with this?

DSM is unsuitable for client-server systems. The server's resources should be abstract data accessed by request, so the server can enforce its rules; with DSM there is no protection (any client could corrupt the table and crash others) and no modularity. DSM is for cooperating parallel processes.

Tuple Spaces exam

DSM shares raw bytes at addresses, which suits number-crunching but forces every process to agree on memory layout. Tuple spaces share small typed records instead, and processes find them by what they contain rather than where they are. The result is a very loose way to coordinate: leave data in a common place, and whoever needs it picks it up.

Three operations

A process says which tuple it wants with a template, which gives the number of fields and, for each field, either a value (which must be equal) or a type (any value of that type matches). For example, take(<String, Integer>) matches <"fred",1958> or <"sid",1964>, whereas take(<String, 1958>) matches only the first. If several tuples match, one is chosen nondeterministically. Because read and take block, the operations also give synchronisation: a process can wait for a tuple that another process has not written yet.

Matching in practice: the UK example (CDK Fig 6.20)

Suppose the space contains <"Capital","Scotland","Edinburgh"> and <"Population","Scotland",5168000>. Then take(<String,"Scotland",String>) removes the capital tuple, and take(<String,"Scotland",Integer>) removes the population tuple. read(<"Population",String,Integer>) returns some population tuple, which stays in the space.

Tuples are immutable: updating a shared counter

Tuples are immutable, so to change one you take it and then write a replacement. While the tuple is out of the space, other processes trying to take it block, which gives mutual exclusion for free:

<s, count> := myTS.take(<"counter", Integer>);   // others now block: mutual exclusion
myTS.write(<"counter", count + 1>);

Properties

Tuple spaces provide space uncoupling, which Linda calls "distributed naming": any sender can reach any one of many receivers, since a tuple goes to whoever matches it. They provide time uncoupling, because tuples persist until they are removed. Addressing is associative (by content). And the two retrieval operations have different patterns: read is one-to-many (many can read one tuple), while take is one-to-one (one tuple goes to one taker).

Programming patterns

• A semaphore (Ex 6.19) is made by writing N <"sem"> tuples. P (wait) is take(<"sem">), which blocks when none are left, and V (signal) is write(<"sem">).
• In master–worker, the master writes <"task", id, data> tuples, and idle workers take them and write back <"result", id, v>. Each task is done once, load balancing is automatic, and workers may come and go.
• RPC over a tuple space (Ex 6.18) has the client write <"req", op, args, clientId> and then take(<"reply", clientId, Object>), while servers loop taking requests. This gains time uncoupling and replaceable servers, but costs extra hops and gives no direct indication of failure (a client cannot tell a dead server from a slow one).

Variations. There can be multiple tuple spaces, which avoids a risk of a single global space, namely unintended aliasing, where a type-only template like <String, Integer> matches unrelated tuples written by some other application. Other variations are distributed implementations, Bauhaus Linda (in which everything is a set), and object spaces such as JavaSpaces.

Implementing a tuple space

There are four broad ways to implement a tuple space.

A centralised implementation is simple, but it is not fault tolerant and not scalable.

Replication can follow the state machine approach: the replicas start empty and deterministically apply the same operations in the same order, which requires totally ordered multicast (§7.5).

Alternatively, replication can follow Xu & Liskov, whose scheme exploits the semantics of each operation, working within the current view of the replicas:

• A write is multicast to all replicas and repeated until all of them acknowledge; duplicates are detected and not re-applied. The writer returns immediately.
• A read is multicast, and the first matching reply is the result, so the reader blocks only until one replica answers.
• A take has two phases, shown in the stepper.

The scheme needs two extra constraints. A worker's operations must run at each replica in the order the worker issued them, and a write must wait until that worker's earlier takes have finished everywhere.

Partitioning is the approach of the York Linda Kernel. Tuples are spread over several Tuple Space Servers (TSSs), with one copy only of each tuple, and the server is chosen by hashing the tuple. A read or take hashes its template to a set of candidate servers and searches them linearly. A Local Tuple Space Manager on each node handles its tuples. Keeping single copies makes take simple (no replicas to agree); the goal is performance for parallel computation, not fault tolerance.

Finally, there are peer-to-peer implementations: PeerSpaces, LIME and TOTA.

Case study: JavaSpaces

JavaSpaces is a Sun specification built on Jini (Java's service-discovery framework), with implementations such as GigaSpaces and Blitz. It is an object space: the items in it are entries, which are objects of classes implementing net.jini.core.entry.Entry. It has four operations:

A lease is a time limit: when it expires the entry is removed automatically, so forgotten entries do not clog the space. An entry matches a template if it is of the same class as the template (or a subclass) and is equal to it on every non-null template field, so a null field acts as a wildcard. Any operation may take place inside a distributed transaction; passing null for txn means no transaction.

import net.jini.core.entry.Entry;
import net.jini.space.JavaSpace;

public class AlarmTupleJS implements Entry {        // CDK Fig 6.24: public fields, no-arg ctor
    public String alarmType;
    public AlarmTupleJS() { }
    public AlarmTupleJS(String t) { alarmType = t; }
}
// Producer: space.write(new AlarmTupleJS("Fire!"), null, 60 * 60 * 1000);   // lease 1 hour
// Consumer: AlarmTupleJS got = (AlarmTupleJS)
//               space.read(new AlarmTupleJS("Fire!"), null, Long.MAX_VALUE); // blocking read
// (space obtained with a helper such as GigaSpaces' SpaceAccessor.findSpace("AlarmSpace"))

Line by line: AlarmTupleJS implements Entry, and, as JavaSpaces requires, has public fields and a public no-argument constructor. Its one field, alarmType, is what templates match on. The producer writes an entry with alarmType = "Fire!", no transaction (null) and a lease of 60 * 60 * 1000 milliseconds, one hour. A consumer builds a template with the same field value and calls read, with no transaction and a timeout of Long.MAX_VALUE, i.e. wait essentially forever. A template new AlarmTupleJS() with a null field would match any alarm.

Check yourselfSelf-test Q12: give the tuple-space operations and properties, and show how to increment a shared counter.

The operations are write (out), which adds a tuple; read (rd), which returns a copy of a matching tuple and blocks; and take (in), which removes a matching tuple atomically and also blocks. Tuples are found by template matching and are immutable. Tuple spaces are space- and time-uncoupled, and associative.

To increment a shared counter, take the tuple and write back a new one: <s,c> := take(<"counter", Integer>); write(<"counter", c+1>).

Check yourselfThe space holds <"x", 3>, <"y", 4> and <"x", "three">. Which tuples can take(<"x", Integer>) return?

1. Only <"x", 3>
2. <"x", 3> or <"x", "three">
3. <"x", 3> or <"y", 4>
4. Any of the three

A. The first field must equal "x" and the second must be of type Integer. <"x","three"> has a String second field, and <"y",4> fails the first field.

Check yourselfHow do you build a semaphore that lets at most 3 processes into a section at once, using only tuple-space operations?

Initialise by writing three <"sem"> tuples. To enter (P), take(<"sem">): the fourth process finds none left and blocks. To leave (V), write(<"sem">), which lets one blocked process through.

Check yourselfIn a replicated tuple space, why is take harder to implement than read or write?

A take is destructive and must be exclusive: all replicas must agree on which one tuple was removed, and no two takers may get the same tuple. A read can use the first reply from any replica, and a write is just multicast until acknowledged. That is why Xu & Liskov's take needs two phases with locking, and the state-machine approach needs totally ordered multicast. CDK names the destructive take as what limits tuple-space scalability.

Comparing and Choosing a Technique exam

The exam rarely asks "define pub-sub" on its own. It describes a system and asks which paradigm fits and why. To answer, you need each paradigm's profile side by side, and a habit of matching the scenario's needs (who receives, how many, when, ordered or not) to those profiles.

The summary table (CDK Fig 6.27)

Read each column as one paradigm's profile, and compare across the first two rows to see where time uncoupling is guaranteed and where it is only possible.

Two observations explain the pattern in the table. First, time uncoupling depends on persistency: queues, DSM and tuple spaces store state by design, while groups and pub-sub only do so if they keep history (JGroups' getState, durable subscriptions). Second, communication-based approaches can scale given good routing, with the exception of groups, which pay for membership and ordering. State-based approaches are limited by the need for consistent shared state, and for tuple spaces the limiting factor is the destructive take.

Choosing: needs to technique

Each row of the next table starts from a need, names the technique that fits it, and gives a scenario to illustrate it.

The same reasoning can be drawn as a rule-of-thumb decision tree. It is a study aid built from the two tables, not an official algorithm, but it asks the questions in the order that usually settles an exam scenario.

A three-part scenario

Self-test Q15 asks for a choice per requirement in one hospital system. Notice that one system can sensibly use three paradigms.

Check yourselfSelf-test Q15: a hospital needs (a) vital-sign alerts to all nurses' displays, (b) lab requests to whichever analyser is free, even if all are briefly down, (c) three replicated record servers kept identical. Choose for each.

• (a) The alerts should use pub-sub, with a topic per ward and a content filter on severity, and with reliable low-latency delivery.
• (b) The lab requests should go on a persistent message queue with competing consumers. Each request is then handled once, and time uncoupling covers the times when all the analysers are down.
• (c) The record servers need group communication with reliable totally ordered multicast, plus membership and failure detection.

Check yourselfAccording to CDK's summary table, which paradigm is associative in all its forms?

1. Pub-sub
2. Message queues
3. DSM
4. Tuple spaces

D. Tuple spaces always find data by content. Pub-sub is associative only in its content-based form; queues and DSM are not associative (DSM is accessed by address).

Check yourselfFor which two paradigms does CDK say time uncoupling is only "possible" rather than guaranteed, and why?

Groups and pub-sub. They are time-uncoupled only if they keep state for absent receivers (group history via getState, retained events and durable subscriptions). Queues, DSM and tuple spaces store state by nature, so they are always time-uncoupled. Time uncoupling depends on persistency.

Check yourselfA legacy payroll system writes records in EBCDIC with big-endian integers; a new HR system expects JSON. Which paradigm, and which of its properties, helps?

A message queue with message transformation: a message broker converts between formats as messages pass through, which is the classic EAI use. Persistence also means neither system has to be up at the same time.

Exam Question: Choose and Draw exam

The 2016 final exam asked students to pick between three indirect paradigms for a concrete app and to draw the design. This section works that question in full and then shows what the two rejected designs would have looked like, so you can argue against them as well as for your choice.

The model answer: publish-subscribe

Choose publish-subscribe, topic-based, through a broker.

The rejected designs, drawn

Drawing the alternatives makes their weaknesses obvious. Both handle the reporting half well; both struggle with the results to every user half.

Check yourselfIn the pub-sub design, which property gives the app time uncoupling for a phone that was switched off when the latest chart was published?

Retained events or durable subscriptions on the chart topic. The broker keeps the last chart (or the events for a durable subscriber), so when the phone reconnects it is notified of the latest chart. Plain pub-sub would give space uncoupling only.

Check yourselfThe examiner changes the scenario: every play report must be counted exactly once even if the ranking server is down for an hour, and results go only to a dashboard. Does your choice change?

Yes, a message queue becomes the natural fit. The requirement is now one consumer per message, reliably, possibly later: a persistent plays queue gives validity and integrity (each report delivered once) and time uncoupling across the server's outage, and there is no longer a one-to-many results problem.