The ALICE experiment is preparing a major upgrade of its inner silicon tracker (the Inner Tracking System) and of its Online and Offline systems for the upcoming Run3 of the LHC starting in 2021.

During Run3, LHC will deliver Pb-Pb collisions at $\sqrt{s_{NN}}\,=\,5.5$ TeV with a peak luminosity $\mathcal{L}\,=\,6\times10^{27}cm^{-2}s^{-1}$ and an interaction rate of 50 kHz, to be compared to the 8 kHz design interaction rate currently delivered by the LHC. The aim of ALICE is to cope with such a high interaction rate improving at the same time the resolution and the efficiency of the silicon tracker. In this context, one of the requirements for a prompt calibration of external detectors and to speed up the offline data processing is to run online the reconstruction of tracks in the Upgraded Inner Tracking System.

A new algorithm based on Cellular Automata has been developed to tackle this issue. In this algorithm the tracking is split in multiple phases to profit from data locality. At first, hit points are organised in sectors of azimuthal angle and longitudinal coordinate; then the algorithm looks for track segments within these sectors of the detector, independently. Track segments with compatible track parameters are marked as neighbours. Neighbouring track segments are then merged at the final stage using a set of rules defined by the Cellular Automaton mechanism, somewhat similar to the set of rules used in the Conway's Game of Life.

The obtained computing and tracking performance are compliant with the requirements of ALICE, being able to reconstruct tracks of transverse momentum down to 100 MeV$/c$ in events with high track density ($\mathrm{d}N/\mathrm{d}\eta$ up to 2000). The tracking and computing performance of this algorithm will be shown in the case of central Pb-Pb events at $\sqrt{s_{NN}}\,=\,5.5$ TeV.