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)

There's Always More to Learn