Are we going to have to start using the words "classical libertarianism" soon? https://en.m.wikipedia.org/wiki/Classical_liberalism#Meaning...
Modern-day right-wing libertarianism is the new kid on the block.
Basically in the late 1800's the main split between anarchists and communists in the First International was not predominantly their end goal.
E.g. consider the famous concept of the "whithering away of the state" (coined by Friedrich Engels, but Engels attributed the idea to Marx): that given that according to Marxism the state is predominantly a tool of class rule, and that communism by their definition is the stage of society where there no longer are any classes, the state will cease to have a political purpose and will "whither away". So anarchists and communists agreed the state was a tool of oppression and that this oppression must be removed, and that the state will eventually disappear.
The split was over methods. How to get there. The anarchists generally favoured a quicker, more immediate, dismantling of the state (whether by taking control and orderly dismantling it, or by rising up and destroying it), while communists generally favoured an intermediate transitional stage. In Marxism the intermediate stage is socialism: A phase where the proletariat is meant to take control of the state (hence the "dictatorship of the proletariat" in contrast with Marx description of capitalist democracies as the "dictatorship of the bourgeoisie"), and for the first time wield it as a weapon of the majority against the minority, and use it to remove the class differences. So communists traditionally saw the state as a tool for the working class.
Eventually this lead to the split of the First International, where Marx came out victorious, and most of the anarchists left when Bakunin was thrown out. Not long after, new libertarian socialist/communist tendencies started "filling the gap" in the International left by the anarchists.
The extent of support for a strong state varied greatly amongst people who called themselves communists, leading to screeds like Lenins "Left Communism: An Infantile Disorder", which targeted exactly libertarian Communists which opposed his ideas of a vanguard.
So who runs the justice system, commands the military, and protects the rights of the citizens?
The state also serves administrative functions, but the existence of these administrative functions do not rely on the state any more than current supranational organs rely on a single world government handing down power: They can continue to exist by having their power delegated from below.
The difference, of course, being that when you are dependent on having your power delegated from "below", you need to thread much more carefully.