In order to conceptualize multi-cellularity in the context of an artificial medium, we must have a very fundamental definition which is independent of the context of the medium. We generally think of the defining property of multi-cellularity as being that the cells stick together, forming a physically coherent unit. However, this is a spatial concept based on Euclidean geometry, and therefore is not relevant to non-Euclidean cyberspace.
While physical coherence might be an adequate criteria for recognizing multi-cellularity in organic organisms, it is not the property that allows multi-cellular organisms to become large and complex. There are algae that consist of strands of cells that are stuck together, with each cell being identical to the next. This is a relatively limiting form of multi-cellularity because there is no differentiation of cell types. It is the specialization of functions resulting from cell differentiation that has allowed multi-cellular organisms to attain large sizes and great complexity. It is differentiation that has generated the MIMD style of parallelism in organic software.
From an evolutionary perspective, an important characteristic of multi-cellular organisms is their genetic unity. All the cells of the individual contain the same genetic material as a result of having a common origin from a single egg cell (some small genetic differences may arise due to somatic mutations; in some species new individuals arise from a bud of tissue rather than a single cell). Genetic unity through common origin, and differentiation are critical qualities of multi-cellularity that may be transferable to media other than organic chemistry.
Buss [9] provides a provocative discussion of the evolution of multi-cellularity, and explores the conflicts between selection at the levels of cell lines and of individuals. From his discussion the following idea emerges (although he does not explicitly state this idea, in fact he proposes a sort of inverse of this idea, p. 65): the transition from single to multi-celled existence involves the extension of the control of gene regulation by the mother cell to successively more generations of daughter cells.
In organic cells, genes are regulated by proteins contained in the cytoplasm. During early embryonic development in animals, an initially very large fertilized egg cell undergoes cell division with no increase in the overall size of the embryo. The large cell is simply partitioned into many smaller cells, and all components of the cytoplasm are of maternal origin. By preventing several generations of daughter cells from producing any cytoplasmic regulatory components, the mother gains control of the course of differentiation, and thereby creates the developmental process. In single celled organisms by contrast, after each cell division, the daughter cell produces its own cytoplasmic regulatory products, and determines its own destiny independent of the mother cell.
Complex digital organisms will be self replicating algorithms, consisting of many distinct processes dedicated to specific tasks (e.g., locating free memory, mates or other resources; defense; replicating the code). These processes must be coordinated and regulated, and may be divided among several cells specialized for specific functions. If the mother cell can influence the regulation of the processes of the daughter, so as to force the daughter cell to specialize in function and express only a portion of its full genetic potentiality, then the essence of multi-cellularity will be achieved.