Coordination (a.k.a. Synchronization) Problems and Protocols

Coordination (a.k.a. Synchronization) Problems and Protocols
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Review

Flow of Control:
- A sequence of control transfers (i.e., transitions between instructions/steps)
Concurrent Flows:
- Two flows, $X$ and $Y$ , are said to running concurrently iff $Y$ began after $X$ began and before $X$ finished or $X$ began after $Y$ began and before $Y$ finished

Motivation for Studying Coordination

The Upside of Concurrent Flows:
- It is sometimes beneficial to solve problems using concurrent flows
The Downside of Concurrent Flows:
- Solving problems using concurrent flows often involves coordination
- Coordination can itself cause problems

Communication

The Assumption:
- The parties that are coordinating can communicate
Communication Mechanisms:
- Transient - The information is only available at the time it is transmitted
- Persistent - The information persists after it is transmitted (until it is modified/destroyed)
Properties of Communication Channels:
- Synchronous - Both parties (the sender and receiver) must participate at the same time
- Asynchronous - The parties can participate at different times

Communications Protocols

Informal Definition:
- An agreement about how communication will proceed
Formal Definition:
- An agreement that governs the procedures used to exchange information between cooperating entities

Important Properties of Coordination Protocols

Sequencing (a.k.a. Serialization):
- It is possible to ensure that one party uses a resource before another party
Mutual Exclusion:
- It is possible to exclude both parties from using a resource at the same time

Important Properties of Coordination Protocols (cont.)

Starvation Freedom:
- If one party wants to use a resource then it can do so eventually
Deadlock Freedom:
- If both parties want to use use a resource then one of them can do so eventually
Fault Tolerance:
- The protocol accounts for incorrect behavior of the parties and/or problems with the channel

Demonstrating that Coordination Protocols have Specific Properties

Testing:
- Is often inadequate, especially for nondeterministic systems
Proofs:
- Are often necessary (as they are when demonstrating the correctness of some kinds of algorithms)

Initiation Problems

The Nature of the Problem:
- $N$ parties have $N$ independent tasks to complete
- There is no benefit (or it is impossible) to subdivide tasks
Irrelevant Properties of the Protocol:
- Sequencing - doesn't arise because the order doesn't matter
- Mutual Exclusion - doesn't arise because the tasks are independent can't be subdivided
- Deadlock Freedom - doesn't arise beacsue the tasks are independent (i.e., require no common resources)
Required Properties of the Protocol:
- Starvation freedom for all parties (i.e., all parties can complete their tasks)

Initiation Problems (cont.)

An Example:
- Two housemates, Mark and Daryl, need to complete two chores between them -- mowing the lawn and washing the dishes
- They have one lawn mower and a small sink (so each chore can be performed by at most one person)
Solutions:
- Only involve a mechanism for initially dividing up the tasks between the parties

Owner-Borrower Problems

The Nature of the Problem:
- Two parties need to share a resource that can only be used by one party at a time
- One of the parties (ie., the owner) has priority
Required Properties of the Protocol:
- Mutual Exclusion
- Deadlock Freedom for the Owner

Owner-Borrower Problems (cont.)

An Example:
- Owen (a marine veterinarian) owns a large exercise tank (that is dark and contains many plants, rocks, etc...)
- Barbara (another marine veterinarian) borrows the tank when it is not in use
- Owen treats orcas and Barbara treats baleen whales
- Both would like to have their animals use the tank
- An orca and a baleen whale can't be in the tank together
Solutions:
- Involve different behaviors for the two parties (i.e, are asymmetric)

Owner-Borrower Problems (cont.)

An Important Characteristic of this Example:
- It isn't possible to look in the tank and see if it is occupied so a communication mechanism is necessary
An Observation about the Communication Mechanism:
- A transient mechanism (e.g., shouting) isn't desirable because the message might be missed

Owner-Borrower Problems - An Incorrect Solution

The Protocol:
- Neither Owen nor Barbara releases an animal
Properties:
- Mutual Exlcusion - Yes
- Deadlock Freedom for the Owner - No

Owner-Borrower Problems - Another Incorrect Solution

The Communication Mechanism:
- Each party has a flag that can be raised and lowered
The Protocol:
- Check to see if the other parties flag is raised
- If not, release your animal then raise your flag
Properties:
- Mutual Exlcusion - No (both parties can check, see no flag, and release)
- Deadlock Freedom for the Owner - No

Owner-Borrower Problems - Still Another Incorrect Solution

The Communication Mechanism:
- Each party has a flag that can be raised and lowered
The Protocol:
- Check to see if the other parties flag is raised
- If not, raise your flag then release your animal
Properties:
- Mutual Exlcusion - No (both parties can check, see no flag, and then act)
- Deadlock Freedom for the Owner - No

Owner-Borrower Problems - A Solution

