  We present an algorithmic embedded desingularization of arithmetic surfaces
bearing in mind implementability. Our algorithm is based on work by
Cossart-Jannsen-Saito, though our variant uses a refinement of the order
instead of the Hilbert-Samuel function as a measure for the complexity of the
singularity. We particularly focus on aspects arising when working in mixed
characteristics. Furthermore, we exploit the algorithm's natural parallel
structure rephrasing it in terms of Petri nets for use in the parallelization
environment GPI-Space with {\sc Singular} as computational back-end.
