1
$\begingroup$

Going through Lamport's paper, I'm a little confused by the second part of the regular set of neighbors definition.

  1. A set of nodes $\{i_1, \ldots, i_p\}$ is said to be a regular set of neighbors of a node if :
    1. each $i_j$ is a neighbor of $i$, and
    2. for any general $k$ different from $i$, there exist paths $y_j,_k$ from $i_j$ to $k$ not passing through $i$ such that any two different paths $y_i,_k$ have no node in common other than $k$.
  2. The graph $G$ is said to be $p$-regular if every node has a regular set of neighbors consisting of $p$ distinct nodes.

I'm assuming $i_j$ is a node in the set. Is it right to assume $k$ is any other node not $i$ or any node not $i$ and not in the set? Also, is it saying that every $y_j,_k$ path will not have a common node or that there must be some $y_j,_k$ paths that don't share a common node?

I put the example graph from Lamport's paper with some labels on the nodes (that was edited with a track pad. Sorry!) just in case it'll help give an explaination. Any and all help is much appreciated!

enter image description here

$\endgroup$
  • $\begingroup$ (1) $k$ is any node different from $i$. Not necessarily in $\{i_1,\ldots,i_p\}$. (2) For every $1 \leq j_1 < j_2 \leq p$, the paths $y_{j_1,k},y_{j_2,k}$ intersect only in $k$. $\endgroup$ – Yuval Filmus Oct 17 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.