Describe point-to-point communication.
- Participants need to exist at the same time
- Participants need to know the addresses of each other and their identities
- It is necessary to establish communication
- Not a good way to communicate with several participants
- Not a good way to implement complex communication
Describe indirect communication, its necessary components, and examples of where it is used.
- Space uncoupling (no need to know the identity, and participants can be replaced, updated, replicated, or migrated)
- Time uncoupling (independent lifetimes and requires persistence in the communication channel)
- Communication through an intermediary (no direct coupling between the sender and the receivers)
- Scenarios where users connect and disconnect very often (mobile environments, messaging services, forums)
- Event dissemination where receivers may be unknown and change often (RSS, events feeds in financial services)
- Scenarios with a very large number of participants (Google Ads system, Spotify)
- Commonly used in cases when change is anticipated and there is a need to provide dependable services
- Requires middleware
- Performance overhead introduced by
- Adding a level of indirection
- Implementation of reliable message delivery
- Ordering guarantees
- More difficult to manage due to lack of direct coupling
- Difficult to achieve end-to-end properties
- Real-time behavior
- Security
====================Summary====================
All problems in computer science can be solved by another level of indirection.
Indirect communication
- Communication between entities in a system
- Through an intermediary
- With no direct coupling between the sender and receivers
Lots of variations in
- Intermediary
- Coupling
- Implementation details and trade-offs
There is no performance problem that cannot be solved by eliminating a level of indirection
Explain the concept of group communication.
- A message is sent to a group
- This message is delivered to all members of the group
- The sender is not aware of the identities of the receivers
- Represents an abstraction over multicast communication
- Reliable dissemination of information to potentially large numbers of clients
- Support for collaborative applications
- Support for a range of fault-tolerance strategies
- Support for system monitoring and management
Explain process groups in group communication.
Process groups
- Abstraction - resilient process
- Messages delivered to a process endpoint, no higher
- Messages
- Unstructured byte arrays
- No marshalling
- Level of service - socket
Explain object groups in group communication.
Object groups
- Higher level approach
- Collection of objects (same class)
- Replication can be transparent to clients
- Invoke on a single object (proxy)
- Requests sent by group communication
- Voting in proxy usually
Describe closed and open group communication.
Closed
- Cooperating servers
- Internal messages
Open
- Notification of services
Describe reliability in group communication.
Unicast delivery reliability properties
- Delivery integrity - message received same as sent, never delivered twice
- Delivery validity - outgoing message eventually delivered
Group communication reliability properties build on unicast
- Delivery integrity - deliver the message correctly at most once to group members
- Delivery validity - the message sent will be eventually delivered (if not all group members fail)
- Agreement/consensus - delivered to all or none of the group members - also called atomic delivery
Describe ordering in group communication.
FIFO ordering - first-in-first-out from a single sender to the group
Causal ordering - preserves potential causality, happens before
Total ordering - messages delivered in the same order to all processes
Perspective - strong reliability and ordering is expensive (scale limited). More probabilistic approaches and weaker delivery possible
Describe membership in group communication.
Providing an interface for group membership changes
- The membership service provides operations to create and destroy process groups and to add or withdraw a process to or from a group
Failure detection
- The service monitors the group members not only in case they should crash but also in case they should become unreachable because of a communication failure
Notifying members of group membership changes
- The service notifies the group’s members when a process is added or when a process is excluded
Performing group address expansion
- When a process multicast a message, it supplies the group identifier rather than a list of processes in the group
What are the working fundamentals of publish-subscribe or distributed event systems?
- Publishers publish structured events to event service
- Subscribers express interest in particular events
- Event service
- Matches published events to subscriptions
- Delivers suitable events
What are some applications of a publish-subscribe system?
- Financial information systems
- Live feeds of real-time data (including RSS)
- Cooperative working - events of shared interest
- Ubiquitous computing - location events
- Lots of monitoring application
- Stock trading system
- Let users see the latest market prices of stock they care about
- Information for a given stock arrives from multiple sources
- Dealers only care about the stock they own (or might)
- May only care to know above some threshold, in addition
- Two kinds of tasks
- Information provider receives updates (events) from a single external source
- Dealer process creates a subscription for each stock its user(s) express interest in
Name and describe the key characteristics of the publish-subscribe systems.
Heterogeneity
- Able to glue together systems not designed to work together
- Have to come up with an external description of what can be subscribed to: simple flat, rich taxonomy, etc
Asynchronism
- Decoupling means you never have to block
Possible delivery guarantees
- All subscribers receive the same events (atomicity)
- Events correctly delivered to subscribers at most once (integrity)
- Message sent will eventually be delivered (validity)
- Real-time
Describe the programming model in a publish-subscribe system.
Publishers
- Disseminate event e through publish(e)
- Register/advertise via a filter (pattern over all events)
- f: advertise(f)
- Expressiveness of pattern is the subscription model
- Can also remove the offer to publish: unadvertise(f)
Subscribers
- Subscribe via a filter (pattern) - f: subscribe(f)
- Receive event e matching - f: notify(f)
- Cancel their subscription - unsubscribe(f)
Describe the subscription model in a publish-subscribe system.
Channel-based
- Publishers publish to named channels
- Subscribers get all events from the channel
- Very simplistic, no filtering (all other models below do)
Topic-based (AKA subject-based)
- Each notification is expressed in multiple fields, one being the topic
- Subscriptions choose topics
- Hierarchical topics can help
Content-based
- Generalization of topic based
- Subscription is expressed over a range of fields (constraints on values)
- Far more expressive than channel-based or topic-based
Type-based
- Use object-based approaches with object types
- Subscriptions defined in terms of types of events
- Matching in terms of types or subtypes of filter
- Ranges from coarse-grained (type names) to fine-grained (attributes and methods of object)
- Advantage: clean integration with object-based programming languages
What are the main concerns regarding a publish-subscribe system?
- Deliver events efficiently to all subscribers that have filters that match the events
- Security
- Scalability
- Failure handling
- Quality of Service (QoS)
- Tradeoffs:
- Latency/reliability
- Ease in implementation/expressive power to specify events of interest
Describe the different architecture schemes in a publish-subscribe system.
Centralized schemes - simple
- Implementing channel-based or topic-based - simple
- Map channels/topics onto groups
- Use the group’s multicast (possibly reliable, ordered)
- Implementation of content/type - more complicated
Distributed
- Most implementations are networks of brokers
Some implementations are peer-to-peer (P2P)
- All publisher and subscriber nodes act as the pub-sub broker
Explain the three types of content-based routing.
- Flooding (with duplicate suppression)
- Filtering (filter-based routing)
- Rendezvous (distributed)
Explain flooding in content-based routing in a publish-subscriber system.
Simplest version
- Send event to all nodes on a network
- Can use underlying multicast/broadcast
More complicated
- Brokers arranged in acyclic forwarding graph
-Each node forwards to all its neighbours (except one that sends it to the node)
See slide 30 of Chapter 5.
Explain filtering in content-based routing in a publish-subscriber system.
Only forwarded where a path to a valid subscriber, I.e., subscription info propagated through the network towards publishers
Detail
- Each node maintains a neighbors list
- For each neighbor, maintain a subscription list/criteria
- Routing table with a list of neighbors and subscribers downstream
See slide 31 of Chapter 5
Explain Rendezvous in content-based routing in a publish-subscriber system.
- It is based on two functions
- SN and EN, used to associate respectively subscriptions and events to brokers in the system
- Given a subscription s
- SN(s) returns a set of nodes which are responsible for storing s and forwarding received events matching s to all those subscribers that subscribed to it
- Given an event e
- EN(e) returns a set of nodes which must receive e to match it against the subscriptions they store
- Event routing is a two-phase process
- First, an event e is sent to all brokers returned by EN(e), then those brokers match it against the subscriptions they store and notify the corresponding subscribers
- This approach works only if for each subscription s and event e, such that e matches s, the intersection between EN(e) and SN(s) is not empty (mapping intersection rule)
See slide 32 of Chapter 5
Explain message queues.
- Intermediary between producers and consumers of data
- Point-to-point, not one-to-many
- Supports time and space uncoupling
- Programming model
- Producer sends a message to a specific queue
- Consumers can
- Block
- Non-block (polling)
- Notify
- Many processes can be sent to a queue
- Many can remove from it
- Queuing policy: usually FIFO, but also priority-based
- Consumers can be selected based on metadata
- Messages are persistent - stored until removed (on disk)
- Transaction support - all-or-none operations
- Automatic message transformation - on arrival, message transforms data from one format to another (data heterogeneity)
-
01 - Introduction1
-
02 - System12
-
03 - SysML22
-
04 - Inter-Process Communication21
-
05 - Indirect Communication21
-
06 - Pipes16
-
07 - Message Queues10
-
08 - External data representation25
-
09 - Kernel and processes29
-
10 - Concurrency / Parallelism11
-
11 - Threads15
-
12 - Shared data between threads15
-
13 - Synchronization13
