STORY HIGHLIGHTS

The fighting was brought to an end with the signing of the Algiers Peace Agreement and establishment of the Ethiopia-Eritrea Border Commission (EEBC) in 2000. However, Ethiopia's refusal to implement the rulings of the EEBC prior to negotiations and Eritrea's insistence on an unconditional and immediate demarcation of the border have locked the two governments in an intractable stalemate.
Despite the official cessation of hostilities, Ethiopia and Eritrea continued their war through proxies by supporting various rebel-movements throughout the Horn of Africa. In this way, they have been fuelling conflict and instability in each other's countries as well as the wider region.
13 years after the Algiers Peace Agreement, domestic conditions in both states and the regional geopolitical equation have undergone substantial changes.
Ethiopia lost its long-time strongman,
The relationship between Eritrea and Ethiopia is arguably the most important and volatile in East Africa. The fall-out between the former brothers-in-arms initiated a two-year-long border war in 1998, which claimed around 100,000 causalities, cost billions of dollars, and continues to serve as the main source of regional instability in the Horn of Africa.
The fighting was brought to an end with the signing of the Algiers Peace Agreement and establishment of the Ethiopia-Eritrea Border Commission (EEBC) in 2000. However, Ethiopia's refusal to implement the rulings of the EEBC prior to negotiations and Eritrea's insistence on an unconditional and immediate demarcation of the border, have locked the two governments in an intractable stalemate.
Despite the official cessation of hostilities in 2000, Ethiopia and Eritreacontinued their war through proxies by supporting various rebel movements throughout the Horn of Africa. In this way, they have been fuelling conflict and instability in each other's countries as well as the wider region.
Thirteen years after the Algiers Peace Agreement, domestic conditions in both states and the regional geopolitical equation have undergone substantial changes.
Ethiopia lost its long-time strongman, Meles Zenawi, in 2012. There are strong indications that Eritrea is also very likely to see the departure of its own leader, President Isaias Afwerki, in the near future. Moreover, Ethiopia has been experiencing robust economic growth and political stability over the last decade, a development that has also coincided with a significant weakening of its regional adversaries. 
The political standoff between Ethiopia and Eritrea has very much been tied to the role, interests and historical experiences of particular individuals and circles that hail from one generation - the Marxist-Leninist student movements turned guerrilla fighters in the 1960s and 1970s. With the political and generational changes that are taking place in both countries, a normalisation of relations between these two states might take place in the not so distant future. 
A new chapter
In Addis Ababa, the discourse on Eritrea has evolved from initially being considered a significant military threat next door to that of concerns over state collapse, civil war and its security implications.
Ethiopia's ruling EPRDF (Ethiopian People's Revolutionary Democratic Front) government faced, as recently as 2007, the tactical alliance of Eritrea, Ethiopian armed rebels and factions in Somalia (such as the Islamic Courts Union - ICU).  To many observers the security equation seemed at that time to be in favour of this alliance.
In a significant turn of developments, Eritrea underwent a process of rapid economic, political and humanitarian decline - a clear indicator of which, is its emergence as one of the top refugee producing countries in the world. In Somalia, the ICU has been eliminated, and its successor al-Shabab has also been dealt a blow that it is unlikely to recover from.
Ethiopian authorities are adamant about the normalisation of relations and economic integration of the two nations.
Armed Ethiopian insurgent groups, such as the Oromo Liberation Front and Ogaden National Liberation Front, have largely declined, due to, among other things, their inability to remain cohesive. In addition to this, the Ethiopian economy - and consequently its military power - has undergone sustained growth over the last decade.
Asmara's support for Somali-based rebel groups made it an international pariah and target of a regime under UN sanctions. Although Eritrea is not the only actor to engage in such actions (Ethiopia harbours a dozen Eritrean rebel groups), the consequences have been particularly severe for Eritrea. This is mainly due to its choice of allies in Somalia, which happened to be at loggerheads with much of the regional and international community. President Isaias Afwerki's inability to play the diplomatic game and persuade the international community to support, or at least understand his viewpoint, created conducive conditions for the late PM Zenawi - who succeeded where Afwerki failed.   
The main concern for policy-makers in Addis Ababa is no longer Asmara's military capacity, but rather the possibility of Eritrea plunging into chaos. This fear is apparently so daunting to Ethiopia that it may prefer a reformed Eritrean government led by People's Front for Democracy and Justice (PFDJ), rather than the insecurities of a violent power transition next door.
On two occasions this year, Ethiopian Prime Minister Hailemariam Desalegn has signalled his government's interest in dialogue and his willingness to go to Asmara for peace talks, at anytime and without any pre-conditions.
Delicate issue of Bademe
At the heart of the stalemate are symbolic politics and domestic constraints on both sides - of which the contested border town of Bademe is an embodiment. 
It is very possible that the EPRDF will hand over the symbolic town of Bademe to Eritrea - which was awarded to the latter by the EEBC - but it can only get away with such a move domestically by selling it as a necessary sacrifice for a comprehensive and durable peace. The fact that the individuals leading the current Ethiopian government did not take part in the decision-making processes of the border war and subsequent peace agreement, means that they are less constrained by the commitments of their predecessors.    
For President Afwerki, on the other hand, the stakes are much higher. In fact, resolving the stalemate is likely to create more challenges than benefits to his personal power base. The suspension of the parliament and the constitution, the universal and indefinite military conscription policy, and in general, the system of one-man rule have all been justified by the need to counter the "Ethiopian threat". A settlement of the border issue would eliminate the rationale for maintaining this system and would undoubtedly lead to new domestic demands for addressing the nation's many political and humanitarian problems.  
'Brothers at war'
Sentimental notions of brotherhood, betrayal, and ethnic-stereotypes have shaped the manner in which Ethiopia's EPRDF and Eritrea's PFDJ ruling parties have been relating to each other since the days of the guerrilla struggle. 
It is now time to think about what the relationship between these two states will look like without the two omnipresent strongmen that have heavily shaped their histories.
The cultural and political intimacy and sense of fraternity that developed during their time as rebel movements led both parties to delay institutionalising the relationship between their newly established regimes in 1993 - and thus made possible the border war. These sentimental aspects also played an important role in making the conflict prolonged and eventually intractable.
This sense of "intimacy" has also had some positive implications. One such effect is the preferential treatment given to Eritrean refugees in Ethiopia - who now number around 100,000 people. Eritrean refugees - provided that they satisfy certain criteria - are given residency and work permits and the opportunity to study in Ethiopian universities (as opposed to refugees from other neighbouring countries). Around 1,200university scholarships have so far been offered to Eritrean refugees.
However, the passing of time has brought with it substantial changes, and the more than a decade-long political and physical barriers  led to an increasing cultural disconnectedness even among the people that live along the border. In Addis Ababa and other urban centres, it is even more challenging to arouse interest for Eritrean affairs among the average Ethiopian.
Post-Zenawi and post-Afwerki
A refugee crisis, high-level defections, and a recent mutiny in the army, are some of many indications that Afwerki's regime is facing an existential threat that may lead to its demise in the near future.
Afwerki is now on "survival mode" and may engage in new and desperate gestures to prolong his time in power, such as opening up to the international community for dialogue and humanitarian aid. However, if his past behaviour is anything to go by, such moves are only likely to be tactical survival manoeuvres that will not reverse the current political trajectory.
It is now time to think about what the relationship between these two states will look like without the two omnipresent strongmen that have heavily shaped their histories.
In Ethiopia, this process of change has already begun, and the time when both countries will be led by a generation without the historical and political baggage inherited from the liberation war, the border war and subsequent peace settlement might not be far ahead in time. Free from these constraints, the post-Afwerki and post-Zenawi Eritrea-Ethiopia relations will most likely not only be normalised, but also much more institutionalised.
Kjetil Tronvoll is a professor of peace and conflict studies at Bjorknes College, and Senior Partner at the International Law and Policy Institute. He has written Brothers at War: Making Sense of the Ethiopian-Eritrean War and The Lasting Struggle for Freedom in Eritrea: Human Rights and Political Development, 1991-2009.  
Goitom Gebreluel is an advisor at the International Law and Policy Institute. He has previously worked for the Norwegian government (Norad) and taught foreign policy studies at Mekelle University, Ethiopia.