RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://www2.cs.uregina.ca/~hamilton/courses/330/notes/distributed/distributed.html below:

Distributed Algorithms

Reference: SGG7, 18.6-18.7

Communication in networks is implemented in a process on one machine communicating with a process on another machine See CS430 for details A distributed algorithm is an algorithm, run on a distributed system, that does not assume the previous existence of a central coordinator. A distributed system is a collection of processors that do not share memory or a clock. Each processor has its own memory, and the processors communicate via communication networks. We will consider two problems requiring distributed algorithms, the coordinator election problem and the value agreement problem (Byzantine generals problem)

Election Algorithms

Election Algorithms

The coordinator election problem is to choose a process from among a group of processes on different processors in a distributed system to act as the central coordinator.
An election algorithm is an algorithm for solving the coordinator election problem. By the nature of the coordinator election problem, any election algorithm must be a distributed algorithm.

-a group of processes on different machines need to choose a coordinator

-peer to peer communication: every process can send messages to every other process.

-Assume that processes have unique IDs, such that one is highest

-Assume that the priority of process P_i is i

(a) Bully Algorithm

Background: any process P_i sends a message to the current coordinator; if no response in T time units, P_i tries to elect itself as leader. Details follow:

Algorithm for process P_ithat detected the lack of coordinator

Process P_i sends an “Election” message to every process with higher priority.
If no other process responds, process P_i starts the coordinator code running and sends a message to all processes with lower priorities saying “Elected P_i”
Else, P_i waits for T’ time units to hear from the new coordinator, and if there is no response à start from step (1) again.

Algorithm for other processes (also called P_i)

If P_i is not the coordinator then P_i may receive either of these messages from P_j

if Pi sends “Elected P_j”; [this message is only received if i < j]

Pi updates its records to say that P_j is the coordinator.

Else if P_j sends “election” message (i > j)

Pi sends a response to P_j saying it is alive

Pi starts an election.

(b) Election In A Ring => Ring Algorithm.

-assume that processes form a ring: each process only sends messages to the next process in the ring

- Active list: its info on all other active processes

- assumption: message continues around the ring even if a process along the way has crashed.

Background: any process P_i sends a message to the current coordinator; if no response in T time units, P_i initiates an election

initialize active list to empty.
Send an “Elect(i)” message to the right. + add i to active list.

If a process receives an “Elect(j)” message

(a) this is the first message sent or seen

initialize its active list to [i,j]; send “Elect(i)” + send “Elect(j)”

(b) if i != j, add i to active list + forward “Elect(j)” message to active list

=> choose highest process ID + send “Elected (x)” message to neighbor

If a process receives “Elected(x)” message,

set coordinator to x

Example:

Suppose that we have four processes arranged in a ring: P1 à P2 à P3 à P4 à P1 …

P4 is coordinator

Suppose P1 + P4 crash

Suppose P2 detects that coordinator P4 is not responding

P2 sets active list to [ ]

P2 sends “Elect(2)” message to P3; P2 sets active list to [2]

P3 receives “Elect(2)”

This message is the first message seen, so P3 sets its active list to [2,3]

P3 sends “Elect(3)” towards P4 and then sends “Elect(2)” towards P4

The messages pass P4 + P1 and then reach P2

P2 adds 3 to active list [2,3]

P2 forwards “Elect(3)” to P3

P2 receives the “Elect(2) message

P2 chooses P3 as the highest process in its list [2, 3] and sends an “Elected(P3)” message
P3 receives the “Elect(3)” message

P3 chooses P3 as the highest process in its list [2, 3] + sends an “Elected(P3)” message

Byzantine Generals Problem

Intuition: Only want to proceed with the plan of attack if they are sure everyone else agrees

Can't trust other generals.

-If generals can't trust one another they can never be sure if they should attack.

Return to Contents

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.3