Networking - "Skip" Ellis

Clarence "Skip" Ellis was born in 1943 in Chicago, was the first African-American to earn a Ph.D. in Computer Science (1969), and the first African-American to be elected a Fellow of the Association for Computing Machinery (1997). Ellis was a pioneer in Computer Supported Cooperative Work (CSCW) and Groupware. He and his team at Xerox PARC created OfficeTalk, one of the first groupware systems. Ellis also pioneered in Operational Transformation, a set of techniques that enables real-time collaborative editing of documents.

Making the Best of a Bad Hand

In 1958, at age 15, Ellis applied for a job as a graveyard shift computer operator to earn money to help his family. He was offered the job because he was the only applicant. Although his job title was computer operator, his main duties were to walk around all night and be visible to prevent break-ins, and to watch over, but not touch, the company's new computer. At the time, the firm’s computer was based on vacuum tube technology (2,400 vacuum tubes), used punch cards as input and output, and filled an extremely large room. In Ellis' free time on the job, he read and re-read the dozens of computer manuals that came with the machine. He taught himself as much as possible about the machine without touching it. Two months after he started the job, Ellis helped the company through an emergency. They had run out of unused punch cards, and needed to use the computer to process payroll by morning. During the emergency, Ellis was the only one who knew how to recycle the used punch cards. He lifted the hood of the computer and disabled the parity check (error code detector) circuitry. The used punch cards were recycled and the company was able to process the payroll. After this experience, the company began to seek him out whenever they had computer problems, and even asked him to operate and program the computer for them. Ellis states that this experience helped ignite his passion for computing.

In 1960, Ellis started Beloit College in rural Wisconsin. Upon arrival, he discovered that he was the only African-American attending the school.

 

In Ellis' junior year, Beloit Collegereceived an IBM 1620as a donation, and he and his chemistry professor were asked to set it up. This was the start of the Beloit College computer lab, of which Ellis was the director. 

IBM 1620

During this period of time, the civil rights movement was gathering momentum across the country. Skip was especially moved by the non-violent protests of Dr. Martin Luther King. On August 28, 1963 Skip was one of 250,000 people who went to Washington, D.C., to hear Dr. King give his "I Have a Dream" speech. From then on, Skip's twin passions were computer science and civil rights.

In 1964, Ellis received a B.S. degree from Beloit double majoring in math and physics. Ellis enrolled at MITfor graduate school, but only stayed a short time because of his civil rights activism. He eventually attended graduate school at the University of Illinois at Urbana-Champaign. In 1969, Clarence Ellis earned a Ph.D. in computer science, becoming the first African-American to do so.  

 

From 1976 to 1984, Ellis was part of the Xerox Palo Alto Research Center (PARC).

 

Xerox PARC

