This is related to trying to resolve the currently faulty second part of my answer to this question, but is by itself a purely real analysis question.
Let $X$ be a set with a uniform structure presented by a function $f:X^2 \rightarrow [0,1]$ satisfying the following conditions:
- $f(x,x) = 0$
- $f(x,y) = f(y,x)$
- For some fixed parameter $1 < \beta \leq 2$, $f(x_0,x_3)\leq \beta \max(f(x_0 ,x_1 ),f(x_1 ,x_2),f(x_2,x_3))$.
It's clear that the sets $\{(x,y)\in X^2 : f(x,y) < \varepsilon\}$ generate a (pseudo-)uniformity on the set $X$. (I say 'pseudo-' because we haven't guaranteed that points are separated by $f$ but it's not really important for this question.)
Let $f_1(x,y) = f(x,y)$ and for $k>1$, let
$$f_k(x,y) = \inf_{z_1,\dots,z_{k-1}} f(x,z_1)+f(z_1,z_2) + \dots + f(z_{k-1},y) .$$
It's clear that $f_k(x,x)=0$, $f_k(x,y)=f_k(y,x)$, and $0\leq f_{k+1}(x,y)\leq f_k(x,y) \leq f(x,y) \leq 1$. This last one implies that the sequence $f_k(x,y)$ is monotonically decreasing and bounded from below and so converges for any $x,y$. Let $d(x,y)=\lim_{k\rightarrow \infty}f_k(x,y)$. It's clear that $d(x,x)=0$, $d(x,y)=d(y,x)$, and $0 \leq d(x,y) \leq f_k(x,y) \leq 1)$. It's also fairly clear that $d(x,y)$ obeys the triangle inequality so in particular it is a pseudo-metric.
You can show with an argument similar to the one around page 16 of this document (page 18 according to the pdf) that $\beta^{-1} f(x,y) \leq d(x,y) \leq f(x,y)$, so $d(x,y)$ induces the same (pseudo-)uniform structure on $X$ as $f$ does. (In the document $\beta = 2$.)
What would allow me to resolve the other question is the sequence $f_k$ converging uniformly. I've gone back and forth on how I feel it's going to turn out for a while now but I can neither prove it nor provide a counterexample. So the question is
Under what conditions does the sequence $f_k$ converge uniformly?
The best I've been able to do is under the assumption that $\beta < \sqrt{2}$ which ends up implying that the chains witnessing the values of $f_k(x,y)$ are very 'clumpy' in that there's a single $f(z_i,z_{i+1})$ which accounts for 'most' of the value of $f_k(x,y)$, but the bound on $f_{k+1}$ in terms of $f_k$ I can compute from this seems to be too marginal to get uniform convergence.
EDIT: This is adapted from this document.
Lemma. If $1 < \beta \leq 2$ then $f(x,y) \leq \beta d(x,y)$.
Proof. We will show that $f(x,y) \leq \beta f_k(x,y)$ for every $k$.
Clearly this is true for $f_1(x,y)=f(x,y)$, since $\beta >1$. Assume that we have shown this result for all $\ell<k$.
Let $z_1,\dots,z_{k-1}$ be some chain and let $z_0 = x$ and $z_k = y$. Let $r=\sum_{i<k} f(z_i,z_{i+1})$.
Find $m<k$ maximal such that $\sum_{i<m} f(z_i,z_{i+1}) \leq \frac{r}{2}$. (It may be the case that $m=0$.) Note that since $m$ is chosen maximally, it must also be the case that $\sum_{m<i<k} f(z_i,z_{i+1})\leq \frac{r}{2}$. Also it's certainly the case that $f(z_m,z_{m+1})\leq r$. By the induction hypothesis $$f(z_0,z_m)\leq \beta f_m(z_0,z_m) \leq \beta \sum_{i<m} f(z_i,z_{i+1})\leq \beta \frac{r}{2}$$ and $$ f(z_{m+1},z_k) \leq \beta f_{k-m-1}(z_{m+1},z_k) \leq \beta \sum_{m<i<k} f(z_i,z_{i+1}) \leq \beta \frac{r}{2}.$$
So now we can apply the assumed inequality to get $$f(z_0,z_k)\leq \beta \max(f(z_0,z_m),f(z_m,z_{m+1}),f(z_{m+1},z_k)) \leq \beta \max(\beta \frac{r}{2},r).$$
Since $\beta\leq 2$, $\beta\frac{r}{2}\leq r$, so we get $f(x,y)=f(z_0,z_k)\leq \beta r$. Since this is true for any such chain we get $f(x,y)\leq \beta f_k(x,y)$, as required. So by induction this is true for all $k$ and we get $f(x,y) \leq \beta d(x,y)$. $\Box$