Compaore, the current chairman of the Organisation of African Unity (OAU), will try to broker an agreement between the two countries on how to implement an OAU peace plan which both sides have nominally signed up to but interpret differently.

``The priority for the OAU at this juncture is an immediate halt to the border conflict between Ethiopia and Eritrea,'' OAU spokesman Ibrahim Dagash told reporters in Addis Ababa.

Compaore will be the latest in a stream of mediators who have tried to negotiate an end to the war, in which tens of thousands of soldiers have died in a battle over a remote and scrubby patch of land along the frontier.

On his return late Sunday from Dohar, Qatar, where he signed a pact with Afeworki to end a four-year break in relations, Beshir said the two sides took "an advanced step (...) to the interests of both our two countries and our peoples".

"We are now awaiting the formation of a joint commission to meet in Doha for laying down programmes for normlisation of our bilateral relations," he added, commending mediation efforts by the emir of Qatar and Libyan leader Moamer Kadhafi.

Qatar's official news agency QNA reported Sunday that both sides would work "to clear the atmosphere and settle the conflict between the Republic of Sudan and Eritrea, as part of the mediation undertaken by Qatar."

They agreed to restore diplomatic ties broken off in December 1994, halt military operations and media campaigns against each other and settle their disputes through negotiation.

Qatar's emir, Sheikh Hamad ibn Khalifa al-Thani, attended the signing of the accord, QNA said without publishing its text.

The Moslem fundamentalist-backed regime of General Beshir, brought to power in a June 1989 coup, has accused Eritrea of support for rebels of the Sudan People's Liberation Army (SPLA), up in arms since 1983 to end Islamic domination of the black, mainly Christian and animist south.

Eritrea's capital Asmara has become a base for exiled northern Sudanese political foes of the Khartoum regime, who have joined in a National Democratic Alliance Coalition (NDA) with the mainstream SPLA.

However, Eritrea is fighting a border war, which has cost many thousands of lives since it began a year ago, with Ethiopia, which has frontiers with both its Horn of Africa of neighbours, while Sudan's conflict has claimed an estimated 1.5 million lives over the years, been a massive strain on the economy, displaced hundreds of thosands of people and worsened famines.

Asked about any role Sudan could play in helping end the territorial conflict between neighbouring Eritrea and Ethiopia, Beshir pledged that as soon as relations between Khartoum and Asmara were restored, "we will embark on efforts for mediation between Eritrea and Ethiopia."

On Saturday, Issaias said his country was "completely convinced of the need to go beyond the mistakes made in the past, and circumstances now favour a normalisation."

Qatar has been mediating for several months between Eritrea and Sudan, which severed relations in December 1994.

Issaias at the weekend said Doha's ideas were based on "creating a climate of stability and security throughout the Horn of Africa in order to enable the countries of the region to exploit their resources."

He said the two sides had agreed to set up a joint commission to "oversee the implementation of the clauses of the agreement, including the exchange of ambassadors and the question of the opposition present in each country."