Summary: For an unweighted undirected graph \(G = (V,E)\), and a pair of positive integers \(\alpha\geq 1\), \(\beta \geq 0\), a subgraph \(G' = (V,H)\), \(H \subseteq E\), is called an \((\alpha,\beta)\)-spanner of \(G\) if for every pair of vertices \(u,v \in V\), \(\mathrm{dist}_{G'}(u,v) \leq \alpha\cdot \mathrm{dist}_G(u,v) + \beta\).{ }It was shown by the first author and D. Peleg [SIAM J. Comput. 33, No. 3, 608–631 (2004; Zbl 1056.05134)] that for any \(\epsilon > 0\), \(\kappa = 1,2,\ldots\), there exists an integer \(\beta = \beta(\epsilon,\kappa)\) such that for every \(n\)-vertex graph \(G\) there exists a \((1+\epsilon,\beta)\)-spanner \(G'\) with \(O(n^{1+1/\kappa})\) edges. An efficient distributed protocol for constructing \((1+\epsilon,\beta)\)-spanners was devised by the first author [“Computing almost shortest paths”, in: Proceedings of the 20th ACM symposium on principles of distributed computing. New York, NY: ACM Press. 53–62 (2001)]. The running time and the communication complexity of that protocol are \(O(n^{1+\rho})\) and \(O(|E|n^{\rho})\), respectively, where \(\rho\) is an additional control parameter of the protocol that affects only the additive term \(\beta\).{ }In this paper we devise a protocol with a drastically improved running time (\(O(n^{\rho})\) as opposed to \(O(n^{1+\rho})\)) for constructing \((1+\epsilon,\beta)\)-spanners. Our protocol has the same communication complexity as the protocol of [the first author, loc. cit.], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [the first author, loc. cit.]. The protocol can be easily extended to a parallel implementation which runs in \(O(\log n + (|E|\cdot n^{\rho}\log n)/p)\) time using \(p\) processors in the EREW PRAM model. In particular, when the number of processors, \(p\), is at least \(|E|\cdot n^{\rho}\), the running time of the algorithm is \(O(\log n)\). We also show that our protocol for constructing \((1+\epsilon,\beta)\)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and \(O(n^{1+1/\kappa}\cdot \log n)\) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor \((1+\epsilon)\) and an additive term of \(\beta\) greater than the shortest paths. Our algorithm processes each edge in time \(O(n^{\rho})\), for an arbitrarily small \(\rho>0\). The only previously known algorithm for the problem [J. Feigenbaum et al., Lect. Notes Comput. Sci. 3142, 531–543 (2004; Zbl 1099.68679)] constructs paths of length \(\kappa\) times greater than the shortest paths, has the same space requirements as our algorithm, but requires \(O(n^{1+1/\kappa})\) time for processing each edge of the input graph. However, the algorithm of [J. Feigenbaum et al., loc. cit.] uses just one pass over the input, as opposed to the constant number of passes in our algorithm.{ }We also show that any streaming algorithm for \(o(n)\)-approximate distance computation requires \(\Omega(n)\) bits of space.