Word of William's defeat at Gerberoi stirred up difficulties in northern England. In August and September 1079 King Malcolm of Scots raided south of the River Tweed, devastating the land between the River Tees and the Tweed in a raid that lasted almost a month. The lack of Norman response appears to have caused the Northumbrians to grow restive, and in the spring of 1080 they rebelled against the rule of William Walcher, the Bishop of Durham and Earl of Northumbria. Walcher was killed on 14 May 1080, and the king dispatched his half-brother Odo to deal with the rebellion. William departed Normandy in July 1080, and in the autumn his son Robert was sent on a campaign against the Scots. Robert raided into Lothian and forced Malcolm to agree to terms, building a fortification at Newcastle-on-Tyne while returning to England. The king was at Gloucester for Christmas 1080 and at Winchester for Whitsun in 1081, ceremonially wearing his crown on both occasions. A papal embassy arrived in England during this period, asking that William do fealty for England to the papacy, a request that he rejected. William also visited Wales during 1081, although the English and the Welsh sources differ on the exact purpose of the visit. The "Anglo-Saxon Chronicle" states that it was a military campaign, but Welsh sources record it as a pilgrimage to St Davids in honour of Saint David. William's biographer David Bates argues that the former explanation is more likely, explaining that the balance of power had recently shifted in Wales and that William would have wished to take advantage of the changed circumstances to extend Norman power. By the end of 1081, William was back on the continent, dealing with disturbances in Maine. Although he led an expedition into Maine, the result was instead a negotiated settlement arranged by a papal legate.