Concurrent Reading and Writing using Mobile Agents

Life of a process

• When a message m arrives
• 1. Receive it
• 2. Evaluate a predicate (with message m and the local variables);
• 3. if predicate = true then
• update zero or more internal variables;
• send zero or more messages;
• end if

• A

• B

• C

• D

• E

• m

Example: Shared memory model

• Address spaces of processes overlap

• M1

• 1

• 3

• 2

• 4

• M2

• Concurrent operations on a shared variable are serialized

• Processes

Variations of shared memory models

• 0

• 3

• 2

• 1

• State reading model
• Each process can read
• the states of its neighbors

• 0

• 3

• 2

• 1

• Link register model
• Each process can read from
• and write to adjacent registers. The entire local state is not shared.

What is the difference between a synchronous distributed system and an asynchronous distributed system?

Synchrony vs. Asynchrony

• Send & receive can be blocking or non-blocking
• Postal communication is asynchronous:
• Telephone communication is synchronous
• Synchronous communication or not?
• Remote Procedure Call,
• Email

• Any constraint defines some form of synchrony …

Modeling wireless networks

• Communication via broadcast
• Limited range
• Dynamic topology
• Collision of broadcasts
• (handled by CSMA/CA)

• RTS

• RTS

• CTS

• Request To Send

• Request To Send

• Clear To Send

Weak vs. Strong Models

• One object (or operation) of a strong model = More than one simpler objects (or simpler operations) of a weaker model.
• Often, weaker models are synonymous with fewer restrictions.
• One can add layers (additional restrictions) to create a stronger model from weaker one.

• Examples
• High level language is stronger than assembly language.
• Asynchronous is weaker than synchronous (communication).
• Bounded delay is stronger than unbounded delay (channel)

Model transformation

• Stronger models
• - simplify reasoning, but
• - needs extra work to implement
• Weaker models
• - are easier to implement.
• - Have a closer relationship with the real world

• “Can model X be implemented using model Y?” is an interesting question in computer science.
• Sample exercises
• Non-FIFO to FIFO channel
• Message passing to shared memory
• Non-atomic broadcast to atomic broadcast

Non-FIFO to FIFO channel

• P

• Q

• buffer

• m1

• m4

• m3

• m2

• 1

• 2

• 3

• 4

• 5

• 6

• 7

• FIFO = First-In-First-Out

• Sends out
• m1, m2, m3, m4, …

Non-FIFO to FIFO channel

• {Sender process P} {Receiver process Q}
• var i : integer {initially 0} var k : integer {initially 0}
• buffer: buffer[0..∞] of msg
• {initially ∀k: buffer [k] = empty
• repeat repeat
• send m[i],i to Q; {STORE} receive m[i],i from P;
• i := i+1 store m[i] into buffer[i];
• forever {DELIVER} while buffer[k] ≠ empty do begin
• deliver content of buffer[k];
• Needs unbounded buffer buffer [k] := empty; k := k+1;
• & unbounded sequence no end
• THIS IS BAD forever

Observations

• Now solve the same problem on a model where
• (a) The propagation delay has a known upper bound of T.
• (b) The messages are sent out @ r per unit time.
• (c) The messages are received at a rate faster than r.
• The buffer requirement drops to r.T.
• (Lesson) Stronger model helps.
• Question. Can we solve the problem using bounded buffer space
• if the propagation delay is arbitrarily large?

Example

• 1 second window

• Last message

• First message

• sender

• receiver

Message-passing to Shared memory

• {Read X by process i}: read x[i]
• {Write X:= v by process i}
• - x[i] := v;
• Atomically broadcast v to
• every other process j (j ≠ i);
• After receiving broadcast,
• process j (j ≠ i) sets x[j] to v.
• Understand the significance of atomic
• operations. It is not trivial, but is very
• important in distributed systems.
• Atomic = all or nothing

• This is incomplete and still
• not correct. There are more
• pitfalls here.

Non-atomic to atomic broadcast

• Atomic broadcast = either everybody or nobody receives
• {process i is the sender}
• for j = 1 to N-1 (j ≠ i) send message m to neighbor [j] (Easy!)
• Now include crash failure as a part of our model.
• What if the sender crashes at the middle?
• How to implement atomic broadcast in presence of crash?

Mobile-agent based communication

• Communicates via messengers instead of (or in addition to) messages.

• What is
• the lowest
• Price of an
• iPad in Iowa?

• Carries both
• program and data

• Best Buy

• Cedar Rapids

• University
• of Iowa

Other classifications of models

• Reactive vs Transformational systems
• A reactive system never sleeps (like: a server)
• A transformational (or non-reactive systems) reaches a fixed point after which no further change occurs in the system (Examples?)
• Named vs Anonymous systems
• In named systems, process id is a part of the algorithm.
• In anonymous systems, it is not so. All are equal.
• (-) Symmetry breaking is often a challenge.
• (+) Easy to switch one process by another with no side effect. Saves log N bits.

Knowledge based communication

• Alice and Bob enter into an agreement: whenever one falls sick, (s)he will call the other person. Since making the agreement, no one called the other person, so both concluded that they are in good health. Assume that the clocks are synchronized, communication links are perfect, and a telephone call requires zero time to reach.
• What kind of interprocess communication model is this?

History

• The paper “Cheating Husbands and Other Stories: A Case Study of Knowledge, Action, and Communication” by Yoram Moses, Danny Dolev, Joseph Halpern (PODC 1985) illustrates how actions are taken and decisions are made without explicit communication using common knowledge. (Adaptation of Gamow and Stern, “Forty unfaithful wives,” Puzzle Math, 1958)
• (Bidding in the game of cards like bridge is an example of knowledge-based communication)

Observations

• Knowledge-based communication relies on making deductions from the absence of a signal or actions.

Cheating Husband’s puzzle:

• In a matriarchal town, the Queen read out the following in a meeting at the town square.
• There are one or more unfaithful husbands in our community.
• None of you know whether your husband is faithful. But each of you which of the other husbands are unfaithful.
• Do not discuss this with anyone, but should you discover that your own husband is unfaithful, you should shoot him on the midnight of the day you find out about it.