A good source to study penance (epitimia) in the medieval Eastern Orthodox Church is the Kanonarion of John the monk, which is apparently not available online.
There is a collection of articles on The History of Byzantine and Eastern Canon Law to 1500, editors Wilfried Hartmann and Kenneth Pennington, in which an article on Canon Law to 1100 by Spyros Troianos (pages 115-169) describes the approach and contents of the Kanonarion. This collection can be found in excerpts here. The summary on p.159f shows, which time periods of exclusion from service and the holy mysteries, with obligations to prayer and fasting, were considered appropriate: 7 years for prostitution, 30 years for incest with a spiritual child, or even until the end of one's life.
Note, that a person's exclusion from service and the holy mysteries is very visible to the community and causes continuous public humiliation, which that person has to bear as part of the penance. Later works on the subject, like the Kanonikon (see p.160 above), were less comprehensive and generally tended to shorten the periods of epitimia required.
Books like the Kanonarion in the Byzantine Empire existed in parallel to Byzantine criminal laws, so public humiliation might indeed be the least concern of a murderer, once his deeds become known - though his confessor is held to silence on the contents of a confession in the Eastern Orthodox Church as well.
Cheers