Xerox PARC (renamed PARC (Palo Alto Research Center Incorporated), formerly, is a research and development company in Palo Alto, California, with a distinguished reputation for its contributions to information technology and hardware systems.

Founded in 1970 as a division of Xerox Corporation, PARC has been in large part responsible for such developments as laser printing, Ethernet, the modern personal computer, graphical user interface (GUI) and desktop paradigm, object-oriented programming, ubiquitous computing, amorphous silicon (a-Si) applications, and advancing very-large-scale integration (VLSI) for semiconductors.

Located in Palo Alto, California, it had a 3,000 mile buffer between it and Xerox headquarters in Rochester, New York afforded scientists at the new lab great freedom to undertake their work, the distance also served as an impediment in persuading management of the promise of some of their greatest achievements.

Xerox PARC has been the inventor and incubator of many elements of modern computing in the contemporary office work place:

  • Laser printers

  • Computer-generated bitmap graphics

  • The graphical user interface, featuring windows and icons, operated with a mouse

  • The WYSIWYG text editor

  • Interpress, a resolution-independent graphical page-description language and the precursor to PostScript

  • Ethernet as a local-area computer network

  • Fully formed object-oriented programming in the Smalltalk programming language and integrated development environment.

  • Model–view–controller software architecture

 

These developments along with the now familiar Stanford Research Institute (SRI) developed mouse were unified into a single model that became the now-standard personal computer. The integration of Ethernet prompted the development of the PARC Universal Packet architecture, much like today's Internet.

Xerox has been heavily criticized (particularly by business historians) for failing to properly commercialize and profitably exploit PARC's innovations. While there is some truth that Xerox management failed to see the potential of many of PARC's inventions, this was mostly a problem with its computing research (a number of GUI engineers left to join Apple Computer), a relatively small part of PARC's operations.     

 

Technologies pioneered by its materials scientists such as liquid-crystal display (LCD), optical disc innovations, and laser printing were actively and successfully introduced by Xerox to the business and consumer markets.

At PARC, Ellis headed a group that invented and developed Officetalk, the first office system to use icons and Ethernet to allow people to collaborate from a distance. OfficeTalk supported standard office automation tasks and tracked "jobs" as they went from person to person in an organization. The focus of office automation research was to reduce the complexity of the user’s interface to the office information system, control the flow of information, and enhance the overall efficiency of the office.”

 

Ellis left Xerox PARC in the mid-1980s to lead the Groupware Research Group at the Microelectronics and Computer Technology Corporation (MCC). While at MCC, he led efforts in Real-time Collaborative Editing, and Operational Transformation.

Collaborative software or groupware is application software designed to help people involved in a common task to achieve their goals. It is designed to address the issues raised by collaborative efforts that are otherwise compartmentalized by time, space or both.

Groupware aimed to place the computer squarely in the middle of communications among managers, technicians, and anyone else who interacts in groups, revolutionizing the way they work.

"If GROUPWARE really makes a difference in productivity long term, the very definition of an office may change. You will be able to work efficiently as a member of a group wherever you have your computer. As computers become smaller and more powerful, that will mean anywhere."                    - David Kirkpatrick, CNN-Money (1993)

Groupware designers did not only have to address technical issues (as in traditional software development) but also consider the organizational aspects and the social group processes that should be supported by the groupware application. Those issues included:

  • Concurrency - How to most efficiently handle independently generated multiple input and output streams.

  • Persistence - Chat and voice communications are routinely non-persistent and evaporate at the end of the session. Virtual room and online file cabinets can persist for years. The designer of the collaborative space needs to consider the information duration needs and implement accordingly.

  • Motivation - Generating full multi-party involvement in the absence of a pre-defined group process was in place.

 

To address these issues, in 1989 Ellis in conjunction with Simon Gibbs pioneered the development of the GROVE (GRoup Outline Viewing Edit) an Operational Transformation (OT) system.

The basic idea of OT can be illustrated by its initial purpose, text editing:

 

A text document with a string "abc" is at two collaborating sites and Concurrently two separate operations are undertaken (the initial position in the character string is identified as:

1. Site 1 = Insert character "x" at position "0"

2. Site 2 = Delete the character "c" at position "2"

Suppose the two operations are independently executed in the order of Site 1 and then at Site 2.

After executing the Site 1 command, the document becomes "xabc".

To execute the Site 2 command properly after the Site command, Site 2 must be transformed to reflect the command made at Site 1 to become Site 2'

When this transformation is made, the Delete "c" command whose positional parameter has increased by one due to the insertion of the "x" by Site 1.

Executing Site 2' on "xabc" deletes the correct character "c" and the document becomes "xab".

If Site 2 command was executed without transformation, it would delete the character at the initial position (2) "b" rather than "c". The basic idea of OT is to transform (or adjust) the parameters of an editing operation according to the effects of previously executed concurrent operations so that the transformed operation can achieve the correct effect and maintain document consistency.

Ellis & Gibbs stated that there two consistency properties are required for collaborative editing systems:

• Causality preservation: ensures the execution order of causally dependent operations is the same as their natural cause-effect order during the process of collaboration. When two operations are not causally dependent, they are concurrent. Two concurrent operations can be executed in different order on two different document copies.

• Convergence: ensures the replicated copies of the shared document be identical at all sites at quiescence (i.e., all generated operations have been executed at all sites).

Since concurrent operations may be executed in different orders and editing operations are not commutative in general, copies of the document at different sites may diverge. In order to combat this problem, in the initial OT algorithm proposed by Ellis & Gibbs each edit is linked to the previous edits that it is dependent upon but not to those edits which it is not to preserve the precedence property.

In order to achieve convergence in a group text editor; collaboration systems utilizing OT typically use replicated document storage, where each client has their own copy of the document; clients operate on their local copies and the changes are then propagated to the rest of the clients; this ensures the client high responsiveness in an otherwise high-latency (latency = the length of time between actions) environment such as the Internet. When a client receives the changes propagated from another client, it typically transforms the changes before executing them; the transformation ensures that application-dependent consistency criteria are maintained by all sites.

Operational Transformation as originally invented for consistency maintenance and concurrency control in collaborative editing of plain text documents. Two decades of research have extended its capabilities and applications. In 2009 OT was adopted as a core technique behind the collaboration features in Google Docs.

 

In his career as an academic, most frequently at the University of Colorado, Ellis preferred to teach undergraduates with little experience in computer science as a way of introducing them to the field. He wanted to encourage students of all backgrounds to stretch their academic abilities and to consider a career in computer science.

Ellis sought to provide opportunities in computer science to underrepresented groups, such as African-American undergraduates at historically black colleges and universities. He helped launch a summer program at CU [University of Colorado] to bring those undergraduate students to Boulder for research. "The purpose of that was to try to get the pipeline to grad school filled with folks who might not otherwise do it if they don't have a mentor," said James Martin, [CU] computer science chairman.

 

In a February 2002 issue of Black Issues in Higher Education, Ellis said he wanted to counter the approach some teachers early in his academic career took when they advised him to not take courses beyond the basic math level. “People put together an image of what I was supposed to be,” he recalled. “So I always tell my students to push.”

In 2014, Clarence “Skip” Ellis died at the age of 71.

For any questions, please contact David Trotman :

415-298-8979

1519 O'farrell St. San Francisco, CA 94115