Title: Theory / Unimportant / CS / Algo / Distributed Lynch / Synchronous Network algorithm
Tags: hasSeenConjDef

Name: Formal Synchronous network system
Definition: A directed graph whose nodes are processes and edges are link
Page: 17
Chapter: 2
Section: 1

Definition: The number of nodes.
Page: 17
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network
Notation: \(n\)

Name: A node
Definition: An element of \(V\)
Page: 17
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network

Name: The outgoing neighbors of \(i\)
Definition: the nodes to which there are edges from \(i\) in \(G\)
Page: 17
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
\(i\in V\)
Notation: \(out-nbrs_i\)

Name: The incoming neighbors of \(i\)
Definition: The nodes from which there are edges to \(i\) in \(G\)
Page: 17
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
\(i\in V\)
Abbreviation: \(in-nbrs_i\)

Name: The distance from \(i\) to \(j\)
Definition: The length of the shortest directed path from \(i\) to \(j\) in \(G\)
Page: 17
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
\(i,j\in V\)
Notation: \(distance(i,j)\)

Name: The diameter of \(G\)
Definition: the maximum \(distance(i,j)\) for \(i,j\in V\)
Page: 17
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
Abbreviation: \(diam\)

Name: A message alphabet
Page: 18
Chapter: 2
Section: 1
Denoted by: \(M\)

Definition: A set of states associated with the node \(i\)
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
\(i\in V\)
Notation: \(states_i\)

Name: The start states of \(i\)
Definition: The initial states of \(i\)
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
\(i\in V\)
Abbreviation: \(start_i\)
Cardinal: Non-empty

Name: The message-generation function
Definition: mapping \(states_i\times out-nbrs_i\) to elements of \(M\cup\{null\}\)
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
\(i\in V\)
Abbreviation: \(msgs_i\)

Name: A state transition function
Definition: A map from \(states_i\) and from vectors of elements of \(M\cup\{null\}\) to \(states_i\)
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
\(i\in V\)
Abbreviation: \(trans_i\)

Name: A process
Definition: Some \(states_i\), \(start_i\), \(msgs_i\) and \(trans_i\)
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,

Name: A channel
Definition: A location that can, at any time, holds at most a single message in \(M\)
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
Name2: A link

Name: A round
Definition: Apply the message-generation function to the current state to generate the messages to be sent to all outgoing neighbors. Put these messages in the appropriate channels.
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,
Definition2: Apply the state-transition function to the current state and the incoming messages to obtain the new state. Remove all messages from the channels.
Conjdef: In this order

Name: An halting state
Definition: A state which does not generate the message and which is its only successor
Page: 19
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,

Question: How to allow some node to starts with some delay.
Answer: Have an environment node which send a wakeup message to all other processes when they must wake up. Before, those states are in quiescent state.
Page: 19
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,

Name: A quiescent state
Definition: A state which does not generate message, and which can change only when receiving a wakeup message.
Page: 19
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,

Name: Execution of the entire system
Definition: Each process start in an arbitrary start state. Rounds are applied infinitely often.
Page: 18
Chapter: 2
Section: 1
Variables: \(G=(V,E)\) a synchronous network,