Distributed computing

WHY DOES DISTANCE DECREASE?

• Well, when you readjust the mean, it decreases for that set.
• When you reassign, every distance gets smaller still.
• So every step readjusts the total distance.
• How do we do this for a distributed asynchronous system?
• What if you have rounds?
• What if you don’t?

SETI-at-Home Style Projects?

• SETI stands for search for extra-terrestrial intelligence. It consists of testing radio signal receptions for some regularity.
• Ideal distributed system project: master sends out work. Servers do work.
• Servers may crash. What to do? Work queue trick: send work description to server and put job at bottom of queue. If server completes, then remove work description from queue.
• Servers may be dishonest. What to do?

BROADCAST PROTOCOLS

• Often it is important to send a message to a group of processes in an all-or-nothing manner. That is, either all non-failing processes should receive the message or none should.
• This is called atomic broadcast
• Assumptions:
• fail-stop processes
• messages are received from one process to another in the order they are sent

ATOMIC (UNORDERED) BROADCAST PROTOCOL

• Application: Update all copies of a replicated data item
• Initiator: Send message m to all destination processes
• Destination process: When receiving m for the first time, send it to all other destinations

• Initiator

• Initiator

Fault-Tolerant Broadcasts

• Reference: “A Modular Approach to Fault-Tolerant Broadcasts and Related Problems” Vassos Hadzilacos and Sam Toueg.
• Describes reliable broadcast, FIFO broadcast, causal broadcast and ordered broadcast.

Stronger Broadcasts

• FIFO broadcast: Reliable broadcast that guarantees that messages broadcast by the same sender are received in the order they were broadcast.
• A bit more precise: If a process broadcasts a message m before it broadcasts a message m’, then no correct process accepts m’ unless it has previously accepted m. (Might buffer a message before accepting it.)