I think the Faint Sun Paradox on Mars has the same solution as on Earth.
1). CO2, H2O & Methane in abundance in primordial atmospheres, globally warmed both planets through greenhouse effects.
2). Massive impacts.
3). High levels of volcanism.
4) Large quantities of geothermal / arethermal heat (Earth / Mars).
Worth noting, Mars Pathfinder in July 1997, landed in the mouth of Ares Vallis, just prior to where it empties out into Chryse Planitia approx 800 KM S E of Viking 1.
Mars Pathfinder carried the Sojourner Rover. Mars Pathfinder although a technology demonstrator, was sent to the mouth of Ares Vallis (incidently the exact same spot as the first choice for Viking 1 lander in 1976, before the site was deemed too risky), to test the assumption that Ares Vallis was a huge flood valley.
The landing site was chosen for MPF, because here, the flood waters would be slowing down & fanning out, dropping the rocks washed down from up to 1,000 KM to the south.
MPF & Sojourner certainly proved this spectacularly. Boulders & rocks were seen to be stacked up & leaning all in one general direction & some rocks were pitted with corners knocked off, also indicative of being swept down in massive floods. There were also a few conglomerates, two or more rocks sort of 'cemented' together by dried sediments. Also Sojourner discovered many types of rocks, some volcanic, some sedimentary, all dumped in the same general location.
MPF data suggested catastrophic flooding, over short periods, perhaps as much as the Black Sea emptying out in less than a week. MER B Opportunity & Phoenix Mars Lander suggests that water may have persisted long term, perhaps both scenarios are correct depending on location.
A sample of MPF & Sojourner images below. It is quite apparent, what I mentioned above.
Andrew Brown.