One of the most accepted definitions of State is "the entity that has the monopoly of power in a given region"

If a clan in Somalia, an indian chief, or a drug dealer in a ghetto has the actual power to punish, he's the State - not necessarily Government.

By that logic, as people organize themselves and get larger, there will always be someone with State prerogatives.

It isn't limited to right libertarians, really. Technically you can probably trace this to the general idea of Westphalian sovereignty: https://en.wikipedia.org/wiki/Westphalian_sovereignty In general, people today have a hard time conceiving of sovereign polities of any kind that are not also nation-states, or depending on your definition of nation, simply "states", as entities that have defined geographical boundaries within which they have a monopoly on violence and legitimacy, and outside of which they have no power of violence and no legitimacy. This is of course an approximation for all the reasons that half-a-dozen people are rushing for the reply link even now, but my point is not that this model is rigidly followed, but that it is simply the default mental model pretty much everybody approaches the world with.

It can help to see how rigidly we all tend to stick with this model to consider something radically different. Imagine a civilization consisting of 100 space stations, ranging in size from a little 20-person thing barely larger than the ISS to a massive million-person station, all in different orbits around different things. What is a "border"? What is "sovereignty" when you are not in an environment where you can (with enough effort) survive without other humans, or without very many other humans, and everyone is inextricably bound in life-or-death relationships, so there simply is no such thing as "self-sufficiency"? (Which I'd submit is a concept very important to sovereignty, even if it so basic to our Earth-thinking frame that we don't even consider it.)

I personally think almost everybody has a blind spot here, thinking a very particular part of the phase space of possible governance is the only one. Even the perennial debates on HN and such are basically between "modern capitalism" and "socialism", two systems that in the grand scheme of things are very similar to each other and only argue about how much sovereignty the state has vs. its citizens, where if you are against one then you must be in favor of the other, as if they are the only two possible methods of governance conceivable.

Even without going as crazy as hypothesizing a space-based civilization, history offers up quite a few alternatives to the modern conception. Some of them are hard to see, because we back-project our assumptions about nation-states on to history if we aren't very careful. But the early Roman empire had a much more complicated de facto structure, and Middle Ages Europe is quite difficult for a modern full of preconceived notions to properly understand, because we simply have no modern referent for the relationship that existed between the Church and the various other polities of the time.

As I understand it from van Notten, the power is institutional and fluid. There are accustomed, practiced, entrenched norms of behavior and custom, which provide general rules for what behavior is against the law -- although it becomes a matter of law only when it affects someone else to the degree they want to seek justice to redress a wrong. Power is embodied by clan leaders (elders who have the support of the majority of their community) and judges, etc, but is fluid in the sense that at any time, if they do something the community doesn't support, they will be replaced casually by their community.

Possibly worth noting - each of these is a coercive system which has some aspect of a "monopoly on violence," just at different levels of abstraction. So by that definition, a clan could be considered a degenerate form of state.