TERMINOLOGY AND BASIC ALGORITHMS

Table of Content

• Chapter 5: Terminology and Basic Algorithms
  
• Assignment 5: Spanning tree

Chapter 5: Terminology and Basic Algorithms

Topology Abstraction and Overlays

·        System: undirected (weighted) graph (N, L), where n = |N|, l = |L|

·        Physical topology

Ø  Nodes: network nodes, routers, all end hosts (whether participating or not)

Ø  Edges: all LAN, WAN links, direct edges between end hosts

Ø  E.g., Fig. 5.1(a) topology + all routers and links in WANs

·        Logical topology (application context)

Ø  Nodes: end hosts where application executes

Ø  Edges: logical channels among these nodes

All-to-all fully connected (e.g., Fig 5.1(b)) or any subgraph thereof, e.g., neighborhood view, (Fig 5.1(a)) – partial system view, needs multi-hop paths, easy to maintain

·        Superimposed topology (a.k.a. topology overlay):

Ø  superimposed on logical topology

Ø  Goal: efficient information gathering, distribution, or search (as in P2P overlays)

Ø  e.g., ring, tree, mesh, hypercube

Topology Abstractions

Figure 5.1: Example topology views at different levels of abstraction

Classifications and Basic Concepts (1)

·        Application execution vs. control algorithm execution, each with own events

o  Control algorithm:

§  for monitoring and auxiliary functions, e.g., creating a ST, MIS, CDS, reaching consensus, global state detection (deadlock, termination etc.), checkpointing

§  superimposed on application execution, but does not interfere

§  its send, receive, internal events are transparent to application execution

§  a.k.a. protocol

·        Centralized and distributed algorithms

o  Centralized: asymmetric roles; client-server configuration; processing and bandwidth bottleneck; point of failure

o  Distributed: more balanced roles of nodes, difficult to design perfectly distributed algorithms (e.g., snapshot algorithms, tree-based algorithms)

·        Symmetric and asymmetric algorithms

Classifications and Basic Concepts (2)

·        Anonymous algorithm: process ids or processor ids are not used to make any execution (run-time) decisions

§   Structurally elegant but hard to design, or impossible, e.g., anonymous leader election is impossible

·        Uniform algorithm: Cannot use n, the number of processes, as a parameter in the code

§   Allows scalability; process leave/join is easy and only neighbors need to be aware of logical topology changes

·        Adaptive algorithm: Let k (≤ n) be the number of processes participating in the context of a problem X when X is being executed. Complexity should be expressible as a function of k, not n.

§   E.g., mutual exclusion: critical section contention overhead expressible in terms of number of processes contending at this time (k)

Classifications and Basic Concepts (3)

·        Deterministic vs. nondeterministic executions

o  Nondeterministic execution: contains at least 1 nondeterministic receive; deterministic execution has no nondeterministic receive

§ Nondeterministic receive: can receive a message from any source

§ Deterministic receive: source is specified

Difficult to reason with

