The entire premise that "Examples of decentralized society [...] are hidden because those in decentralized societies never bothered to keep records" is bizarre, especially when applied to the Middle Ages.

As soon as the barbarian kindgom stabilised after the immediate aftermath of 476 AD, they started bookkeeping again. The truly "dark" ages in terms of scarce surviving records lasted maybe 250 years, but already by the 7th century you have surviving law codes that tell quite a bit about the societial structure of the time.

And specifically, decentralized power-sharing in the Middle Ages is so not-hidden there is even a videogame about it, called Crusader Kings II.