The Haudenosaunee (Iroquois Confederacy) was a constitutional, representative democracy with pre-Columbian roots. In basic operation, it functioned like this:

The root of Haudenosaunee politics are the oia:ner (to use the Mohawk term), the Clan Mothers. The oai:ner are chosen by the residence of each longhouse (all members of the same clan, or men who had married into the clan). The longhouse oai:ner then filter up through the political ranks, from town to nation to confederacy, with the most prestigious oia:ner from all over the confederacy convening in the Clan Mother / Women's Council at Gaustauyea in western New York. Certain prominent oia:ner had the authority to appoint roia:ner, their male equivalents on the Grand / Men's Council, which met at Onondaga. The Grand Council was initially composed of 50 roia:ner, but after Hiawatha died, his seat was never filled so in practice there were only 49 roia:ner. These 49 seats were divided unevenly among the five nations (Seneca, Cayuga, Onondaga, Oneida, and Mohawk) that composed the confederacy. However, each nation only got one collective vote so the number of representatives didn't matter much. Additionally there was a separate class of representatives on the Grand Council appointed based on a meritocratic system. The elected council at Gaustauyea and the appointed council at Onondaga worked in tandem, with the women setting the confederacy's agenda, which the men then debated and negotiated, and the women could then veto if they chose. Both sides had the power to remove members from the other if their were found to be abusing their power.

Unfortunately, we know a lot more about how the Grand Council functioned than how the Clan Mother Council functioned. The Gayanashagowa, the oral (now written obviously) constitution of the confederacy, is almost exclusively concerned with the operation of the Grand Council and only briefly touches on what the oia:ner were up to (it mentions their power to appoint and remove representatives, and the Grand Council's ability to remove them if they fail to uphold their responsibilities, along with a few other things). In general, the responsibilities of the oia:ner are clan-oriented and internal while the responsibilities of the roia:ner are nation-oriented and external.

In 899, the Qarmatians, a revolutionary Ismaili Shia movement, broke away from the Abbasid Caliphate. Within just a few years, under the leadership of Abu Said al-Jannabi, they conquered east Arabia and establish themselves in an oasis capital, Al-Hasa, in the modern eastern province of Saudi Arabia, near the Persian Gulf coast. The Qarmatians are best known for raiding Mecca during the Hajj and stealing the rock from the Ka'ba in 930 AD which they held for ransom for twenty years.

The Qarmatians formed a republic which lasted over 150 years. The leadership was hereditary and held by the descendants of Abu Said al-Jannabi. The Jannabi leader had authority of the military, but was otherwise appears to have been a first among equals among others in a consultative council, which made decisions by consensus.

Obviously, this doesn't square with our modern concepts of a republic - no one was elected. But it differed vastly from the forms of monarchy seen in Baghdad, Cairo and Cordoba in that time.

What also separated the Qarmatians was their radical state structure: it's a state which has been variously described as utopian and proto-communistic. The state owned plantations and grain mills, providing cheap produce to the citizen population. Those who were poor and in debt were provided interest-free loans to get them back on their feet. Land taxes were abolished and new taxes introduced on pilgrims to Mecca, on the lucrative pearl trade, and on ships passing through their controlled ports. Coinage was replaced with lead tokens, though foreign coins have also been discovered from this period, suggesting trade, particularly with the co-religionist Fatimid state, continued.

Of course one has to be very careful calling them even 'proto-communist', as such a political theory would not be expounded for another thousand years, but the Qarmatians did have a type of communal political and social structure which resembles modern communist ideals. Then again, they were still a slave owning society, and the above-mentioned state-run plantations were largely run on slave labour.

The Qarmatians believed that they were entering the end times and were expecting the coming of "The Mahdi", and the heralding of the Day of Judgement. This may explain their government form and society, which differ radically both with their contemporaries and with the states that succeeded them. Unsympathetic writers at the time relay communal sexual practices, though this is most likely the kind of sexual slander that can be found made against rivals people and groups throughout many cultures and periods. Some writers also noted that the Qarmatians ate any kind of meat, including that of carnivores (cats, dogs), regardless of whether the food was halal, and archaeological evidence suggests this may be true - digs in Bahrain's medieval capital have found bones of cats butchered for meat, but that may equally be a sign of famine and desperate times.

The Qarmatian republic slowly weakened over the 10th century, possibly due to the failure of the promised Mahdi and the end of times to appear, undermining the religious movement. Over time, the Qarmatians lost territory and tributaries, shrinking around the capital. In the 1050s, a local revolt backed up by a Seljuk Turk army finally broke the last vestiges of Qarmatian rule, and in 1067 sieged their finally holding successfully. The revolt's leader, Abdulla al-Uyuni, established a new local dynasty which ruled as a hereditary emirate, and the religious fanaticism gave way to a quietest Shia theology.

Of course this is not a republic in the traditional form and does not follow the western historical and modern concepts of republics. But neither did this state follow the normal form of governance observed among all its neighbouring states.

Well, after the fall of the Umayyads and its subsequent sacking, Cordoba was a republic of sorts from 1031 CE to 1091 CE. The leading citizens entrusted matters to an Ibn Jawhar, one of their own. Ibn Jawhar devised a political order quite unlike anything seen before in the Islamic World. This 'democratic' system put constraints on the 'Custodian of the Community', the title that Ibn Jawhar used, by having all decisions require approval from a 'senate', or 'a council of ministers and judicious men'.

Sources: The Legacy of Muslim Spain, by Salma Jayyusi and Manuela Marín; published by BRILL in 1994. Link to specific page: https://books.google.ca/books?id=cbfORLWv1HkC&lpg=PP1&pg=PA52#v=onepage&q&f=false

The Formation of Al-Andalus: History and society, part 1, page 52, Manuela Marín, Julio Samsó, Ma. Isabel Fierro Link to specific reference: https://books.google.ca/books?id=3k9pAAAAMAAJ&q=%22cordoban+republic%22&dq=%22cordoban+republic%22&ei=uwbYSe-zD4eyNJjLid8C&pgis=1