How to address dependencies when publishing a chain of papers
Dependencies like these are a great place to use preprints.
The arXiv is usually a good preprint server for computer science research (other fields use others, like bioRxiv, ChemRxiv, etc). Your preprint can go up immediately, and then it's publicly available with a DOI for citation ever after.
This both clearly establishes ordering and allows paper B to cite paper A in its preprint form. Even if paper B makes it all the way to publication before paper A, the preprint can be linked to the final form after paper A is published, which indexing and citation services use to consolidate the versions together.
Finally, most journals allow preprints these days, and some even force you to use them, so in most circumstances there is no downside to posting a preprint.