The Communication Mechanism:
- Each party has a flag that can be raised and lowered
The Foundation of the Protocol:
- When a party wants to release an animal they first raise their flag and then looks at the other flag
- When their animal returns they lower their flag
Owen's Release Details:
- Don't release an orca until Barbara's flag is lowered
Barbara's Release Details:
- If Owen's flag is up then Barbara lowers her flag
- Barbara waits until Owen's flag is lowered then raises her flag and releases a baleen whale

Owner-Borrower Problems - A Proof of Mutual Exclusion

Assume the Contrary:
- Assume a baleen whale and an orca are both in the tank
Finding a Contradiction:
- According to the protocol, when Owen looked his flag was already up. So, Barbara's flag must not have been up
- Hence, Barbara must have looked after Owen looked (because otherwise her flag would be up)
- However, if Barbara looked after Owen looked then she must have seen Owen's flag raised and hence she would not have released a baleen whale (which is a contradiction)
An Interesting Aspect of this Proof:
- It only involves the starting and ending times of actions, not their duration

Owner-Borrower Problems - Other Properties

Proof of Deadlock Freedom for the Owner:
- If Owen and Barbara both raise their flags then Barbara will eventually notice and lower hers, allowing Owen to release an orca
Starvation Freedom?
- No -- Barbara defers to Owen so Owen can keep Barbara's baleen whales waiting forever

Producer-Consumer Problems

The Nature of the Problem:
- One party produces a product, but only if no units are available
- The other party attempts to consume a product, but only if units are available
Required Properties of the Protocol:
- Mutual Exclusion
- Starvation Freedom

Producer-Consumer Problems (cont.)

An Example:
- There is a cougar pen (with solid walls, a roof, and two doors)
- Carol has a cougar that she releases into the pen when it is hungry and there is a meal in the pen
- Peter places a meal in the pen when there isn't one in the pen and when the cougar is not in the pen
Solutions:
- Involve different behaviors for the two parties

Producer-Consumer Problems (cont.)

An Important Characteristic of this Example:
- It isn't possible to look in the pen and see if it is occupied so a communication mechanism is needed
An Observation about the Communication Mechanism:
- A transient mechanism (e.g., shouting) isn't desirable because the message might be missed

Producer-Consumer Problems - A Solution

The Communication Mechanism:
- There is a light on top of the pen that both parties can turn on and off with switches
The Foundation of the Protocol:
- Peter adds a meal when the light is on
- Carol releases the cougar when the light is off
Peter's Details:
- Waits until the light is on
- Enters the pen
- Puts a meal in the pen
- Leaves the pen
- Turns the light off
Carol's Release Details:
- Waits until the light is off
- Releases the cougar into the pen when it is hungry
- Waits until the cougar eats and exits the pen and then turns the light on

Producer-Consumer Problems - A Proof of Mutual Exclusion

A State Model:
The Proof:
- There are no transitions between the "with Peter" and "with Cougar" states

Producer-Consumer Problems - A Proof of Starvation Freedom

Assume the Potential for Starvation:
- CougarHungry is true
- NoMeal is true
The Proof:
- Regardless of the starting state, eventually, the system will transition to OffWithCougar

Reader-Writer Problems

The Nature of the Problem:
- There are one or more parties that modify (i.e., write to) an entity's properties
- There are one or more parties that access (i.e., read from) an entity's properties
Required Properties of the Protocol:
- Each writer must have exclusive access to the entity
- Readers may share access to the entity

Reader-Writer Problems (cont.)

Examples:
- Reservation Systems - multiple parties can obtain information at the same time but only one party can make a reservation at a time
- Backup Systems - multiple parties can retrieve archived files at the same time but only one party can save a file at a time
Variants:
- Favor Readers - Don't keep readers waiting unless a writer has already been granted access
- Favor Writers - Readers must wait on writers, even if the writers are themselves waiting on other parties

Rendezvous Problems

The Nature of the Problem:
- There are two parties, Andrea and Bill, each of whom performs two tasks in order, $(A1, A2)$ for Andrea and $(B1, B2)$ for Bill
Required Properties of the Protocol:
- Sequencing - $A1$ must happen before $B2$ and $B1$ must happen before $A2$
- Starvation Freedom
- Deadlock Freedom

Rendezvous Problems (cont.)

Number of Permutations:
- There are $4! = 24$ possible orderings of the four tasks
Sequence-Satisfying Permutations:
- There are six permutations that satisfy the two cross-person sequencing requirements: (A1, B1, A2, B2), (A1, B1, B2, A2), (A1, B2, B1, A2), (B1, A1, A2, B2), (B1, A1, B2, A2), (B1, A2, A1, B2)
- Only four of these are consistent with the within-person sequencing: (A1, B1, A2, B2), (A1, B1, B2, A2), (B1, A1, A2, B2), (B1, A1, B2, A2)