Non-Orthogonal Multiple-Access (NOMA) is a promising technology for improving spectral efficiency over conventional orthogonal multiple-access techniques. Most previous applications and implementations of NOMA have assumed a centralized environment, with only a few adopting it in distributed networks. Such distributed algorithms usually do not make full use of their power domains. Thus, the performance improvement from NOMA is rather limited. The open question is to what extent NOMA technology can speed up transmission scheduling in a distributed setting. We answer this question affirmatively by presenting an efficient distributed Age-of-Information (AoI) scheduling algorithm. Through rigorous analysis, we show that our proposed algorithm achieves a logarithmic-factor reduction of the Maximum Peak Age (MPA) over state-of-the-art approaches that do not use NOMA by better leveraging the available transmission power range. We also show that our algorithm is asymptotically optimal up to a constant factor. Extensive experiments demonstrate that our algorithm performs well in a realistic information system in terms of minimizing the maximum peak age.