Asynchronous Resource Discovery
A Scalable and Dynamic Network Topology and Service
Part Ⅰ Introduction
Origin
We need a scalable technique in distributed message system, it may be summarized as follows
Self-Organization
The resulting network is self-constructed and decentralized
Dynamic
Each node can join or leave the network at any time
Robustness
Dealing with node failure and fault-tolerance
All roads lead to Rome?
Paxos / Zab
A family of protocols for solving distributed consensus
Totem
Single-ring ordering and membership protocol
Leader election
A series of classic distributed algorithms
Resource discovery
A series of algorithms about how to discover each other
Gossip
A class of algorithms are built upon a gossip or rumor style unreliable, asynchronous information exchange protocol
Paxos
Quorums principle - 2N+1
Two-phase protocol agreed value
Dueling proposers and leadership
Zab – Atomic broadcast protocol
Stricter ordering guarantee than Paxos
The main difference is that Zab is designed for primary-backup system, like Zookeeper, rather than for state machine replication.
Totem
Virtual synchrony
Group membership
Group broadcast
Total order is guaranteed
Protocol
Total-ordering protocol
Agreed Order
Safe Order
Membership protocol
Recovery protocol
Simple and Lightweight Algorithms
Leader election
LCR algorithm – 〖Ο(𝑛^2 )〗^
HS algorithm improved it - Ο(𝑛 log𝑛 )
Bully algorithm - Ο(𝑛^2 )
Resource discovery
The common first step in distributed system
Who on the network wants to cooperate with me?
Gossip algorithms
This is an amazing algorithm!
reliable communication is not assumed
robust against node failures and changes in topology
And it seems very simple
Just exchange information between each other periodically and randomly
Performance
How to measure it?
Time complexity
The number of rounds until all the required outputs are produced, or until the processes all halt
Message complexity
The total number of messages have been sent throughout the execution
Pointer complexity
The number of bits in the message
Problem Definition
Asynchronous resource discovery
Exactly one node in every weakly connected component is designated as leader
The leader node knows the ids of all the nodes in its component
All nodes know the id of their leader
Gossip-based membership
An inexpensive membership management
A small and partial, but more accurate view of membership rather than whole view of membership
The result is a decentralized topology with good connectivity and robustness, and low diameter
Resource Discovery
Previous Work
Flooding algorithm : Ω(d 𝑖𝑛𝑖𝑡𝑖𝑎𝑖𝑙·m 𝑖𝑛𝑖𝑡𝑖𝑎𝑖𝑙)
A machine is initially configured to have a fixed set of neighbors machines, and direct communication is only allowed with machines in this set
Swamping algorithm: Ω(n²)
It is similar to flooding, but it may swap with all current neighbors
Random Pointer Jump: (num. rounds) · n
One kind of “pull style” gossiping algorithm
Name-Dropper: O(n log² n)
One kind of “push style” gossiping algorithm
Generic Algorithm
Union-Find
find( A ) - finds what set A belongs to
union( A, B ) - merge A’s set with B’s set
union by rank
path compression
Basic algorithm
Find an unexplored node u
Reach the current leader, l, of node u
Merge l into v
Inform all of l’s nodes of their new leader
Asynchronous Resource Discovery
Each node begins in state ‘explore’ and during its execution may change its state to ‘wait’ and then
‘conqueror’, ‘passive’, ‘conquered’ or ‘inactive’. A diagram with all the state transition is shown in Figure 1.
We will call a node leader if its state is not ‘conquered’ or ‘inactive’ or ‘passive’. Thus the state of a leader
node is ‘explore’ or ‘wait’ or ‘conqueror’. Each node maintains five sets of ids: local, done, more, unaware,
and unexplored, a FIFO queue previous, two id pointers: id, and next, and one integer: phase. The id
field holds the node’s unique id. Initially local holds the set of ids the node initially knows. The set more
initially contains the element {id}, next = id, phase = 1, the sets done, unaware, unexplored, and the
queue previous are empty.
Complexity
Generic Algorithm ⟶ Ο(𝑛 log𝑛 )
Bounded, and the Ad-hoc algorithms ⟶ Ο(𝑛𝛼(𝑛,𝑛))
‘query’ and ‘query reply’ messages ⟶ at most 4𝑛
‘search’ and ‘release’ messages ⟶ Ο(𝑛𝛼(𝑛,𝑛))
‘merge accept’, ‘merge fail’, and ‘info’ messages ⟶ at most 2𝑛
‘conquer’, ‘more/done’ messages ⟶ at most 2𝑛∙log𝑛 in the Generic Algorithm, and at most 2𝑛 in the Bounded model.