o  Asynchronous system: re-execution of deterministic program will produce same partial order on events ((used in debugging, unstable predicate detection etc.)

o  Asynchronous system: re-execution of nondeterministic program may produce different partial order (unbounded delivery times and unpredictable congestion, variable local CPU scheduling delays)

Classification and Basic Concepts (4)

·        Execution inhibition (a.k.a. freezing)

Protocols that require suspension of normal execution until some stipulated operations occur are inhibitory

Ø Concept: Different from blocking vs. nonblocking primitives

Ø Analyze inhibitory impact of control algo on underlying execution

Ø Classification 1:

§  Non-inhibitory protocol: no event is disabled in any execution

§  Locally inhibitory protocol: in any execution, any delayed event is a locally delayed event, i.e., inhibition under local control, not dependent on any receive event

§  Globally inhibitory: in some execution, some delayed event is not locally delayed

Ø Classification 2: send inhibitory/ receive inhibitory/ internal event inhibitory

Classifications and Basic Concepts (5)

·        Synchronous vs. asynchronous systems

Ø Synchronous:

§ upper bound on message delay

§ known bounded drift rate of clock wrt. real time

§ known upper bound for process to execute a logical step

Ø Asynchronous: above criteria not satisfied spectrum of models in which some combo of criteria satisfied

Algorithm to solve a problem depends greatly on this model Distributed systems inherently asynchronous

·        On-line vs. off-line (control) algorithms

§  On-line: Executes as data is being generated Clear advantages for debugging, scheduling, etc.

§  Off-line: Requires all (trace) data before execution begins

Classification and Basic Concepts (6)

·        Wait-free algorithms (for synchronization operations)

§  resilient to n − 1 process failures, i.e., ops of any process must complete in bounded number of steps, irrespective of other processes

§  very robust, but expensive

§  possible to design for mutual exclusion

§  may not always be possible to design, e.g., producer-consumer problem

·        Communication channels

§  point-to-point: FIFO, non-FIFO At application layer, FIFO usually provided by network stack

Classifications and Basic Concepts (7)

·        Process failures (sync + async systems) in order of increasing severity

§  Fail-stop: Properly functioning process stops execution. Other processes learn about the failed process (thru some mechanism)

§  Crash: Properly functioning process stops execution. Other processes do not learn about the failed process

§  Receive omission: Properly functioning process fails by receiving only some of the messages that have been sent to it, or by crashing.

§  Send omission: Properly functioning process fails by sending only some of the messages it is supposed to send, or by crashing. Incomparable with receive omission model.

§  General omission: Send omission + receive omission

§  Byzantine (or malicious) failure, with authentication: Process may (mis) behave anyhow, including sending fake messages.

Authentication facility =⇒ If a faulty process claims to have received a message from a correct process, that is verifiable.

§  Byzantine (or malicious) failure, no authentication

The non-malicious failure models are ”benign”

Classifications and Basic Concepts (8)

·        Process failures (contd.) → Timing failures (sync systems):

§ General omission failures, or clocks violating specified drift rates, or process violating bounds on time to execute a step

§ More severe than general omission failures

Failure models influence design of algorithms

·        Link failures

§ Crash failure: Properly functioning link stops carrying messages

§ Omission failure: Link carries only some of the messages sent on it, not others

§ Byzantine failure: Link exhibits arbitrary behavior, including creating fake messages and altering messages sent on it

·Link failures → Timing failures (sync systems): messages delivered faster/slower than specified behavior

Complexity Measures and Metrics

·       Each metric specified using lower bound (Ω), upper bound (O), exact bound (θ)

·        Metrics

§ Space complexity per node

§ System-wide space complexity (6= n · space complexity per node). E.g., worst case may never occur at all nodes simultaneously!

§ Time complexity per node

§ System-wide time complexity. Do nodes execute fully concurrently?

§ Message complexity

o  Number of messages (affects space complexity of message ovhd)

o  Size of messages (affects space complexity of message ovhd + time component via increased transmission time)

o  Message time complexity: depends on number of messages, size of messages,

concurrency in sending and receiving messages

§ Other metrics: # send and # receive events; # multicasts, and how implemented?

§ (Shared memory systems): size of shared memory; # synchronization operations

Program Structure

·        Communicating Sequential Processes (CSP) like:

                                    ∗ [ G1 −→ CL1 || G2 −→ CL2 || · · · || Gk −→ CLk ]

·        The repetitive command “*” denotes an infinite loop.

·        Inside it, the alternative command ‘||” is over guarded commands. Specifies execution of exactly one of its constituent guarded commands.

·        Guarded command syntax: “G −→ CL” guard G is boolean expression, CL is list of commands to be executed if G is true. Guard may check for message arrival from another process.

·        Alternative command fails if all the guards fail; if > 1 guard is true, one is nondeterministically chosen for execution.

·        G_m −→ CL_m: CL_m and G_m atomically executed.

Basic Distributed Graph Algorithms: Listing

·        Sync 1-initiator ST (flooding)                                   

·        Async 1-initiator ST (flooding)

·        Async conc-initiator ST (flooding)

·        Async DFS ST

·        Broadcast & convergecast on tree

·        Sync 1-source shortest path

·        Distance Vector Routing

·        Async 1-source shortest path

·        All sources shortest path:

·        Floyd-Warshall

·        Sync, async constrained flooding

·        MST, sync

·        MST, async

·        Synchronizers: simple, α, β, γ

·        MIS, async, randomized

·        CDS

·        Compact routing tables

·        Leader election: LCR algorithm

·        Dynamic object replication

Sync 1-initiator ST (flooding)

Synchronous 1-init Spanning Tree: Example

Figure 5.2: Tree in boldface; round numbers of QUERY are labeled

·        Designated root. Node A in example.

·        Each node identifies parent

·        How to identify child nodes?

Synchronous 1-init Spanning Tree: Complexity

Termination: after diameter rounds.

How can a process terminate after setting its parent?

Complexity:

·        Local space: O(degree)

·        Global space: O(∑local space)

·        Local time: O(degree + diameter)

·        Message time complexity: d rounds or message hops

·        Message complexity: ≥ 1, ≤ 2 messages/edge. Thus, [l, 2l]

Spanning tree: analogous to breadth-first search

 

Async 1-init Spanning Tree: Operation

·        root initiates flooding of QUERY to identify tree edges

·        parent: 1st node from which QUERY received

Ø ACCEPT (+ rsp) sent in response; QUERY sent to other nbhs

Ø Termination: when ACCEPT or REJECT (- rsp) received from non-parent nbhs. Why?

·        QUERY from non-parent replied to by REJECT

·        Necessary to track neighbors? to determine children and when to terminate?

·        Why is REJECT message type required?

·        Can use of REJECT messages be eliminated? How? What impact?

Asynchronous 1-init Spanning Tree: Complexity

Local termination: after receiving ACCEPT or REJECT from non-parent nbhs.

Complexity:

·        Local space: O(degree)

·        Global space: O(∑ local space)

·        Local time: O(degree)

·        Message complexity: ≥ 2, ≤ 4 messages/edge. Thus, [2l, 4l]

·        Message time complexity: d + 1 message hops.

Spanning tree: no claim can be made. Worst case height n − 1

Asynchronous 1-init Spanning Tree: Example

Figure 5.3: Tree in boldface; Number indicates approximate order in which QUERY get sent

·        Designated root. Node A in example.

·        tree edges: QUERY + ACCEPT msgs

·        cross-edges and back-edges: 2(QUERY + REJECT) msgs

Asynchronous Spanning Tree: Concurrent Initiators

Figure 5.4: Concurrent initiators A,G,J No pre-designated root:

·        Option 1: Merge partial STs. Difficult based on local knowledge, can lead to cycles

·        Option 2: Allow one ST computation instance to proceed; supress others.

§  Used by algorithm; selects root with higher process id to continue

§  3 cases: newroot < = > myroot

Algorithm:

·        A node may spontaneously initiate algorithm and become ”root”.

·        Each ”root” initiates variant of 1-init algorithm; lower priorities suppressed at intermediate nodes

·        Termination: Only root detects termination. Needs to send extra messages to inform others.

·        Time complexity: O(l)

·        Message complexity: O(nl)

Asynchronous Spanning Tree: Code (1/2)

Asynchronous Spanning Tree: Code (2/2)

Asynchronous DFS Spanning Tree

·        Handle concurrent initiators just as for the non-DFS algorithm, just examined

·        When QUERY, ACCEPT, or REJECT arrives: actions depend on whether myroot < = newroot

·        Termination: only successful root detects termination. Informs others using ST edges.

·        Time complexity: O(l)

·        Message complexity: O(nl)

Asynchronous DFS Spanning Tree: Code

Broadcast and Convergecast on a Tree (1)

Figure 5.5: Tree structure for broadcast and convergecast

Question:

·        how to perform BC and CC on a ring? on a mesh?

·        Costs?

Broadcast and Convergecast on a Tree (2)

Broadcast: distribute information

BC1. Root sends info to be broadcast to all its children. Terminate.

BC2. When a (nonroot) node receives info from its parent, it copies it and forwards it to its children. Terminate.

Convergecast: collect info at root, to compute a global function

CVC1. Leaf node sends its report to its parent. Terminate.

CVC2. At a non-leaf node that is not the root: When a report is received from all the child nodes, the collective report is sent to the parent. Terminate.

CVC3. At root: When a report is received from all the child nodes, the global function is evaluated using the reports. Terminate.

Uses: compute min, max, leader election, compute global state functions

Time complexity: O(h); Message complexity: n − 1 messages for BC or CC

Single Source Shortest Path: Sync Bellman-Ford

·        Weighted graph, no cycles with negative weight

·        No node has global view; only local topology

·        Assumption: node knows n; needed for termination

·        After k rounds: length at any node has length of shortest path having k hops

·        After k rounds: length of all nodes up to k hops away in final MST has stabilized

·        Termination: n − 1 rounds

·        Time Complexity: n − 1 rounds

·        Message complexity: (n − 1) · l messages

Sync Distributed Bellman-Ford: Code

Distance Vector Routing

·        Used in Internet routing (popular upto to mid-1980s), having dynamically changing graph, where link weights model delay/ load

·        Variant of sync Bellman-Ford; outer for loop is infinite

·        Track shortest path to every destination

·        length replaced by LENGTH[1..n]; parent replaced by PARENT[1..n]

·        kth component denotes best-known length to LENGTH[k]

·        In each iteration

§ apply triangle inequality for each destination independently

§ Triangle inequality: (LENGTH[k] > (LENGTH_j[k] + weight_j,i)

§ Node I estimates weightij using RTT or queuing delay to neighbor j

Single Source Shortest Path: Async Bellman-Ford

·        Weighted graph, no cycles with negative weight

·        No node has global view; only local topology

·        exponential Ω(cⁿ) number of messages and exponential Ω(cⁿ· d) time complexity in the worst case, where c is some constant

·        If all links have equal weight, the algorithm computes the minimum-hop path; the minimum-hop routing tables to all destinations are computed using O(n²·l) messages

Async Distributed Bellman-Ford: Code

 All-All Shortest Paths: Floyd-Warshall

 

Figure 5.6: (a) Triangle inequality for Floyd-Warshall algorithm. (b) VIA relationships along a branch of the sink tree for a given (s,t) pair

All-All Shortest Paths: Floyd-Warshall

After pivot iterations of the outer loop,

Invariant

“LENGTH[i, j] is the shortest path going through intermediate nodes from the set {i, . . . , pivot}. VIA[i, j] is the corresponding first hop. ”

Complexity (centralized): O(n³)

Distributed Floyd-Warshall (1)

·        Row i of LENGTH[1..n, 1..n], VIA[1..n, 1..n] stored at i, which is responsible for updating the rows. (So, i acts as source.)

·        Corresponding to centralized algorithm, line (4):

Ø How does node i access remote datum LENGTH[pivot,t] in each iteration pivot?

§  Distributed (dynamic) sink tree: In any iteration pivot, all nodes s | LENGTH[s,t] ≠ ∞ are on a sink tree, with sink at t

Ø How to synchronize execution of outer loop iteration at different nodes? (otherwise, algorithm goes wrong).

§  Simulate ”synchronizer”: e.g., use receive to get data LENGTH[pivot, ∗] from parent on sink tree

Distributed Floyd-Warshall: Data structures

 Distributed Floyd-Warshall: Code

Distributed Floyd-Warshall: Dynamic Sink Tree

Rename LENGTH[i, j], VIA[i, j] as LEN[j], PARENT[j] in distributed algorithm =⇒ LENGTH[i, pivot] is LEN[pivot]

At any node i, in iteration pivot:

·        iff LEN[pivot] 6= ∞ at node i, then pivot distributes LEN[∗] to all nodes (including i) in sink tree of pivot

·        Parent-child edges in sink tree need to be IDed. How?

§ A node sends IN TREE to PARENT[pivot]; NOT IN TREE to other neighbors

§ Receive IN TREE from k =⇒ k is a child in sink tree of pivot

·        Await IN TREE or NOT IN TREE from each neighbor.

This send-receive is synchronization!

·        pivot broadcasts LEN[∗] down its sink tree.

         This send-receive is synchronization!

·        Now, all nodes execute triangle inequality in pseudo lock-step

Time Complexity: O(n²) execution/node, + time for n broadcasts Message complexity: n iterations;

·        2 IN TREE or NOT IN TREE msgs of size O(1) per edge: O(l) msgs

·        ≤ n − 1 PIV LEN msgs of size O(n): O(n) msgs

Total O(n(l + n)) messages; Total O(nl + n³) message space

Distributed Floyd-Warshall: Sink Tree

Figure 5.7: Identifying parent-child nodes in sink tree

Constrained Flooding (no ST)

·        FIFO channels; duplicates depected using seq. nos.

·        Asynchronous flooding:

§ used by Link State Routing in IPv4

§ Complexity: 2l messages worst case; Time: d sequential hops

·        Synchronous flooding (to learn one datum from each processor):

§ STATEVEC[k] is estimate of k’s datum

§ Message complexity: 2ld messages, each of size n

§ Time complexity: d rounds

Async Constrained Flooding (no ST)

Sync Constrained Flooding (no ST)

Algorithm learns all nodes identifiers

Minimum Spanning Tree (MST): Overview

Assume undirected weighted graph. If weights are not unique, assume some tie-breaker such as nodeIDs are used to impose a total order on edge weights.

·        Review defns: forest, spanning forest, spanning tree, MST

·        Kruskal’s MST:

§ Assume forest of graph components

§ maintain sorted list of edges

§ In each of n − 1 iterations, identify minimum weight edge that connects two different components

§ Include the edge in MST

§ O(l log l)

·        Prim’s MST:

§ Begin with a single node component

§ In each of n − 1 iterations, select the minimum weight edge incident on the component. Component expands using this selected edge.

§ O(n²) (or O(n log n) using Fibonacci heaps in dense graphs)

GHS Synchronous MST Algorithm: Overview

Gallagher-Humblet-Spira distributed MST uses Kruskal’s strategy. Begin with forest of graph components.

·        MWOE (minimum weight outgoing edge): ”outgoing” is logical, i.e., indicates direction of expansion of component

·        Spanning trees of connected components combine with the MWOEs to still retain the spanning tree property in combined component

·        Concurrently combine MWOEs:

§ after k iterations, ≤components =⇒ at most log n iterations

·        Each component has a leader node in an iteration

·        Each iteration within a component has 5 steps, triggered by leader

§ broadcast-convergecast phase: leader identifies MWOE

§ broadcast phase: (potential) leader for next iteration identified

§ broadcast phase: among merging components, 1 leader is selected; it identifies itself to all in the new component

Minimum Weight Outgoing Edge: Example

Figure 5.8: Merging of MWOE components. (a) Cycle len = 2 possible. (b) Cycle len > 2 not possible.

Observation 5.1

For any spanning forest {(N_i, L_i)| i = 1 . . . k} of graph G, consider any component (N_j, L_j). Denote by λj, the edge having the smallest weight among those that are incident on only one node in Nj. Then an MST for G that includes all the edges in each L_i in the spanning forest, must also include edge λi.

MST Example

Figure 5.9: Phases within an iteration in a component.

(a) Root broadcasts SEARCH MWOE;

(b) Convergecast REPLY MWOE occurs.

(c) Root broadcasts ADD MWOE;

(d) If the MWOE is also chosen as the MWOE by the component at the other end of the MWOE, the incident process with the higher ID is the leader for the next iteration; and broadcasts NEW LEADER.

Sync GHS: Message Types

Sync GHS: Code

GHS: Complexity

·        log n rounds (synchronous)

·        Time complexity: O(n log n)

·        Message complexity:

Ø  In each iteration, O(n) msgs along tree edges (steps 1,3,4,5)

Ø  In each iteration, l EXAMINE msgs to determine MWOEs

Hence, O((n + l) · log n) messages

·        Correctness requires synchronous operation

Ø  In step (2), EXAMINE used to determine if unmarked neighbor belongs to same component. If nodes of an unmarked edge are in different levels, problem!

Ø  Consider EXAMINE sent on edge (j, k), belonging to same component. But k may not have learnt it belongs to new component and new leader ID; and replies +ve

Ø  Can lead to cycles.

MST (asynchronous)

·        Synchronous GHS simulated using extra msgs/steps.

Ø New leader does BC/CC on marked edges of new component.

§  In Step (2), recipient of EXAMINE can delay response if in old round

§  n · log n extra messages overall

Ø On involvement in a new round, inform each neighbor

§  Send EXAMINE when all nbhs along unmarked edges in same round

§  l · log n extra messages overall

·        Engineer!! asynchronous GHS:

Ø msg O(n log n + l) time: O(n log n (l + d))

Ø Challenges

§  determine levels of adjacent nodes

§  repeated combining with singleton components =⇒ log n becomes n

§  If components at different levels, coordinate search for MWOEs, merging

Synchronizers

Definition

Class of transformation algorithms that allow a synchronous program (designed for a synchronous system) to run on asynchronous systems.

·        Assumption: failure-free system

·        Designing tailor-made async algo from scratch may be more efficient than using synchronizer

Process safety

Process i is safe in round r if all messages sent by i have been received.

Implementation key: signal to each process when it is safe to go to next round, i.e., when all msgs to be received have arrived

Synchronizers: Notation

M_a = M_s + (M_init + rounds · M_round ) (1)

T_a = T_s + T_init + rounds · T_round (2)

·        M_s: # messages in the synchronous algorithm.

·        rounds: # rounds in the synchronous algorithm.

·        T_s: time for the synchronous algorithm.

          Assuming one unit (message hop) per round, this equals rounds.

·        M_round : # messages needed to simulate a round,

·        T_round : # sequential message hops to simulate a round.

·        M_init, T_init: # messages, # sequential message hops to initialize async system.

Synchronizers: Complexity

The message and time complexities for synchronizers.

h_c is the greatest height of a tree among all the clusters.

L_c is the number of tree edges and designated edges in the clustering scheme for the synchronizer.

d is the graph diameter.

Simple Synchronizer

·        A process sends each neighbor 1 message/round

 Combine messages or send dummy message

·        On receiving a msg from each neighbor, go to next round.

·        Neighbors P_i, P_j may be only one round apart

·        P_i in roundi can receive msg from only roundi or roundi + 1 of neighbor.

·        Initialization:

Ø  Any process may start round x.

Ø  In d time units, all processes would be in round x.

Ø  T_init = d, M_init = 0.

·        Complexity: M_round = 2|L|,T_round = 1.

α Synchronizer

·        P_i in round r moves to r + 1 if all neighbors are safe for round r.

·       When neighbor P_j receives ack for each message it sent, it informs P_i (and its other neighbors) that it is safe.

Figure 5.10: Example. (a) Execution msgs (1) and acks (2). (b) “I am safe” msgs (3).

α Synchronizer: Complexity

·        Complexity:

Ø L’ msgs ⇒ l’acks; transport layer acks ⇒free!

Ø 2|L| messages/round to inform neighbors of safety.

                        M_round = O(|L|).T_round = O(1).

·        Initialization: None. Any process may spontaneously wake up.

β Synchronizer

Initialization: rooted spanning tree, O(n log n + |L|) messages, O(n) time.

Operation:

·        Safe nodes initiate convergecast (CvgC)

·        intermediate nodes propagate CvgC when their subtree is safe.

·        When root becomes safe and receives CvgC from all children, initiates tree broadcast to inform all to move to next round.

Complexity: l’acks for free, due to transport layer.

M_round = 2(n − 1)

T_round = 2 log n average; 2n worst case

γ Synchronizer: Clusters

·        Set of clusters; each cluster has a spanning tree

·        Intra-cluster: β synchronizer over tree edges

·        Inter-cluster: α synchronizer over designated inter-cluster edges. (For 2 neighboring clusters, 1 inter-cluster edge is designated.)

Figure 5.11: Cluster organization. Only tree edges and inter-cluster designated edges are shown.

γ Synchronizer: Operation and Complexity

·        Within cluster, β synchronizer executed

·        Once cluster is stabilized, α synchronizer over inter-cluster edges

·        To convey stabilization of inter-cluster α synchronizer, within a cluster, CvgC and BC phases over tree

·        This CvgC initiated by leaf nodes once neighboring clusters are stabilized.

·        M_round = O(Lc ),T_round = O(hc ).

·γ Synchronizer: Code

Maximal Independent Set: Definition

·        For a graph (N, L), an independent set of nodes N’, where N’⊂ N, is such that for each i and j in N’, (i, j) 6∈ L.

·        An independent set N’ is a maximal independent set if no strict superset of N’ is an independent set.

·        A graph may have multiple MIS; perhaps of varying sizes.

The largest sized independent set is the maximum independent set.

·        Application: wireless broadcast - allocation of frequency bands (mutex)

·        NP-complete

Luby’s Randomized Algorithm, Async System

Iteratively:

·        Nodes pick random nos, exchange with nbhs

·        Lowest number in neighborhood wins (selected in MIS)

·        If neighbor is selected, I am eliminated (⇒ safety)

·        Only neighbors of selected nodes are eliminated (⇒ correctness)

Complexity:

·        In each iteration, ≥ 1 selected, ≥ 1 eliminated ⇒ ≤ n/2 iterations.

·        Expected # iterations O(log, n) due to randomized nature.

Luby’s Maximal Independent Set: Code

Maximal Independent Set: Example

Figure 5.12: (a) Winners and losers in round 1. (b) Winners up to round 1, losers in round 2.

Third round: I is winner. MIS={C, E, G, I,K}.

Note: {A, C, G, J} is a smaller MIS.

Connected Dominating Set (CDS)

·        A dominating set of graph (N, L) is a set N’ ⊆ N | each node in N \ N’ has an edge to some node in N’.

·        A connected dominating set (CDS) of (N, L) is a dominating set N’ such that the subgraph induced by the nodes in N’ is connected.

·        NP-Complete

Ø Finding the minimum connected dominating set (MCDS)

Ø Determining if there exists a dominating set of size k < |N|

·        Poly-time heuristics: measure using approximation factor, stretch factor

Ø Create ST; delete edges to leaves

Ø Create MIS; add edges to create CDS

·        Application: backbone for broadcasts

Compact Routing Tables (1)

 

Figure 5.13: Tree label based routing tables. Tree edges labels in rectangles. Non-tree edges in dashed lines.

Avoid tables of size n – large size, more processing time

·        Hierarchical routing – hierarchical clustered network, e.g., Ipv4

·        Tree labeling schemes

Ø Logical tree topology for routing

Ø Node labels | dests reachable via link labeled by contiguous addresses [x, y]

Ø Small tables but traffic imbalance

Compact Routing Tables (2)

·          Interval routing:

Ø Node labeling: B is a 1:1 mapping on N.

Ø Edge labeling: I labels each edge in L by some subset of node labels B(N)| for any node x

§  all destinations are covered (∪y∈_NeighboursI(x, y) ∪ B(x) = N) and

§  there is no duplication of coverage (I(x, w) ∩ I(x, y) = ∅ for w, y ∈ Neighbours).

Ø For any s, t, there exists a path hs = x0, x1 . . . xk−1, xk = ti where B(t) ∈ I(xi−1, xi) for each i ∈ [1, k].

Ø Interval labeling possible for every graph!

Ø No guarantee on path lengths; not robust to topology changes.

·        Prefix routing: Node, channel labels from same domain, view as strings

Ø To route: use channel whose label is longest prefix of dest.

Compact Routing Tables (3)

Stretch factor of a routing scheme r

maxi,j∈N {}.

Designing compact routing schemes:

·        rich in graph algorithmic problems

·        Identify and prove bounds on efficiency of routes

·        Different specialized topologies (e.g., grid, ring, tree) offer scope for easier results

Leader Election

·        Defn: All processes agree on a common distinguished process (leader)

·        Distributed algorithms not completely symmetrical; need a initiator, finisher process; e.g., MST for BC and CvgC to compute global function

·        LeLang Chang Roberts (LCR) algorithm

§ Asynchronous unidirectional ring

§ All processes have unique IDs

§ Processes circulate their IDs; highest ID wins

§ Despite obvious optimizations, msg complexity n · (n − 1)/2; time complexity O(n).

·        Cannot exist deterministic leader election algorithm for anonymous rings

·        Algorithms may be uniform

Leader Election - LCR algorithm: Code

Leader Election: Hirschberg-Sinclair Algorithm

·        Binary search in both directions on ring; token-based

·        In each round k, each active process does:

Ø   Token circulated to 2^k nghbrs on both sides

Ø   P_i is a leader after round k iff i is the highest ID among 2^k nghbrs in both directions

⇒ After round k, any pair of leaders are at least 2^k apart

⇒ # leaders diminishes logarithmically as n/2^k

·           Only winner (leader) after a round proceeds to next round.

·        In each round, max n msgs sent using supression as in LCR

·        log n rounds

·        Message complexity: O(n · log n) (formulate exact expression)!

·        Time complexity: O(n).

Object Replication Problems

·        Weighted graph (N, L), k users at Nk ⊆ N nodes, r replicas of a object at N_r ⊆ N.

·        What is the optimal placement of the replicas if k > r and accesses are read-only?

·   Evaluate all choices for Nr to identify min(_{i∈Nk,ri ∈Nr} dist_i,ri), where dist_i,ri is the cost from node i to r_i, the replica nearest to i.

·        If Read accesses from each user in Nk have a certain frequency (or weight), the minimization function changes.

·        Address BW of each edge.

·        Assume user access is a Read with prob. x, and an Update with prob. 1 − x. Update requires all replicas to be updated.

·           What is the optimal placement of the replicas if k > r?

Adaptive Data Replication: Problem Formulation

Network (V, E). Assume single replicated object.

·        Replication scheme: subset R of V | each node in R has a replica.

·        r_i, w_i: rates of reads and writes issued by i

·        c_r(i), c_w (i): cost of a read and write issued by i.

·        R: set of all possible replication schemes.

·        Goal: minimize cost of the replication scheme:

        [ ri· cr(i) + wi· cw (i)]

Arbitrary graph: cost is NP-Complete

·        Hence, assume tree overlay

·        Assume one copy serializability, implemented by Read-One-Write-All (ROWA) policy.

Adaptive Data Replication over Tree Overlay

·        All communication, set R on tree T overlay

·        R: amoeba-like subgraph, moves to center-of-gravity of activity

§  Expands when Read cost is higher

§  Shrinks when Write cost is higher

§  Equilibrium-state R is optimal; converges in d + 1 steps once Read-Write pattern stabilizes

§  Dynamic activity: algorithm re-executed in epochs

·        Read: From closest replica, along T. Use parent pointers.

·        Write: To closest replica, along T. Then propagate in R.

Use R − neighbor, set of neighbors in R.

·        Implementation: (i) in R? (ii) R − neighbor, (iii) parent.

Adaptive Data Replication: Convergence (1)

Figure 5.14: Nodes in ellipse belong to R.

C is R-fringe

A, E are R-fringe and R-neighbour

D is R-neighbour

R-neighbour: i ∈ R; and has at least one neighbour j 6∈ R.

R-fringe: i ∈ R; and has only one neighbour j ∈ R. Thus, i is a leaf in the subgraph of T induced by R and j is parent of i.

singleton: |R| =1 and i ∈ R.

Adaptive Data Replication: Tests

Figure 5.15: (a) Expansion test. (b) Contraction test. (c) Switch test.

R-neighbour may also be R-fringe or singleton. In either case, the expansion test executed first; if it fails, contraction test or switch test is executed.

Tests at end of each epoch.

Expansion test: R-neighbour node i includes neighbor j in R if r > w.

Contraction test: R-fringe node i excludes itself from R if w > r.

Before exiting, seek permission from j to avoid R = ∅.

Switch test: Singleton node i transfers its replica to j if r + w being forwarded by j is greater than r + w that node I receives from all other nodes.

Adaptive Data Replication: Code (1)

Adaptive Data Replication: Code (2)

Assignment 5: Spanning tree

Show using example how a DFS spanning tree can be built on some arbitrarily connected network (with 6 nodes and at least 15 edges).

Compute the message and time complexity(?) of the DFS spanning tree.

Design the BFS spanning tree.

Read(materials from website) and design your own flooding based spanning tree.

Explain applications of Spanning Tree in distributed systems.

What do you mean by broadcast and convergecast in a distributed system. How is a spanning tree is useful for achieving these two applications?

Explain the message complexity of DFS spanning tree construction.

Explain the roles of parent and reject message in DFS spanning tree construction

Explain the role of unexplored set in DFS tree construction. Also explain how this construction is similar to using a stack in DFS algorithm for graphs.

How to create an MST in distributed system?