Protocols and Decentralized Multiagent Systems Flashcards
Centralized System
Central technical entity that mediates interactions between users
Amazon, Facebook, Typical autonomous system (e.g., driverless cars)
- Usually realized in software as a Web service or platform
- Application state in central entity
- Users coordinate based on shared memory
Decentralized System: System of Autonomous Social Principals
- Principals engage on basis of arms-length interactions realized via messaging
- Each’s principal’s software encodes its decision making
Agents Helping Principals Exercise Autonomy
- Each agent reflects the autonomy of its principal
- How can we realize a multiagent system based that accommodates the autonomy of its principals?
- Does not unduly constrain an agent’s decision making
- Supports flexible interactions
- Enables loose coupling between agents
Decentralized Applications Motivate Communication Protocols
- A protocol defines how the agents ought to communicate with one another
- A protocol is a model of a decentralized application!
- What are the main requirements for protocol specifications?
- How can we specify a communication protocol?
- Roles (abstracting over agents)
- Message schemas, i.e., allowed content
- Message emission and reception, point-to-point or multicast, between specified roles
- Constraints on message occurrence
- Constraints on message ordering
- Agents participate in a protocol by playing a role in it
- How can we develop agents suitable for a role?
Protocol for a Healthcare Application
Patient sends a Complaint to Physician, who sends a Prescription to Pharmacy, who
sends Fulfill to Patient
- Autonomy means no one need send any message!
- Three parties, not client server
- Healthcare standards: Health Level 7 (HL7), Integrate the Healthcare Enterprise (IHE)
- Informally described interactions difficult to implement correctly
Protocol for Purchase Order (PO) Fulfillment Application
Several items in a PO that may be wrapped and packed independently to create a
shipment
A Purchase Protocol (Just the Happy Path)
Specified as a UML interaction diagram
Unhappy path (featuring Reject) would be in another UML diagram
Protocols and Roles as State Machines
Protocol: shared view; roles: each local view
! and ? mean send and receive, respectively
Protocols Promote Interoperation, Autonomy,
Heterogeneity
- Autonomy by
- Minimally constraining agents’ decision making and interactions
- Interoperation by specifying
- Schemas of messages exchanged
- Meanings of messages, which determine the state of the interaction
- Correct behaviors
- Heterogeneity by
- Providing the standard to which agents are implemented
- Defining the extent of heterogeneity: the agents can be heterogeneous with regard to everything else
- All of the above contribute to loose coupling!
Challenge: Information Integrity in Interactions
Interactions must compute consistent information objects
Integrity Violations
Can Be Avoided By Local Checks
Integrity Violation: Race Condition
Cannot be Avoided By Local Checks; Requires Verification
Challenge: Interactions Must Not Deadlock
There must always be a path that agents can take that leads to a final state
Challenge: Asynchronous Communication
Practical; Offered by the Internet
- Senders and receivers do not have to rendezvous (synchronize) to perform a communication
- Sender puts a message into the communication infrastructure regardless of the state of the receiver
- Receiver receives the message whenever the infrastructure delivers it
- Decouples senders and receivers
- Conducive to autonomy
Properties of the Communication Infrastructure
How can we achieve each property?
- Noncreative: Must only sent messages be received?
- Will an infrastructure create messages?
- Reliable: Must a message that is sent be received?
- Will an infrastructure drop messages?
- Ordered: Must the messages from a sender to a receiver be delivered in the order in which they were sent?
- Will an infrastructure deliver messages in any order?
- Global: Must the messages from different senders to the same receiver be received in the order in which they were sent?
- Called “causal” ordering in the literature but that term refers to potential causality
Challenge: Unordered, Asynchronous Communication
The Gold Standard!
- Today: Commonplace to rely on communication infrastructures that
provide first-in first-out (FIFO) delivery- E.g., as provided by TCP and message queues
- But ordered delivery has drawbacks
- Hidden synchronization
- An additional assumption for the multiagent system to work correctly
- Couples the agents through the infrastructure
- Challenge: Coordinate decentralized computation without assuming ordered delivery infrastructure
Challenge: Engineering with Agent Communication
- Begin from a protocol
- Generate role skeletons (or endpoints) from the protocol
- For each role skeleton, implement one or more agents who realize (“flesh out”) it
- Map each skeleton to a set of incoming and outgoing messages and the changes each message induces in the local state
- Implement methods to process each incoming message
- Send messages allowed by the protocol
- Challenge: Generating role skeletons that ensure interoperation
- Not trivial when a protocol involves more than two roles
- The protocol must be such that such skeletons are derivable from it
Challenge: Modeling Application Meaning
Meaning lies in the application domain
- Offers, Shipments, Payments are domain objects that have meaning to users and on the basis of which they perform their decision making
- Offer is a domain object with an unique identifier and an associated item and price
- Each Offer set ups a commitment from Seller to Buyer that if Payment is made within 3 days, then Shipment will be made within 5 days.
- Challenge: Protocols must enable capturing application meaning
- Communications compute (create and change state of) domain objects, which capture the state of the application!
Indequate: Control Flow-Based Approaches For Modeling Protocols
UML interaction diagrams, state machines, etc.
- Cannot model appplication meaning, which is necessarily grounded in information!
- Cannot meet the foregoing challenges
- Need an information-based approach for modeling protocols
