Ever since Indonesia achieved independence in 1949, the Jakarta government has faced a constant battle to keep the nation's 13,000 islands together.
Click on the map below for some of the main areas of conflict.
Acehnese rebels and the Indonesian government signed a peace agreement in August 2005 aimed at ending nearly 26 years of a bitter separatist campaign, which has left nearly 15,000 people, mainly civilians, dead.
The deal was the result of six months of negotiations, after the two sides vowed to resolve the crisis in the wake of the December 2004 tsunami which killed more than 120,000 Acehnese.
Gam rebels have been fighting for Acehnese independence
Many people in Aceh trace their problems back to 1949, when the Dutch recognised Indonesian independence after four years of guerrilla warfare.
Aceh became part of the Republic of Indonesia, despite not having been formally incorporated into the Dutch colonies.
The Indonesian Government used armed troops to annex the region, and the military's heavy-handed tactics fuelled resentment among the local population.
In 1959, in an effort to appease the Acehnese, Jakarta gave the province a special status which conferred a certain amount of autonomy, especially over religious and educational matters.
Aceh has a higher proportion of Muslims than other areas of Indonesia, and was allowed to introduce Sharia law in 2001.
ACEH: KEY FACTS
Province on the north-western tip of Sumatra
Higher percentage of Muslims than other parts of Indonesia
Gam rebels have fought decades-long separatist campaign
Year-long military crackdown beginning in May 2003 weakened Gam, but failed to capture senior members
December 2004 Indian Ocean tsunami devastates region
August 2005 peace agreement aimed at ending conflict
But despite concessions such as this, many Acehnese continued to resent Jakarta's rule. A major point of contention was the revenue from the province's rich oil and gas resources, most of which went straight to the central purse.
Another government move which angered Aceh was President Suharto's policy of transmigration, in which many Indonesians from overcrowded Java were settled in the province, increasing competition for jobs.
After the fall of Suharto in May 1998, General Wiranto - then the head of the armed forces - ended the military's control over Aceh and publicly apologised for human rights abuses in the province.
But the low-level conflict with Gam continued, as the rebels refused to back down from their demands for a separate state.
Hopes for peace in Aceh were raised when the two sides signed an agreement in December 2002, which offered partial autonomy and free elections in exchange for rebel disarmament.
The deal collapsed in May 2003, when both sides failed to fulfil their side of the bargain. The rebels refused to give up their weapons, and the Indonesian military did not withdraw to agreed defensive positions.
On 19 May, Indonesia declared martial law in the province, and launched an all-out military offensive against Gam rebels.
A year after it was first imposed, the martial law was downgraded to a state of emergency.
In December 2004, Aceh was devastated by the Indian Ocean earthquake and tsunami.
Prompted by the urgency of Aceh's reconstruction needs, both sides resumed talks in January 2005.
After four rounds of discussions, they came to an agreement, with both sides making key concessions.
Under the deal, the rebels put to one side their demand for full independence, accepting instead a form of local self-government and the right eventually to establish a political party.
In turn, the Indonesian government agreed to release political prisoners and offer farmland to former combatants.
Non-local Indonesian troops and police are leaving Aceh, and Gam rebels have disarmed, in a process overseen by a joint European Union and Asean monitoring team.
But all sides say there is still much work to be done, and analysts warn that there is still deep mistrust between Gam and the government.